Description
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.
Parent
- 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 code — Perfect codes and combinatorial designs are related [3].
- Hexacode — The shortened hexacode is perfect [4; 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]
- E. F. Assmus, Jr. and H. F. Mattson, Jr., “Coding and Combinatorics”, SIAM Review 16, 349 (1974) DOI
- [4]
- 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