Module gf2m 

The Galois fields $\mathrm{GF}(2^{m})$: the arithmetic on which comnum_fec builds the BCH and Reed–Solomon codes.

Model

The field is generated by a primitive element $\alpha$, a root of a primitive polynomial $p(x)$ of degree $m$ over $\mathrm{GF}(2)$: its $2^{m} - 1$ non-zero elements are the powers $\alpha^{0}, \dots, \alpha^{2^{m}-2}$. An element is stored as the $m$ bits of its polynomial representation (bit $i$ the coefficient of $\alpha^{i}$), so that the addition is the exclusive or, and a table of the powers and of the logarithms gives the product

$$ \alpha^{i} \alpha^{j} = \alpha^{(i + j) \bmod (2^{m} - 1)}. $$

The minimal polynomial of $\alpha^{i}$ is the product over its conjugates, $m_{i}(x) = \prod_{j} \left(x - \alpha^{i 2^{j}}\right)$, a binary polynomial.

primitive_polynomial gives the conventional primitive polynomial of every degree 2 to 16: the ones of the tables of Lin & Costello (Table 2.7) and of the coding standards (DVB, CD, QR codes use $x^{8} + x^{4} + x^{3} + x^{2} + 1$ for $m = 8$).

Examples

use comnum_math::gf2m::{Field, primitive_polynomial};
// GF(16) with p(x) = 1 + x + x⁴: α⁴ = α + 1 = 0b0011
let f = Field::new(4, primitive_polynomial(4).unwrap())?;
assert_eq!(f.pow(4), 0b0011);
assert_eq!(f.mul(f.pow(7), f.pow(12)), f.pow(4));          // α⁷ α¹² = α¹⁹ = α⁴
assert_eq!(f.minimal_polynomial(1), vec![1, 1, 0, 0, 1]);  // p(x) itself

References

1. S. Lin and D. J. Costello, Error Control Coding, 2nd ed., Pearson, 2004, ch. 2 (Table 2.7: primitive polynomials, Table 2.8: GF($2^{4}$)).

Structs

Field

The Galois field $\mathrm{GF}(2^{m})$ by exponential and logarithm tables.

Functions

primitive_polynomial

The conventional primitive polynomial of degree m (bit $i$ the coefficient of $x^{i}$) for $2 \le m \le 16$, None otherwise.