[Jump to code hierarchy]

Self-dual linear code

Description

An \([n,n/2]_q\) code that is equal to its dual, \(C^\perp = C\), where the dual is defined with respect to an inner product, most commonly either Euclidean or Hermitian. Self-dual codes exist only for even lengths and have dimension \(k=n/2\). A code that is equivalent to its dual is called iso-dual.

An even (doubly even) self-dual code is called Type I (Type II) [1,2]. Ternary (quaternary) self-dual codes are called Type III (Type IV), and each of their codewords has weight three (two).

Protection

The generator matrix of the Hermitian dual of a code with generator matrix \(G = [I_k~~A]\) is \([-\bar{A}^T~~I_{n-k}]\), where \(\bar{A}\) contains matrix elements of \(A\) raised to the \(p\)th power. A code is Hermitian self-dual if and only if \(A \bar{A}^{T} = -I_{n/2}\).

The minimum distance of a Hermitian self-dual \([n,n/2]\) code satisfies \begin{align} d\leq\begin{cases} 2\left\lfloor \frac{n}{8}\right\rfloor +2 & q=2\text{ and code is singly even}\\ 4\left\lfloor \frac{n}{24}\right\rfloor +4 & q=2\text{ and code is doubly even}\\ 3\left\lfloor \frac{n}{12}\right\rfloor +3 & q=3\\ 2\left\lfloor \frac{n}{6}\right\rfloor +2 & q=4\text{ and code is even} \end{cases}~, \tag*{(1)}\end{align} except for \(n = 22\) modulo four for the second case, where the bound is increased by four [3]. A self-dual code saturating the above inequality is called extremal.

Fixed-weight codewords of extremal self-dual doubly even binary codes whose length divides 24 form a combinatorial 5-design [4]. The extended Golay code and the \([48,24,12]\) self-dual code are two such codes. It is not yet known whether a \([72,36,16]\) self-dual code exists; see [5,6][7; Remark 4.3.11].

Doubly even self-dual codes have been classified up to \(n\leq 40\) [8]. The \([22,11]\) and \([24,12]\) doubly even self-dual codes have been classified, and there are nine inequivalent codes with the latter parameters [9].

For ternary self-dual codes, see [10][7; Remark 4.3.14]. Ternary extremal self-dual codes have been classified for \(n=28\) [11].

Notes

See books [12,13] for more on self-dual codes.See Refs. [14,15] for constructions of binary self-dual codes.See Tables of Self-Dual Codes by P. Gaborit and A. Otmani for a database of self-dual codes over \(GF(2)\), \(GF(3)\), \(GF(4)\) (Euclidean or Hermitian), \(GF(5)\), and \(GF(7)\). See also Ref. [16].See Database of self-dual codes by M. Harada and A. Munemasa for a database of self-dual codes over \(GF(2)\), \(GF(3)\), \(GF(5)\), and \(GF(7)\).

