Encyclopedia

Dual code

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated March 10, 2024

In coding theory, the dual code of a linear code

$C\subset \mathbb {F} _{q}^{n}$

is the linear code defined by

$C^{\perp }=\{x\in \mathbb {F} _{q}^{n}\mid \langle x,c\rangle =0\;\forall c\in C\}$

where

$\langle x,c\rangle =\sum _{i=1}^{n}x_{i}c_{i}$

is a scalar product. In linear algebra terms, the dual code is the annihilator of C with respect to the bilinear form $\langle \cdot \rangle$ . The dimension of C and its dual always add up to the length n:

$\dim C+\dim C^{\perp }=n.$

A generator matrix for the dual code is the parity-check matrix for the original code and vice versa. The dual of the dual code is always the original code.

01Self-dual codes

A self-dual code is one which is its own dual. This implies that n is even and dim C = n/2. If a self-dual code is such that each codeword's weight is a multiple of some constant $c>1$ , then it is of one of the following four types:

Type I codes are binary self-dual codes which are not doubly even. Type I codes are always even (every codeword has even Hamming weight).
Type II codes are binary self-dual codes which are doubly even.
Type III codes are ternary self-dual codes. Every codeword in a Type III code has Hamming weight divisible by 3.
Type IV codes are self-dual codes over F₄. These are again even.

Codes of types I, II, III, or IV exist only if the length n is a multiple of 2, 8, 4, or 2 respectively.

If a self-dual code has a generator matrix of the form $G=[I_{k}|A]$ , then the dual code $C^{\perp }$ has generator matrix $[-{\bar {A}}^{T}|I_{k}]$ , where $I_{k}$ is the $(n/2)\times (n/2)$ identity matrix and ${\bar {a}}=a^{q}\in \mathbb {F} _{q}$ .

Watch videos about Dual codeExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Dual code”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.