In mathematics and computer science, in the field of coding theory, the Hamming bound is a limit on the parameters of an arbitrary block code: it is also known as the sphere-packing bound or the volume bound from an interpretation in terms of packing balls in the Hamming metric into the space of all possible words. It gives an important limitation on the efficiency with which any error-correcting code can utilize the space in which its code words are embedded. A code that attains the Hamming bound is said to be a perfect code.
Background on error-correcting codes An original message and an encoded version are both composed in an alphabet of q letters. Each code word contains n letters. The original message (of length m) is shorter than n letters. The message is converted into an n-letter codeword by an encoding algorithm, transmitted over a noisy channel, and finally decoded by the receiver. The decoding process interprets a garbled codeword, referred to as simply a word, as the valid codeword "nearest" the n-letter received string. Mathematically, there are exactly qm possible messages of length m, and each message can be regarded as a vector of length m. The encoding scheme converts an m-dimensional vector into an n-dimensional vector. Exactly qm valid codewords are possible, but any one of qn words can be received because the noisy channel might distort one or more of the n letters when a codeword is transmitted.
Statement of the bound
Preliminary definitions An alphabet set A q {\displaystyle {\mathcal {A}}_{q}} is a set of symbols with q {\displaystyle q} elements. The set of strings of length n {\displaystyle n} on the alphabet set A q {\displaystyle {\mathcal {A}}_{q}} are denoted A q n {\displaystyle {\mathcal {A}}_{q}^{n}} . (There are q n {\displaystyle q^{n}} distinct strings in this set of strings.) A q {\displaystyle q} -ary block code of length n {\displaystyle n} is a subset of the strings of A q n {\displaystyle {\mathcal {A}}_{q}^{n}} , where the alphabet set A q {\displaystyle {\mathcal {A}}_{q}} is any alphabet set having q {\displaystyle q} elements. (The choice of alphabet set A q {\displaystyle {\mathcal {A}}_{q}} makes no difference to the result, provided the alphabet is of size q {\displaystyle q} .)
Defining the bound Let A q ( n , d ) {\displaystyle \ A_{q}(n,d)} denote the maximum possible size of a q {\displaystyle q} -ary block code C {\displaystyle \ C} of length n {\displaystyle n} and minimum Hamming distance d {\displaystyle d} between elements of the block code (necessarily positive for q n > 1 {\displaystyle q^{n}>1} ). Then, the Hamming bound is:
A q ( n , d ) ≤ q n ∑ k = 0 t ( n k ) ( q − 1 ) k {\displaystyle \ A_{q}(n,d)\leq {\frac {q^{n}}{\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}}}}
where
t = ⌊ d − 1 2 ⌋ . {\displaystyle t=\left\lfloor {\frac {d-1}{2}}\right\rfloor .}
Proof It follows from the definition of d {\displaystyle d} that if at most
t = ⌊ 1 2 ( d − 1 ) ⌋ {\displaystyle t=\left\lfloor {\frac {1}{2}}(d-1)\right\rfloor }
… excerpt ends here. Continue reading the full article.
