Preparata code[1]
Description
A nonlinear binary \((2^{m+1}, 2^{2^{m+1}-2m-2}, 6)\) code where \(m\) is odd. Puncturing a Preparata code yields the shortened Preparata code with parameters \((2^{m+1}-1, 2^{2^{m+1}-2m-2}, 5)\).
The automorphism groups of Preparata and shortened Preparata codes are determined in Refs. [2–4].
Rate
The rate is \(\frac{2^{m+1}-2m-2}{2^{m+1}}\), tending to 1 as \(m\) becomes large.Notes
See corresponding MinT database entry [5].Cousins
- Small-distance block code— Shortened Preparata codes form an infinite family of small-distance block codes with minimum distance \(5\).
- Nearly perfect code— Shortened Preparata codes are uniformly packed and nearly perfect [6]. 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.
- Quasi-perfect code— Shortened Preparata codes are quasi-perfect [7; pg. 475].
- Reed-Muller (RM) code— Preparata codes are nonlinear subcodes of second-order Reed-Muller codes, and shortened Preparata codes are obtained from them by puncturing.
- Binary BCH code— Preparata codes contain twice as many codewords as the extended double-error-correcting BCH codes of the same length and minimum distance, and have the greatest possible number of codewords for this minimum distance [1][7; pg. 475].
- \([2^r-1,2^r-r-1,3]\) Hamming code— The union of a shortened Preparata code and some of its translates forms a Hamming code [7; pg. 475].
- \([2^m,2^m-m-1,4]\) Extended Hamming code— Any code with the same parameters as the Preparata code must be a distance invariant subcode of a (possibly nonlinear) code with the same parameters as the extended Hamming code [8,9].
- Combinatorial design— Preparata codewords of each weight form 3-designs, and the minimum-weight codewords yield infinite families of 4-designs, including Steiner 4-designs with block sizes 5 and 6 [10; Rem. 5.5.6 and Thms. 5.5.7, 5.5.11][7; pg. 471].
- Quaternary RM (QRM) code— The binary Preparata code is the Gray-map image of the quaternary code QRM\((m-2,m)\) [11; Thm. 19].
- Gray code— The binary Preparata code is the Gray-map image of the quaternary code QRM\((m-2,m)\) [11; Thm. 19].
- ZRM code— Each Preparata code is contained in a corresponding dual of ZRM\((1,m)\) [11].
- Kerdock code— Preparata codes are duals of Kerdock codes in that their distance distribution is equal to the MacWilliams transform of the distance distribution of Kerdock codes [4]. However, the two codes are images of a pair of mutually dual linear codes over \(\mathbb{Z}_4\) under the Gray map [12][13; Sec. 6.3].
- \(((2^m,2^{2^m−5m+1},8))\) Goethals-Preparata code— The \(((2^m,2^{2^m−5m+1},8))\) Goethals-Preparata code is constructed using the classical Goethals and Preparata codes [14,15]. A construction using the \(\mathbb{Z}_4\) versions of the Goethals and Preparata codes and the Gray map yields qubit code families with similar parameters [16].
Primary Hierarchy
Parents
Preparata codes are equivalent to Hergert codes for \(r=2\) [17; Thm. 2].
Preparata code
Children
The NR code is the smallest Preparata code.
References
- [1]
- F. P. Preparata, “A class of optimum nonlinear double-error-correcting codes”, Information and Control 13, 378 (1968) DOI
- [2]
- W. M. Kantor, “Spreads, Translation Planes and Kerdock Sets. I”, SIAM Journal on Algebraic Discrete Methods 3, 151 (1982) DOI
- [3]
- W. M. Kantor, “Spreads, Translation Planes and Kerdock Sets. II”, SIAM Journal on Algebraic Discrete Methods 3, 308 (1982) DOI
- [4]
- W. Kantor, “On the inequivalence of generalized Preparata codes”, IEEE Transactions on Information Theory 29, 345 (1983) DOI
- [5]
- R. Schürer and W. Ch. Schmid. “Preparata Codes.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2015-09-03. mint.sbg.ac.at/desc_CPreparata.html
- [6]
- J. M. Goethals and S. L. Snover, “Nearly perfect binary codes”, Discrete Mathematics 3, 65 (1972) DOI
- [7]
- F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (Elsevier, 1977)
- [8]
- 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
- [9]
- G. V. Zaitsev, V. A. Zinoviev, and N. V. Semakov (1973). “Interrelation of Preparata and Hamming codes and extension of Hamming codes to new double-error-correcting codes”. In Proc. 2nd International Symp. Inform. Theory (pp. 257-263)
- [10]
- V. D. Tonchev, “Codes and designs.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [11]
- A. R. Hammons, P. V. Kumar, A. R. Calderbank, N. J. A. Sloane, and P. Solé, “The Z_4-Linearity of Kerdock, Preparata, Goethals and Related Codes”, (2002) arXiv:math/0207208
- [12]
- A. R. Calderbank, A. R. Hammons, P. V. Kumar, N. J. A. Sloane, and P. Solé, “A linear construction for certain Kerdock and Preparata codes”, (1993) arXiv:math/9310227
- [13]
- S. T. Dougherty, “Codes over rings.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [14]
- M. Grassl and M. Rotteler, “Non-additive quantum codes from Goethals and Preparata codes”, 2008 IEEE Information Theory Workshop 396 (2008) arXiv:0801.2144 DOI
- [15]
- M. Grassl and M. Rotteler, “Quantum Goethals-Preparata codes”, 2008 IEEE International Symposium on Information Theory (2008) arXiv:0801.2150 DOI
- [16]
- S. Ling and P. Sole. 2008. Nonadditive quantum codes from Z4-codes. hal.archives-ouvertes.fr/hal-00338309/fr
- [17]
- P. Delsarte and J. M. Goethals, “Alternating bilinear forms over GF(q)”, Journal of Combinatorial Theory, Series A 19, 26 (1975) DOI
Page edit log
- Victor V. Albert (2023-11-22) — most recent
- Shuubham Ojha (2023-11-22)
Cite as:
“Preparata code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/preparata