Binary block code

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 detect or correct transmission errors.

A binary repetition code represents one bit by repeating it a fixed number of times. Majority decoding corrects fewer than half as many bit flips as the block length.

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

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 Hamming ball of radius $r$ about a word $x$ is the set of words whose Hamming distance from $x$ is at most $r$.

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.

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