[Jump to code hierarchy]

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\).

Cousins

Member of code lists

Primary Hierarchy

Classical Domain
Galois-field Kingdom
\(q\)-ary codeECC
Completely regular code
Uniformly packed code
Parents
Uniformly packed code
Quasi-perfect codes are uniformly packed [4; Def. 2.5].
Weighted-covering codeECC
A quasi-perfect code is a special case of an \(m\)-weighted covering code with \(m\)-covering radius \(r=t+1\) [5; Ch. 13].
Quasi-perfect code
Children
Nearly perfect codePerfect binary
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 [6].

References

[1]
D. Gorenstein, W. W. Peterson, and N. Zierler, “Two-error correcting Bose-Chaudhuri codes are quasi-perfect”, Information and Control 3, 291 (1960) DOI
[2]
T. Helleseth, “No primitive binaryt-error-correcting BCH code witht > 2is quasi-perfect (Corresp.)”, IEEE Transactions on Information Theory 25, 361 (1979) DOI
[3]
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (Elsevier, 1977)
[4]
J. Borges, J. Rifà, and V. A. Zinoviev, “On Completely Regular Codes”, (2017) arXiv:1703.08684
[5]
G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein, Covering Codes (Elsevier, 1997)
[6]
S. M. Dodunekov and J. E. M. Nilsson, “Algebraic decoding of the Zetterberg codes”, IEEE Transactions on Information Theory 38, 1570 (1992) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

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 | Mastodon |  | 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/edit/main/codes/classical/q-ary_digits/packing/quasi_perfect.yml.