Linear code

A binary linear $[n,k,d]$ code is a $k$-dimensional subspace of ${\mathbb{F}}_2^n$ with least nonzero weight $d$. A parity-check matrix presents it as a kernel.

Two linear codes are monomially equivalent if a permutation of coordinates followed by multiplication of individual coordinates by nonzero field elements takes one to the other. This preserves dimension and Hamming distance. Choosing different representatives for projective parity-check columns produces this equivalence.

A nonzero length-$n$, dimension-$k$ linear code is maximum distance separable if its minimum Hamming distance equals $n-k+1$, attaining the Singleton bound. Reed-Solomon codes and generalized Reed-Solomon codes provide examples because a nonzero polynomial of degree at most $k-1$ has at most $k-1$ distinct polynomial roots.

For distinct elements $a_1,\dots ,a_n$ of a finite field, a Reed-Solomon code consists of the evaluation vectors $(f(a_1),\dots ,f(a_n))$ of polynomials with degree less than $k$. It has dimension $k$ and minimum Hamming distance $n-k+1$, so it is a maximum distance separable code. A nonzero polynomial has at most its degree many distinct polynomial roots. Primitive cyclic Reed-Solomon codes use all nonzero field elements, ordered as powers of a primitive root of unity; arbitrary evaluation sets need not give a cyclic code.

Let $n=q-1$ and let $\omega$ be a primitive root of unity in ${\mathbb{F}}_q$. The length-$n$ cyclic code with consecutive zeros of a cyclic code ${\omega }^b,\dots ,{\omega }^{b+n-k-1}$ has dimension $k$. It equals the generalized Reed-Solomon code of vectors $({\omega }^{j(1-b)}f({\omega }^j){)}_{j=0}^{n-1}$, $\mathrm{deg}f<k$. The choice $b=1$ is the unweighted Reed-Solomon code on these evaluation points; allowing other offsets makes this family closed under dual codes.

With syndromes $S_{\ell }={\sum }_i{E}_i{X}_i^{b+\ell }$ and distinct error-location values $X_i$, form $S(z)={\sum }_{\ell =0}^{n-k-1}{S}_{\ell }{z}^{\ell }$ and the error locator polynomial $\Lambda (z)={\prod }_i(1-X_{i}z)$. There is an error evaluator polynomial $\Omega$ of degree less than the number of errors satisfying the key equation. When the number of errors is at most $\lfloor (n-k)/2\rfloor$, the Berlekamp-Massey algorithm or extended Euclidean algorithm recovers these polynomials, normalized by $\Lambda (0)=1$.

For $n=q-1$ and $a_j={\omega }^j$, the two evaluation forms are $a_j^{1-b}f(a_j)$ and $a_j^{b}h(a_j)$, with $\mathrm{deg}f<k$ and $\mathrm{deg}h<n-k$. Their dot product is ${\sum }_j{a}_{j}f(a_j)h(a_j)=0$, since every appearing exponent is between one and $n-1$ and the sums of those powers of $a_j$ vanish. Comparing dimensions proves equality with the dual code. In particular, the dual of the unweighted evaluation code has multipliers $a_j$; it need not be an unweighted evaluation code on the same ordered points.

A generalized Reed-Solomon code consists of $(v_{i}f(a_i){)}_{i=1}^n$, where the evaluation points are distinct, all coordinate multipliers $v_i$ are nonzero, and $\mathrm{deg}f<k$. It remains a maximum distance separable code. Its dual code is another generalized Reed-Solomon code with dimension $n-k$ and multipliers proportional to $v_i^{-1}{\prod }_{j\ne i}(a_i-a_j{)}^{-1}$.

For a linear code of length $n$ and dimension $k$ over ${\mathbb{F}}_q$, the code rate is $R=k/n$. There are $q^k$ possible messages represented by $q^k$ codewords of length $n$. More generally a block code $C\subseteq {\mathbb{F}}_q^n$ has rate ${\log }_q|C|/n$. This is a dimensionless redundancy measure, distinct from information transmitted per unit physical time.

The asymptotic rate-distance function is ${\alpha }_q(\delta )={\mathrm{limsup}}_{n\to \infty }{n}^{-1}{\log }_q{A}_q(n,\max \{1,\lceil \delta n\rceil \})$. It is the best asymptotic code rate available at the specified relative minimum distance. A limsup is used because the definition does not assume an ordinary limit exists.

