Description
A binary code whose parameters satisfy the Johnson bound with equality.
An \((n,K,2t+1)\) binary code is nearly perfect if parameters \(n\), \(K\), and \(t\) are such that the Johnson bound [1], \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 ([4], Sec. 2.3.5; see also Ref. [5], Ch. 17). All nearly perfect binary codes are either perfect, or correspond to either shortened Preparata codes or one of the \((2^{2^r-2-r},2^r-2,3)\) codes for \(r\geq 3\) [6].
Similar definitions can be made for \(q\)-ary codes, but all nearly perfect \(q\)-ary codes must be perfect [7,8].
Cousins
- Combinatorial design— The minimum-weight codewords in a nearly perfect code containing the zero vector support a \(t\)-\((n,2t+1,\lfloor (n-t)/(t+1) \rfloor)\) design, while the minimum-weight codewords in the extended code support a \((t+1)\)-\((n+1,2t+2,\lfloor (n-t)/(t+1) \rfloor)\) design [9; Thm. 5.5.4].
- Preparata code— Shortened Preparata codes are uniformly packed and nearly perfect [2]. For any word \(u\) and shortened Preparata codebook \(C\) with \(d(u, C) > 2\), we have that \(u\) has distance 2 or 3 to exactly \(\left\lfloor (2^{m+1}-1)/3\right\rfloor\) codewords.
- Nordstrom-Robinson (NR) code— The punctured \((15,256,5)\) NR code saturates the Johnson bound and is therefore nearly perfect [9; Exam. 5.5.5].
- \([2^r-1,2^r-r-1,3]\) Hamming code— Shortened Hamming codes \([2^r-2,2^r-r-2,3]\) are nearly perfect ([5], pg. 533).
Member of code lists
Primary Hierarchy
References
- [1]
- S. Johnson, “A new upper bound for error-correcting codes”, IEEE Transactions on Information Theory 8, 203 (1962) DOI
- [2]
- J. M. Goethals and S. L. Snover, “Nearly perfect binary codes”, Discrete Mathematics 3, 65 (1972) DOI
- [3]
- N. V. Semakov, V. A. Zinoviev, and G. V. Zaitsev, “Uniformly Packed Codes”, Problemy Peredachi Informatsii, 7:1 (1971), 38–50; Problems of Information Transmission, 7:1 (1971), 30–39.
- [4]
- W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
- [5]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [6]
- K. Lindström. “The nonexistence of unknown nearly perfect binary codes.” PhD thesis, Turun yliopisto, 1975.
- [7]
- 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.
- [8]
- K. Lindström, “All nearly perfect codes are known”, Information and Control 35, 40 (1977) DOI
- [9]
- V. D. Tonchev, “Codes and designs.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
Page edit log
- Victor V. Albert (2022-07-19) — most recent
Cite as:
“Nearly perfect code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/nearly_perfect