Block code

A block code assigns source messages to words of a fixed length over an alphabet. Its codewords form a subset of that fixed-length word space; a binary block code uses the two-symbol finite field ${\mathbb{F}}_2$.

A binary $[n,m,d]$ code is a set of $m$ distinct words in ${\mathbb{F}}_2^n$ whose minimum pairwise Hamming distance is $d$. Here $n$ is the block length and $m$ is the number of codewords.

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.

A binary repetition code represents one bit by repeating it $n$ times, using codewords $0^n$ and $1^n$. Their Hamming distance is $n$, and the code rate is $1/n$. For odd $n$, the majority function recovers the input whenever fewer than half the positions have flipped. Even $n$ allows a tied vote, so a decoder must specify how it handles that case.

For $n=3$, the received words $000,001,010,100$ decode to zero; $111,110,101,011$ decode to one. The decoder therefore corrects every single flip. This guarantee concerns the number of flipped positions, independent of any probabilistic model.

If each position passes independently through a binary symmetric channel with crossover probability $q$, a decoded error requires at least two flips. The binomial distribution givesAt $q=0.1$, the uncoded error probability is $0.1$, while the three-bit code's decoded error probability is $0.028$. This improvement costs three transmitted bits per message bit. For $0<q<1/2$, $3q^2-2q^3<q$; for $q>1/2$, one should first exploit the known tendency to invert symbols rather than applying the same majority rule blindly.

Independent flips are an essential assumption for the displayed formula. If a single common disturbance flips all three positions together with probability $q$, repetition provides no improvement. More efficient error-correcting codes distribute redundancy across larger message blocks; repetition is useful as a transparent example of the geometry and the reliability–rate tradeoff.

The Hamming distance between two equal-length words is the number of coordinates in which they differ.

The Hamming space of length $n$ over a finite field ${\mathbb{F}}_q$ is the set ${\mathbb{F}}_q^n$ equipped with Hamming distance, the number of coordinates at which two words differ. The Hamming weight of a word is its distance from zero.

This is the maximum Hamming distance between the characteristic vectors of members of a set family. In a down-set, one can replace a pair by disjoint subsets with the same union, so the maximum distance equals the largest size of a union of two members. A t-intersecting family has diameter at most $n-t$.

On binary words of length $n$, normalized Hamming distance is the fraction of differing coordinates. Unlike unscaled Hamming distance, it makes the Hamming cubes a Lévy family under uniform probability measures.

The Hamming cube is $\{-1,1{\}}^n$, or equivalently $\{0,1{\}}^n$, equipped with Hamming distance. Under its uniform probability measure, the distance from a fixed vertex has the binomial distribution with parameters $n,1/2$. This converts geometric ball sizes into probability tails.

An inclusion-maximal separated set of separation $an$ covers the Hamming cube by strict-radius $an$ balls. The Hoeffding lower-tail bound for Hamming balls then gives at least $e^{2n(1/2-a{)}^2}$ selected vertices. At $a=1/8$ this yields $e^{9n/32}$ vertices, all separated by at least $n/8$.

This Hamming distance on partitions identifies a group with its complement because exchanging the two group names does not change the partition. Complementation is an isometry of the ordinary Hamming distance, so minimizing over this two-element group action gives a quotient metric and preserves the triangle inequality. Negating a zero-one indicator is not complementation; with $\pm 1$ membership vectors, it is.

Suppose $v_i=\pm 1/\sqrt{n}$ encodes the true partition and $\hat{v}$ is a unit estimated eigenvector. Every coordinate of the wrong sign contributes at least $1/n$ to ${\min }_{\sigma =\pm 1}\Vert \hat{v}-\sigma v{\Vert }_2^2=2(1-|{\hat{v}}^{\top }v|)$. Since this is at most $2(1-|{\hat{v}}^{\top }v{|}^2)$, which is the squared Frobenius distance between the rank-one orthogonal projection matrices, the bound follows. Coordinates estimated as zero may be assigned consistently to either group.

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 relative minimum distance of a length-$n$ code of minimum distance $d$ is $d/n$. It expresses the guaranteed separation as a fraction of the block length.

// Target: algebra.bigb

The quantity $A_q(n,d)$ is the largest cardinality of a length-$n$ code over an alphabet of size $q$ with minimum Hamming distance at least $d$. The code need not be linear.

// Target: algebra.bigb

The Hamming ball of radius $r$ about a word $x$ is the set of words whose Hamming distance from $x$ is at most $r$.

For $0\le \rho \le 1-1/q$, the exponential growth rate of a q-ary Hamming ball is $H_q(\rho )$. Stirling's formula gives the exponent of each summand $\left(\genfrac{}{}{0ex}{}{n}{i}\right)(q-1{)}^i$, and the sum lies between its largest term and $n+1$ times that term. Above the entropy-maximizing radius fraction, the exponent is one.

