section-error-detecting-correcting-codes.ipynb

Kernel:

%%html
<link href="http://mathbook.pugetsound.edu/beta/mathbook-content.css" rel="stylesheet" type="text/css" />
<link href="https://aimath.org/mathbook/mathbook-add-on.css" rel="stylesheet" type="text/css" />
<style>.subtitle {font-size:medium; display:block}</style>
<link href="https://fonts.googleapis.com/css?family=Open+Sans:400,400italic,600,600italic" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700&subset=latin,latin-ext" rel="stylesheet" type="text/css" /><!-- Hide this cell. -->
<script>
var cell = $(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    $('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>

Important: to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the "Run" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard.

ParseError: KaTeX parse error: \newcommand{\lt} attempting to redefine \lt; use \renewcommand

Section8.1Error-Detecting and Correcting Codes

¶

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

Figure8.1Encoding and decoding 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 . The message is transmitted and then decoded. We will consider the occurrence of errors during transmission. An occurs if there is a change in one or more bits in the codeword. A 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.

Example8.2

One possible coding scheme would be to send a message several times and to compare the received copies with one another. Suppose that the message to be encoded is a binary $n$-tuple $(x_{1}, x_{2}, \ldots, x_{n})\text{.}$ The message is encoded into a binary $3n$-tuple by simply repeating the message three times:

$$\begin{equation*} (x_{1}, x_{2}, \ldots, x_{n}) \mapsto (x_{1}, x_{2}, \ldots, x_{n}, x_{1}, x_{2}, \ldots, x_{n}, x_{1}, x_{2}, \ldots, x_{n}). \end{equation*}$$

To decode the message, we choose as the $i$th digit the one that appears in the $i$th place in at least two of the three transmissions. For example, if the original message is $(0110)\text{,}$ then the transmitted message will be $(0110\; 0110\; 0110)\text{.}$ If there is a transmission error in the fifth digit, then the received codeword will be $(0110\; 1110\; 0110)\text{,}$ which will be correctly decoded as $(0110)\text{.}$²We will adopt the convention that bits are numbered left to right in binary $n$-tuples. This triple-repetition method will automatically detect and correct all single errors, but it is slow and inefficient: to send a message consisting of $n$ bits, $2n$ extra bits are required, and we can only detect and correct single errors. We will see that it is possible to find an encoding scheme that will encode a message of $n$ bits into $m$ bits with $m$ much smaller than $3n\text{.}$

Example8.3

, a commonly used coding scheme, is much more efficient than the simple repetition scheme. The ASCII (American Standard Code for Information Interchange) coding system uses binary 8-tuples, yielding $2^{8} = 256$ possible 8-tuples. However, only seven bits are needed since there are only $2^7 = 128$ ASCII characters. What can or should be done with the extra bit? Using the full eight bits, we can detect single transmission errors. For example, the ASCII codes for A, B, and C are

$$\begin{align*} \text{A} & = 65_{10} = 01000001_{2},\\ \text{B} & = 66_{10} = 01000010_{2},\\ \text{C} & = 67_{10} = 01000011_{2}. \end{align*}$$

Notice that the leftmost bit is always set to 0; that is, the 128 ASCII characters have codes

$$\begin{align*} 00000000_{2} & = 0_{10},\\ & \vdots\\ 01111111_{2} & = 127_{10}. \end{align*}$$

The bit can be used for error checking on the other seven bits. It is set to either 0 or 1 so that the total number of 1 bits in the representation of a character is even. Using even parity, the codes for A, B, and C now become

$$\begin{align*} \text{A} & = 01000001_{2},\\ \text{B} & = 01000010_{2},\\ \text{C} & = 11000011_{2}. \end{align*}$$

Suppose an A is sent and a transmission error in the sixth bit is caused by noise over the communication channel so that $(0100\; 0101)$ is received. We know an error has occurred since the received word has an odd number of 1s, and we can now request that the codeword be transmitted again. When used for error checking, the leftmost bit is called a .

By far the most common error-detecting codes used in computers are based on the addition of a parity bit. Typically, a computer stores information in $m$-tuples called . Common word lengths are 8, 16, and 32 bits. One bit in the word is set aside as the parity check bit, and is not used to store information. This bit is set to either 0 or 1, depending on the number of 1s in the word.

Adding a parity check bit allows the detection of all single errors because changing a single bit either increases or decreases the number of 1s by one, and in either case the parity has been changed from even to odd, so the new word is not a codeword. (We could also construct an error detection scheme based on ; that is, we could set the parity check bit so that a codeword always has an odd number of 1s.)

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 $(1001\; 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.

Transmitted	Received Word
Codeword	000	001	010	011	100	101	110	111
000	0	1	1	2	1	2	2	3
111	3	2	2	1	2	1	1	0

Table8.4A repetition code

Example8.5

Suppose that our original message is either a 0 or a 1, and that 0 encodes to (000) and 1 encodes to (111). If only a single error occurs during transmission, we can detect and correct the error. For example, if a 101 is received, then the second bit must have been changed from a 1 to a 0. The originally transmitted codeword must have been (111). This method will detect and correct all single errors.

In Table 8.4, we present all possible words that might be received for the transmitted codewords (000) and (111). Table 8.4 also shows the number of bits by which each received 3-tuple differs from each original codeword.

SubsectionMaximum-Likelihood Decoding

¶

The coding scheme presented in Example 8.5 is not a complete solution to the problem because it does not account for the possibility of multiple errors. For example, either a (000) or a (111) could be sent and a (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 (000), have errors in all three bits, and receive the 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\text{.}$ 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 .³This section requires a knowledge of probability, but can be skipped without loss of continuity.

Figure8.6Binary symmetric channel

A 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$ (Figure 8.6). The probability that no errors occur during the transmission of a binary codeword of length $n$ is $p^{n}\text{.}$ 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{equation*} (0.999)^{10,000} \approx 0.00005. \end{equation*}$$

Theorem8.7

If a binary $n$-tuple $(x_{1}, \ldots, x_{n})$ is transmitted across a binary symmetric channel with probability $p$ that no error will occur in each coordinate, then the probability that there are errors in exactly $k$ coordinates is

$$\begin{equation*} \binom{n}{k} q^kp^{n - k}. \end{equation*}$$

Proof

Fix $k$ different coordinates. We first compute the probability that an error has occurred in this fixed set of coordinates. The probability of an error occurring in a particular one of these $k$ coordinates is $q\text{;}$ the probability that an error will not occur in any of the remaining $n-k$ coordinates is $p\text{.}$ The probability of each of these $n$ independent events is $q^{k}p^{n-k}\text{.}$ The number of possible error patterns with exactly $k$ errors occurring is equal to

$$\begin{equation*} \binom{n}{k} = \frac{n!}{k!(n - k)!}, \end{equation*}$$

the number of combinations of $n$ things taken $k$ at a time. Each of these error patterns has probability $q^{k}p^{n-k}$ of occurring; hence, the probability of all of these error patterns is

$$\begin{equation*} \binom{n}{k} q^{k}p^{n - k}. \end{equation*}$$

Example8.8

Suppose that $p = 0.995$ and a 500-bit message is sent. The probability that the message was sent error-free is

$$\begin{equation*} p^{n} = (0.995)^{500} \approx 0.082. \end{equation*}$$

The probability of exactly one error occurring is

$$\begin{equation*} \binom{n}{1} qp^{n - 1}= 500(0.005)(0.995)^{499} \approx 0.204. \end{equation*}$$

The probability of exactly two errors is

$$\begin{equation*} \binom{n}{2} q^{2}p^{n - 2}= \frac{500 \cdot 499}{2}(0.005)^{2}(0.995)^{498} \approx 0.257. \end{equation*}$$

The probability of more than two errors is approximately

$$\begin{equation*} 1 - 0.082 - 0.204 - 0.257 = 0.457. \end{equation*}$$

SubsectionBlock Codes

¶

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)$- 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

$$\begin{equation*} E:{\mathbb Z}^{m}_{2} \rightarrow {\mathbb Z}^{n}_{2} \end{equation*}$$

and a

$$\begin{equation*} D:{\mathbb Z}^{n}_{2} \rightarrow {\mathbb Z}^{m}_{2}. \end{equation*}$$

A is any element in the image of $E\text{.}$ 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.

Example8.9

The even-parity coding system developed to detect single errors in ASCII characters is an $(8,7)$-block code. The encoding function is

$$\begin{equation*} E(x_7, x_6, \ldots, x_1) = (x_8, x_7, \ldots, x_1), \end{equation*}$$

where $x_8 = x_7 + x_6 + \cdots + x_1$ with addition in ${\mathbb Z}_2\text{.}$

Let ${\mathbf x} = (x_1, \ldots, x_n)$ and ${\mathbf y} = (y_1, \ldots, y_n)$ be binary $n$-tuples. The or , $d({\mathbf x}, {\mathbf y})\text{,}$ 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 for a code, $d_{\min}\text{,}$ is the minimum of all distances $d({\mathbf x}, {\mathbf y})\text{,}$ where ${\mathbf x}$ and ${\mathbf y}$ are distinct codewords. The , $w({\mathbf x})\text{,}$ of a binary codeword ${\mathbf x}$ is the number of 1s in ${\mathbf x}\text{.}$ Clearly, $w({\mathbf x}) = d({\mathbf x}, {\mathbf 0})\text{,}$ where ${\mathbf 0} = (00 \cdots 0)\text{.}$

Example8.10

Let ${\mathbf x} = (10101)\text{,}$ ${\mathbf y} = (11010)\text{,}$ and ${\mathbf z} = (00011)$ be all of the codewords in some code $C\text{.}$ Then we have the following Hamming distances:

$$\begin{equation*} d({\mathbf x},{\mathbf y}) = 4, \qquad d({\mathbf x},{\mathbf z}) = 3, \qquad d({\mathbf y},{\mathbf z}) = 3. \end{equation*}$$

The minimum distance for this code is 3. We also have the following weights:

$$\begin{equation*} w({\mathbf x}) = 3, \qquad w({\mathbf y}) = 3, \qquad w({\mathbf z}) = 2. \end{equation*}$$

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.

Proposition8.11

Let ${\mathbf x}\text{,}$ ${\mathbf y}\text{,}$ and ${\mathbf z}$ be binary $n$-tuples. Then

1. $w({\mathbf x}) = d( {\mathbf x}, {\mathbf 0})\text{;}$

2. $d( {\mathbf x}, {\mathbf y}) \geq 0\text{;}$

3. $d( {\mathbf x}, {\mathbf y}) = 0$ exactly when ${\mathbf x} = {\mathbf y}\text{;}$

4. $d( {\mathbf x}, {\mathbf y})= d( {\mathbf y}, {\mathbf x})\text{;}$

5. $d( {\mathbf x}, {\mathbf y}) \leq d( {\mathbf x}, {\mathbf z}) + d( {\mathbf z}, {\mathbf y})\text{.}$

The weights in a particular code are usually much easier to compute than the Hamming distances between all codewords in the code. If a code is set up carefully, we can use this fact to our advantage.

Suppose that ${\mathbf x} = (1101)$ and ${\mathbf y} = (1100)$ are codewords in some code. If we transmit (1101) and an error occurs in the rightmost bit, then (1100) will be received. Since (1100) is a codeword, the decoder will decode (1100) as the transmitted message. This code is clearly not very appropriate for error detection. The problem is that $d({\mathbf x}, {\mathbf y}) = 1\text{.}$ If ${\mathbf x} = (1100)$ and ${\mathbf y} = (1010)$ are codewords, then $d({\mathbf x}, {\mathbf y}) = 2\text{.}$ If ${\mathbf x}$ is transmitted and a single error occurs, then ${\mathbf y}$ can never be received. Table 8.12 gives the distances between all 4-bit codewords in which the first three bits carry information and the fourth is an even parity check bit. We can see that the minimum distance here is 2; hence, the code is suitable as a single error-detecting code.

	0000	0011	0101	0110	1001	1010	1100	1111
0000	0	2	2	2	2	2	2	4
0011	2	0	2	2	2	2	4	2
0101	2	2	0	2	2	4	2	2
0110	2	2	2	0	4	2	2	2
1001	2	2	2	4	0	2	2	2
1010	2	2	4	2	2	0	2	2
1100	2	4	2	2	2	2	0	2
1111	4	2	2	2	2	2	2	0

Table8.12Distances between 4-bit codewords

To determine exactly what the error-detecting and error-correcting capabilities for a code are, we need to analyze the minimum distance for the code. Let ${\mathbf x}$ and ${\mathbf y}$ be codewords. If $d({\mathbf x}, {\mathbf y}) = 1$ and an error occurs where ${\mathbf x}$ and ${\mathbf y}$ differ, then ${\mathbf x}$ is changed to ${\mathbf y}\text{.}$ The received codeword is ${\mathbf y}$ and no error message is given. Now suppose $d({\mathbf x}, {\mathbf y}) = 2\text{.}$ Then a single error cannot change ${\mathbf x}$ to ${\mathbf y}\text{.}$ Therefore, if $d_{\min} = 2\text{,}$ we have the ability to detect single errors. However, suppose that $d({\mathbf x}, {\mathbf y}) = 2\text{,}$ ${\mathbf y}$ is sent, and a noncodeword ${\mathbf z}$ is received such that

$$\begin{equation*} d({\mathbf x}, {\mathbf z}) = d({\mathbf y}, {\mathbf z}) = 1. \end{equation*}$$

Then the decoder cannot decide between ${\mathbf x}$ and ${\mathbf y}\text{.}$ Even though we are aware that an error has occurred, we do not know what the error is.

Suppose $d_{\min} \geq 3\text{.}$ Then the maximum-likelihood decoding scheme corrects all single errors. Starting with a codeword ${\mathbf x}\text{,}$ an error in the transmission of a single bit gives ${\mathbf y}$ with $d({\mathbf x}, {\mathbf y}) = 1\text{,}$ but $d({\mathbf z}, {\mathbf y}) \geq 2$ for any other codeword ${\mathbf z} \neq {\mathbf x}\text{.}$ If we do not require the correction of errors, then we can detect multiple errors when a code has a minimum distance that is greater than or equal to 3.

Theorem8.13

Let $C$ be a code with $d_{\min} = 2n + 1\text{.}$ Then $C$ can correct any $n$ or fewer errors. Furthermore, any $2n$ or fewer errors can be detected in $C\text{.}$

Proof

Suppose that a codeword ${\mathbf x}$ is sent and the word ${\mathbf y}$ is received with at most $n$ errors. Then $d( {\mathbf x}, {\mathbf y}) \leq n\text{.}$ If ${\mathbf z}$ is any codeword other than ${\mathbf x}\text{,}$ then

$$\begin{equation*} 2n+1 \leq d( {\mathbf x}, {\mathbf z}) \leq d( {\mathbf x}, {\mathbf y}) + d( {\mathbf y}, {\mathbf z}) \leq n + d( {\mathbf y}, {\mathbf z}). \end{equation*}$$

Hence, $d({\mathbf y}, {\mathbf z} ) \geq n+1$ and ${\mathbf y}$ will be correctly decoded as ${\mathbf x}\text{.}$ Now suppose that ${\mathbf x}$ is transmitted and ${\mathbf y}$ is received and that at least one error has occurred, but not more than $2n$ errors. Then $1 \leq d( {\mathbf x}, {\mathbf y} ) \leq 2n\text{.}$ Since the minimum distance between codewords is $2n +1\text{,}$ ${\mathbf y}$ cannot be a codeword. Consequently, the code can detect between 1 and $2n$ errors.

Example8.14

In Table 8.15, the codewords ${\mathbf c}_1 = (00000)\text{,}$ ${\mathbf c}_2 = (00111)\text{,}$ ${\mathbf c}_3 = (11100)\text{,}$ and ${\mathbf c}_4 = (11011)$ determine a single error-correcting code.

	00000	00111	11100	11011
00000	0	3	3	4
00111	3	0	4	3
11100	3	4	0	3
11011	4	3	3	0

Table8.15Hamming distances for an error-correcting code

SubsectionHistorical Note

¶

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.