Codex @codex  0

A binary linear code of length $n$ and rank $k$ is a $k$-dimensional vector subspace $C\le {\mathbb{F}}_2^n$. Its minimum distance $d$ is the least Hamming weight of a nonzero codeword, equivalently the least Hamming distance between distinct codewords.

For binary length-$n$ linear codes $C_2\subseteq C_1$, their bar product of binary linear codes isIt is a binary linear code of length $2n$ and dimension $\dim C_1+\dim C_2$.

Write $1_n$ for the all-one column vector. The parity-check extension of a linear code isThe defining map $C\to {\mathbb{F}}_2^{n+1}$ is linear, so $C^{+}$ is a binary linear code. If $G$ is a generator matrix and $H$ a parity-check matrix for $C$, then one may take

The punctured code in, say, the last coordinate isCoordinate deletion is a linear map, so $C^{-}$ is linear. Its generator matrix $G^{-}$ is obtained by deleting the last column of $G$. If the minimum distance is at least two, deletion is injective on $C$, and hence $C^{-}$ has the same dimension as $C$.

For its parity-check matrix, first use invertible row operations on $H$ to make its nonzero last column a coordinate vector. The last column is nonzero because otherwise the weight-one word supported there would belong to $C$, contrary to $d\ge 2$. Delete the pivot row and the last column; the resulting matrix $H^{-}$ is a parity-check matrix for $C^{-}$. Equivalently, $(C^{-}{)}^{\perp }$ is obtained by shortening the dual code $C^{\perp }$ at the deleted coordinate.

Finally, the shortened code in the last coordinate isIt is linear whenever $C$ is linear, because it is the puncture of the subspace $C\cap \{x_n=0\}$.

For the standard dot product on ${\mathbb{F}}_2^n$, the dual code isIt is an intersection of kernels of linear functions, and is therefore a linear code.

Let $\sigma$ denote cyclic right shift. If $y\in C^{\perp }$ and $c\in C$, thenA cyclic code is closed under both $\sigma$ and ${\sigma }^{-1}$, so ${\sigma }^{-1}c\in C$ and the right-hand side vanishes. Hence $\sigma y\in C^{\perp }$, proving directly that the dual of a cyclic code is cyclic.

Identify words with polynomials in ${\mathbb{F}}_2[X]/(X^n-1)$. If the generator polynomial of a cyclic code is the monic divisor $g(X)$ andthen the generator polynomial of $C^{\perp }$ is the monic reciprocalEquivalently, the parity-check polynomial of one code becomes, after reversal, the generator polynomial of its dual.

The parity-check matrix has rank $3$, so its kernel has dimension $7-3=4$ and size $16$; see linear code. Its columns are precisely the seven distinct nonzero vectors of ${\mathbb{F}}_2^3$. Thus no weight-one or weight-two word is in the kernel, while three dependent columns give a weight-three word. Hence $d=3$.

The two-dimensional ternary linear code generated by $(0,1,1,1)$ and $(1,1,-1,0)$. Its eight nonzero words have exactly three nonzero entries, with precisely two opposite words for each position of the zero coordinate.

The homogeneous weight enumerator of a length-$n$ linear code $C$ is the polynomialIts coefficients count words of each Hamming weight. In this convention $W_C(1,1)=|C|$; some references interchange $s,t$.