Data compression

 

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.