Description
A type of \(q\)-ary code whose parameters satisfy the Hamming bound with equality.
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 [3–15].
Parents
- Completely regular code — Perfect codes and extended perfect codes are completely regular [16].
- Covering code — Perfect codes are covering codes with minimum number of codewords
Children
- Perfect binary code
- \(q\)-ary Hamming code
- Ternary Golay code — The ternary Golay code is perfect.
Cousins
- Combinatorial design — Perfect codes and combinatorial designs are related [17,18].
- Editing code — Perfect deletion correcting codes can be constructed using combinatorial design theory [19,20].
- Hexacode — The shortened hexacode is perfect [21; Exer. 578].
- Perfect quantum code — A classical (quantum) perfect code saturates the classical (quantum) Hamming bound.
References
- [1]
- K. Lindström, “All nearly perfect codes are known”, Information and Control 35, 40 (1977) DOI
- [2]
- V. D. Tonchev, "Codes and designs." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [3]
- 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
- [4]
- J. Schnheim, “On linear and nonlinear single-error-correcting q-nary perfect codes”, Information and Control 12, 23 (1968) DOI
- [5]
- Lindström, Bernt. "On group and nongroup perfect codes in q symbols." Mathematica Scandinavica 25.2 (1969): 149-158.
- [6]
- M. Mollard, “Une nouvelle famille de 3-codes parfaits sur GF(q)”, Discrete Mathematics 49, 209 (1984) DOI
- [7]
- 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
- [8]
- H. Bauer, B. Ganter, and F. Hergert, “Algebraic techniques for nonlinear codes”, Combinatorica 3, 21 (1983) DOI
- [9]
- 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.
- [10]
- 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.
- [11]
- 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
- [12]
- K. T. Phelps, “A Combinatorial Construction of Perfect Codes”, SIAM Journal on Algebraic Discrete Methods 4, 398 (1983) DOI
- [13]
- T. Etzion and A. Vardy, “Perfect binary codes: constructions, properties, and enumeration”, IEEE Transactions on Information Theory 40, 754 (1994) DOI
- [14]
- 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
- [15]
- 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
- [16]
- J. Borges, J. Rifà, and V. A. Zinoviev, “On Completely Regular Codes”, (2017) arXiv:1703.08684
- [17]
- E. F. Assmus, Jr. and H. F. Mattson, Jr., “Coding and Combinatorics”, SIAM Review 16, 349 (1974) DOI
- [18]
- K. T. Phelps, “Combinatorial designs and perfect codes”, Electronic Notes in Discrete Mathematics 10, 220 (2001) DOI
- [19]
- P. A. H. Bours, “On the construction of perfect deletion-correcting codes using design theory”, Designs, Codes and Cryptography 6, 5 (1995) DOI
- [20]
- A. Mahmoodi, Designs, Codes and Cryptography 14, 81 (1998) DOI
- [21]
- W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
Page edit log
- Victor V. Albert (2022-07-19) — most recent
- Mustafa Doger (2022-04-01)
- Victor V. Albert (2022-03-21)
- Victor V. Albert (2021-12-01)
Cite as:
“Perfect code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/perfect