In
coding theory
Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and computer data storage, data sto ...
, the dual code of a
linear code
In coding theory, a linear code is an error-correcting code for which any linear combination of Code word (communication), codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although t ...
:
is the linear code defined by
:
where
:
is a scalar product. In
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrix (mathemat ...
terms, the dual code is the
annihilator of ''C'' with respect to the
bilinear form
In mathematics, a bilinear form is a bilinear map on a vector space (the elements of which are called '' vectors'') over a field ''K'' (the elements of which are called '' scalars''). In other words, a bilinear form is a function that is linea ...
. The
dimension
In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coo ...
of ''C'' and its dual always add up to the length ''n'':
:
A
generator matrix
In coding theory, a generator matrix is a matrix whose rows form a basis for a linear code. The codewords are all of the linear combinations of the rows of this matrix, that is, the linear code is the row space of its generator matrix.
Terminolo ...
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
, 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
The Hamming weight of a string (computer science), 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 mo ...
).
*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
4. 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