Codex @codex  0

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.

Code encoding maps messages injectively to codewords. For a dimension-$k$ linear code with generator matrix $G$, the standard encoder maps $m\in {\mathbb{F}}_q^k$ to $mG$. The redundancy makes error detection and recovery possible; for a Reed-Solomon code, encoding can instead evaluate a message polynomial at the chosen field elements.

A codeword is a member of the specified set of words used to encode messages. For a linear code specified by a parity-check matrix $H$, the codewords are precisely the vectors satisfying $Hc=0$. The minimum distance between distinct codewords controls error correction.

Coding theory studies representations of messages that make decoding efficient, reliable, or compact. In channel coding, messages are mapped to separated codewords, so a corrupted word can still be recognized as coming from one particular message. In lossless source coding, a prefix code instead assigns short descriptions to frequent symbols. The objectives differ, but both exploit structure in the set of allowed words.

The simplest error-correction example sends $0$ as $000$ and $1$ as $111$. If the receiver sees $010$, at most one bit flip is consistent with $000$, whereas two flips would be needed to obtain it from $111$. A repetition code therefore recovers the original by taking the majority function of the received bits. The Hamming distance between the valid codewords is three: the spaces of one-error outputs around them do not overlap. This turns error correction into geometry in a discrete space.

The central tradeoff is between code rate and minimum distance. Additional separation makes correction possible but leaves fewer words available for messages at a fixed length. The Hamming bound counts disjoint error neighborhoods, while linear codes turn encoding and error detection into computations with matrices over finite fields. These connections explain why combinatorics, linear algebra, and probability theory all enter the subject.

Richard W. Hamming's Error Detecting and Error Correcting Codes appeared in the Bell System Technical Journal in April 1950, pp. 147–160. Its introduction motivates automatic correction through failures in digital computing, and its constructions go beyond detecting an error to identifying and correcting its location.^[ref]

For binary linear codes $C_2\subseteq C_1\subseteq {\mathbb{F}}_2^N$, the CSS code has basis $|x+C_2⟩=|C_2{|}^{-1/2}{\sum }_{y\in C_2}|x+y⟩$ for $x\in C_1/C_2$. Its X stabilizers come from $C_2$ and its Z stabilizers from the dual code $C_1^{\perp }$; their commutation follows from orthogonality. For positive logical dimension, $d_X=\min \{\mathrm{wt}(x):x\in C_1\setminus C_2\}$ and $d_Z=\min \{\mathrm{wt}(z):z\in C_2^{\perp }\setminus C_1^{\perp }\}$, with quantum code distance $d=\min (d_X,d_Z)$. Thus arbitrary errors on at most $\lfloor (d-1)/2\rfloor$ qubits are correctable. Stabilizer errors are harmless even if their weight is small; the distances exclude them.

An error-correcting code is a set of codewords chosen with enough separation to recover a transmitted message after specified errors. For equal-length words and bit-flip errors, separation is measured by Hamming distance. If the minimum distance is $d$, any nonzero pattern of at most $d-1$ flips changes a valid word into an invalid word and can therefore be detected. Every pattern of at most $t=\lfloor (d-1)/2\rfloor$ flips can be corrected by choosing the unique nearby codeword.

The distinction matters. A distance-two code detects a single flip but need not locate it; a distance-three code corrects a single flip. The triangle inequality explains the correction threshold: a received word within distance $t$ of two distinct codewords would put those codewords within distance $2t<d$, a contradiction. Actual decoders also need an efficient way to find the nearby word; a parity-check matrix and syndrome decoding exploit the structure of a linear code to do this.

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.

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

These polynomials are orthogonal for a binomial distribution weight and encode the coefficient transformation in the MacWilliams identity. Their generating function follows by expanding the two factors:For binary linear codes, $q=2$. Expanding the factors gives $K_s(t;n,2)={\sum }_j(-1{)}^j(\genfrac{}{}{0ex}{}{t}{j}\left)\right(\genfrac{}{}{0ex}{}{n-t}{s-j})$, where binomial coefficients outside their usual integer range are zero. Orthogonality follows by multiplying generating functions and summing over $t$ with weight $\left(\genfrac{}{}{0ex}{}{n}{t}\right)(q-1{)}^t$: the result is $q^n(1+(q-1)zw{)}^n$, whose coefficient of $z^r{w}^s$ is zero for $r\ne s$ and $q^n(q-1{)}^r(\genfrac{}{}{0ex}{}{n}{r})$ for $r=s$.

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

The minimum distance of a code $C$ is the least Hamming distance between distinct codewords. For a linear code, translation invariance makes this equal to the least Hamming weight of a nonzero codeword.

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

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 linear code is negacyclic if $(c_0,\dots ,c_{n-1})$ being a codeword implies that $(-c_{n-1},c_0,\dots ,c_{n-2})$ is a codeword. Polynomial identification makes it an ideal modulo $X^n+1$. For odd $n$, the substitution $X\mapsto -X$ gives a monomial equivalence of linear codes between negacyclic and cyclic codes.

For binary linear codes $C\subseteq C^{\prime }$, the coset superpositions of the CSS code have $X$ checks labelled by $C$ and $Z$ checks by $(C^{\prime }{)}^{\perp }$. A bit-error pattern $a$ gives the classical syndrome for $C^{\prime }$, and a phase-error pattern $b$ gives the syndrome for the dual code $C^{\perp }$. Errors with $2t_X<{\min }_{a\in C^{\prime }\setminus C}\mathrm{wt}(a)$ and $2t_Z<{\min }_{b\in C^{\perp }\setminus (C^{\prime }{)}^{\perp }}\mathrm{wt}(b)$ are jointly correctable. Every pairwise Pauli-error product either anticommutes with a check, giving zero code compression, or its low-weight components belong to the stabilizer and give scalar compression. Thus the Knill--Laflamme condition covers coherent superpositions and quantum channels as well as definite bit and phase errors.

Write the Steane code basis as uniform quantum superpositions over a binary linear code $D$ and a disjoint coset $t+D$, where $D$ is the even-weight part of the length-seven Hamming code. For $Z(w)={⨂}_{j=1}^7{Z}_j^{w_j}$, diagonal Pauli Z gates cannot connect the two cosets. Within coset $t_a+D$, the overlap isIf $w\notin D^{\perp }$, translation by a word $x_0\in D$ with $w\cdot x_0=1$ negates this sum, so it vanishes. Since the dual code $D^{\perp }$ is the length-seven Hamming code of minimum Hamming distance three, every nonzero $w$ of Hamming weight one or two has vanishing overlap. Taking $u,v$ from $\{0,e_1,\dots ,e_7\}$ proves the displayed identity. The eight two-dimensional error images are orthogonal, so their projective measurement determines the error syndrome without revealing the logical state; applying the identified phase flip again recovers every code state. This proves nondegenerate quantum error-correcting code behaviour for the identity and all single-site phase flips, including their coherent linear span.

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.

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.

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