Dual linear code 

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 self-orthogonal code is called maximal if it is not contained in the dual of any other code. 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. A code that is equivalent to its dual via permutations is called iso-dual. A code admits a complementary dual if \(C\) and \(C^{\perp}\) do not share any codewords. 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\). The automorphism group of a linear binary code and its dual are the same [1; pg. 230].

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^{\perp}]\) code, where the dual distance \(d^{\perp}\) 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

Children

Cousins

  • Dual lattice code — Dual lattices are lattice analogues of dual codes.
  • Combinatorial design — Linear codes and their duals are related to combinatorial designs via the Assmus-Mattson theorem [3,4] (see [5; Sec. 5.4]).
  • Golay code — The dual of the Golay code is its \([23,11,8]\) even-weight subcode [6,7].
  • \([2^m-1,m,2^{m-1}]\) simplex code — Hamming and simplex codes are dual to each other.
  • \([2^r,2^r-r-1,4]\) Extended Hamming code — Extended Hamming and first-order RM codes are dual to each other.
  • \([7,4,3]\) Hamming code — The dual of the Hamming code is its even-weight subcode, the \([7,3,4]\) little Hamming code, also known as the \(S(2,3)\) simplex code [6,7].
  • Hergert code — Hergert codes are duals of DG codes in that their distance distribution is equal to the MacWilliams transform of the distance distribution of DG codes [8]. However, the two codes are images of a pair of mutually dual linear codes over \(\mathbb{Z}_4\) under the Gray map [9,10].
  • Single parity-check (SPC) code — Binary SPCs and repetition codes are dual to each other.
  • Reed-Muller (RM) code — The codes RM\((r,m)\) and RM\((m-r-1,m)\) are dual to each other.
  • Hsu-Anastasopoulos LDPC (HA-LDPC) code — HA-LDPC and MN-LDPC codes are dual to each other [11].
  • 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 [12; Thm. 1.9.13].
  • Dual additive code — Different inner products are typically used to define duals of linear and additive codes.
  • \(q\)-ary simplex code — \(q\)-ary Hamming and \(q\)-ary simplex codes are dual to each other.
  • Dual code over \(R\)
  • Majorana stabilizer code — Classical self-orthogonal codes can be used to construct Majorana stabilizer codes [13]. 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\).
  • Hermitian qubit code — Hermitian qubit codes are constructed from Hermitian self-orthogonal linear codes over \(GF(4)\) via the \(GF(4)\) representation.
  • Qubit CSS code — CSS codes for which \(C_X=C_Z \equiv C\) are called self-orthogonal or homogeneous [14] since \(C^{\perp} \subseteq C\). The stabilizer group of such codes is invariant under the Hadamard gate exchanging \(X\) and \(Z\).
  • Qubit stabilizer code — Qubit stabilizer codes are in one-to-one correspondence with symplectic self-orthogonal binary linear codes of length \(2n\) via the binary symplectic representation.
  • Hermitian Galois-qudit code — Hermitian codes are constructed from Hermitian self-orthogonal linear codes over \(GF(q^2)\) via the \(GF(q^2)\) representation.

References

[1]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[2]
Y. Fan and L. Zhang, “Galois self-dual constacyclic codes”, Designs, Codes and Cryptography 84, 473 (2016) DOI
[3]
E. F. Assmus Jr. and H. F. Mattson Jr., “New 5-designs”, Journal of Combinatorial Theory 6, 122 (1969) DOI
[4]
A. R. Calderbank, P. IDelsarte, and N. J. A. Sloane, “A strengthening of the Assmus-Mattson theorem”, IEEE Transactions on Information Theory 37, 1261 (1991) DOI
[5]
V. D. Tonchev, "Codes and designs." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[6]
W. Feit. Some remarks on weight functions of spaces over GF(2), unpublished (1972)
[7]
C. L. Mallows and N. J. A. Sloane, “Weight enumerators of self-orthogonal codes”, Discrete Mathematics 9, 391 (1974) DOI
[8]
F. B. Hergert, “On the delsarte-goethals codes and their formal duals”, Discrete Mathematics 83, 249 (1990) DOI
[9]
A. R. Hammons et al., “The Z/sub 4/-linearity of Kerdock, Preparata, Goethals, and related codes”, IEEE Transactions on Information Theory 40, 301 (1994) DOI
[10]
A. R. Hammons Jr. et al., “The Z_4-Linearity of Kerdock, Preparata, Goethals and Related Codes”, (2002) arXiv:math/0207208
[11]
K. KASAI and K. SAKANIWA, “Spatially-Coupled MacKay-Neal Codes and Hsu-Anastasopoulos Codes”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E94-A, 2161 (2011) arXiv:1102.4612 DOI
[12]
W. C. Huffman, J.-L. Kim, and P. Solé, "Basics of coding theory." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[13]
S. Vijay and L. Fu, “Quantum Error Correction for Complex and Majorana Fermion Qubits”, (2017) arXiv:1703.00459
[14]
Y.-J. Wang et al., “Construction of Multiple-Rate Quantum LDPC Codes Sharing One Scalable Stabilizer Circuit”, IEEE Transactions on Communications 71, 1071 (2023) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

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/edit/main/codes/classical/q-ary_digits/dual/dual.yml.