Hamming bound

The Hamming bound limits the size of a code with a given minimum distance by requiring that equal-radius Hamming balls around its codewords be disjoint within the ambient space.

Hamming distance: The number of coordinate positions in which two words of equal length differ. Minimum distance determines the radius of the disjoint balls used in the bound.
Error-correcting code: A set of words designed so that transmitted messages can be recovered despite a limited number of errors. The Hamming bound limits the number of codewords such a set can contain.
Binary code: A code whose words are sequences over the two-symbol alphabet, usually represented by 0 and 1. For binary codes, the bound uses Hamming-ball volumes from binomial sums.
Richard Hamming: An American mathematician and engineer whose work established foundational methods in coding theory. His 1950 paper introduced codes that correct errors and the bound now bearing his name.
Hamming ball: The set of words at Hamming distance at most a specified radius from a center word. The bound counts these balls around codewords and compares their total size with the whole space.
Minimum distance: The smallest Hamming distance between any two distinct codewords in a code. It fixes the largest number of errors that the code can uniquely correct.
Linear code: A code that forms a vector subspace over a finite field. The bound supplies a general size limit against which linear-code constructions are compared.
Error detection and correction: Methods that identify or recover corrupted data by adding structured redundancy. The Hamming bound formalizes a fundamental limit on correction within this broader problem.
Sphere-packing bound: An upper bound on how many nonoverlapping equal-radius spheres can fit in a given space. This general packing principle is the geometric idea behind the Hamming bound.
Finite field: A field with finitely many elements, commonly used as the alphabet for algebraic codes. The alphabet size sets the number of words in the ambient space being packed.

Linked from 1 page