Hamming bound

A perfect code, or densely packed code designated in coding theory a block code in which each word only to exactly one code word has a minimum Hamming distance.

Maximum- likelihood decoding being employed usually this means that each received word is a code word can be clearly assigned. Hence the name is derived from perfect, because there are no ambiguous decoding options.

Mathematical Description

Be a block code with, where is the alphabet used. have a Hamming distance of. It can thus

Correct errors.

Needs to be perfect, the minimum Hamming distance between two words of a code be odd, since it is otherwise a word with what is contrary to the definition of a perfect code.

Since the code is error correcting, a word can be assigned a code word clearly, if the Hamming distance is. Conversely, this means for a given codeword sure all words are decoded x with a Hamming distance of at most after. This is written as a set:

This amount is (sometimes hypercube ) also referred to as a ball with radius. The number of elements is:

For flaws there from possible positions for the error. Here are per fault incorrect icons available. There are balls. These are disjoint subsets of. Hence the inequality

Solving for and with the following:

This inequality for the number of code words is called Hamming barrier or barrier -packing.

In a perfect code all the words contained in exactly one of the balls (in other words: The balls cover the room). Why then applies the equality of Hammingschranke for this code.

Alternative interpretation

This limit one can also illustrate as follows ( for simplicity explained only on the basis of binary codes, that is for ):

For an error-correcting code, the decoder must receive enough information to distinguish all of the following cases can:

• Different information words and each
• All possible patterns of bit errors of the bits of a codeword

Since there are ways to distribute bit error bits, resulting in total

Cases that need to be distinguished with the bits available, that

In a perfect code equality holds, that is, the bits wear exactly the information required minimum. This (in) equation corresponding to the above general definition for the case and.

While it is actually only interested in the correction of the information, what would satisfy correspondingly less additional information - these bits additional information would have to be error free but, of course, what usually can not be guaranteed. Therefore, correction of all bits is required.

Known Perfect Codes

If the alphabet size q is a prime power, then: If C is a perfect code with parameters, so there is a code D with the same parameters, so that D is one of the following codes:

• A trivial code. A code is here trivial if it either contains only a single code word, or if it contains all possible words in the given block length.
• A binary repetition code of odd code word length. The parameters are for a.
• A Hamming code over the finite field, with parameters
• The binary Golay code with parameters
• The ternary Golay code with parameters with

The codes and have the same parameters and can thus n with the same block length equal to correct many errors. The conversion of a trivial code into a linear code with the same parameters is simple: If the code comprises a single code word, it may instead be the zero vector are used as the only code word, and the resultant code is linear. The only remaining trivial code is one that contains all possible words in the given block length. But this is already linear. The rest of the code from the list already are linear codes. There are so perfect for each code that is not a linear code in general, a linear code with the same parameters - if the size of the alphabet is a prime power.

It is an open question whether, and for which parameters there are not trivial perfect codes, if the alphabet size is not a prime power.

For practical purposes, the codes are trivial uninteresting since either no information can be transmitted or not errors can be corrected.