Open main menu

Wikipedia β

Hamming bound

  (Redirected from Perfect code)

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.

Contents

Background on error-correcting codesEdit

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 garbled codewords (words) can be received, because the noisy channel might distort one or more of the n letters while the codeword is being transmitted.

Statement of the boundEdit

Let   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, the Hamming bound is:

 

where

 

ProofEdit

It follows from the definition of   that 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 word as the codeword that was sent). Thus the code is said to be capable of correcting   errors.

For each codeword  , consider a ball of fixed radius   around  . Every pair of these balls (Hamming spheres) are non-intersecting by the  -error-correcting property. Let   be the number of words in each ball (in other words, the volume of the ball). A word that is in such a ball can deviate in at most   components from those of the ball's centre, which is a codeword. The number of such words is then obtained by choosing up to   of the   components of a codeword to deviate to one of   possible other values (recall, the code is  -ary: it takes values in  ). Thus,

 

  is the (maximum) total number of codewords in  , and so, by the definition of  , the greatest number of balls with no two balls having a word in common. Taking the union of the words in these balls centered at codewords, results in a set of words, each counted precisely once, that is a subset of   (where   words) and so:

 

Whence:

 

Covering radius and packing radiusEdit

For an   code C (a subset of  ), the covering radius of C is the smallest value of r such that every element of   is contained in at least one ball of radius r centered at each codeword of C. The packing radius of C is the largest value of s such that the set of balls of radius s centered at each codeword of C are mutually disjoint.

From the proof of the Hamming bound, it can be seen that for  , we have:

st and tr.

Therefore, sr and if equality holds then s = r = t. The case of equality means that the Hamming bound is attained.

Perfect codesEdit

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  . Another example is given by the repeat codes, where each symbol of the message is repeated an odd fixed number of times to obtain a codeword where q = 2. All of these examples are often called the 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.[1]

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.[2] Another way to say this is that a code is quasi-perfect if its covering radius is one greater than its packing radius.[3]

See alsoEdit

NotesEdit

  1. ^ Hill (1988) p. 102
  2. ^ McWilliams and Sloane, p. 19
  3. ^ Roman 1992, pg. 140

ReferencesEdit