TOPICS
Search

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_(i=0)^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_(i=0)^e(n; i)=2^(n-k).

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


See also

Error-Correcting Code, Golay Code, Hamming Code, Nearly Perfect Code

This entry contributed by David Terr

Explore with Wolfram|Alpha

References

MacWilliams, F. J. and Sloane, N. J. A. The Theory of Error-Correcting Codes. Amsterdam, Netherlands: North-Holland, 1977.Roman, S. Coding and Information Theory. New York: Springer-Verlag, 1992.van Lint, J. H. An Introduction to Coding Theory, 2nd ed. New York: Springer-Verlag, 1992.

Referenced on Wolfram|Alpha

Perfect Code

Cite this as:

Terr, David. "Perfect Code." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/PerfectCode.html

Subject classifications