Dual linear code[1]


For any \([n,k]_q\) linear code \(C\), the dual (or orthogonal) code, \begin{align} C^\perp = \{ y\in GF(q)^{n} ~|~ x\cdot y=0 \forall x\in C\}, \tag*{(1)}\end{align} where the ordinary, standard, or Euclidean inner product is \(x\cdot y = \sum_{i=1}^n x_i y_i\) for coordinates \(x_i,y_i\).

A code that is contained in its dual, \(C \subseteq C^\perp\), is called self-orthogonal or weakly self-dual. A code that contains its dual, \(C^\perp \subseteq C\), is called dual-containing. A code that is equal to its dual, \(C^\perp = C\), is called self-dual. The dual of a dual code is the original code. A code is dual-containing iff its dual is self-orthogonal.

The dual code \(C^\perp\) is the row space of the parity check matrix of \(C\). The dual code is the kernel of the encoding map for \(C\), and \(\dim C^\perp = n-k\).

An alternative definition of dual substitutes the Euclidean inner product for the Hermitian inner product, \begin{align} x\cdot y \to x\cdot \bar{y} = \sum_{i=1}^n x_i y^{p}_i~. \tag*{(2)}\end{align} Self-dual codes with respect to the above product are called Hermitian self-dual; similar definitions hold for self-orthogonal and dual-containing.

More general inner products can also be considered [2].


The dual of an \([n,k,d] \) code is an \([n,n-k,d'']\) code, where \(d''\) is not always related to \(d\). The generator matrix of \(C^\perp\) is the parity check matrix of \(C\), and visa versa.

The minimum distance of a binary self-dual code satisfies \begin{align} d\leq 4\left[\frac{n}{24}\right]+4 \tag*{(3)}\end{align} unless \(n = 22\) modulo four [3].

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}\).


See books [4][5] for more on self-dual codes.See Refs. [6][7] for constructions of binary self-dual codes.See Tables of Self-Dual Codes 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. [8].



  • Divisible code — Binary self-dual codes are singly-even. The minimum distance of doubly-even binary self-dual codes asymptotically satisfies \(d\leq0.1664n+o(n)\) [9].
  • Dual lattice code — Dual lattices are lattice analogues of dual codes. There are several parallels between (doubly-even) self-dual binary codes and (even) unimodular lattices [10][4]. There are also parallels between self-dual codes over \(\mathbb{Z}_{2k}\) and even unimodular lattices [11].
  • Niemeier lattice code — Niemeier lattice codes can be constructed from ternary self-dual codes of length 24 [12].
  • Golay code — The extended Golay code is self-dual.
  • Hadamard code — The Hadamard code is the dual of the extended Hamming Code.
  • Reed-Muller (RM) code — The codes RM\((r,m)\) and RM\((m-r-1,m)\) are dual to each other.
  • Cyclic linear \(q\)-ary code — See Refs. [13][14] for tables of cyclic self-dual codes.
  • Maximum distance separable (MDS) code — A linear binary or \(q\)-ary \([n,k,n-k+1]\) code is MDS if and only if its dual \([n,n-k,k+1]\) is MDS ([1], Thm. 1.9.13).
  • Dual additive code — The difference between the definitions of dual linear and dual additive codes is in the trace used in the inner product. Self-dual linear codes are also self-dual additive codes.
  • Dodecacode — The dodecacode is self-dual.
  • Hexacode — The hexacode is Euclidean and Hermitian self-dual.
  • Ternary Golay Code — The extended ternary Golay code is self-dual.
  • Tetracode — The tetracode is self-dual.
  • Calderbank-Shor-Steane (CSS) stabilizer code — CSS codes for which \(C_X=C_Z \equiv C\) are called self-orthogonal since \(C^{\perp} \subseteq C\). The stabilizer group of such codes is invariant under the Hadamard gate exchanging \(X\) and \(Z\).
  • Majorana stabilizer code — Classical self-orthogonal codes can be used to construct Majorana stabilizer codes [15]. The direct relationship between the two codes follows from expressing the Majorana strings as binary vectors – akin to the binary symplectic representation – and observing that the binary stabilizer matrix \(S\) for such a Majorana stabilizer code satisfies \(S\cdot S^T=0\) because it has commuting stabilizers, which is precisely the condition \(G\cdot G^T=0\) on the generator matrix \(G\) of a self-orthogonal classical code. A self-orthogonal classical code \(C\) with parameters \([2N,k,d]\) yields a Majorana stabilizer code with parameters \([[N,N-k,d^\perp]]_f\), where \(d^\perp\) is the code distance of the dual code \(C^\perp\).
  • Qubit stabilizer code — Symplectic representations of stabilizer group elements form a linear code over \(GF(2)\) that is self-orthogonal with respect to the symplectic inner product ([1], Thm. 27.3.6).
  • Stabilizer code over \(GF(4)\) — If the classical additive code of quaternary vectors corresponding a stabilizer code over \(GF(4)\) is linear, then the code is self-orthogonal with respect to both the trace-Hermitian and Hermitian inner products ([1], Thm. 27.4.1). In other words, the extra trace operation can be removed from the definition of inner product.
  • True Galois-qudit stabilizer code — Hermitian self-orthogonal linear codes over \(GF(q^2)\) yield true stabilizer codes via either the symplectic representation (showing self-orthogonality under the trace-symplectic inner product; see Ref. [16], Corr. 1) or the stabilizer-over-\(GF(q^2)\) construction (showing self-orthogonality under the trace-alternating inner product; see Ref. [17], Corr. 19 or Ref. [1], Thm. 27.3.8).