// Target: algebra.bigb

For a uniform vertex of the Hamming cube, distance from a fixed vertex is the sum of $n$ independent Bernoulli random variables with parameter $1/2$. The lower-tail Hoeffding inequality implies that the fraction of vertices at distance at most $an$, $0<a<1/2$, is at most $e^{-2n(1/2-a{)}^2}$. Strict-radius balls satisfy the same upper bound.

For $0<\rho \le 1/2$, the number of binary words within Hamming distance $\rho n$ of a fixed word is at most $e^{nh(\rho )}$, with the binary entropy function in natural logarithms. In $1={\sum }_j\left(\genfrac{}{}{0ex}{}{n}{j}\right){\rho }^j(1-\rho {)}^{n-j}$, each summand weight for $j\le \rho n$ is at least ${\rho }^{\rho n}(1-\rho {)}^{n(1-\rho )}=e^{-nh(\rho )}$. Also $h^{\prime \prime }(\rho )=-1/(\rho (1-\rho ))\le -4$, so $\log 2-h(1/2-a)\ge 2a^2$. These two bounds give the approximate-recovery denominator in the list-decoding Fano inequality.

A code of minimum distance $d$ is perfect if its Hamming balls of radius $\lfloor (d-1)/2\rfloor$ partition the ambient word space. Every word then has a unique nearest codeword within the code's error-correction radius.

The length-$23$ binary Golay code is the cyclic code over ${\mathbb{F}}_2$ generated byIt has dimension $12$, minimum Hamming distance $7$, and its radius-$3$ Hamming balls partition ${\mathbb{F}}_2^{23}$. Its parity extension has length $24$, dimension $12$, and minimum Hamming distance $8$.

// Target: algebra.bigb

The extended binary Golay code is the parity extension of the length-$23$ binary Golay code. It is a self-dual code and a doubly even code, with minimum Hamming distance eight. Its radius-three Hamming balls are disjoint but do not cover its Hamming space; it is not a perfect code.

For a binary symmetric matrix $A$ with $A^2=I$, the syndrome of an error $(p,q)$ relative to the column parity-check matrix $(I;A)$ is $s=p+qA$. An error of total Hamming weight at most three has at most one nonzero bit in one half. Test $s$, each $s+A_i$, $sA$, and each $sA+A_i$ for weights at most three, two, three and two respectively. These identify $(s,0)$, $(s+A_i,e_i)$, $(0,sA)$ and $(e_i,sA+A_i)$. For the extended binary Golay code, minimum Hamming distance eight guarantees that at most one such error exists.

Suppose a binary symmetric matrix $A$ satisfies $A^2=I$, has one row of Hamming weight eleven and eleven rows of Hamming weight seven, and every sum of two distinct rows has Hamming weight six. Then $(I\mid A)$ generates a self-dual code. Its rows have weights twelve or eight; their mutual orthogonality makes every generated word doubly even. A weight-four word $(u,uA)$ would have left-half weight one, two, three or four. The first two cases are excluded by the stated row weights; weight three would force $uA$ to be a unit vector and hence $u$ to be a row of $A$; weight four would force $uA=0$. Thus weight four is impossible and the minimum Hamming distance is eight.

The generator polynomial of a cyclic code defining the binary Golay code is $1+X+X^5+X^6+X^7+X^9+X^{11}$.

A root $\beta$ of the binary Golay generator polynomial has order $23$, and the Frobenius endomorphism shows that $\beta ,{\beta }^2,{\beta }^3,{\beta }^4$ are roots: $2^8\equiv 3(\mathrm{mod}23)$. The BCH bound gives minimum Hamming distance at least five. The circular autocorrelation of the binary Golay generator makes its parity extension doubly even, excluding original weights five and six. The generator itself has Hamming weight seven, proving that the distance is exactly seven.

// Target: algebra.bigb

The polynomial identity $(X+1)g(X)g^{\mathrm{rev}}(X)=X^{23}+1$, where $g^{\mathrm{rev}}(X)=X^{11}g(X^{-1})$, impliesEvery coefficient is the binary inner product of the coefficient vector of $g$ with one cyclic shift. Thus every such inner product is one. Appending a parity bit to the cyclic shifts gives mutually orthogonal weight-eight vectors, so orthogonal generators of doubly even codes applies.

// Target: algebra.bigb

For a code of length $n$, size $M$, and minimum distance $d$ over an alphabet of size $q$, puncturing $d-1$ coordinates gives the Singleton bound

The Plotkin bound limits a code whose minimum distance is more than the average distance between unrestricted words. For a binary code with $n<2d$ and even $d$,

Puncturing a code at one coordinate deletes that coordinate from every codeword. For a code of minimum distance $d\ge 2$, puncturing preserves its number of words and gives minimum distance $d$ or $d-1$.