Perfect binary code

Description

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 [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.

Parents

  • Nearly perfect code — Perfect binary codes are nearly perfect, and \(t+1\) divides \(n-t\) for such codes. In addition, any perfect code can be extended to a nearly perfect code.
  • Perfect code

Children

Cousins

References

[1]
K. Lindström, “All nearly perfect codes are known”, Information and Control 35, 40 (1977) DOI
[2]
H. Bombin and M. A. Martin-Delgado, “Homological error correction: Classical and quantum codes”, Journal of Mathematical Physics 48, 052105 (2007) arXiv:quant-ph/0605094 DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: perfect_binary

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

Cite as:

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

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/bits/covering/perfect_binary.yml.