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.
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.
An alphabet set
l{A}q
q
n
l{A}q
n | |
l{A} | |
q |
qn
q
n
n | |
l{A} | |
q |
l{A}q
q
l{A}q
q
Let
Aq(n,d)
q
C
n
d
qn>1
Then, the Hamming bound is:
Aq(n,d)\leq
qn | |||||||||
|
{k}(q-1)k}
where
t=\left\lfloor | d-1 |
2 |
\right\rfloor.
It follows from the definition of
d
t=\left\lfloor
1 | |
2 |
(d-1)\right\rfloor
t
For each codeword
c\inC
t
c
t
m
t
t
n
(q-1)
q
n | |
l{A} | |
q |
m= \begin{matrix}
t | |
\sum | |
k=0 |
\binom{n}{k}(q-1)k \end{matrix}.
Aq(n,d)
C
t
n | |
l{A} | |
q |
n| | |
|l{A} | |
q |
=qn
Aq(n,d) x m=Aq(n,d) x \begin{matrix}
t | |
\sum | |
k=0 |
\binom{n}{k}(q-1)k \end{matrix} \leqqn.
Whence:
Aq(n,d)\leq
qn | |
\begin{matrix |
t | |
\sum | |
k=0 |
\binom{n}{k}(q-1)k \end{matrix}}.
See main article: Delone set. For an
Aq(n,d)
n | |
l{A} | |
q |
n | |
l{A} | |
q |
From the proof of the Hamming bound, it can be seen that for
t=\left\lfloor | 1 |
2 |
(d-1)\right\rfloor
s ≤ t and t ≤ r.Therefore, s ≤ r and if equality holds then s = r = t. The case of equality means that the Hamming bound is attained.
Codes that attain the Hamming bound are called perfect codes. Examples include codes that have only one codeword, and codes that are the whole of
n | |
\scriptstylel{A} | |
q |
A perfect code may be interpreted as one in which the balls of Hamming radius t centered on codewords exactly fill out the space (t is the covering radius = packing radius). A quasi-perfect code is one in which the balls of Hamming radius t centered on codewords are disjoint and the balls of radius t+1 cover the space, possibly with some overlaps.[1] Another way to say this is that a code is quasi-perfect if its covering radius is one greater than its packing radius.
. Jessie MacWilliams . N.J.A. Sloane . Neil Sloane . The Theory of Error-Correcting Codes . North-Holland . 1977 . 0-444-85193-3 . registration .
. Vera Pless . Introduction to the Theory of Error-Correcting Codes. Introduction to the Theory of Error-Correcting Codes . John Wiley & Sons . 1982 . 0-471-08684-3 .
. Jack van Lint . Introduction to Coding Theory . 2nd . Springer-Verlag . . 86 . 1992 . 3-540-54894-7 . registration .