Delsarte-Goethals (DG) code

Delsarte-Goethals (DG) code[1]

Description

Member of a family of \((2^{2t+2},2^{(2t+1)(t-d+2)+2t+3},2^{2t+1}-2^{2t+1-d})\) binary nonlinear codes for parameters \(r \geq 1\) and \(m = 2t+2 \geq 4\), denoted by DG\((m,r)\), that generalizes the Kerdock code.

The code DG\((m,r)\) is a nonlinear subcode of the second-order Reed-Muller code RM\((2,m)\), and equals RM\((2,m)\) at \(r=1\) [2; pg. 461]. The code is the union of certain cosets of RM\((1,m)\) in RM\((2,m)\) that are specified by bilinear forms [1]. The code DG\((m,r+1)\) is a union of disjoint translates of DG\((m,r)\).

While DG\((m,r)\) is not generally linear, it is the Gray map image of a certain extended cyclic linear code over \(\mathbb{Z_4}\) [3]. These codes are distance invariant [3], so the distance and weight distributions are the same.

Their automorphism groups are determined in Ref. [4].

Decoding

Since the equivalent \(\mathbb{Z_4}\) codes are extended cyclic codes, efficient encoding and decoding is possible [3].

Realizations

Space-time signaling [5].Compressed neighbor discovery in a network [6].

Parent

Binary code

Child

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

Cousins

Quaternary linear code over \(\mathbb{Z}_4\) — DG codes can be seen, via the Gray map, as extended linear cyclic codes over \(\mathbb{Z}_4\) [3,7].
Gray code — DG codes can be seen, via the Gray map, as extended linear cyclic codes over \(\mathbb{Z}_4\) [3,7].
Reed-Muller (RM) code — The code DG\((m,r)\) is a subcode of the second-order Reed-Muller code RM\((2,m)\), and equals RM\((2,m)\) at \(r=1\) [2; pg. 461]. The code is the union of certain cosets of the first-order RM\((1,m)\) code in RM\((2,m)\) that are specified by bilinear forms [1].
Goethals code — Hergert codes for a given \(m\) are duals of DG\((m,1/2(m-2))\) codes in that their distance distribution is equal to the MacWilliams transform of the distance distribution of the DG codes [8]. However, the two codes are images of a pair of mutually dual linear codes over \(\mathbb{Z}_4\) under the Gray map [3,7].
Hergert code — Hergert codes are duals of DG codes in that their distance distribution is equal to the MacWilliams transform of the distance distribution of DG codes [8]. However, the two codes are images of a pair of mutually dual linear codes over \(\mathbb{Z}_4\) under the Gray map [3,7].

References

[1]: P. Delsarte and J. M. Goethals, “Alternating bilinear forms over GF(q)”, Journal of Combinatorial Theory, Series A 19, 26 (1975) DOI
[2]: F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[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]: C. Carlet, “The automorphism groups of the Delsarte-Goethals codes”, Designs, Codes and Cryptography 3, 237 (1993) DOI
[5]: A. R. Calderbank, S. N. Diggavi, and N. Al-Dhahir, “Space-time signaling based on Kerdock and Delsafte-Goethals codes”, 2004 IEEE International Conference on Communications (IEEE Cat. No.04CH37577) (2004) DOI
[6]: A. Thompson and R. Calderbank, “Compressed Neighbour Discovery using Sparse Kerdock Matrices”, (2018) arXiv:1801.04537
[7]: A. R. Hammons Jr. et al., “The Z_4-Linearity of Kerdock, Preparata, Goethals and Related Codes”, (2002) arXiv:math/0207208
[8]: F. B. Hergert, “On the delsarte-goethals codes and their formal duals”, Discrete Mathematics 83, 249 (1990) DOI

Page edit log

Victor V. Albert (2024-01-11) — most recent
Madhura Pankaja (2024-01-11)

Cite as:

“Delsarte-Goethals (DG) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/delsarte_goethals

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