Error-Detecting and Correcting Codes

Let us examine a simple model of a communications system for transmitting and receiving coded messages ().

Uncoded messages may be composed of letters or characters, but typically they consist of binary \(m\)-tuples. These messages are encoded into codewords, consisting of binary \(n\)-tuples, by a device called an encoder. The message is transmitted and then decoded. We will consider the occurrence of errors during transmission. An error occurs if there is a change in one or more bits in the codeword. A decoding scheme is a method that either converts an arbitrarily received \(n\)-tuple into a meaningful decoded message or gives an error message for that \(n\)-tuple. If the received message is a codeword (one of the special \(n\)-tuples allowed to be transmitted), then the decoded message must be the unique message that was encoded into the codeword. For received non-codewords, the decoding scheme will give an error indication, or, if we are more clever, will actually try to correct the error and reconstruct the original message. Our goal is to transmit error-free messages as cheaply and quickly as possible.

The even parity system is easy to implement, but has two drawbacks. First, multiple errors are not detectable. Suppose an A is sent and the first and seventh bits are changed from \(0\) to \(1\). The received word is a codeword, but will be decoded into a C instead of an A. Second, we do not have the ability to correct errors. If the 8-tuple \((\codeword{1001}\; \codeword{1000})\) is received, we know that an error has occurred, but we have no idea which bit has been changed. We will now investigate a coding scheme that will not only allow us to detect transmission errors but will actually correct the errors.

The coding scheme presented in is not a complete solution to the problem because it does not account for the possibility of multiple errors. For example, either a \((\codeword{000})\) or a \((\codeword{111})\) could be sent and a \((\codeword{001})\) received. We have no means of deciding from the received word whether there was a single error in the third bit or two errors, one in the first bit and one in the second. No matter what coding scheme is used, an incorrect message could be received. We could transmit a \((\codeword{000})\), have errors in all three bits, and receive the codeword \((\codeword{111})\). It is important to make explicit assumptions about the likelihood and distribution of transmission errors so that, in a particular application, it will be known whether a given error detection scheme is appropriate. We will assume that transmission errors are rare, and, that when they do occur, they occur independently in each bit; that is, if \(p\) is the probability of an error in one bit and \(q\) is the probability of an error in a different bit, then the probability of errors occurring in both of these bits at the same time is \(pq\). We will also assume that a received \(n\)-tuple is decoded into a codeword that is closest to it; that is, we assume that the receiver uses maximum-likelihood decoding. This section requires a knowledge of probability, but can be skipped without loss of continuity.

A binary symmetric channel is a model that consists of a transmitter capable of sending a binary signal, either a \(0\) or a \(1\), together with a receiver. Let \(p\) be the probability that the signal is correctly received. Then \(q = 1 - p\) is the probability of an incorrect reception. If a \(1\) is sent, then the probability that a \(1\) is received is \(p\) and the probability that a \(0\) is received is \(q\) (). The probability that no errors occur during the transmission of a binary codeword of length \(n\) is \(p^{n}\). For example, if \(p=0.999\) and a message consisting of 10,000 bits is sent, then the probability of a perfect transmission is \[\begin{aligned}\end{aligned}\].

Condensed — the full section is in Judson, Abstract Algebra: Theory and Applications.

If we are to develop efficient error-detecting and error-correcting codes, we will need more sophisticated mathematical tools. Group theory will allow faster methods of encoding and decoding messages. A code is an \((n, m)\)-block code if the information that is to be coded can be divided into blocks of \(m\) binary digits, each of which can be encoded into \(n\) binary digits. More specifically, an \((n, m)\)-block code consists of an encoding function \[\begin{aligned}\end{aligned}\] and a decoding function \[\begin{aligned}\end{aligned}\]. A codeword is any element in the image of \(E\). We also require that \(E\) be one-to-one so that two information blocks will not be encoded into the same codeword. If our code is to be error-correcting, then \(D\) must be onto.

Let \({\mathbf x} = (x_1, \ldots, x_n)\) and \({\mathbf y} = (y_1, \ldots, y_n)\) be binary \(n\)-tuples. The Hamming distance or distance, \(d({\mathbf x}, {\mathbf y})\), between \({\mathbf x}\) and \({\mathbf y}\) is the number of bits in which \({\mathbf x}\) and \({\mathbf y}\) differ. The distance between two codewords is the minimum number of transmission errors required to change one codeword into the other. The minimum distance for a code, \(d_{\min}\), is the minimum of all distances \(d({\mathbf x}, {\mathbf y})\), where \({\mathbf x}\) and \({\mathbf y}\) are distinct codewords. The weight, \(w({\mathbf x})\), of a binary codeword \({\mathbf x}\) is the number of \(1\)s in \({\mathbf x}\). Clearly, \(w({\mathbf x}) = d({\mathbf x}, {\mathbf 0})\), where \({\mathbf 0} = (\codeword{00 \cdots 0})\). \(d(\mathbf x, \mathbf y)\) Hamming distance between \(\mathbf x\) and \(\mathbf y\) \(d_{\min}\) the minimum distance of a code \(w(\mathbf x)\) the weight of \(\mathbf x\)

The following proposition lists some basic properties about the weight of a codeword and the distance between two codewords. The proof is left as an exercise.

Condensed — the full section is in Judson, Abstract Algebra: Theory and Applications.

Modern coding theory began in 1948 with C. Shannon's paper, A Mathematical Theory of Information [7]. This paper offered an example of an algebraic code, and Shannon's Theorem proclaimed exactly how good codes could be expected to be. Richard Hamming began working with linear codes at Bell Labs in the late 1940s and early 1950s after becoming frustrated because the programs that he was running could not recover from simple errors generated by noise. Coding theory has grown tremendously in the past several decades. The Theory of Error-Correcting Codes, by MacWilliams and Sloane [5], published in 1977, already contained over 1500 references. Linear codes (Reed-Muller \((32, 6)\)-block codes) were used on NASA's Mariner space probes. More recent space probes such as Voyager have used what are called convolution codes. Currently, very active research is being done with Goppa codes, which are heavily dependent on algebraic geometry.