Parity-check matrix ($H$)

A parity-check matrix $H$ for a linear code $C$ satisfies

For a cyclic code whose generator polynomial has distinct roots ${\alpha }_1,\dots ,{\alpha }_r$ in a splitting field $E$, the rows $(1,{\alpha }_i,\dots ,{\alpha }_i^{n-1})$ impose precisely the codeword conditions $c({\alpha }_i)=0$. Expanding each value in a basis of $E$ over the original finite field, then discarding dependent equations, gives a parity-check matrix over that field of rank $r$. Alternatively choose one root from each Frobenius conjugate orbit and expand its value in the field it generates.

In the usual column convention, a codeword $c$ of a linear code obeys $H{c}^T=0$, so its nonzero coordinates give a linear dependence among columns of its parity-check matrix. Conversely a dependence gives a nonzero codeword supported on those coordinates. Minimizing the support gives the minimum Hamming distance of a linear code. In the transposed convention $cP=0$, the corresponding objects are the rows of $P$. The size of a dependent set means the number of its coordinate positions, even when some check vectors coincide.

A binary check polynomial $h={\sum }_{j=0}^{N-1}{h}_j{X}^j$ modulo $X^N+1$ gives the circulant matrix $B_{ti}=h_{t-i\mathrm{mod}N}$ representing multiplication by $h$. Its kernel is the cyclic code. Selecting independent rows gives a parity-check matrix of rank equal to the redundancy, even when the supplied polynomial is not the canonical check polynomial.

// Target: algebra.bigb

If a binary length-$N$ cyclic code has generator of degree $r$ and check polynomial $h$ of degree $N-r$, use the coefficient vectors of $h^{\ast },X{h}^{\ast },\dots ,X^{r-1}{h}^{\ast }$ as the rows of a parity-check matrix. They have distinct leading positions and are independent. Their scalar products with a word are the coefficients of $X^{N-r},\dots ,X^{N-1}$ in its product with $h$, which vanish for codewords.

// Target: algebra.bigb

The syndrome of a received word $y$ with respect to a parity-check matrix $H$ is $s=H{y}^T$. It vanishes exactly when $y$ is a codeword and otherwise identifies the coset containing the error pattern.

For a linear code with parity-check matrix $H$, write the received word as $y=c+e$, where $c$ is a codeword and $e$ an error pattern. Its syndrome depends only on the error because $H{c}^T=0$. A syndrome decoder chooses a representative error $\hat{e}$ with that syndrome and returns $y-\hat{e}$. Choosing a minimum-Hamming weight representative gives minimum-distance decoding; within the guaranteed correction radius it recovers the unique transmitted codeword. Several representatives may tie outside that radius.

For a rank-$(N-k)$ parity-check matrix of a linear code $C$, two words have equal syndromes exactly when their difference lies in $C$. Thus attainable syndromes label cosets bijectively. For a received word $c+e$, its syndrome is that of the error $e$, so minimum-weight representatives provide minimum-distance decoding.

// Target: algebra.bigb

A coset leader is a minimum-Hamming-weight word in a coset of a linear code. It represents a most economical error pattern with the associated syndrome. Several leaders can tie; they need not be unique outside the code's guaranteed correction radius.