# 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

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