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\).
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.
Notes
Parents
- Dual linear code
- Self-dual additive code — 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 [9; Thm. 27.4.1] ([5; Thm. 9.10.3]).
Children
- Pless symmetry code
- Hexacode — The hexacode is Hermitian self-dual and, as a result, is also trace-Hermitian self-dual additive [5; Sec. 9.10]. The hexacode and the shortened hexacode are extremal [5; Tab. 9.14][10; Tm. 12].
- Tetracode — The tetracode is Euclidean self-dual.
Cousins
- Divisible code — Binary self-dual codes are singly-even and binary self-orthogonal codes that are not doubly-even are singly-even [11; Def. 4.1.6]. The minimum distance of doubly-even binary self-dual codes asymptotically satisfies \(d\leq0.1664n+o(n)\) [12].
- Unimodular lattice code — 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,4].
- Niemeier lattice code — Niemeier lattice codes can be constructed from ternary self-dual codes of length 24 [13].
- Combinatorial design code — Self-dual extremal codes yield combinatorial \(\leq 5\)-designs using the Assmus-Mattson theorem [14] (see [15; Sec. 5.4]). See [16; Table 1.61, pg. 683] for a table of combinatorial designs obtained from self-dual codes.
- Golay code — The extended Golay code is self-dual.
- Cyclic linear \(q\)-ary code — See Refs. [17,18] for tables of cyclic self-dual codes.
- Ternary Golay code — The extended ternary Golay code is self-dual.
References
- [1]
- S. Kurz, “Divisible Codes”, (2022) 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]
- Self-Dual Codes and Invariant Theory (Springer-Verlag, 2006) DOI
- [5]
- W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
- [6]
- S. Bouyuklieva, “Some optimal self-orthogonal and self-dual codes”, Discrete Mathematics 287, 1 (2004) DOI
- [7]
- M. Harada, “Binary extremal self-dual codes of length 60 and related codes”, Designs, Codes and Cryptography 86, 1085 (2017) arXiv:1706.01694 DOI
- [8]
- P. Gaborit and A. Otmani, “Experimental constructions of self-dual codes”, Finite Fields and Their Applications 9, 372 (2003) DOI
- [9]
- M. F. Ezerman, "Quantum Error-Control Codes." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [10]
- G. Hoehn, “Self-dual Codes over the Kleinian Four Group”, (2000) arXiv:math/0005266
- [11]
- S. Bouyuklieva, "Self-dual codes." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [12]
- I. Krasikov and S. Litsyn, “Linear programming bounds for doubly-even self-dual codes”, IEEE Transactions on Information Theory 43, 1238 (1997) DOI
- [13]
- P. S. Montague, “A new construction of lattices from codes over GF(3)”, Discrete Mathematics 135, 193 (1994) DOI
- [14]
- E. F. Assmus Jr. and H. F. Mattson Jr., “New 5-designs”, Journal of Combinatorial Theory 6, 122 (1969) DOI
- [15]
- V. D. Tonchev, "Codes and designs." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [16]
- C. J. Colbourn, editor , CRC Handbook of Combinatorial Designs (CRC Press, 2010) DOI
- [17]
- Yan Jia, San Ling, and Chaoping Xing, “On Self-Dual Cyclic Codes Over Finite Fields”, IEEE Transactions on Information Theory 57, 2243 (2011) DOI
- [18]
- S. Jitman et al., “Abelian Codes in Principal Ideal Group Algebras”, IEEE Transactions on Information Theory 59, 3046 (2013) DOI
Page edit log
- Victor V. Albert (2023-04-21) — most recent
Cite as:
“Self-dual linear code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/self_dual