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 isodual. Any self-dual code is isodual, and hence formally self-dual [1; Rem. 4.2.2].
A binary singly even (doubly even) self-dual code is called Type I (Type II), a ternary self-dual code is called Type III, and a Hermitian self-dual code over \(\mathbb{F}_4\) is called Type IV [1; Rems. 4.1.10 and 4.3.2]. Type III codes are 3-divisible, while Type IV codes are 2-divisible [1; Thm. 4.1.9]. Self-dual doubly even binary codes exist iff \(8|n\), self-dual ternary codes exist iff \(4|n\), and Hermitian self-dual codes over \(\mathbb{F}_4\) exist iff \(n\) is even [1; Thm. 4.1.13].
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 formally self-dual even binary code, a Type II binary self-dual code, a Type III ternary self-dual code, and a Type IV Hermitian self-dual code over \(\mathbb{F}_4\) satisfies \begin{align} d\leq\begin{cases} 2\left\lfloor \frac{n}{8}\right\rfloor +2\\ 4\left\lfloor \frac{n}{24}\right\rfloor +4\\ 3\left\lfloor \frac{n}{12}\right\rfloor +3\\ 2\left\lfloor \frac{n}{6}\right\rfloor +2 \end{cases} \tag*{(1)}\end{align} respectively [1; Thm. 4.3.1]. More generally, binary self-dual codes satisfy Rains’s bound \(d\leq 4\lfloor n/24\rfloor+4\), except when \(n\equiv 22\) modulo \(24\), in which case \(d\leq 4\lfloor n/24\rfloor+6\) [1; Thm. 4.3.6]. A self-dual code meeting the relevant upper bound is called extremal [1; Def. 4.3.7].
Fixed-weight codewords of extremal Type II codes of length divisible by \(24\) form combinatorial 5-designs [1; Thm. 4.3.16(a)]. 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 [1; Rem. 4.3.11]; see also [2–4].
Doubly even self-dual codes have been classified up to \(n\leq 40\) [5]. The \([22,11]\) and \([24,12]\) doubly even self-dual codes have been classified, and there are nine inequivalent codes with the latter parameters [6].
For ternary self-dual codes, see [4,8][7; Remark 4.3.14]. Ternary self-dual codes have been classified for \(n=24\) [9] and, in the extremal case, for \(n=28\) [10].
Notes
See books [11,12] for more on self-dual codes.See Refs. [13,14] 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 \(\mathbb{F}_2\), \(\mathbb{F}_3\), \(\mathbb{F}_4\) (Euclidean or Hermitian), \(\mathbb{F}_5\), and \(\mathbb{F}_7\). See also Ref. [15].See Database of self-dual codes by M. Harada and A. Munemasa for a database of self-dual codes over \(\mathbb{F}_2\), \(\mathbb{F}_3\), \(\mathbb{F}_5\), and \(\mathbb{F}_7\).Cousins
- Divisible code— Binary self-orthogonal codes are even, doubly even binary codes are self-orthogonal, and binary self-dual codes split into singly-even Type I and doubly-even Type II families [1; Def. 4.1.6][1; Rems. 4.1.7 and 4.1.10]. Ternary self-dual codes are 3-divisible and Hermitian self-dual quaternary codes are 2-divisible [1; Thm. 4.1.9].
- Group-algebra code— Self-dual group codes exist exactly when the base field has characteristic \(2\) and the underlying group has even order [16; Thm. 16.5.4].
- Conformal-field theory (CFT) code— Even self-dual binary codes and even unimodular lattices define CFTs [17–19]. Self-dual ternary codes define superconformal field theories (SCFTs) [20].
- Niemeier lattice— The nine inequivalent \([24,12]\) doubly even self-dual codes [6] yield certain Niemeier lattices via Construction A [21]. Niemeier lattices can be constructed from ternary self-dual codes of length 24 [22].
- 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 [11,23,24]. Even self-dual binary codes and even unimodular lattices define CFTs [17–19].
- Combinatorial design— Self-dual extremal codes yield combinatorial \(\leq 5\)-designs using the Assmus-Mattson theorem [25] (see [26; Sec. 5.4]). See [27; Table 1.61, pg. 683] for a table of combinatorial designs obtained from self-dual codes.
- Binary quadratic-residue (QR) code— The length-\(72\) extended binary quadratic-residue code is self-dual but not extremal [1; Rem. 4.3.10].
- \((16,256,6)\) Nordstrom-Robinson (NR) code— The NR code is self-dual in that its distance distribution is invariant under the MacWilliams transform [28]. It maps to the octacode, a self-dual code over \(\mathbb{Z}_4\) under the Gray map [30–32][29; Sec. 6.3].
- Reed-Muller (RM) code— The codes RM\((r,m)\) and RM\((m-r-1,m)\) are dual to each other, with the case \(m = 2r+1\) being self dual.
- Quasi-cyclic code— Quasi-cyclic self-dual constructions include double circulant codes and, in odd characteristic, their negacirculant analogs such as double negacirculant and four-negacirculant codes [1; Sec. 4.4].
- Generalized RM (GRM) code— The dual of a GRM code is also a GRM code [33,34].
- \([5,3,3]_4\) Shortened hexacode— The hexacode and the shortened hexacode are extremal [12; Tab. 9.14][35; Tm. 12].
- \([11,6,5]_3\) Ternary Golay code— The extended ternary Golay code is self-dual, i.e., a Type III code in the terminology of [1; Rems. 4.2.6 and 4.3.2].
- Cyclic linear \(q\)-ary code— See Refs. [36,37] for tables of cyclic self-dual codes.
- \(q\)-ary duadic code— Under certain conditions, extended odd-like duadic codes are self-dual [38; Sec. 2.7].
- 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 [21].
- Self-dual code over \(\mathbb{Z}_4\)— Under the Gray map, any self-dual code over \(\mathbb{Z}_4\) maps to a formally self-dual binary code [39].
- Self-dual polytope code— Self-dual polytope codes are spherical analogues of self-dual linear codes.
- Jump code— Iso-dual codes can be used to construct jump codes [40].
- Hermitian qubit code— Hermitian qubit codes are constructed from Hermitian self-orthogonal linear codes over \(\mathbb{F}_4\) via the \(\mathbb{F}_4\) representation. This relation yields bounds on self-dual codes over \(\mathbb{F}_4\) [41].
- Triorthogonal code— Self-dual binary codes can be used to construct triorthogonal codes [42].
Primary Hierarchy
Parents
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 [43; Thm. 27.4.1][12; Thm. 9.10.3].
Self-dual linear codes are over fields, which are also rings.
Self-dual linear code
Children
Karlin codes are Euclidean self-dual doubly even codes [44; Ch. 16], and some of them are extremal [45,46].
The extended Golay code is the unique \([24,12,8]\) code, and in particular the unique self-dual doubly even code with those parameters [47][1; Rem. 4.3.11].
The \([48,24,12]\) code is the unique self-dual doubly even code with those parameters [48][1; Rem. 4.3.11].
The \([8,4,4]\) extended Hamming code is the smallest doubly even self-dual code, and the unique Type II code of length \(8\) [1; Rem. 4.3.10].
The hexacode is Hermitian self-dual [1; Rem. 4.2.6] and, as a result, is also trace-Hermitian self-dual additive [12; Sec. 9.10]. The hexacode and the shortened hexacode are extremal [12; Tab. 9.14][35; Tm. 12].
The RS\(_4\) is the smallest Type II Euclidean self-dual code [11; Sec. 2.4.2].
The tetracode is Euclidean self-dual, i.e., Type III in the terminology of [1; Rems. 4.2.6 and 4.3.2].
References
- [1]
- S. Bouyuklieva, “Self-dual codes.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [2]
- N. Sloane, “Is there a (72,36) d = 16 self-dual code? (Corresp.)”, IEEE Transactions on Information Theory 19, 251 (1973) DOI
- [3]
- S. Dougherty, J.-L. Kim, and P. Solé, “Open Problems in Coding Theory”, Contemporary Mathematics 79 (2015) DOI
- [4]
- E. M. Rains and N. J. A. Sloane, “Self-Dual Codes”, (2002) arXiv:math/0208001
- [5]
- K. Betsumiya, M. Harada, and A. Munemasa, “A complete classification of doubly even self-dual codes of length 40”, (2012) arXiv:1104.3727
- [6]
- 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
- [7]
- E. M. Rains and N. J. A. Sloane, “Self-dual codes,” in Handbook of Coding Theory, Vol. I, Part 1, eds. V. S. Pless and W. C. Huffman (Elsevier, 1998), pp. 177-294
- [8]
- W. Cary Huffman, “On the classification and enumeration of self-dual codes”, Finite Fields and Their Applications 11, 451 (2005) DOI
- [9]
- M. Harada and A. Munemasa, “A complete classification of ternary self-dual codes of length 24”, Journal of Combinatorial Theory, Series A 116, 1063 (2009) DOI
- [10]
- M. Harada, A. Munemasa, and B. Venkov, “Classification of ternary extremal self-dual codes of length 28”, Mathematics of Computation 78, 1787 (2008) DOI
- [11]
- Self-Dual Codes and Invariant Theory (Springer-Verlag, 2006) DOI
- [12]
- W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
- [13]
- S. Bouyuklieva, “Some optimal self-orthogonal and self-dual codes”, Discrete Mathematics 287, 1 (2004) DOI
- [14]
- M. Harada, “Binary extremal self-dual codes of length 60 and related codes”, Designs, Codes and Cryptography 86, 1085 (2017) arXiv:1706.01694 DOI
- [15]
- P. Gaborit and A. Otmani, “Experimental constructions of self-dual codes”, Finite Fields and Their Applications 9, 372 (2003) DOI
- [16]
- W. Willems, “Codes in Group Algebras.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [17]
- K. S. NARAIN, “New Heterotic String Theories in Uncompactified Dimensions < 10”, Current Physics–Sources and Comments 246 (1989) DOI
- [18]
- L. Dolan, P. Goddard, and P. Montague, “Conformal field theory, triality and the monster group”, Physics Letters B 236, 165 (1990) DOI
- [19]
- L. Dolan, P. Goddard, and P. Montague, “Conformal field theories, representations and lattice constructions”, Communications in Mathematical Physics 179, 61 (1996) arXiv:hep-th/9410029 DOI
- [20]
- D. Gaiotto and T. Johnson-Freyd, “Holomorphic SCFTs with small index”, Canadian Journal of Mathematics 74, 573 (2021) arXiv:1811.00589 DOI
- [21]
- 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
- [22]
- P. S. Montague, “A new construction of lattices from codes over GF(3)”, Discrete Mathematics 135, 193 (1994) DOI
- [23]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [24]
- J. Henriksson and B. McPeak, “Averaging over codes and an \(SU(2)\) modular bootstrap”, (2023) arXiv:2208.14457
- [25]
- E. F. Assmus Jr. and H. F. Mattson Jr., “New 5-designs”, Journal of Combinatorial Theory 6, 122 (1969) DOI
- [26]
- V. D. Tonchev, “Codes and designs.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [27]
- C. J. Colbourn, editor , CRC Handbook of Combinatorial Designs (CRC Press, 2010) DOI
- [28]
- W. Kantor, “On the inequivalence of generalized Preparata codes”, IEEE Transactions on Information Theory 29, 345 (1983) DOI
- [29]
- S. T. Dougherty, “Codes over rings.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [30]
- A. R. Calderbank, A. R. Hammons, P. V. Kumar, N. J. A. Sloane, and P. Solé, “A linear construction for certain Kerdock and Preparata codes”, (1993) arXiv:math/9310227
- [31]
- G. D. Forney Jr., N. J. A. Sloane, and M. D. Trott. “The Nordstrom-Robinson code is the binary image of the octacode.” In Coding and Quantization: DIMACS/IEEE workshop 1992 Oct 19 (pp. 19-26). American Mathematical Society
- [32]
- Z. X. Wan, Quaternary Codes (WORLD SCIENTIFIC, 1997) DOI
- [33]
- P. Delsarte, J. M. Goethals, and F. J. Mac Williams, “On generalized ReedMuller codes and their relatives”, Information and Control 16, 403 (1970) DOI
- [34]
- N. Ron-Zewi and M. Sudan, “A new upper bound on the query complexity for testing generalized Reed-Muller codes”, (2012) arXiv:1204.5467
- [35]
- G. Höhn, “Self-dual Codes over the Kleinian Four Group”, (2000) arXiv:math/0005266
- [36]
- Yan Jia, San Ling, and Chaoping Xing, “On Self-Dual Cyclic Codes Over Finite Fields”, IEEE Transactions on Information Theory 57, 2243 (2011) DOI
- [37]
- 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
- [38]
- C. Ding, “Cyclic Codes over Finite Fields.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [39]
- A. Bonnecaze, P. Sole, and A. R. Calderbank, “Quaternary quadratic residue codes and unimodular lattices”, IEEE Transactions on Information Theory 41, 366 (1995) DOI
- [40]
- T. Beth, C. Charnes, M. Grassl, G. Alber, A. Delgado, and M. Mussinger, Designs, Codes and Cryptography 29, 51 (2003) DOI
- [41]
- A. R. Kalra and S. Prakash, “Invariant Theory, Magic State Distillation, and Bounds on Classical Codes”, (2026) arXiv:2501.10163
- [42]
- M. Shi, H. Lu, J.-L. Kim, and P. Sole, “Triorthogonal Codes and Self-dual Codes”, (2024) arXiv:2408.09685
- [43]
- M. F. Ezerman, “Quantum Error-Control Codes.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [44]
- F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (Elsevier, 1977)
- [45]
- M. Karlin, V. K. Bhargava, and S. E. Tavares, “A note on extended quaternary quadratic residue codes and their binary images”, Information and Control 38, 148 (1978) DOI
- [46]
- K. Betsumiya, T. A. Gulliver, M. Harada, and A. Munemasa, “On Type II codes over F/sub 4/”, IEEE Transactions on Information Theory 47, 2242 (2001) DOI
- [47]
- P. Delsarte and J. M. Goethals, “Unrestricted codes with the golay parameters are unique”, Discrete Mathematics 12, 211 (1975) DOI
- [48]
- 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
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