Cousins

  • Divisible code— Binary self-dual codes are singly even, and binary self-orthogonal codes that are not doubly even are singly even [17; Def. 4.1.6]. The minimum distance of doubly even binary self-dual codes asymptotically satisfies \(d\leq0.1664n+o(n)\) [18]. Doubly even self-dual codes have been classified up to \(n\leq 40\) [8].
  • Unimodular lattice— Unimodular lattices are lattice analogues of self-dual codes. There are several parallels between (doubly even) self-dual binary codes and (even) unimodular lattices [2,12].
  • Niemeier lattice— The nine inequivalent \([24,12]\) doubly even self-dual codes [9] yield certain Niemeier lattices via Construction A [19]. Niemeier lattices can be constructed from ternary self-dual codes of length 24 [20].
  • Combinatorial design— Self-dual extremal codes yield combinatorial \(\leq 5\)-designs using the Assmus-Mattson theorem [4] (see [21; Sec. 5.4]). See [22; Table 1.61, pg. 683] for a table of combinatorial designs obtained from self-dual codes.
  • Nordstrom-Robinson (NR) code— The NR code is self-dual in that its distance distribution is invariant under the MacWilliams transform [23]. It maps to the octacode, a self-dual code over \(\mathbb{Z}_4\) under the Gray map [24–26].
  • Ternary Golay code— The extended ternary Golay code is self-dual.
  • Cyclic linear \(q\)-ary code— See Refs. [27,28] for tables of cyclic self-dual codes.
  • Harada-Kitazume code— Codewords consisting of 0 and 2 of nine Harada-Kitazume codes are of the form \(2c\), where \(c\) is a codeword of one of the nine corresponding \([24,12]\) doubly even self-dual codes [19].
  • Jump code— Iso-dual codes can be used to construct jump codes [29].
  • Hermitian qubit code— Hermitian qubit codes are constructed from Hermitian self-orthogonal linear codes over \(GF(4)\) via the \(GF(4)\) representation. This relation yields bounds on self-dual codes over \(GF(4)\) [30].
  • Triorthogonal code— Self-dual binary codes can be used to construct triorthogonal codes [31].

Member of code lists

Primary Hierarchy

Classical Domain
Galois-field Kingdom
\(q\)-ary codeECC
Additive \(q\)-ary codeECC
Linear \(q\)-ary codeECC
Dual linear code
Parents
Dual linear code
Self-dual additive codeECC
Self-dual linear codes with respect to some inner product are automatically self-dual additive under the same inner product since linear codes are additive. In addition, quaternary linear codes are Hermitian self-orthogonal (self-dual) iff they are trace-Hermitian self-orthogonal (self-dual) additive [32; Thm. 27.4.1] ([13; Thm. 9.10.3]).
Self-dual linear code
Children
\([24, 12, 8]\) Extended Golay code
The extended Golay code is the unique code at its parameters and happens to be self-dual and doubly even [33][7; Remark 4.3.11].
Karlin double circulant code
Karlin double circulant codes are self-dual doubly even codes [34; Ch. 16]
\([48,24,12]\) self-dual code
The \([48,24,12]\) self-dual code is the only self-dual doubly even code at its parameters [35].
\([8,4,4]\) extended Hamming code
The \([8,4,4]\) extended Hamming code is the smallest doubly even self-dual code.
Pless symmetry code
Hexacode
The hexacode is Hermitian self-dual and, as a result, is also trace-Hermitian self-dual additive [13; Sec. 9.10]. The hexacode and the shortened hexacode are extremal [13; Tab. 9.14][36; Tm. 12].
Tetracode
The tetracode is Euclidean self-dual.

References

