Perfect code 


An \((n,K,2t+1)_q\) code is perfect if parameters \(n\), \(K\), \(t\), and \(q\) are such that the Hamming (a.k.a. sphere-packing) bound \begin{align} \sum_{j=0}^{t}(q-1)^{j}{n \choose j}\leq q^{n}/K \tag*{(1)}\end{align} becomes an equality. In other words, the code's packing radius matches its covering radius.

For example, for a binary \(q=2\) code with one logical bit (\(K=2\)) and \(t=1\), the bound becomes \(n+1 \leq 2^{n-1}\). Perfect codes are those for which balls of Hamming radius \(t\) exactly fill the space of all \(n\) \(q\)-ary strings.

Any perfect linear code is either a repetition code, a Hamming code, or a binary or ternary Golay code [1]. If \(q\) is a prime power, any distance-three code is either a Hamming code or a nonlinear code with the same parameters; see [2; pg. 100] for more details. There are many nonlinear perfect codes [315].


  • Covering code — Perfect codes are covering codes with minimum number of codewords




K. Lindström, “All nearly perfect codes are known”, Information and Control 35, 40 (1977) DOI
V. D. Tonchev, "Codes and designs." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
H. S. Shapiro and D. L. Slotnick, “On the Mathematical Theory of Error-Correcting Codes”, IBM Journal of Research and Development 3, 25 (1959) DOI
J. Schnheim, “On linear and nonlinear single-error-correcting q-nary perfect codes”, Information and Control 12, 23 (1968) DOI
Lindström, Bernt. "On group and nongroup perfect codes in q symbols." Mathematica Scandinavica 25.2 (1969): 149-158.
M. Mollard, “Une nouvelle famille de 3-codes parfaits sur GF(q)”, Discrete Mathematics 49, 209 (1984) DOI
M. Mollard, “A Generalized Parity Function and Its Use in the Construction of Perfect Codes”, SIAM Journal on Algebraic Discrete Methods 7, 113 (1986) DOI
H. Bauer, B. Ganter, and F. Hergert, “Algebraic techniques for nonlinear codes”, Combinatorica 3, 21 (1983) DOI
Laborde, J. M., & SCHÜTZENBERGER, M. (1983). Une nouvelle famille de codes binaires, parfaits, non linéaires. Comptes rendus des séances de l'Académie des sciences. Série 1, Mathématique, 297(1), 67-70.
J. L. Vasilyev On nongroup close-packed codes (in Russian), Probl. Kibernet., 8 (1962), 337-339, translated in Probleme der Kibernetik 8 (1965), 375-378.
D. S. Krotov, “Lower bounds for the number of m-quasigroups of order four and of the number of perfect binary codes”, Diskretn. Anal. Issled. Oper., Ser. 1, 7:2 (2000), 47–53
K. T. Phelps, “A Combinatorial Construction of Perfect Codes”, SIAM Journal on Algebraic Discrete Methods 4, 398 (1983) DOI
T. Etzion and A. Vardy, “Perfect binary codes: constructions, properties, and enumeration”, IEEE Transactions on Information Theory 40, 754 (1994) DOI
D. S. Krotov and S. V. Avgustinovich, “On the Number of \(1\)-Perfect Binary Codes: A Lower Bound”, IEEE Transactions on Information Theory 54, 1760 (2008) arXiv:math/0608278 DOI
P. Ostergard and O. Pottonen, “The Perfect Binary One-Error-Correcting Codes of Length <formula formulatype="inline"><tex Notation="TeX">\(15\)</tex></formula>: Part I—Classification”, IEEE Transactions on Information Theory 55, 4657 (2009) arXiv:0806.2513 DOI
E. F. Assmus, Jr. and H. F. Mattson, Jr., “Coding and Combinatorics”, SIAM Review 16, 349 (1974) DOI
K. T. Phelps, “Combinatorial designs and perfect codes”, Electronic Notes in Discrete Mathematics 10, 220 (2001) DOI
W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
Page edit log

Your contribution is welcome!

on (edit & pull request)— see instructions

edit on this site

Zoo Code ID: perfect

Cite as:
“Perfect code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022.
@incollection{eczoo_perfect, title={Perfect code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:

Cite as:

“Perfect code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022.