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.

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.

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

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.

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

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.

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

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.