Dual code

From Wikipedia, the free encyclopedia

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}^p

and p is the characteristic of Fq. In linear algebra terms, the dual code is the annihilator of C with respect to the bilinear form <,>. The dimension of C and its dual always add up to n:

\dim C + \dim C^\perp = n.

The dual of the dual code is always the original code.

For binary codes, the dual code consists of all code words, as binary strings, that have 1s in places overlapping the 1s in each word from C always at an even number of locations.

[edit] 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. Self-dual codes can be classified into 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 F4. 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.