Nearly perfect code[1,2] 

Description

An \((n,K,2t+1)\) binary code is nearly perfect if parameters \(n\), \(K\), and \(t\) are such that the Johnson bound \begin{align} \frac{{n \choose t}\left(\frac{n-t}{t+1}-\left\lfloor \frac{n-t}{t+1}\right\rfloor \right)}{\left\lfloor \frac{n}{t+1}\right\rfloor }+\sum_{j=0}^{t}{n \choose j}\leq2^{n}/K \tag*{(1)}\end{align} becomes an equality ([3], Sec. 2.3.5; see also Ref. [4], Ch. 17). All nearly perfect binary codes are either perfect, or correspond to either Preparata codes or one of the \((2^{2^r-2-r},2^r-2,3)\) codes for \(r\geq 3\) [5].

Similar definitions can be made for \(q\)-ary codes, but all nearly perfect \(q\)-ary codes must be perfect [6,7].

Parents

Children

  • Perfect binary 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.
  • Repetition code
  • Preparata code — Preparata codes are uniformly packed and nearly perfect [1]. For any word \(u\) and Preparata codebook \(C\) with \(d(u, C) > 2\), we have that \(u\) has a distance 2 or 3 to exactly \(\left\lfloor (2^{m+1}-1)/3\right\rfloor\) codewords.
  • Single parity-check (SPC) code

Cousins

References

[1]
J. M. Goethals and S. L. Snover, “Nearly perfect binary codes”, Discrete Mathematics 3, 65 (1972) DOI
[2]
N. V. Semakov, V. A. Zinov'ev, G. V. Zaitsev, “Uniformly Packed Codes”, Probl. Peredachi Inf., 7:1 (1971), 38–50; Problems Inform. Transmission, 7:1 (1971), 30–39
[3]
W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
[4]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[5]
Kauko Lindström. "The nonexistence of unknown nearly perfect binary codes." PhD diss., Turun yliopisto, 1975.
[6]
K. Lindstrom and M. J. Aaltonen, "The nonexistence of nearly perfect nonbinary codes for 1 =< e =< 10", Ann. Univ. Turku, Ser. A I, No. 172, 1976.
[7]
K. Lindström, “All nearly perfect codes are known”, Information and Control 35, 40 (1977) DOI
Page edit log

Your contribution is welcome!

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

edit on this site

Zoo Code ID: nearly_perfect

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

Cite as:

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

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/covering/nearly_perfect.yml.