Coding theory is the subject devoted to the theory of error-correcting
codes. Errorcorrecting codes were invented to correct
errors over unreliable transmission links. With digital communications and
digital storage media ubiquitous in the modern world, errorcorrecting
codes have grown in importance. Advances in error-correcting codes have made it
possible to transmit information across the solar system using weak
transmitters and to store data robustly on storage media so that it is
resistant to damage, such as scratches on a compact disk.
Error-correcting codes work by encoding data as strings of symbols, such
as bit strings, that contain redundant information that helps identify which
codeword may have been sent when a string of symbols, potentially different
than the string sent, is received. Coding theory is an active area, with new and better
codes being devised at a steady pace.
Definitions:
Let A be any finite set (called an alphabet), and let An denote the set of all n-tuples with entries in A. A block code of
length n containing M codewords over
the alphabet A is a subset of An
of size M. Such a block code is called an [n,M]-code over A.
The Hamming distance d(x, y) between two n-tuples x and y Î
An is the number of entries in
which they differ.
Let C be an [n,M]-code
over A. The Hamming distance of C is the smallest
Hamming distance over all pairs of distinct codewords
in C. If C has Hamming distance d, then C is
sometimes referred to as an [n,M,
d]-code.
The information rate (or rate) of an [n,M]-code over an alphabet
of size q is
R=logq
M/n .
Suppose that a codeword c from a block code is transmitted and r
is received. The error-vector is e = r − c (formed by subtracting componentwise).
The number of errors is the number of nonzero components in e.
A code is said to detect t errors if the decoder is
capable of detecting any pattern of t or fewer errors per codeword that
may be introduced by the channel.
A code is said to correct t errors if the decoder
is capable of correcting any pattern of t or fewer errors per codeword
that may be introduced by the channel.
If C1 and C2 are two [n,M]-codes over an alphabet A, then C1
and C2 are said to be equivalent codes if there
is a fixed permutation of the coordinate positions which transform one code to
the other.
The parity check bit of a bit string is 0 if there are an even number of bits in the string and is 1 if there
are an odd number of bits in the string.
Facts:
1. The main objective of coding theory is the design of
codes such that:
• an efficient
algorithm is known for encoding messages;
• an efficient
algorithm is known for decoding;
• the error-correcting
capability of the code is high;
• the information rate
of the code is high.
2. For applications in which a two-way communications
channel is available (for example, a telephone circuit), it is sometimes
economical to use error detection and retransmission upon error, in a so-called
automatic repeat request (ARQ) strategy, rather than so-called forward
error correction (FEC) techniques capable of actually correcting errors at
the cost of more complex decoding equipment. This is not an option when the
communications channel is effectively one-way or unperturbed source data is not
available for retransmission (for example in CD-ROM storage and deep-space
communications systems).
3. For any n-tuples x,
y, z Î An, the Hamming distance satisfies the following:
• d(x, y) ≥ 0 with equality if and only if x = y;
• d(x, y) = d(y,
x);
• d(x, y) + d(y,
z) ≥ d(x, z).
4. The information rate R of a block code measures
the fraction of information of the code which is non-redundant; the information
rate R satisfies the inequality 0 < R ≤ 1.
5. When a word r is received, the decoder must
make some decision. This decision may be one of the following:
• no errors have
occurred; accept r as a codeword;
• errors have occurred;
correct r to a codeword c;
• errors have occurred; no
correction is possible.
6. Let C be an [n,M, d]-code.
• If used only for
error detection, C can detect d−1 errors.
• If used for error
correction, C can correct
errors.
7. Equivalent codes have the same distance,
and hence the same error-correcting capabilities.
8. Adding a parity check bit to a bit string of length n
produces a bit string of length n+1 with an even number of 0s.
9. Different families of error-correcting codes have
been, and continue to be, designed to meet the particular requirements of
applications. One type of requirement is the ability to correct specific types
of errors. For example, when signals are sent over radio channels, including
those from deep space, interference can produce errors in a run of bits.
Similarly, damage to storage media, such as a compact disk, can produce errors that
come in clusters. Some of the codes designed to correct errors of these types,
known as burst errors, are Reed Solomon codes, interleaved Reed-Solomon
codes and fire codes.
Examples:
1. The code produced by adding a parity check bit to each
bit string of length n can detect a single error. (It detects an odd
number of errors, but not an even number of errors; no error correction is
possible using this code.) For example, suppose the bit string 0111 is received
where the code word sent is a bit string of length three with a parity check
bit added. Since 0111 contains three 1s, it cannot be a codeword. Hence, an
error was made in transmission. This error cannot be corrected. To see this,
note that if exactly one bit error was made in the transmission, any of the codewords 0110, 0101, 0011, and 1111 could have been sent.
2. C = {0100011, 1010101,
1101111} is a [7, 3, 3]-code over the
binary alphabet. The information rate of C is R = log2
3/7 ≈ 0.226.
3. The binary repetition code of length n is
the code C = {00 . . . 0,
11 . . . 1}. The code has
distance n, and so can correct
errors. If used only
for error detection, then C can detect n−1 errors. Although the error-correcting capabilities of C are
very good, its information rate R = 1/n is very poor.