Dual linear code

Dual linear code[1]

Description

For any \([n,k]\) binary or \(q\)-ary linear code \(C\), the dual code, \begin{align} C^\perp = \{ y\in GF(q)^{\times n} ~|~ x\cdot y=0 \forall x\in C\}, \end{align} 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\).

A code that contains its dual, \(C^\perp \subseteq C\), is called weakly self-dual or self-orthogonal. 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.

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.

Parent

Error-correcting code (ECC)

Cousins

Calderbank-Shor-Steane (CSS) stabilizer code — CSS codes for which \(C_X=C_Z \equiv C\) are called weakly self-dual since \(C^{\perp} \subseteq C\). The stabilizer group of such codes is invariant under the Hadamard gate exchanging \(X\) and \(Z\).
Hadamard code — The Hadamard code is the dual of the extended Hamming Code.
Majorana stabilizer code — Classical weakly self-dual codes can be used to construct Majorana stabilizer codes [2]. 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 weakly self-dual classical code. A weakly self-dual 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\).

References

[1]: W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021). DOI
[2]: Sagar Vijay and Liang Fu, “Quantum Error Correction for Complex and Majorana Fermion Qubits”. 1703.00459

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/properties/dual.yml.