Kerdock code[1] 


Binary nonlinear \((2^m, 2^{2m}, 2^{m-1} - 2^{(m-2)/2})\) for even \(m\) consisting of the first-order Reem-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 transmission rate is \(2m/2^m\) which tends to 0 as \(m\) becomes large, hence these codes are asymptotically poor.


Soft decision decoding involves extending the Fast Hadamard Transform decoding algorithm for the binary first-order Reed-Muller code to Kerdock code [2].Complexity of soft decision decoding algorithm: \(4^m\) multiplications and \(m4^m\) additions [2,3].


Digital fingerprinting: \(t\)-collision secure schemes can be designed to detect a pirated copy once \(t\) users have colluded [4].


See corresponding MinT database entry [5].




  • 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 RM\((1,m)\).
  • 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].
  • Hamming code — Kerdock codes can be obtained by Hensel-lifting Hamming codes to \(\mathbb{Z}_4\) [2].
  • Qubit stabilizer code — Kerdock codes can be used to form a subset of stabilizer states, and the corresponding Clifford-group automorphisms of this set form a particular group [10] that is a unitary two-design [11].
  • 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 [12] (cf. [13]).
  • Kerdock spherical code — Kerdock spherical codes can be obtained from Kerdock codes using the binary antipodal mapping [14; pg. 157].


A. M. Kerdock, “A class of low-rate nonlinear binary codes”, Information and Control 20, 182 (1972) DOI
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
A. R. Hammons Jr. et al., “The Z_4-Linearity of Kerdock, Preparata, Goethals and Related Codes”, (2002) arXiv:math/0207208
T. H. Helleseth et al., “On the&amp;lt;tex&amp;gt;$”, IEEE Transactions on Information Theory 50, 3312 (2004) DOI
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.
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
W. Kantor, “On the inequivalence of generalized Preparata codes”, IEEE Transactions on Information Theory 29, 345 (1983) DOI
A. R. Calderbank et al., “A linear construction for certain Kerdock and Preparata codes”, (1993) arXiv:math/9310227
W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
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
T. Can et al., “Kerdock Codes Determine Unitary 2-Designs”, IEEE Transactions on Information Theory 66, 6104 (2020) arXiv:1904.07842 DOI
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).
H. Cohn, A. Kumar, and G. Minton, “Optimal simplices and codes in projective spaces”, Geometry &amp; Topology 20, 1289 (2016) arXiv:1308.3188 DOI
T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
Page edit log

Your contribution is welcome!

on (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.
@incollection{eczoo_kerdock, title={Kerdock code}, booktitle={The Error Correction Zoo}, year={2023}, editor={Albert, Victor V. and Faist, Philippe}, url={} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:

Cite as:

“Kerdock code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023.