code_rs/coding/
bch.rs

1//! Encoding and decoding of the (63, 16, 23) BCH code described by P25.
2//!
3//! These algorithms are derived from *Coding Theory and Cryptography: The Essentials*,
4//! Hankerson, Hoffman, et al, 2000.
5
6use std;
7
8use binfield_matrix::matrix_mul_systematic;
9
10use crate::coding::bmcf;
11use crate::coding::galois::{GaloisField, P25Codeword, P25Field, Polynomial, PolynomialCoefs};
12
13/// Encode the given 16 data bits into a 64-bit codeword.
14pub fn encode(word: u16) -> u64 {
15    matrix_mul_systematic(word, GEN)
16}
17
18/// Try to decode the given 64-bit word to the nearest codeword, correcting up to 11
19/// bit errors.
20///
21/// If decoding was successful, return `Some((data, err))`, where `data` is the 16 data
22/// bits and `err` is the number of bits corrected. Otherwise, return `None` to indicate
23/// an unrecoverable error.
24pub fn decode(bits: u64) -> Option<(u16, usize)> {
25    // The BCH code is only over the first 63 bits, so strip off the P25 parity bit.
26    let word = bits >> 1;
27
28    bmcf::Errors::new(syndromes(word)).map(|(nerr, errs)| {
29        // Flip all error bits.
30        let fixed = errs.fold(word, |w, (loc, pat)| {
31            assert!(pat.power().unwrap() == 0);
32            w ^ 1 << loc
33        });
34
35        // Strip off the parity bits.
36        ((fixed >> 47) as u16, nerr)
37    })
38}
39
40/// Generator matrix from P25, transformed for more efficient codeword generation.
41const GEN: &[u16] = &[
42    0b1110110001000111,
43    0b1001101001100100,
44    0b0100110100110010,
45    0b0010011010011001,
46    0b1111111100001011,
47    0b1001001111000010,
48    0b0100100111100001,
49    0b1100100010110111,
50    0b1000100000011100,
51    0b0100010000001110,
52    0b0010001000000111,
53    0b1111110101000100,
54    0b0111111010100010,
55    0b0011111101010001,
56    0b1111001111101111,
57    0b1001010110110000,
58    0b0100101011011000,
59    0b0010010101101100,
60    0b0001001010110110,
61    0b0000100101011011,
62    0b1110100011101010,
63    0b0111010001110101,
64    0b1101011001111101,
65    0b1000011101111001,
66    0b1010111111111011,
67    0b1011101110111010,
68    0b0101110111011101,
69    0b1100001010101001,
70    0b1000110100010011,
71    0b1010101011001110,
72    0b0101010101100111,
73    0b1100011011110100,
74    0b0110001101111010,
75    0b0011000110111101,
76    0b1111010010011001,
77    0b1001011000001011,
78    0b1010011101000010,
79    0b0101001110100001,
80    0b1100010110010111,
81    0b1000111010001100,
82    0b0100011101000110,
83    0b0010001110100011,
84    0b1111110110010110,
85    0b0111111011001011,
86    0b1101001100100010,
87    0b0110100110010001,
88    0b1101100010001111,
89    0b0000000000000011,
90];
91
92impl_polynomial_coefs!(BchCoefs, 23);
93
94/// Polynomial with BCH coefficients.
95type BchPolynomial = Polynomial<BchCoefs>;
96
97/// Generate the syndrome polynomial s(x) from the given received word r(x).
98///
99/// The resulting polynomial has the form s(x) = s<sub>1</sub> + s<sub>2</sub>x + ··· +
100/// s<sub>2t</sub>x<sup>2t</sup>, where s<sub>i</sub> = r(α<sup>i</sup>).
101fn syndromes(word: u64) -> BchPolynomial {
102    BchPolynomial::new((1..=BchCoefs::syndromes()).map(|p| {
103        // Compute r(α^p) with the polynomial representation of the bitmap. The LSB of
104        // `word` maps to the coefficient of the degree-0 term.
105        (0..P25Field::size()).fold(P25Codeword::default(), |s, b| {
106            if word >> b & 1 == 0 {
107                s
108            } else {
109                s + P25Codeword::for_power(b * p)
110            }
111        })
112    }))
113}
114
115#[cfg(test)]
116mod test {
117    use super::*;
118    use super::{syndromes, BchCoefs};
119    use crate::coding::galois::{P25Codeword, Polynomial, PolynomialCoefs};
120    use std;
121
122    impl_polynomial_coefs!(TestCoefs, 23, 50);
123
124    #[test]
125    fn validate_coefs() {
126        BchCoefs::default().validate();
127    }
128
129    #[test]
130    fn verify_gen() {
131        // Verify construction of BCH generator polynomial g(x).
132
133        let p = Polynomial::<TestCoefs>::new(
134            [
135                P25Codeword::for_power(0),
136                P25Codeword::for_power(0),
137                P25Codeword::for_power(0),
138            ]
139            .iter()
140            .cloned(),
141        ) * Polynomial::new(
142            [
143                P25Codeword::for_power(0),
144                P25Codeword::default(),
145                P25Codeword::for_power(0),
146                P25Codeword::default(),
147                P25Codeword::for_power(0),
148                P25Codeword::for_power(0),
149                P25Codeword::for_power(0),
150            ]
151            .iter()
152            .cloned(),
153        ) * Polynomial::new(
154            [
155                P25Codeword::for_power(0),
156                P25Codeword::for_power(0),
157                P25Codeword::default(),
158                P25Codeword::for_power(0),
159                P25Codeword::for_power(0),
160                P25Codeword::default(),
161                P25Codeword::for_power(0),
162            ]
163            .iter()
164            .cloned(),
165        ) * Polynomial::new(
166            [
167                P25Codeword::for_power(0),
168                P25Codeword::default(),
169                P25Codeword::for_power(0),
170                P25Codeword::for_power(0),
171                P25Codeword::default(),
172                P25Codeword::for_power(0),
173                P25Codeword::for_power(0),
174            ]
175            .iter()
176            .cloned(),
177        ) * Polynomial::new(
178            [
179                P25Codeword::for_power(0),
180                P25Codeword::default(),
181                P25Codeword::for_power(0),
182                P25Codeword::for_power(0),
183            ]
184            .iter()
185            .cloned(),
186        ) * Polynomial::new(
187            [
188                P25Codeword::for_power(0),
189                P25Codeword::default(),
190                P25Codeword::default(),
191                P25Codeword::for_power(0),
192                P25Codeword::default(),
193                P25Codeword::default(),
194                P25Codeword::for_power(0),
195            ]
196            .iter()
197            .cloned(),
198        ) * Polynomial::new(
199            [
200                P25Codeword::for_power(0),
201                P25Codeword::for_power(0),
202                P25Codeword::for_power(0),
203                P25Codeword::default(),
204                P25Codeword::default(),
205                P25Codeword::for_power(0),
206                P25Codeword::for_power(0),
207            ]
208            .iter()
209            .cloned(),
210        ) * Polynomial::new(
211            [
212                P25Codeword::for_power(0),
213                P25Codeword::for_power(0),
214                P25Codeword::for_power(0),
215                P25Codeword::default(),
216                P25Codeword::for_power(0),
217                P25Codeword::default(),
218                P25Codeword::for_power(0),
219            ]
220            .iter()
221            .cloned(),
222        ) * Polynomial::new(
223            [
224                P25Codeword::for_power(0),
225                P25Codeword::for_power(0),
226                P25Codeword::default(),
227                P25Codeword::default(),
228                P25Codeword::default(),
229                P25Codeword::default(),
230                P25Codeword::for_power(0),
231            ]
232            .iter()
233            .cloned(),
234        );
235
236        assert_eq!(p.degree().unwrap(), 47);
237
238        let gen = 0o6331_1413_6723_5453u64;
239
240        for i in 0..=47 {
241            let coef = gen >> i & 1;
242
243            assert_eq!(p[i].power(), if coef == 0 { None } else { Some(0) });
244        }
245    }
246
247    #[test]
248    fn test_encode() {
249        assert_eq!(
250            encode(0b1111111100000000),
251            0b1111111100000000100100110001000011000010001100000110100001101000
252        );
253        assert_eq!(encode(0b0011) & 1, 0);
254        assert_eq!(encode(0b0101) & 1, 1);
255        assert_eq!(encode(0b1010) & 1, 1);
256        assert_eq!(encode(0b1100) & 1, 0);
257        assert_eq!(encode(0b1111) & 1, 0);
258    }
259
260    #[test]
261    fn test_syndromes() {
262        let w = encode(0b1111111100000000) >> 1;
263
264        assert_eq!(syndromes(w).degree(), None);
265        assert_eq!(syndromes(w ^ 1 << 60).degree().unwrap(), 21);
266    }
267
268    #[test]
269    fn test_decode() {
270        assert!(decode(encode(0b0000111100001111) ^ 1 << 63).unwrap() == (0b0000111100001111, 1));
271
272        assert!(decode(encode(0b1100011111111111) ^ 1).unwrap() == (0b1100011111111111, 0));
273
274        assert!(
275            decode(encode(0b1111111100000000) ^ 0b11010011 << 30).unwrap()
276                == (0b1111111100000000, 5)
277        );
278
279        assert!(
280            decode(encode(0b1101101101010001) ^ (1 << 63 | 1)).unwrap() == (0b1101101101010001, 1)
281        );
282
283        assert!(
284            decode(encode(0b1111111111111111) ^ 0b11111111111).unwrap() == (0b1111111111111111, 10)
285        );
286
287        assert!(
288            decode(encode(0b0000000000000000) ^ 0b11111111111).unwrap() == (0b0000000000000000, 10)
289        );
290
291        assert!(
292            decode(encode(0b0000111110000000) ^ 0b111111111110).unwrap()
293                == (0b0000111110000000, 11)
294        );
295
296        assert!(
297            decode(encode(0b0000111110000000) ^ 0b111111111110).unwrap()
298                == (0b0000111110000000, 11)
299        );
300
301        assert!(decode(encode(0b0000111110001010) ^ 0b1111111111110).is_none());
302        assert!(decode(encode(0b0000001111111111) ^ 0b11111111111111111111110).is_none());
303        assert!(decode(
304            encode(0b0000001111111111) ^ 0b00100101010101000010001100100010011111111110
305        )
306        .is_none());
307
308        for i in 0..1u32 << 17 {
309            assert_eq!(decode(encode(i as u16)).unwrap().0, i as u16);
310        }
311    }
312}
code_rs/coding/bch.rs

code_rs/coding/
bch.rs
