Quasi-perfect code

Description

Perfect codes \((n,K,d)_q\) are those for which balls of Hamming radius \(t=\left\lfloor (d-1)/2\right\rfloor\) 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. In other words, any \(q\)-ary string is at most \(t+1\) bit flips away from a codeword of a quasi-perfect code.

Protection

Correct errors of weight \(t\) as well as some errors of weight \(t+1\).

Parent

  • Weighed-covering code — A quasi-perfect code is an \(m\)-weighed covering code for \(r=t+1\), \(m_0=m_1=\cdots=m_{t+1}=1\), and \(m_t=m_{t+1}=1/\left\lfloor (n+1)(t+1) \right\rfloor\) ([1], Ch. 13).

Children

  • Nearly perfect code — Nearly perfect codes are quasi-perfect ([2], pg. 533).
  • Zetterberg code — Zetterberg codes are quasi-perfect, with each \(n\)-bit string at most three bit-flips away from a codeword [3].

Cousin

  • Binary BCH code — Only double error-correcting BCH codes \([2^m-1,n-2m,5]\) are quasi-perfect [4][5] (see also Ref. [2], Ch. 9).

References

[1]
G. Cohen, I. Honkala, S. Litsyn, A. Lobstein, Covering codes. Elsevier, 1997.
[2]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[3]
S. M. Dodunekov and J. E. M. Nilsson, “Algebraic decoding of the Zetterberg codes”, IEEE Transactions on Information Theory 38, 1570 (1992). DOI
[4]
D. Gorenstein, W. W. Peterson, and N. Zierler, “Two-error correcting Bose-Chaudhuri codes are quasi-perfect”, Information and Control 3, 291 (1960). DOI
[5]
T. Helleseth, “No primitive binary<tex>t</tex>-error-correcting BCH code with<tex>t > 2</tex>is quasi-perfect (Corresp.)”, IEEE Transactions on Information Theory 25, 361 (1979). DOI

Zoo code information

Internal code ID: quasi_perfect

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: quasi_perfect

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

Cite as:

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

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/properties/covering/quasi_perfect.yml.