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

Child

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 2-design [11]. As such, cluster states form complex projective 2-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 2-design [11]. As such, cluster states form complex projective 2-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, P. V. Kumar, A. R. Calderbank, N. J. A. Sloane, and P. Sole, “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., 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
[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, A. R. Hammons Jr., P. V. Kumar, N. J. A. Sloane, and P. Solé, “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, P. Cameron, W. Kantor, and J. Seidel, “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, N. Rengaswamy, R. Calderbank, and H. D. Pfister, “Kerdock Codes Determine Unitary 2-Designs”, IEEE Transactions on Information Theory 66, 6104 (2020) arXiv:1904.07842 DOI
[12]
T. Fuchs, D. Gross, F. Krahmer, R. Kueng, and D. G. Mixon, “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 &amp; 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, H. G. Schaathun, T. H. Helleseth, and H. G. Schaathun, “On the&amp;lt;tex&amp;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

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: kerdock

Cite as:
“Kerdock code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/kerdock
BibTeX:
@incollection{eczoo_kerdock, title={Kerdock code}, booktitle={The Error Correction Zoo}, year={2023}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/kerdock} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/kerdock

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.