Module bch 

Binary BCH codes, shortened: the outer code of DVB-S2 (comnum_systems::dvbs2).

Model

In the Galois field $\mathrm{GF}(2^{m})$ generated by a primitive element $\alpha$ (root of a primitive polynomial $p(x)$), the narrow-sense BCH code of designed distance $2t + 1$ has the generator polynomial

$$ g(x) = \operatorname{lcm}\left(m_{1}(x), m_{3}(x), \dots, m_{2t-1}(x)\right), $$

with $m_{i}$ the minimal polynomial of $\alpha^{i}$ (Lin & Costello, ch. 6). The code of length $2^{m} - 1$ is shortened to $n$ bits by fixing its first information bits to zero. The encoder is systematic: the $k$ message bits $m_{k-1}, \dots, m_{0}$ (the highest degree first, in transmission order) followed by the $n - k$ coefficients of $x^{n-k} m(x) \bmod g(x)$. The decoder computes the syndromes $S_{j} = r(\alpha^{j})$, the error-locator polynomial by the Berlekamp–Massey algorithm and its roots by a Chien search over the $n$ positions; it corrects up to $t$ errors and reports a failure beyond (when the locator has fewer roots than its degree). The field arithmetic is that of comnum_math::gf2m.

Examples

use comnum_fec::bch::Bch;
// the (15, 7) BCH code, t = 2, of GF(16) with p(x) = 1 + x + x⁴
let code = Bch::new(4, 0b1_0011, 2, 15)?;
assert_eq!(code.k(), 7);
assert_eq!(code.generator(), &[1, 0, 0, 0, 1, 0, 1, 1, 1]);   // 1 + x⁴ + x⁶ + x⁷ + x⁸
let msg = [1, 0, 1, 1, 0, 0, 1];
let mut c = code.encode(&msg)?;
c[2] ^= 1;
c[11] ^= 1;
let (decoded, corrected) = code.decode(&c)?;
assert_eq!((decoded, corrected), (msg.to_vec(), Some(2)));

References

1. S. Lin and D. J. Costello, Error Control Coding, 2nd ed., Pearson, 2004, ch. 6.
2. ETSI EN 302 307-1 V1.4.1, Digital Video Broadcasting (DVB); Second generation framing structure, channel coding and modulation systems (DVB-S2), 2014, § 5.3.1.

Structs

Bch

A shortened binary BCH code (see the module).