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 data storage. Codes are stud ...
, the dual code of a
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 ...
:
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 matrices ...
terms, the dual code is the
annihilator of ''C'' with respect to the
bilinear form . 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 coor ...
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.
Terminol ...
for the dual code is the
parity-check matrix In coding theory, a parity-check matrix of a linear block code ''C'' is a matrix which describes the linear relations that the components of a codeword must satisfy. It can be used to decide whether a particular vector is a codeword and is also used ...
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
In mathematics an even integer, that is, a number that is divisible by 2, is called evenly even or doubly even if it is a multiple of 4, and oddly even or singly even if it is not. The former names are traditional ones, derived from ancient Gree ...
. Type I codes are always
even
Even may refer to:
General
* Even (given name), a Norwegian male personal name
* Even (surname)
* Even (people), an ethnic group from Siberia and Russian Far East
** Even language, a language spoken by the Evens
* Odd and Even, a solitaire game w ...
(every codeword has even
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 o ...
).
*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