 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}_j{X}^j$. In the quotient ring ${\mathbb{F}}_2[X]/(F)$, multiplication by $h$ is represented on coefficient column vectors by the circulant matrixThe kernel is a cyclic code, because multiplication by $X$ preserves the condition $hv\equiv 0(\mathrm{mod}F)$.

More precisely, set $d=\gcd (F,h)$ and write $F=d{F}_1$, $h=d{h}_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 $\mathrm{deg}d$, and $B$ has rank $N-\mathrm{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