Kerdock code

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

The transmission rate is $2m/2^m$ which tends to 0 as $m$ becomes large, hence these codes are asymptotically poor.

Decoding

Soft decision decoding involves extending the Fast Hadamard Transform decoding algorithm for the first-order RM code to Kerdock code [3].Complexity of soft decision decoding algorithm: $4^m$ multiplications and $m4^m$ additions [3,4].

Notes

See corresponding MinT database entry [5].

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. https://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

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/nonlinear/gray_map/originals/kerdock.yml.