= Polynomial multiplication parity-check matrix
Let $F(X)=X^N+1$ over the <field with two elements> and write $h=\sum_{j=0}^{N-1}h_jX^j$. In the <quotient ring> $\mathbb F_2[X]/(F)$, multiplication by $h$ is represented on coefficient column vectors by the <circulant matrix>
$$
B_{ti}=h_{t-i\bmod N}.
$$
The <kernel> is a <cyclic code>, because multiplication by $X$ preserves the condition $hv\equiv0\pmod F$.
More precisely, set $d=\gcd(F,h)$ and write $F=dF_1$, $h=dh_1$, with $F_1$ and $h_1$ <coprime polynomials>. Then $F\mid hv$ if and only if $F_1\mid v$. Hence the <kernel> is generated by $F/d$, has <dimension> $\deg d$, and $B$ has <rank> $N-\deg d$. Selecting independent rows of $B$ therefore gives a <parity-check matrix> for this <cyclic code>, even when $h$ was not supplied as a canonical check <polynomial>. If $h=F/g$ for a divisor $g$ of $F$, the <kernel> is exactly the <cyclic code> generated by $g$.
// Target: algebra.bigb
Back to article page
