In coding theory

Coding theory

Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...

, the dual code of a linear code

Linear code

In coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although Turbo codes can be seen as a hybrid of these two types. Linear codes allow for...

is the linear code defined by


where


is a scalar product. In linear algebra

Linear algebra

Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...

 terms, the dual code is the annihilator

Annihilator (ring theory)

In mathematics, specifically module theory, annihilators are a concept that generalizes torsion and orthogonal complement.-Definitions:Let R be a ring, and let M be a left R-module. Choose a nonempty subset S of M...

 of C with respect to the bilinear form <,>. The dimension

Dimension (vector space)

In mathematics, the dimension of a vector space V is the cardinality of a basis of V. It is sometimes called Hamel dimension or algebraic dimension to distinguish it from other types of dimension...

 of C and its dual always add up to the length n:


A generator matrix

Generator matrix

In coding theory, a generator matrix is a basis for a linear code, generating all its possible codewords.If the matrix is G and the linear code is C,where w is a codeword of the linear code C, c is a row vector, and a bijection exists between w and c. A generator matrix for an q-code has...

 for the dual code is a parity-check matrix

Parity-check matrix

In coding theory, a parity-check matrix of a linear block code Cis a generator matrix of the dual code. As such, a codeword c is in C if and only if the matrix-vector product Hc=0....

 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 , 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
  Even code
  A binary code is called an even code if the Hamming weight of all its codewords is even. An even code should have a generator polynomial that include minimal polynomial as a product. Furthermore, a binary code is called doubly even if the Hamming weight of all its codewords is divisible by 4...
  
   (every codeword has even Hamming weight
  Hamming weight
  The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the most typical case, a string of bits, this is the number of 1's in the string...
  
  ).
• 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.