Perfect code

Description

An \((n,K,2t+1)_q\) \(q\)-ary 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 \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}\). Any perfect linear code is either a repetition code, a Hamming code, or a binary or ternary Golay code.

Perfect codes are those for which balls of Hamming radius \(t\) exactly fill the space of all \(n\) \(q\)-ary strings. Quasi-perfect codes are those for which balls of Hamming radius \(t\) are disjoint, while balls of radius \(t+1\) cover the space with possible overlaps.

For binary 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), \end{align} where \(h\) is the binary entropy function.

Parent

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

Children

Cousins

  • Binary repetition code — Repetition codes for odd \(n\) are perfect.
  • Graph homology code — A family of homology codes saturate the asymptotic Hamming bound [1].
  • Perfect quantum code — A classical (quantum) perfect code saturates the classical (quantum) Hamming bound.
  • Zetterberg code — Zetterberg codes are quasi-perfect, with each \(n\)-bit string at most three bit-flips away from a codeword [2].

Zoo code information

Internal code ID: perfect

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} }
Permanent link:
https://errorcorrectionzoo.org/c/perfect

References

[1]
H. Bombin and M. A. Martin-Delgado, “Homological error correction: Classical and quantum codes”, Journal of Mathematical Physics 48, 052105 (2007). DOI; quant-ph/0605094
[2]
S. M. Dodunekov and J. E. M. Nilsson, “Algebraic decoding of the Zetterberg codes”, IEEE Transactions on Information Theory 38, 1570 (1992). DOI

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/properties/perfect.yml.