// Target: algebra.bigb

A linear code over the two-element finite field. Its dimension $r$ gives $2^r$ codewords. Its weight enumerator in the convention $W_C(s,t)={\sum }_{c\in C}{s}^{w(c)}{t}^{n-w(c)}$ is symmetric in $s,t$ exactly when the all-ones word belongs to $C$: adding that word complements every bit and replaces weight $w$ by $n-w$. Conversely symmetry makes the coefficient of $s^n$ equal the coefficient of $t^n$, which is one.

A length-$n$, dimension-$k$ binary linear code has full support when no coordinate vanishes on every codeword, equivalently when the union of the supports of a vector of all codewords covers every coordinate. Every coordinate is then a nonzero linear functional on the message vector space ${\mathbb{F}}_2^k$. Translation by a vector on which it is one pairs the zero and one fibers, so exactly $2^{k-1}$ codewords contribute one in that coordinate. Summing these contributions proves the formula. If there are $r$ nonzero columns in a full-rank generator matrix, the same argument gives $r{2}^{k-1}$ instead.

For a binary linear code $C$, the linear functional $\sigma (x)={\sum }_j{x}_j$ records Hamming weight modulo two. Its kernel of a linear map is the even-weight subcode. If $\sigma {|}_C$ vanishes, this is all of $C$; otherwise rank-nullity theorem gives dimension $\dim C-1$. This also proves closure under addition without treating ordinary integer weight as a linear function.

A binary linear code is doubly even when the Hamming weight of every codeword is divisible by four.

// Target: algebra.bigb

Suppose the generators of a binary linear code have Hamming weights divisible by four and have pairwise zero binary inner products. Their linear span is doubly even: for any two vectors,The binary inner product says the intersection size is even. Induction on the number of generators in a sum proves divisibility by four.

// Target: algebra.bigb

A linear subspace $W\subseteq {\mathbb{F}}_2^n$ is self-orthogonal if $u\cdot v=0$ for every $u,v\in W$. The standard bilinear form is nondegenerate, whence $\dim W+\dim W^{\perp }=n$ and $\dim W\le \lfloor n/2\rfloor$. The condition with $u=v$ means every vector has even Hamming weight. Such a binary linear code gives the linear algebra behind the Eventown theorem.

If a self-orthogonal binary subspace has odd length $n$ and dimension $(n-1)/2$, its dual code is obtained by adjoining the all-ones word. Self-orthogonality makes every codeword even-weight, so $1\in C^{\perp }$ but $1\notin C$. Comparing dimensions proves the formula. The dimension hypothesis alone is insufficient: $C=⟨100⟩$ at length three is a counterexample.

The code consisting of all even-weight binary words. For $n\ge 1$ its dimension is $n-1$, and its weight enumerator is $[(t+s{)}^n+(t-s{)}^n]/2$, by selecting the even terms of the binomial theorem. The length-one code contains only zero.

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$.

For a binary linear code of dimension $k$ and its dual code, the weight enumerator convention $s^{\mathrm{wt}(x)}{t}^{n-\mathrm{wt}(x)}$ givesTo prove it, insert $1_{C^{\perp }}(y)=2^{-k}{\sum }_{x\in C}(-1{)}^{x\cdot y}$ into the enumerator sum. Summing independently over each coordinate of $y$ yields a factor $t+s$ if $x_j=0$ and $t-s$ if $x_j=1$.

A parity bit records whether the number of one bits in a word is even or odd and can detect every error that flips an odd number of bits.

Apply one CNOT gate from each input qubit to the same target. Their actions commute because controls remain unchanged and each contribution is added modulo two. This reversible circuit computes the parity bit with exactly one two-qubit gate per input, and its inverse is the same circuit. Unlike measuring the inputs to compute parity classically, the unitary preserves quantum superposition and can be uncomputed after phase application.

The length-$n$ even-weight code consists of binary words whose coordinates sum to zero. It has parameters $[n,n-1,2]$.

The binary repetition code is $\{0^n,1^n\}$ and has parameters $[n,1,n]$.

The zero code contains only the zero word and has dimension zero.

