##  [Hamming Bound](/hamming-bound-0) 

 Definition

For a q-ary block code of length n with minimum Hamming distance d and unique-decoding radius t = floor((d-1)/2), the Hamming bound (sphere-packing bound in Hamming metric) states that the number of codewords M satisfies M · V_q(n,t) ≤ q^n, where V_q(n,t)=∑_{i=0}^t binom(n,i)(q-1)^i is the volume of a Hamming sphere of radius t. It follows from the requirement that Hamming spheres of radius t around distinct codewords be disjoint for guaranteed unique decoding up to t errors.

 

 

 

 

 

 





## Principle

Principle

Counting (disjoint) decoding spheres in the Hamming metric yields an upper bound on code size: disjointness required for guaranteed unique decoding implies that the total volume covered by spheres cannot exceed the space size q^n.

 

 

 

 

 





## Demonstration

Demonstration

Illustrative scenario → Binary (q=2) block codes of length n with minimum distance d=3 imply t=1. Each codeword excludes its Hamming neighbors at distance ≤1; since each Hamming sphere contains 1+n vectors, M(1+n) ≤ 2^n, which constrains maximum M and shows that certain large code sizes are impossible under unique decoding up to one error.

 

 

 

 

## Misapplication

Misapplication

Applying the Hamming bound to list decoding or to codes that allow decoding beyond t (e.g., employing soft decisions or side information) is erroneous; the bound presumes unique decoding within radius t and disjoint decoding spheres.

 

 

 

 

 





## Consequence

Consequence

Provides an explicit combinatorial upper limit on achievable code size for given n and d; used to rule out parameter triples (n, M, d) and to identify when perfect codes (equality case) can exist or must be impossible.

 

 

 

 

## Reversal

Reversal

The bound is not applicable to decoding strategies that permit overlap (list decoding) or to channels where symbol errors are not well modeled by Hamming distance; furthermore, tightness holds only for exceptional 'perfect' codes—usually the bound is loose for many parameter regimes.

 

 

 

 

 





## Boundary

Boundary

Clearly within → block codes over finite alphabets under Hamming metric with requirement of unique decoding up to t errors. Boundary case → codes with same minimum distance but using probabilistic decoders where average error rates rather than guaranteed error-free decoding matter. Clearly outside → codes evaluated under different metrics (e.g., Euclidean for real-valued channels) or settings with soft information.

 

 

 

 

 





## Semantic Tension

Semantic Tension

Hamming upper bound ↔ Gilbert–Varshamov lower bound: counting-based upper limits compete with greedy-existence lower bounds, producing a feasible interval for M; tension appears in determining how tight either bound is for finite n.

 

 

 

 

 





## Synthesis

Synthesis

The Hamming bound is a simple combinatorial impossibility statement: to guarantee unique correction of up to t errors every codeword must exclude a Hamming sphere of radius t, and those spheres cannot overlap. It yields hard upper limits on code size and highlights when only special parameter sets (perfect codes) saturate the bound.