Hamming Sphere-Packing Bound

The Hamming Sphere-Packing Bound provides a fundamental limitation on the parameters of an error-correcting code. It states that the total volume of non-overlapping Hamming spheres around each codeword must not exceed the total volume of the ambient space.

Worked Example

Consider a binary code with length n = 7 correcting up to t = 1 errors, such as the Hamming(7,4) code.

The volume of one Hamming sphere of radius 1 is V = 1 + 7 = 8.
For M = 16 codewords, the used sphere budget is 16 × 8 = 128.
The binary space size is 2⁷ = 128.
The budget slack is 128 - 128 = 0, meaning it perfectly packs the space. The code is "Not ruled out".

Experiment

In the Hamming Sphere-Packing Bound module, you can adjust the parameters:

Select Bits n to change the space dimensionality.
Select Errors t to change the radius of the Hamming balls.
Select Codewords M to see if that many non-overlapping spheres can fit in the space.

Observe the "Verdict" output. When the "Used sphere budget" exceeds the "Binary space size", the slack becomes negative, and such a code is "Ruled out".

Limitations

Passing the Hamming bound is a necessary condition, but not sufficient. A result of "Not ruled out" does not prove that a code with those parameters actually exists. Additionally, the bound assumes all spheres are completely disjoint, which is required for guaranteed error correction, but not for probabilistic decoding.

References

Tonchev, V. D. "Coding Theory". https://pages.mtu.edu/~tonchev/Coding-Theory-Tohoku-June-09.pdf.

Hamming Sphere-Packing Bound