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\).
Parents
- Uniformly packed code — Quasi-perfect codes are uniformly packed [1; Def. 2.5].
- 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\) ([2], Ch. 13).
Children
- Nearly perfect code — Nearly perfect codes are quasi-perfect [3; pg. 533].
- Zetterberg code — Zetterberg codes are quasi-perfect, with each \(n\)-bit string at most three bit-flips away from a codeword [4].
Cousins
- Binary BCH code — Only double error-correcting BCH codes \([2^m-1,n-2m,5]\) are quasi-perfect [5,6] (see also Ref. [3], Ch. 9).
- Preparata code — Punctured Preparata codes are quasi-perfect [3; pg. 475].
References
- [1]
- J. Borges, J. Rifà, and V. A. Zinoviev, “On Completely Regular Codes”, (2017) arXiv:1703.08684
- [2]
- G. Cohen, I. Honkala, S. Litsyn, A. Lobstein, Covering codes. Elsevier, 1997.
- [3]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [4]
- S. M. Dodunekov and J. E. M. Nilsson, “Algebraic decoding of the Zetterberg codes”, IEEE Transactions on Information Theory 38, 1570 (1992) DOI
- [5]
- D. Gorenstein, W. W. Peterson, and N. Zierler, “Two-error correcting Bose-Chaudhuri codes are quasi-perfect”, Information and Control 3, 291 (1960) DOI
- [6]
- 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
Page edit log
- Victor V. Albert (2022-07-19) — most recent
Cite as:
“Quasi-perfect code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/quasi_perfect