Dual linear code[1]

Description

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].

Protection

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

Notes

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].

Parent

Cousins

  • 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).

References

[1]
W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[2]
Y. Fan and L. Zhang, “Galois self-dual constacyclic codes”, Designs, Codes and Cryptography 84, 473 (2016) 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]
I. Krasikov and S. Litsyn, “Linear programming bounds for doubly-even self-dual codes”, IEEE Transactions on Information Theory 43, 1238 (1997) DOI
[10]
J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
[11]
E. Bannai et al., “Type II codes, even unimodular lattices, and invariant rings”, IEEE Transactions on Information Theory 45, 1194 (1999) DOI
[12]
P. S. Montague, “A new construction of lattices from codes over GF(3)”, Discrete Mathematics 135, 193 (1994) DOI
[13]
Yan Jia, San Ling, and Chaoping Xing, “On Self-Dual Cyclic Codes Over Finite Fields”, IEEE Transactions on Information Theory 57, 2243 (2011) DOI
[14]
S. Jitman et al., “Abelian Codes in Principal Ideal Group Algebras”, IEEE Transactions on Information Theory 59, 3046 (2013) DOI
[15]
S. Vijay and L. Fu, “Quantum Error Correction for Complex and Majorana Fermion Qubits”, (2017) arXiv:1703.00459
[16]
A. Ashikhmin and E. Knill, “Nonbinary quantum stabilizer codes”, IEEE Transactions on Information Theory 47, 3065 (2001) DOI
[17]
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
BibTeX:
@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:
https://errorcorrectionzoo.org/c/dual

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.