The whole-space binary code is ${\mathbb{F}}_2^n$, with parameters $[n,n,1]$.

The Hamming weight $\mathrm{wt}(x)$ of a word is the number of its nonzero coordinates.

Store the Hamming weight of each possible byte in a 256-entry table. Extract each byte of a word by a logical right shift and a bit mask, then sum its table entries. The byte positions partition the word's bits, proving the formula. A 32-bit word needs four lookups, which can be unrolled. Logical extraction does not depend on the endianness of a stored word. The speed advantage depends on table-access costs as well as instruction counts.

The minimum Hamming distance of a nonzero linear code is the smallest Hamming weight of a nonzero codeword.

Every binary linear $[n,k,d]$ code satisfiesPuncturing on the support of a minimum-weight codeword reduces the rank by one and leaves minimum distance at least $\lceil d/2\rceil$, which proves the bound inductively.

A generator matrix for a linear code has a basis of the code as its rows, so its row space is the code.

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.

The parity-check extension of a binary linear code appends to each codeword the sum of its coordinates in ${\mathbb{F}}_2$, making every extended word have even Hamming weight.

Shortening a code at one coordinate first retains only words with a chosen symbol there and then applies puncturing at that coordinate. The minimum distance cannot decrease. In a binary code one coordinate-symbol fibre contains at least half of the words.

The dual code $C^{\perp }$ consists of the words orthogonal to every word of $C$ under the standard dot product. A parity-check matrix for $C$ is a generator matrix for $C^{\perp }$.

A linear code is self-dual when it equals its dual code under the standard dot product. For a length-$2k$ code with a rank-$k$ generator matrix $G$, this is equivalent to $G{G}^T=0$: orthogonality gives inclusion in the dual code, and equal dimensions give equality. Over ${\mathbb{F}}_2$, a generator matrix $(I\mid A)$ therefore generates a self-dual code exactly when $A{A}^T=I$.

For a binary self-dual code, every word $c$ satisfies $c\cdot c=0$. In characteristic two this is ${\sum }_i{c}_i=0$, so the all-ones word is orthogonal to every codeword and lies in the dual code, hence the code itself. The dual code dimension identity gives even length and half-length dimension.

The binary Reed-Muller code $\mathrm{RM}(d,r)$ evaluates Boolean polynomials of degree at most $r$ on ${\mathbb{F}}_2^d$. It has parametersThe dimension counts square-free monomials, and the minimum weight follows inductively from the decomposition $(u,u+v)$.

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

If $C_2\subseteq C_1$ have minimum distances $d_2,d_1$, respectively, thenIndeed, $\mathrm{wt}(u)+\mathrm{wt}(u+v)\ge \mathrm{wt}(v)$, while the words $(u,u)$ and $(0,v)$ attain the two candidate bounds.

If $H_i$ is a parity-check matrix of $C_i$, then a parity-check matrix of $C_1|C_2$ isIts equations say that the first half $u$ lies in $C_1$ and that the sum of the two halves lies in $C_2$.

For $0<r<d$,Consequently

Under the standard binary inner product,The product of representing polynomials has degree at most $d-1$, so its evaluation word has even weight; equality follows by comparing dimensions.

The binary Hamming code of redundancy $r$ has parameters $[2^r-1,2^r-r-1,3]$. Its parity-check matrix has every nonzero vector of ${\mathbb{F}}_2^r$ as a column.

For $s\ge 2$, use one nonzero representative from each one-dimensional subspace of ${\mathbb{F}}_3^s$ as a parity-check matrix column. The rank is $s$; no zero or proportional columns imply minimum Hamming distance at least three. Two independent columns and the representative of their sum give a weight-three relation, proving equality. Every nonzero syndrome uniquely identifies one column and one nonzero error value.

For odd $s\ge 3$, put $n=(3^s-1)/2$ and choose $\alpha$ of order $n$ in ${\mathbb{F}}_{3^s}$. Because $n$ is odd, the powers ${\alpha }^i$, $0\le i<n$, represent every projective point once. The cyclic code defined by $c(\alpha )=0$ is therefore monomially equivalent to a ternary Hamming code, with the displayed generator polynomial of a cyclic code. This statement requires a qualification: at $s=2$, every ternary cyclic length-four, dimension-two code has a weight-two generator, so none has Hamming distance three.

