Dual code

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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.

Self-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:^[1]

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}$ .