W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
Y. Fan and L. Zhang, “Galois self-dual constacyclic codes”, Designs, Codes and Cryptography 84, 473 (2016) DOI
E. M. Rains, “Shadow bounds for self-dual codes”, IEEE Transactions on Information Theory 44, 134 (1998) DOI
Self-Dual Codes and Invariant Theory (Springer-Verlag, 2006) DOI
W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes (Cambridge University Press, 2003) DOI
S. Bouyuklieva, “Some optimal self-orthogonal and self-dual codes”, Discrete Mathematics 287, 1 (2004) DOI
M. Harada, “Binary extremal self-dual codes of length 60 and related codes”, Designs, Codes and Cryptography 86, 1085 (2017) arXiv:1706.01694 DOI
P. Gaborit and A. Otmani, “Experimental constructions of self-dual codes”, Finite Fields and Their Applications 9, 372 (2003) DOI
I. Krasikov and S. Litsyn, “Linear programming bounds for doubly-even self-dual codes”, IEEE Transactions on Information Theory 43, 1238 (1997) DOI
J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
E. Bannai et al., “Type II codes, even unimodular lattices, and invariant rings”, IEEE Transactions on Information Theory 45, 1194 (1999) DOI
P. S. Montague, “A new construction of lattices from codes over GF(3)”, Discrete Mathematics 135, 193 (1994) DOI
Yan Jia, San Ling, and Chaoping Xing, “On Self-Dual Cyclic Codes Over Finite Fields”, IEEE Transactions on Information Theory 57, 2243 (2011) DOI
S. Jitman et al., “Abelian Codes in Principal Ideal Group Algebras”, IEEE Transactions on Information Theory 59, 3046 (2013) DOI
S. Vijay and L. Fu, “Quantum Error Correction for Complex and Majorana Fermion Qubits”, (2017) arXiv:1703.00459
A. Ashikhmin and E. Knill, “Nonbinary quantum stabilizer codes”, IEEE Transactions on Information Theory 47, 3065 (2001) DOI
A. Ketkar et al., “Nonbinary stabilizer codes over finite fields”, (2005) arXiv:quant-ph/0508070
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: dual

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

Cite as:

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

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