Sphere-packing bound

The sphere-packing bound (also known as the Hamming bound) is a fundamental limit on the size of an error-correcting code. It states that for a code of length n over an alphabet of size q that can correct up to t errors, the total number of codewords cannot exceed q^n divided by the volume of a Hamming sphere of radius t. The bound arises from the simple geometric constraint that the spheres of radius t around each codeword must be disjoint — if they overlapped, a received word falling in the overlap could not be unambiguously decoded. The bound is tight for perfect codes such as the Hamming codes and the Golay code, but for most parameters the best known codes fall well below it, leaving a gap that is one of the persistent mysteries of discrete mathematics. The sphere-packing bound is the geometric counterpart to the algebraic Singleton bound and the probabilistic Gilbert-Varshamov bound, and the relationship between these three limits defines the practical frontier of coding theory.