[1]
S. Kurz, “Divisible Codes”, (2023) arXiv:2112.11763
[2]
J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
[3]
E. M. Rains, “Shadow bounds for self-dual codes”, IEEE Transactions on Information Theory 44, 134 (1998) DOI
[4]
E. F. Assmus Jr. and H. F. Mattson Jr., “New 5-designs”, Journal of Combinatorial Theory 6, 122 (1969) DOI
[5]
N. Sloane, “Is there a (72,36) d = 16 self-dual code? (Corresp.)”, IEEE Transactions on Information Theory 19, 251 (1973) DOI
[6]
S. Dougherty, J.-L. Kim, and P. Solé, “Open Problems in Coding Theory”, Contemporary Mathematics 79 (2015) DOI
[7]
E. M. Rains and N. J. A. Sloane, “Self-dual codes,” in Handbook of Coding Theory, eds. V. S. Pless and W. C. Huffman. Amsterdam: Elsevier, 1998, pp. 177–294.
[8]
K. Betsumiya, M. Harada, and A. Munemasa, “A complete classification of doubly even self-dual codes of length 40”, (2012) arXiv:1104.3727
[9]
V. Pless and N. J. A. Sloane, “On the classification and enumeration of self-dual codes”, Journal of Combinatorial Theory, Series A 18, 313 (1975) DOI
[10]
W. Cary Huffman, “On the classification and enumeration of self-dual codes”, Finite Fields and Their Applications 11, 451 (2005) DOI
[11]
M. Harada, A. Munemasa, and B. Venkov, “Classification of ternary extremal self-dual codes of length 28”, Mathematics of Computation 78, 1787 (2009) DOI
[12]
Self-Dual Codes and Invariant Theory (Springer-Verlag, 2006) DOI
[13]
W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
[14]
S. Bouyuklieva, “Some optimal self-orthogonal and self-dual codes”, Discrete Mathematics 287, 1 (2004) DOI
[15]
M. Harada, “Binary extremal self-dual codes of length 60 and related codes”, Designs, Codes and Cryptography 86, 1085 (2017) arXiv:1706.01694 DOI
[16]
P. Gaborit and A. Otmani, “Experimental constructions of self-dual codes”, Finite Fields and Their Applications 9, 372 (2003) DOI
[17]
S. Bouyuklieva, "Self-dual codes." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[18]
I. Krasikov and S. Litsyn, “Linear programming bounds for doubly-even self-dual codes”, IEEE Transactions on Information Theory 43, 1238 (1997) DOI
[19]
M. Harada and M. Kitazume, “Z4-Code Constructions for the Niemeier Lattices and their Embeddings in the Leech Lattice”, European Journal of Combinatorics 21, 473 (2000) DOI
[20]
P. S. Montague, “A new construction of lattices from codes over GF(3)”, Discrete Mathematics 135, 193 (1994) DOI
[21]
V. D. Tonchev, "Codes and designs." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[22]
C. J. Colbourn, editor , CRC Handbook of Combinatorial Designs (CRC Press, 2010) DOI
[23]
W. Kantor, “On the inequivalence of generalized Preparata codes”, IEEE Transactions on Information Theory 29, 345 (1983) DOI
[24]
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
[25]
Forney Jr GD, Sloane NJ, Trott MD. The Nordstrom-Robinson code is the binary image of the octacode. In Coding and Quantization: DIMACS/IEEE workshop 1992 Oct 19 (pp. 19-26). Amer. Math. Soc..
[26]
Z. X. Wan, Quaternary Codes (WORLD SCIENTIFIC, 1997) DOI
[27]
Yan Jia, San Ling, and Chaoping Xing, “On Self-Dual Cyclic Codes Over Finite Fields”, IEEE Transactions on Information Theory 57, 2243 (2011) DOI
[28]
S. Jitman, S. Ling, H. Liu, and X. Xie, “Abelian Codes in Principal Ideal Group Algebras”, IEEE Transactions on Information Theory 59, 3046 (2013) DOI
[29]
T. Beth, C. Charnes, M. Grassl, G. Alber, A. Delgado, and M. Mussinger, Designs, Codes and Cryptography 29, 51 (2003) DOI
[30]
A. R. Kalra and S. Prakash, “Invariant Theory and Magic State Distillation”, (2025) arXiv:2501.10163
[31]
M. Shi, H. Lu, J.-L. Kim, and P. Sole, “Triorthogonal Codes and Self-dual Codes”, (2024) arXiv:2408.09685
[32]
M. F. Ezerman, "Quantum Error-Control Codes." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[33]
P. Delsarte and J. M. Goethals, “Unrestricted codes with the golay parameters are unique”, Discrete Mathematics 12, 211 (1975) DOI
[34]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[35]
S. K. Houghten, C. W. H. Lam, L. H. Thiel, and J. A. Parker, “The extended quadratic residue code is the only (48,24,12) self-dual doubly-even code”, IEEE Transactions on Information Theory 49, 53 (2003) DOI
[36]
G. Hoehn, “Self-dual Codes over the Kleinian Four Group”, (2000) arXiv:math/0005266
Page edit log

Your contribution is welcome!

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

edit on this site

Zoo Code ID: self_dual

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

Cite as:

“Self-dual linear code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/self_dual

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/q-ary_digits/dual/self_dual.yml.