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 [1].
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 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}\).
Parent
Child
Cousins
- Dual lattice code — Dual lattices are lattice analogues of dual codes.
- Combinatorial design code — Linear codes and their duals are related to combinatorial designs via the Assmus-Mattson theorem [2] (see [3; Sec. 5.4]).
- Hadamard code — The Hadamard code is the dual of the extended Hamming Code. Conversely, the shortened Hadamard code is the dual of the Hamming Code.
- Reed-Muller (RM) code — The codes RM\((r,m)\) and RM\((m-r-1,m)\) are dual to each other.
- 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 [4; Thm. 1.9.13].
- Dual additive code — Different inner products are typically used to define duals of linear and additive codes.
- Self-dual additive code — The difference between the definitions of dual linear and dual additive codes is in the trace used in the inner product.
- Dual code over \(R\)
- Majorana stabilizer code — Classical self-orthogonal codes can be used to construct Majorana stabilizer codes [5]. 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 CSS 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\).
- Qubit stabilizer code — Binary symplectic representations of stabilizer group elements form a linear code over \(GF(2)\) that is self-orthogonal with respect to the symplectic inner product [6; Thm. 27.3.6].
- 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. [7], Corr. 1) or the stabilizer-over-\(GF(q^2)\) construction (showing self-orthogonality under the trace-alternating inner product; see [8; Corr. 19][6; Thm. 27.3.8].
References
- [1]
- Y. Fan and L. Zhang, “Galois self-dual constacyclic codes”, Designs, Codes and Cryptography 84, 473 (2016) DOI
- [2]
- E. F. Assmus Jr. and H. F. Mattson Jr., “New 5-designs”, Journal of Combinatorial Theory 6, 122 (1969) DOI
- [3]
- V. D. Tonchev, "Codes and designs." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [4]
- W. C. Huffman, J.-L. Kim, and P. Solé, "Basics of coding theory." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [5]
- S. Vijay and L. Fu, “Quantum Error Correction for Complex and Majorana Fermion Qubits”, (2017) arXiv:1703.00459
- [6]
- M. F. Ezerman, "Quantum Error-Control Codes." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [7]
- A. Ashikhmin and E. Knill, “Nonbinary quantum stabilizer codes”, IEEE Transactions on Information Theory 47, 3065 (2001) DOI
- [8]
- A. Ketkar et al., “Nonbinary stabilizer codes over finite fields”, (2005) arXiv:quant-ph/0508070
Page edit log
- Victor V. Albert (2022-07-22) — most recent
- Micah Shaw (2022-06-28)
- Victor V. Albert (2021-12-18)
- Dhruv Devulapalli (2021-12-17)
Cite as:
“Dual linear code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/dual