galois.roots_to_parity_check_matrix(n: int, roots: FieldArray) → FieldArray

Converts the generator polynomial roots into the parity-check matrix \(\mathbf{H}\) for an \([n, k]\) cyclic code.

Parameters
n: int

The codeword size \(n\).

roots: FieldArray

The \(2t\) roots of the generator polynomial \(g(x)\).

Returns

The \((2t, n)\) parity-check matrix \(\mathbf{H}\), such that given a codeword \(\mathbf{c}\), the syndrome is defined by \(\mathbf{s} = \mathbf{c}\mathbf{H}^T\).

Examples

Compute the parity-check matrix for the \(\mathrm{RS}(15, 9)\) code.

In [1]: GF = galois.GF(2**4)

In [2]: alpha = GF.primitive_element

In [3]: t = 3

In [4]: roots = alpha**np.arange(1, 2*t + 1); roots
Out[4]: GF([ 2,  4,  8,  3,  6, 12], order=2^4)

In [5]: g = galois.Poly.Roots(roots); g
Out[5]: Poly(x^6 + 7x^5 + 9x^4 + 3x^3 + 12x^2 + 10x + 12, GF(2^4))

In [6]: galois.roots_to_parity_check_matrix(15, roots)
Out[6]: 
GF([[ 9, 13, 15, 14,  7, 10,  5, 11, 12,  6,  3,  8,  4,  2,  1],
    [13, 14, 10, 11,  6,  8,  2,  9, 15,  7,  5, 12,  3,  4,  1],
    [15, 10, 12,  8,  1, 15, 10, 12,  8,  1, 15, 10, 12,  8,  1],
    [14, 11,  8,  9,  7, 12,  4, 13, 10,  6,  2, 15,  5,  3,  1],
    [ 7,  6,  1,  7,  6,  1,  7,  6,  1,  7,  6,  1,  7,  6,  1],
    [10,  8, 15, 12,  1, 10,  8, 15, 12,  1, 10,  8, 15, 12,  1]],
   order=2^4)
Last update: Aug 27, 2022