Preparata code[1]
Description
A nonlinear binary \((2^{m+1}-1, 2^{m+1}-2m-2, 5)\) code where \(m\) is odd. The size of this code is twice the size of the largest possible linear code with the same length and distance.
Codewords of extended Preparata codes can be thought of as characteristic functions of the tuple \((X,Y)\), where \(X, Y\) belong to \(GF(2)^m\), along with the following properties: (i) \(|X| = |Y| = 2^{m}\), (ii) \(\sum_{x \in X} x = \sum_{y \in Y} y \), and (iii) \(\sum_{x \in X} x^{3} + (\sum_{x \in X} x)^{3} = \sum_{y \in Y} y^{3} \). Preparata codes are obtained by leaving out the coordinate in the zeroth positions in the first half.
The automorphism group of these codes is determined in Refs. [2–4].
Rate
The rate is \(\frac{2^{m+1}-2m-2}{2^{m+1}-1}\).
Decoding
Preparata Codes can be decoded using a syndrome calculation based algorithm to correct all error patterns of Lee weight atmost 2 and detect all/ some error patterns of Lee weight 3/ 4 [5,6].
Notes
See corresponding MinT database entry [7].
Parents
- Hergert code — Preparata codes are equivalent to Hergert codes for \(r=2\) [8; Thm. 2].
- Nearly perfect code — Preparata codes are uniformly packed and nearly perfect [9]. 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.
- Small-distance block code
Child
- Nordstrom-Robinson (NR) code — The NR code is the smallest Preparata code.
Cousins
- Quasi-perfect code — Punctured Preparata codes are quasi-perfect [10; pg. 475].
- Reed-Muller (RM) code — A Preparata code can be written as a union of a linear subcode \(\mathcal{C}\) of RM\((m-2,m)\) and the \(2^{m-1}-1\) representatives of coset formed by \(\mathcal{C}\) in RM\((m-2,m)\). The coset representatives are given by \(|1|x^j|0|x^{j}\theta_{1}|\), where \(1\leq j \leq 2^{m-1}-1\). \(\mathcal{C}\) comprises of codewords of the form \(|g(1)|g(x)(1+\theta_{1})|f(1)+g(1)|g(x)(1+\theta_{1})+f(x)(1+\theta_{1}+\theta_{3})|\), where \(f(x)\) and \(g(x)\) are arbitrary, and where \(\theta_{1}\) and \(\theta_{3}\) denote the primitive idempotents corresponding to cyclotomic cosets \(C_1\) and \(C_3\) respectively.
- Binary BCH code — Preparata codes contain twice as many code words as the double-error-correcting BCH codes of the same length, which is the largest number of code words possible for given length and distance [1].
- \([2^r-1,2^r-r-1,3]\) Hamming code — Preparata codes can be obtained by Hensel-lifting Hamming codes to \(\mathbb{Z}_4\) [5]. The union of the dual a Preparata code and some of its translates forms a Hamming code [10; pg. 475].
- Combinatorial design — Preparata codewords of each weight form a 3-design [10; pg. 471].
- Quaternary RM (QRM) code — The image of the Preparata code under the Gray map yields the QRM\((m-2,m)\) code [6; Thm. 19].
- Gray code — The image of the Preparata code under the Gray map yields the QRM\((m-2,m)\) code [6; Thm. 19].
- 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 [11][12; 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 [13,14]. 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 [15].
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]
- A. R. Hammons et al., “The Z/sub 4/-linearity of Kerdock, Preparata, Goethals, and related codes”, IEEE Transactions on Information Theory 40, 301 (1994) DOI
- [6]
- A. R. Hammons Jr. et al., “The Z_4-Linearity of Kerdock, Preparata, Goethals and Related Codes”, (2002) arXiv:math/0207208
- [7]
- Rudolf Schürer and Wolfgang Ch. Schmid. “Preparata Codes.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2015-09-03. https://mint.sbg.ac.at/desc_CPreparata.html
- [8]
- P. Delsarte and J. M. Goethals, “Alternating bilinear forms over GF(q)”, Journal of Combinatorial Theory, Series A 19, 26 (1975) DOI
- [9]
- J. M. Goethals and S. L. Snover, “Nearly perfect binary codes”, Discrete Mathematics 3, 65 (1972) DOI
- [10]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [11]
- A. R. Calderbank et al., “A linear construction for certain Kerdock and Preparata codes”, (1993) arXiv:math/9310227
- [12]
- W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [13]
- M. Grassl and M. Rotteler, “Non-additive quantum codes from Goethals and Preparata codes”, 2008 IEEE Information Theory Workshop (2008) arXiv:0801.2144 DOI
- [14]
- M. Grassl and M. Rotteler, “Quantum Goethals-Preparata codes”, 2008 IEEE International Symposium on Information Theory (2008) arXiv:0801.2150 DOI
- [15]
- S. Ling and P. Sole. 2008. Nonadditive quantum codes from Z4-codes. https://hal.archives-ouvertes.fr/hal-00338309/fr/.
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