Perfect code

Encyclopedia : P : PE : PER : Perfect code

Let C be an error-correcting code consisting of N codewords,in which each codeword consists of n letters taken from an alphabet A of length q, and every two distinct codewords differ in at least [d=2e+1] places. Then C is said to be perfect if for every possible word w_0 of length n with letters in A, there is a unique code word w in C in which at most e letters of w differ from the corresponding letters of [w_0].

It is straightforward to show that C is perfect if

[\sum_^e(n; i)(q-1)^i=(q^n)/N].

If C is a binary linear code, then q==2 and N==2^k, where k is the number of generators of C, in which case C is perfect if

[\sum_^e(n; i)=2^(n-k)].

Hamming codes and the Golay code are examples of perfect codes.

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.