Hamming bound
Encyclopedia
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 which attains the Hamming bound is said to be a perfect code.
contains n letters. The original message (of length m) is shorter than n letters. The message is converted into an n-letter code word by an encoding algorithm, transmitted over a noisy channel
, and finally decoded by the receiver. The decoding process interprets a garbled code word as the valid code word "nearest" the n-letter received string.
Mathematically, there are exactly qm possible messages of length m, and each such 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 code words are possible, but any one of qn garbled code words can be received, because the noisy channel might distort one or more of the n letters while the code word is being transmitted.
denote the maximum possible size of a 
-ary block code 
of length 
and minimum Hamming distance
(a 
-ary block code of length 
is a subset of the strings of 
where the alphabet set 
has 
elements).
Then:
where
, if at most 
errors are made during transmission of a codeword then minimum distance decoding will decode it correctly (i.e., it decodes the received codeword as the codeword that was sent). Thus the code is said to be capable of correcting 
errors.
For a given codeword
, consider the ball
of radius
around 
. Each such ball (Hamming sphere) is non-intersecting by the t-error-correcting property, and each ball contains (in other words the volume of the ball) 
codewords. Since we may allow (or choose) up to 
of the 
components of a codeword to deviate (from the value of the corresponding component of the ball's centre
) to one of
possible other values (recall, the code is q-ary: it takes values in 
), we can define:
Let
be the total number of codewords in 
. Taking the union
of the balls over all codewords we observe that the resulting set of codewords is contained in
. Then since each ball is non-intersecting we may sum the number of elements in each to deduce:
Whence:
. These are often called trivial perfect codes.
In 1973, it was proved that any non-trivial perfect code over a prime-power alphabet has the parameters of a Hamming code
or a Golay code.
A perfect code may be interpreted as one in which the balls of Hamming radius t centred on codewords exactly fill out the space. A quasi-perfect code is one in which the balls of Hamming radius t centred on codewords are disjoint and the balls of radius t+1 cover the space, possibly with some overlaps.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, in the field of coding theory
Coding theory
Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...
, the Hamming bound is a limit on the parameters of an arbitrary block code
Block code
In coding theory, block codes refers to the large and important family of error-correcting codes that encode data in blocks.There is a vast number of examples for block codes, many of which have a wide range of practical applications...
: 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 which 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 wordCode word
In communication, a code word is an element of a standardized code or protocol. Each code word is assembled in accordance with the specific rules of the code and assigned a unique meaning...
contains n letters. The original message (of length m) is shorter than n letters. The message is converted into an n-letter code word by an encoding algorithm, transmitted over a noisy channel
Channel (communications)
In telecommunications and computer networking, a communication channel, or channel, refers either to a physical transmission medium such as a wire, or to a logical connection over a multiplexed medium such as a radio channel...
, and finally decoded by the receiver. The decoding process interprets a garbled code word as the valid code word "nearest" the n-letter received string.
Mathematically, there are exactly qm possible messages of length m, and each such message can be regarded as a vector
Coordinate vector
In linear algebra, a coordinate vector is an explicit representation of a vector in an abstract vector space as an ordered list of numbers or, equivalently, as an element of the coordinate space Fn....
of length m. The encoding scheme converts an m-dimensional vector into an n-dimensional vector. Exactly qm valid code words are possible, but any one of qn garbled code words can be received, because the noisy channel might distort one or more of the n letters while the code word is being transmitted.
Statement of the bound
Let denote the maximum possible size of a -ary block code of length and minimum Hamming distanceHamming distance
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different...
(a -ary block code of length is a subset of the strings of where the alphabet set has elements).Then:
where
Proof
By definition of, if at most errors are made during transmission of a codeword then minimum distance decoding will decode it correctly (i.e., it decodes the received codeword as the codeword that was sent). Thus the code is said to be capable of correcting errors.For a given codeword
, consider the ballBall (mathematics)
In mathematics, a ball is the space inside a sphere. It may be a closed ball or an open ball ....
of radius
around . Each such ball (Hamming sphere) is non-intersecting by the t-error-correcting property, and each ball contains (in other words the volume of the ball) codewords. Since we may allow (or choose) up to of the components of a codeword to deviate (from the value of the corresponding component of the ball's centreBall (mathematics)
In mathematics, a ball is the space inside a sphere. It may be a closed ball or an open ball ....
) to one of
possible other values (recall, the code is q-ary: it takes values in ), we can define:Let
be the total number of codewords in . Taking the unionUnion (set theory)
In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...
of the balls over all codewords we observe that the resulting set of codewords is contained in
. Then since each ball is non-intersecting we may sum the number of elements in each to deduce:Whence:
Perfect codes
Codes that attain the Hamming bound are called perfect codes. Examples include codes that have only one codeword, and codes that use the whole of. These are often called trivial perfect codes.In 1973, it was proved that any non-trivial perfect code over a prime-power alphabet has the parameters of a Hamming code
Hamming code
In telecommunication, Hamming codes are a family of linear error-correcting codes that generalize the Hamming-code invented by Richard Hamming in 1950. Hamming codes can detect up to two and correct up to one bit errors. By contrast, the simple parity code cannot correct errors, and can detect only...
or a Golay code.
A perfect code may be interpreted as one in which the balls of Hamming radius t centred on codewords exactly fill out the space. A quasi-perfect code is one in which the balls of Hamming radius t centred on codewords are disjoint and the balls of radius t+1 cover the space, possibly with some overlaps.
See also
- Griesmer boundGriesmer boundIn the mathematics of coding theory, the Griesmer bound, named after James Hugo Griesmer, is a bound on the length of binary codes of dimension k and minimum distance d.There is also a very similar version for non-binary codes....
- Singleton boundSingleton boundIn coding theory, the Singleton bound, named after Richard Collom Singleton, is a relatively crude bound on the size of a block code C with block length n, size r and minimum distance d.-Statement of the Bound:...
- Gilbert-Varshamov boundGilbert-Varshamov boundIn coding theory, the Gilbert–Varshamov bound is a bound on the parameters of a code . It is occasionally known as the Gilbert–Shannon–Varshamov bound , but the Gilbert–Varshamov bound is by far the most popular name...
- Plotkin boundPlotkin boundIn the mathematics of coding theory, the Plotkin bound, named after Morris Plotkin, is a bound on the maximum possible number of codewords in binary codes of given length n and given minimum distance d.- Statement of the bound :...
- Johnson bound