Description
A type of binary code whose parameters satisfy the Hamming bound with equality.
An \((n,K,2t+1)\) binary code is perfect if parameters \(n\), \(K\), and \(t\) are such that the binary Hamming (a.k.a. sphere-packing) bound \begin{align} \sum_{j=0}^{t} {n \choose j} \leq 2^{n}/K \tag*{(1)}\end{align} becomes an equality. For example, for a 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\) binary strings.
Any perfect linear binary code is either a binary repetition code, a binary Hamming code, or the binary Golay code [2][1; Thm. 3.3.1].
For codes with \(K=2^k\), one can work out an asymptotic Hamming bound in the large-\(n,k,t\) limit, \begin{align} \frac{k}{n}\leq 1-h(t/n), \tag*{(2)}\end{align} where \(h\) is the binary entropy function.
There are many inequivalent nonlinear perfect binary codes [3–7]; for example, there are 5983 inequivalent perfect distance-three codes of length 15 [8]. Nonlinear perfect codes can have arbitrary finite groups as their automorphism groups [9], including the trivial group [10,11]. The automorphism group of a distance-three perfect binary code is no greater than the automorphism of the Hamming code of the same length [12–15].
Cousins
- Combinatorial design— If a perfect binary code contains the zero vector, then its minimum-weight codewords support a Steiner \((t+1)\)-\((n,2t+1,1)\) design, while the minimum-weight codewords in the extended code support a Steiner \((t+2)\)-\((n+1,2t+2,1)\) design [16; Thm. 5.3.1(b)].
- Cycle code— A family of cycle codes saturate the asymptotic Hamming bound [17].
- Repetition code— Repetition codes are trivially perfect for odd \(n\) [18; Def. 12.3.4][19; pg. 180].
Primary Hierarchy
References
- [1]
- P. R. J. Östergård, “Construction and Classification of Codes.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [2]
- K. Lindström, “All nearly perfect codes are known”, Information and Control 35, 40 (1977) DOI
- [3]
- J. L. Vasilyev, “On nongroup close-packed codes” (in Russian), Problemy Kibernetiki, 8 (1962), 337-339, translated in Probleme der Kibernetik 8 (1965), 375-378.
- [4]
- D. S. Krotov, “Lower bounds for the number of m-quasigroups of order four and of the number of perfect binary codes”, Diskretnyi Analiz i Issledovanie Operatsii, Ser. 1, 7:2 (2000), 47–53.
- [5]
- K. T. Phelps, “A Combinatorial Construction of Perfect Codes”, SIAM Journal on Algebraic Discrete Methods 4, 398 (1983) DOI
- [6]
- T. Etzion and A. Vardy, “Perfect binary codes: constructions, properties, and enumeration”, IEEE Transactions on Information Theory 40, 754 (1994) DOI
- [7]
- 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
- [8]
- 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
- [9]
- K. T. Phelps, “Every finite group is the automorphism group of some perfect code”, Journal of Combinatorial Theory, Series A 43, 45 (1986) DOI
- [10]
- S. V. Avgustinovich and F. I. Solov’eva, “Perfect binary codes with trivial automorphism group”, 1998 Information Theory Workshop (Cat. No.98EX131) 114 DOI
- [11]
- O. Heden, F. Pasticci, and T. Westerbäck, “On the symmetry group of extended perfect binary codes of length \(n+1\) and rank \(n-\log(n+1)+2\)”, Advances in Mathematics of Communications 6, 121 (2012) DOI
- [12]
- F. I. Solov’eva and S. T. Topalova, “On Automorphism Groups of Perfect Binary Codes and Steiner Triple Systems”, Problemy Peredachi Informatsii, 36:4 (2000), 53–58; Problems of Information Transmission, 36:4 (2000), 331–335.
- [13]
- F. I. Solov’eva and S. T. Topalova, “Perfect binary codes and Steiner triple systems with maximum orders of automorphism groups”, Diskretnyi Analiz i Issledovanie Operatsii, Ser. 1, 7:4 (2000), 101–110.
- [14]
- S. A. Malyugin, “On the order of the automorphism group of perfect binary codes”, Diskretnyi Analiz i Issledovanie Operatsii, Ser. 1, 7:4 (2000), 91–100.
- [15]
- O. Heden, “On the size of the symmetry group of a perfect code”, Discrete Mathematics 311, 1879 (2011) DOI
- [16]
- V. D. Tonchev, “Codes and designs.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [17]
- H. Bombin and M. A. Martin-Delgado, “Homological error correction: Classical and quantum codes”, Journal of Mathematical Physics 48, (2007) arXiv:quant-ph/0605094 DOI
- [18]
- P. Boyvalenkov, D. Danev, “Linear programming bounds.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [19]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [20]
- P. Delsarte, “Four fundamental parameters of a code and their combinatorial significance”, Information and Control 23, 407 (1973) DOI
- [21]
- P. R. J. Ostergard, O. Pottonen, and K. T. Phelps, “The Perfect Binary One-Error-Correcting Codes of Length 15: Part II—Properties”, IEEE Transactions on Information Theory 56, 2571 (2010) arXiv:0903.2749 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 binary code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/perfect_binary