# Kerdock code[1]

## Description

Binary nonlinear \((2^m, 2^{2m}, 2^{m-1} - 2^{(m-2)/2})\) for even \(m\) consisting of the first-order Reed-Muller code RM\((1,m)\) with maximum-rank cosets of RM\((1,m)\) in RM\((2,m)\).

The size of code book, \(|2^{m-1}||\text{RM}(1,m)|\), is twice the size of the largest possible linear code with the same length and distance. The relative minimum distance tends to \(\frac{1}{2}\) as \(m\) becomes large.

Let the matrices \(A = [a_{ij}]\) constitute the Kerdock set \(K\), i.e., a set of symmetric binary matrices with zero diagonal entries with the property that differences of distinct matrices in the set have full rank. Define Boolean functions of the form \(Q(X) + l(X) + b\), where \(Q(X) = \sum_{1 \leq i < j \leq m} a_{ij}X_{i}X_{j}\), the function \(l(X)\) is linear in \(m\) variables, and \(b\) is a bit. Codewords are formed as evaluations of these functions over \(GF(2)^{m}\) in the variable \(X \in GF(2)^{m}\).

The automorphism group of these codes is \(\Gamma A_{1}(\mathbb{F}_{2^{m-1}})\times\mathbb{F}_{2}\) [2].

## Rate

## Decoding

## Notes

## Parent

- Delsarte-Goethals (DG) code — A Kerdock code of length \(2^m\) is equivalent to DG\((m,m/2)\) and is a subcode of DG\((m,r)\) [6; pg. 461].

## Child

- Nordstrom-Robinson (NR) code — The NR code is the smallest Kerdock code.

## Cousins

- Reed-Muller (RM) code — Kerdock code is a subcode of a second-order RM Code [6; pg. 457]. It consists of a number of cosets of RM\((2,m)\) created by quotienting with first-order RM\((1,m)\) codes.
- \([2^m,m+1,2^{m-1}]\) First-order RM code — Kerdock code is a subcode of a second-order RM Code [6; pg. 457]. It consists of a number of cosets of RM\((2,m)\) created by quotienting with first-order RM\((1,m)\) codes.
- Preparata 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 [7]. However, the two codes are images of a pair of mutually dual linear codes over \(\mathbb{Z}_4\) under the Gray map [8][9; Sec. 6.3].
- \([2^r-1,2^r-r-1,3]\) Hamming code — Kerdock codes can be obtained by Hensel-lifting Hamming codes to \(\mathbb{Z}_4\) [3].
- Cluster-state code — Kerdock codes correspond to cluster states, and the corresponding Clifford-group automorphisms of this set form a particular group [10] that is a unitary two-design [11]. As such, cluster states form complex projective two-designs. These are useful in matrix-vector multiplication [12].
- \(t\)-design — Kerdock codes correspond to cluster states, and the corresponding Clifford-group automorphisms of this set form a particular group [10] that is a unitary two-design [11]. As such, cluster states form complex projective two-designs. These are useful in matrix-vector multiplication [12].
- Universally optimal \(q\)-ary code — Kerdock codes are asymptotically universally optimal [9; Exam. 12.3.25].
- 24-cell code — The 24-cell is a special case of a family of codes for real projective planes, constructed using Kerdock codes [13] (cf. [14]).
- Quaternary RM (QRM) code — The image of the Kerdock code under the Gray map yields the QRM\((1,m)\) code [4; Thm. 19].
- Gray code — The image of the Kerdock code under the Gray map yields the QRM\((1,m)\) code [4; Thm. 19].
- Frameproof (FP) code — Kerdock codes of sufficient order are separating [15,16].
- Kerdock spherical code — Kerdock spherical codes can be obtained from Kerdock codes using the antipodal mapping [17; pg. 157].

## References

- [1]
- A. M. Kerdock, “A class of low-rate nonlinear binary codes”, Information and Control 20, 182 (1972) DOI
- [2]
- C. Carlet, “The Automorphism Groups of the Kerdock Codes”, Journal of Information and Optimization Sciences 12, 387 (1991) DOI
- [3]
- 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
- [4]
- A. R. Hammons Jr. et al., “The Z_4-Linearity of Kerdock, Preparata, Goethals and Related Codes”, (2002) arXiv:math/0207208
- [5]
- Rudolf Schürer and Wolfgang Ch. Schmid. “Kerdock Codes.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2015-09-03. http://mint.sbg.ac.at/desc_CKerdock.html
- [6]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [7]
- W. Kantor, “On the inequivalence of generalized Preparata codes”, IEEE Transactions on Information Theory 29, 345 (1983) DOI
- [8]
- A. R. Calderbank et al., “A linear construction for certain Kerdock and Preparata codes”, (1993) arXiv:math/9310227
- [9]
- W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [10]
- A. Calderbank et al., “Z\({}_{\text{4}}\) -Kerdock Codes, Orthogonal Spreads, and Extremal Euclidean Line-Sets”, Proceedings of the London Mathematical Society 75, 436 (1997) DOI
- [11]
- T. Can et al., “Kerdock Codes Determine Unitary 2-Designs”, IEEE Transactions on Information Theory 66, 6104 (2020) arXiv:1904.07842 DOI
- [12]
- T. Fuchs et al., “Sketching with Kerdock’s crayons: Fast sparsifying transforms for arbitrary linear maps”, (2021) arXiv:2105.05879
- [13]
- Levenshtein, V. I. (1982). Bounds on the maximal cardinality of a code with bounded modulus of the inner product. In Soviet Math. Dokl (Vol. 25, No. 2, pp. 526-531).
- [14]
- H. Cohn, A. Kumar, and G. Minton, “Optimal simplices and codes in projective spaces”, Geometry & Topology 20, 1289 (2016) arXiv:1308.3188 DOI
- [15]
- Krasnopeev, A., and Yu L. Sagalovich. "The Kerdock codes and separating systems." Eight International Workshop on Algebraic and Combinatorial Coding Theory. Vol. 7. No. 7.2. 2002.
- [16]
- T. H. Helleseth et al., “On the&lt;tex&gt;$”, IEEE Transactions on Information Theory 50, 3312 (2004) DOI
- [17]
- T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.

## Page edit log

- Victor V. Albert (2023-11-22) — most recent
- Shuubham Ojha (2023-11-22)

## Cite as:

“Kerdock code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/kerdock