Perfect code

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. 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 Ref. [2], pg. 100, for more details.

Parent

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

Children

Cousin

  • 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]
W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: perfect

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

Cite as:

“Perfect code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/perfect

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/q-ary_digits/covering/perfect.yml.