Set $n=(3^s-1)/2$ and let $\beta$ be a primitive element of a finite field ${\mathbb{F}}_{3^s}$. The powers $1,\beta ,\dots ,{\beta }^{n-1}$ represent every projective point once. Their kernel code is a ternary Hamming code. Since ${\beta }^n=-1$, its polynomial description is a negacyclic code, generated by the minimal polynomial of an algebraic element $\beta$ over ${\mathbb{F}}_3$.

Let $\omega$ generate ${\mathbb{F}}_{2^s}^{\times }$, $s\ge 2$, and set $n=2^s-1$. The binary cyclic code defined by $c(\omega )=0$ has a parity-check matrix consisting of every nonzero vector of ${\mathbb{F}}_2^s$ once, after choosing a basis and ordering its columns. It is therefore a Hamming code. Its generator polynomial is the minimal polynomial of an algebraic element $m_{\omega }(x)={\prod }_{j=0}^{s-1}(x-{\omega }^{2^j})$, of degree $s$.

Here $N=2^l-1$, $m=2^{l-1}$ and the weight enumerator convention is $W_C(s,t)={\sum }_{c\in C}{s}^{\mathrm{wt}(c)}{t}^{N-\mathrm{wt}(c)}$. The dual code is the binary simplex code, with enumerator $t^N+(2^l-1)s^m{t}^{m-1}$. The MacWilliams identity gives the formula. For $l=3$, the ordinary enumerator $W_C(z,1)$ is $1+7z^3+7z^4+z^7$; for $l=1$, the degenerate one-word code has enumerator $t$.

For $n=2^{\ell }-1$, a codeword in a Hamming code is a subset of the nonzero vectors of ${\mathbb{F}}_2^{\ell }$ whose sum is zero. Ordered weight-three supports of a vector are determined by two distinct nonzero vectors, giving $n(n-1)$ choices. For weight four, the third vector must avoid the three nonzero vectors in the linear span of the first two, giving $n(n-1)(n-3)$ choices. For weight five, the first three must be linearly independent, and the fourth must avoid all seven nonzero vectors in their linear span, giving $n(n-1)(n-3)(n-7)$ choices. The final vector is their sum. Dividing by $3!$, $4!$, and $5!$ counts unordered supports of a vector and proves the displayed weight enumerator coefficients.

Adding an overall parity bit to the Hamming code of length seven gives an eight-bit linear code with minimum Hamming distance four: every resulting weight is even, every original nonzero weight is at least three, and a weight-three word extends to weight four. Thus it detects up to three errors when testing codeword membership and corrects one error. Joint single-error correction and double-error detection uses the overall parity together with the seven-bit syndrome.

The binary linear code known as the Hamming code of length seven is the kernel of a $3\times 7$ parity-check matrix whose columns are all the nonzero vectors of ${\mathbb{F}}_2^3$. Its dimension is four. No one-column or two-column sum vanishes, but some three-column sum does, so its minimum Hamming distance is three. The syndrome of a one-bit error is its column, uniquely identifying the erroneous position.

The binary simplex code is the dual of the binary Hamming code. For redundancy $r$ it has parameters $[2^r-1,r,2^{r-1}]$.

Its relation to the Hamming code is duality, not equality of the code families.

When the columns of $H$ are every nonzero vector in ${\mathbb{F}}_2^l$, a nonzero row vector $a$ defines a nonzero linear functional $v\mapsto a\cdot v$. Exactly half the $2^l$ input vectors take value $1$: translation by any vector on which the functional is $1$ pairs its zero and one fibres. Removing the zero input removes only a zero value. Thus every nonzero word in the binary simplex code has Hamming weight $2^{l-1}$.

A Hamming code has $2^{2^r-r-1}$ words, and each radius-one Hamming ball contains $1+(2^r-1)=2^r$ vectors. Its minimum distance is three, so these balls are disjoint, and their total size is $2^{2^r-1}$. They therefore partition the ambient space, making the code perfect.

A code of minimum Hamming distance $d$ detects every pattern of at most $d-1$ errors and uniquely corrects every pattern of at most $\lfloor (d-1)/2\rfloor$ errors. The correction claim follows because Hamming balls of that radius around distinct codewords are disjoint.