Distance, Detection and Correction

The previous chapter, Capacity and Shannon's Theorem, closed on a random code of 16 codewords of 12 bits in which two pairs of codewords differed in only 2 positions, so the code barely beat sending each message bit three times. The coding theorem proves that good codes exist but builds none, and a random draw leaves to chance the property that matters most, the distance between codewords. This chapter makes that distance the design target.

Channels, Signals and Likelihoods built the binary symmetric channel $\text{BSC}(p)$, which flips each bit independently with probability $p$, and the binary erasure channel, which loses a bit openly instead of flipping it, and Capacity and Shannon's Theorem measured how many bits per use such channels carry.

The chapter defines the distance between two words, pictures every word of $n$ bits as a corner of a cube, and proves from the smallest distance $d$ between codewords how many errors a code detects, how many it corrects, and how many errors and erasures it handles together. The same counting then prices the checks in daily use, single parity, the ISBN and Luhn check digits and rectangular parity, and the chapter ends with the Gray code, which uses a distance of one on purpose.

Every number in the chapter is recomputed by ch08_distance_detection_and_correction.py in the python/ folder of the companion repository ecc-book-lab, and the charts are drawn by ch08_charts.py in the same folder.

01.Distance and Weight

Take $x = 10110$ and $y = 11011$ and compare them position by position from the left. They disagree in positions 2, 3 and 5, so three single-bit flips turn one into the other, and no fewer will do, since each disagreeing position must be flipped at least once. XOR, written $\oplus$, gives 1 where two bits differ and 0 where they agree, so $10110 \oplus 11011 = 01101$ marks the disagreements in one step, as Figure 1 shows.

Distance is never negative, it is zero only for equal words, and it is symmetric. The fourth property of a distance, the triangle inequality, rests on a lemma that uses the bitwise AND, written $a \wedge b$, which is 1 only where both words hold a 1. For the example, $10110 \wedge 11011 = 10010$.

On the example the right side is $3 + 4 - 2 \times 2 = 3$, the weight of $01101$.

Proof. Let $k$ count the positions where both words hold a 1, and $u$ and $v$ the positions where only $a$ or only $b$ does. Then $w(a) = k + u$, $w(b) = k + v$ and $w(a \wedge b) = k$. The XOR is 1 exactly in the $u + v$ positions where one word holds a 1, so $w(a \oplus b) = u + v = w(a) + w(b) - 2k$. $\blacksquare$

Proof. Let $a = x \oplus y$ and $b = y \oplus z$. XOR can be regrouped freely, like addition, and a word XORed with itself is all zeros, so $a \oplus b = x \oplus z$. By Equation 1 and Equation 2,

$$d(x, z) = w(a \oplus b) = w(a) + w(b) - 2\,w(a \wedge b) \le w(a) + w(b) = d(x, y) + d(y, z),$$

since a weight is never negative. $\blacksquare$

Equality holds when $a \wedge b$ is all zeros, so that no flip on the way from $x$ to $y$ is undone on the way to $z$. With $x = 00000$, $y = 01101$ and $z = 11011$ the inequality reads $4 \le 3 + 3$, and the detour costs two extra flips.

Errors fit the same picture. Write what the channel does as an error pattern $e$, a word with a 1 wherever a bit flipped. A sent codeword $c$ arrives as $c \oplus e$, at distance $w(c \oplus e \oplus c) = w(e)$ from $c$, so the received word lies exactly as far from what was sent as the number of errors.

02.Minimum Distance

The four words $00000$, $01101$, $10110$ and $11011$ form a small code, called $C_5$ in this chapter. Table 1 lists all six pairs of its codewords.

No two codewords are fewer than 3 flips apart, and that single number turns out to decide what the code can detect and correct.

$C_5$ is a $(5, 4, 3)$ code of rate $2/5$. For scale, the four 2-bit words have $d = 1$, the even-weight 3-bit words $000$, $011$, $101$ and $110$ have $d = 2$, and the repetition code $R_3$ of The Repetition Code, with codewords $000$ and $111$, has $d = 3$. Checking every pair takes $M(M - 1)/2$ comparisons, but every XOR in the table is itself a codeword of $C_5$, and that gives a shortcut.

Proof. Such a code contains the all-zero word $0$, since $c \oplus c = 0$. For different codewords $c$ and $c'$, the distance $w(c \oplus c')$ is the weight of a nonzero codeword. Conversely, every nonzero codeword $c$ has weight $w(c) = d(0, c)$, a distance between two codewords. The two lists hold the same numbers, so they have the same smallest value. $\blacksquare$

For $C_5$ the nonzero weights are 3, 3 and 4, so $d = 3$ follows from three weights instead of six distances. Codes closed under XOR are the subject of the Part Linear Block Codes.

The random code of the previous chapter shows what happens without design. Figure 2 counts its 120 pairs by distance. The mean is 6.11, near the $n/2 = 6$ expected for random words, but two pairs, $110000101100$ with $110000111000$ and $110010011110$ with $110011010110$, sit at distance 2. That is what chance predicts. A second random word lies within distance 2 of a first when it is one of the $1 + 12 + 66 = 79$ such words, which happens with probability $79/4096 = 0.0193$, so 120 pairs are expected to hold 2.31 close pairs. The dots give the same expectation, $120\binom{12}{k}/4096$, at every distance $k$.

Those two pairs dominate the failures. At $p = 0.01$ the previous chapter's decoder fails on a block with probability 0.0032306, and the four codewords in the close pairs, a quarter of the code, account for 0.82 of that, because one flip in either position where a close pair differs leaves the received word halfway between them.

03.The Geometry of the Binary Cube

The Repetition Code drew the eight 3-bit words as the corners of a cube, with an edge between words that differ in one bit. The $n$-cube does the same for all $2^n$ words of $n$ bits. Each word has $n$ neighbors and each edge joins two words, so the $n$-cube has $n\,2^n/2 = n\,2^{n-1}$ edges, 12 for $n = 3$ and 32 for $n = 4$. Walking an edge flips one bit, so the shortest walk from $x$ to $y$ has exactly $d(x, y)$ edges, since each differing position must be flipped once and flipping them one at a time suffices.

Table 2 lists the radius-1 balls of $R_3$ in the 3-cube, and those of the fourfold code $R_4$, with codewords $0000$ and $1111$, in the 4-cube.

The two balls of $R_3$ share no word and hold all 8, as Figure 3 shows, so every received word is within one flip of exactly one codeword. The balls of $R_4$ hold 10 of the 16 words. The six words of weight 2 lie at distance 2 from both codewords and point to neither, and Figure 4 draws them in the middle column.

Proof. The words at distance exactly $i$ from $c$ are the words $c \oplus e$ with $w(e) = i$, and different patterns give different words. A pattern of weight $i$ is a choice of $i$ positions out of $n$, and Counting Errors with the Binomial Distribution counted $\binom{n}{i}$ such choices. Adding over $i$ from 0 to $t$ gives the ball. $\blacksquare$

For $t = 1$ the sum is $1 + n$, the sizes 4 and 5 in the table. If the balls of radius $t$ around $M$ codewords share no word, they hold $M\,V(n, t)$ of the $2^n$ words, so

This is the sphere-packing bound, also called the Hamming bound after Hamming's 1950 paper [1], and Correcting Errors shows that it applies to every code that corrects $t$ errors. For $C_5$ the four balls of size $V(5, 1) = 6$ hold 24 of the 32 words. Sixteen codewords of 6 bits cannot correct one error, since $16 \times 7 = 112$ exceeds $2^6 = 64$, but at length 7 the count is $16 \times 8 = 128 = 2^7$, and the Hamming $(7, 4)$ code of the Part Linear Block Codes fills the 7-cube with no word to spare.

04.Detecting Errors

Send $01101$ from $C_5$ and let the channel flip positions 3 and 4, the pattern $00110$. The received word $01011$ is at distances 3, 2, 4 and 1 from $00000$, $01101$, $10110$ and $11011$. It is not a codeword, so the receiver knows something went wrong, though its nearest codeword, $11011$, was not the one sent. Flip positions 1, 3 and 4 instead, the pattern $10110$, and the receiver gets $11011$, a codeword, with no sign that anything happened.

Proof. Let $c$ be sent and $1 \le w(e) \le d - 1$. The received word is at distance $w(e) > 0$ from $c$, so it differs from $c$. If it were another codeword $c'$, then $d(c, c') = w(e) < d$, contradicting the definition of $d$, so it is flagged. For the second part, take codewords $c$ and $c'$ at distance exactly $d$. The pattern $e = c \oplus c'$ has weight $d$ and turns $c$ into $c'$, which the detector accepts. $\blacksquare$

For $C_5$ the guarantee covers one and two errors, and the pattern $10110$ that escaped is the XOR of two codewords at distance 3. Most heavier patterns are caught as well, and for a code closed under XOR the escapes are easy to name. The word $c \oplus e$ is a codeword exactly when $e$ is, so the patterns that escape are the nonzero codewords, whichever codeword was sent. Write $A_i$ for the number of codewords of weight $i$. Each pattern of weight $i$ occurs on $\text{BSC}(p)$ with probability $p^i (1 - p)^{n - i}$, so the probability of an undetected error is

$C_5$ has $A_3 = 2$ and $A_4 = 1$, so $P_{ud} = 2p^3 (1 - p)^2 + p^4 (1 - p)$, which is $1.9701 \times 10^{-6}$ at $p = 0.01$, against $1 - 0.99^5 = 0.049010$ for any error at all. Of the ten patterns of weight 3, only the two that are codewords escape.

05.Correcting Errors

Suppose $C_5$ delivers $10111$. Its distances to the four codewords are 4, 3, 1 and 2, so the nearest is $10110$, one flip away. Decisions by Bayes' Rule showed why nearest is right. On $\text{BSC}(p)$ with $p < 1/2$ and equally likely codewords, a codeword at distance $k$ from the received word has likelihood $p^k (1 - p)^{n - k}$, which shrinks as $k$ grows, so the nearest codeword is the most likely one.

Proof. If a word $y$ were within $t$ of two codewords $c$ and $c'$, the triangle inequality would give $d(c, c') \le 2t < d$, which is impossible, so the balls are disjoint. A pattern with $w(e) \le t$ leaves $c \oplus e$ in the ball of $c$ and no other, and the decoder returns $c$. The condition $d \ge 2t + 1$ means $t \le (d - 1)/2$, whose largest whole solution is the rounded-down value. For the last part, take codewords $c$ and $c'$ at distance $d$ and flip $t + 1$ of the positions where they differ, starting from $c$. If $d = 2t + 1$, the word reached is within $t$ of $c'$ and is miscorrected. If $d = 2t + 2$, it is $t + 1$ from both and is flagged. $\blacksquare$

As $d$ runs from 1 to 7, $t$ runs through 0, 0, 1, 1, 2, 2 and 3, about half the detection guarantee $d - 1$, because a corrected word must stay nearer its own codeword than any other. An even distance leaves a word exactly halfway, which Figure 5 shows being flagged.

Proof. Since $t \le s$, the condition gives $2t \le d - 1$, so the correction bound covers weights up to $t$. Now let $t < w(e) \le s$. The received word is more than $t$ from $c$, so the decoder cannot return $c$. If it returned another codeword $c'$, then $c'$ would be within $t$ of the received word, and the triangle inequality would give $d(c, c') \le s + t \le d - 1$, which is impossible. So the word is flagged. $\blacksquare$

$R_4$, with $d = 4$, takes $t = 1$ and $s = 2$, correcting $0001$ to $0000$ and flagging $0011$. $R_5$, with $d = 5$, can correct one error and flag two or three, or correct two and flag nothing beyond them, in which case three errors on $00000$, such as $00111$, are miscorrected to $11111$. Which is better depends on whether a wrong answer costs more than a resend, the question of the next chapter.

06.Errors and Erasures Together

An erasure is a symbol marked as lost, the event of the binary erasure channel in Three Discrete Channels, and the receiver knows where it is. Take the code $E_6$ with codewords $000000$, $001111$, $110011$ and $111100$, whose minimum distance is 4. Send $110011$, erase position 3 and flip position 6. The receiver gets $11?010$ and compares only the five positions it trusts, as Table 3 shows.

The nearest codeword on those positions is $110011$, the one sent, recovered despite one error and one erasure.

Proof. Delete the $e$ erased positions from every codeword. Each deletion removes at most one difference between two codewords, so the shortened codewords still differ pairwise in at least $d - e$ positions, and since $d - e > 2t \ge 0$, no two have become equal. On the kept positions the received word holds exactly $t$ errors. By the correction bound, nearest-codeword decoding recovers the sent codeword when $d - e \ge 2t + 1$, which is $2t + e < d$. $\blacksquare$

The bound is tight. The codewords $000000$ and $001111$ differ in positions 3 to 6, and erasing those four, so that $e = d$, leaves both reading $00????$. An erasure costs half an error, so with no errors a code fills $d - 1$ erasures, twice the errors it corrects. For $d = 4$ that allows up to 3 erasures, or one error with one erasure. Even single parity, with $d = 2$, fills one erasure, since the missing bit must make the count of 1s even, the idea behind Parity as a spare disk.

07.Single Parity

The even-weight code of $n$ bits, the single parity check of Detecting Instead of Correcting, holds every word with an even number of 1s. Flipping one bit makes the count odd, so $d = 2$, and parity does better than the detection bound promises.

Proof. The checker computes the XOR of all received bits. For $c \oplus e$ this equals the XOR of the bits of $c$, which is 0 because $c$ has even weight, combined with the XOR of the bits of $e$, which is 1 exactly when $w(e)$ is odd. $\blacksquare$

Detecting Instead of Correcting wrote $E$ and $O$ for the total probability of the even-weight and the odd-weight error patterns on $\text{BSC}(p)$, and showed from the binomial theorem that $E + O = 1$ and $E - O = (1 - 2p)^n$. Subtracting the two gives $2O = 1 - (1 - 2p)^n$, the chance that the checker raises its alarm.

For $n = 8$ and $p = 0.01$, $0.98^8 = 0.850763$, so the alarm sounds with probability 0.074618. Some error occurs with probability $1 - 0.99^8 = 0.077255$, so errors slip through with probability 0.0026368. The share of corrupted words the checker flags is its coverage,

which here is 0.96587, or 96.6%. The approximation keeps terms up to $p^2$. By the binomial theorem $(1 - 2p)^n \approx 1 - 2np + 2n(n - 1)p^2$ and $(1 - p)^n \approx 1 - np + \tfrac12 n(n - 1)p^2$, so the alarm probability is about $np - n(n - 1)p^2$ and the chance of some error about $np - \tfrac12 n(n - 1)p^2$. Dividing both by $np$ and writing $a = (n - 1)p$, the coverage is about $(1 - a)/(1 - a/2) \approx (1 - a)(1 + a/2) \approx 1 - a/2$, which is 0.965 for $n = 8$. Misses grow with length because they are mostly pairs of errors, and a longer word holds more pairs.

Figure 6 plots the coverage. At $p = 0.01$ a 32-bit word covers 0.86561 and a 64-bit word 0.76469. At $p = 1/2$ every received word is equally likely and half have even weight, so the coverage is $2^{n-1}/(2^n - 1)$, which is $128/255 = 0.50196$ for $n = 8$.

In hardware the XOR of all the bits is the parity tree of The parity tree, and a lab later in this Part checks the parity detection formula against simulated channels.

08.Check Digits

People who copy numbers make two common mistakes. A substitution replaces one digit with another, and an adjacent swap exchanges two neighbors, typing 72 for 27. A check digit is an extra digit chosen so that a weighted sum of all the digits meets a fixed rule, and Gallian surveys the schemes in use [2] [3]. Catching every substitution means that two valid numbers differ in at least two digits, a minimum distance of 2, which says nothing yet about swaps. The arithmetic uses congruence. For a modulus $m$, $a \equiv b \pmod{m}$ means that $a - b$ is a multiple of $m$, so $116 \equiv 6 \pmod{11}$ because $116 = 10 \times 11 + 6$.

ISBN-10

An ISBN-10 is ten digits $x_1, \dots, x_{10}$, read from the left, of which the tenth is the check, chosen so that

The weights run from 10 down to 1, and a check value of 10 is written X. Table 4 finds the check digit for 0-13-042672, the start of the ISBN of Lin and Costello's textbook [4].

The sum 116 leaves remainder 6 modulo 11, so the check digit, with weight 1, is $11 - 6 = 5$, and 0-13-042672-5 has weighted sum $121 = 11 \times 11$.

Proof. Substituting $b$ for $a$ where the weight is $w$ changes the sum by $w(b - a)$, with $1 \le w \le 10$ and $b - a$ nonzero and between $-10$ and 10, so neither factor is a multiple of 11. Because 11 is prime, a product is a multiple of 11 only when a factor is, which is Euclid's lemma, so the change is not a multiple of 11. Swapping $a$ at weight $w_i$ with $b$ at weight $w_j$ changes the sum by $w_i b + w_j a - w_i a - w_j b = (w_i - w_j)(b - a)$. The weights differ, so $w_i - w_j$ is nonzero and between $-9$ and 9, and again neither factor is a multiple of 11. $\blacksquare$

The proof needs a prime modulus and distinct weights, and the price is the eleventh symbol X.

ISBN-13

Since 1 January 2007 ISBNs have 13 digits. An older book's ISBN-13 puts 978 in front of the first nine digits of its ISBN-10 and computes a new check digit by the rule of the 13-digit EAN barcode on retail goods, with weights alternating 1 and 3 from the left and modulus 10,

Table 5 applies the rule to the same book. The terms add to 93, so the check digit 7 brings the sum to 100, and the number is 978-0-13-042672-7.

Proof. A substitution changes the sum by $w(b - a)$ with $w$ equal to 1 or 3. For $w = 1$ the change is nonzero and between $-9$ and 9. For $w = 3$, if $3(b - a)$ were a multiple of 10, so would be $7 \times 3(b - a) = 20(b - a) + (b - a)$, and hence $b - a$, which is impossible. Neighbors carry the weights 1 and 3, so a swap changes the sum by $\pm 2(b - a)$, a multiple of 10 exactly when $b - a$ is a multiple of 5, that is, when the digits differ by 5. Positions two apart carry equal weights, so a swap there changes nothing. $\blacksquare$

The pairs that differ by 5, such as 2 and 7, are 10 of the 90 ordered pairs of different digits, so ISBN-13 catches $80/90$, or 88.9%, of adjacent swaps. The worked example An ISBN-13 Swap That Slips Through follows one. The weights are not to blame. In any weighted sum modulo 10, an even weight $w$ makes $5w$ a multiple of 10 and a weight divisible by 5 makes $2w$ one, so some substitution in that position escapes. Catching every substitution therefore forces odd weights, the difference of two odd weights is even, and an even number times 5 is a multiple of 10. No weighted sum of decimal digits modulo 10 catches every substitution and every adjacent swap.

The Luhn formula

The Luhn formula, patented by Hans Peter Luhn of IBM in 1960 [5] and used on payment card numbers, escapes that limit by not being a weighted sum. Number the digits from the right, the check digit being digit 1. Every digit in an even position is doubled, and 9 is subtracted when the result exceeds 9. Writing $y_j$ for the $j$-th digit from the right and $D(x)$ for the doubled value, a number is valid when

Doubling sends the digits $0, 1, \dots, 9$ to $0, 2, 4, 6, 8, 1, 3, 5, 7, 9$, each digit exactly once. For 314159265, the first nine digits of $\pi$, the check digit is 3. Table 6 checks 3141592653 and two corrupted copies.

Proof. A substitution changes the sum by $b - a$ or by $D(b) - D(a)$. Both are nonzero, the second because $D$ sends different digits to different digits, and both lie between $-9$ and 9, so neither is a multiple of 10. Of two neighbors exactly one is doubled. If $a$ starts in the doubled position, the pair contributes $D(a) + b$ before the swap and $D(b) + a$ after, a change of $f(b) - f(a)$ with $f(x) = D(x) - x$. For $x = 0, \dots, 9$, $f$ takes the values $0, 1, 2, 3, 4, -4, -3, -2, -1, 0$, so $f(b) - f(a)$ lies between $-8$ and 8 and is a multiple of 10 only when it is 0. The function $f$ repeats only the value 0, at $x = 0$ and $x = 9$, so only that swap escapes. Positions two apart are both doubled or both not, so a swap there leaves the sum unchanged. $\blacksquare$

The swap in the table changed the sum by $f(9) - f(5) = 4$. Only 2 of the 90 ordered pairs escape, so Luhn catches 97.8% of adjacent swaps. The companion script confirms this on numbers of 10 and 16 digits and on all 10,000 valid five-digit strings, and shows that the weights 1, 3, 1, 3, 1 in place of doubling let 10 pairs through. Figure 7 compares the three schemes.

09.Rectangular Parity

One parity bit detects an error but cannot locate it. Arrange the data in a grid with a parity bit for each row and each column, and the crossing of a failed row and a failed column points at the error. Figure 8 sends 16 data bits as a 4 by 4 array with rows 1011, 0110, 1101 and 0010. The row parities are 1, 0, 1 and 1, the column parities 0, 0, 1 and 0, and a corner bit, 1, makes both the parity row and the parity column even. The channel flips the data bit in row 3, column 2.

In Table 7 only row 3 and column 2 fail, so the decoder flips the bit where they cross. The scheme spends 25 bits on 16, a rate of $16/25 = 0.64$, and its power follows from its minimum distance.

Proof. The XOR of two valid arrays is valid, since each parity bit is the XOR of the bits it covers, so it suffices to find the smallest weight of a nonzero valid array, in which every row and column holds an even number of 1s. A row holding a 1 holds at least two, in columns $j$ and $j'$, and each of those columns holds a second 1 in another row, so the weight is at least 4. With exactly four, the second 1s of columns $j$ and $j'$ share a row, or each of their rows would hold a single 1, so the array is a rectangle. Conversely every row and column of a rectangle is even, and an array whose rows and columns are all even is valid, because its data bits produce exactly the parity bits present. Two rows and two columns can be chosen in $\binom{5}{2}^2 = 100$ ways. $\blacksquare$

With $d = 4$ the budget allows correcting one error and detecting two, the guarantee of $R_4$ at a rate of 0.64 instead of 0.25. The companion script confirms that all 25 single errors are corrected and all 300 double errors flagged. Three errors can deceive the decoder. With errors at $(1, 1)$, $(1, 3)$ and $(3, 1)$, written as (row, column), row 1 and column 1 hold two errors each and stay even, so only row 3 and column 3 fail, the signature of one error at $(3, 3)$. Flipping that bit completes a rectangle and delivers a valid array that was not sent. Grid codes like this, called product codes, go back to Elias [6], and later Parts build much stronger ones.

10.Gray Codes

A rotary sensor reports which of eight sectors a shaft points into, as a 3-bit word read from three tracks. In plain binary the boundary from sector 3, $011$, to sector 4, $100$, changes all three bits, and since the tracks never switch at exactly the same instant, a reading mid-change can catch any of the $2^3 = 8$ combinations, such as $111$, sector 7. If neighboring sectors had words differing in one bit, a reading mid-change could only return one of the two sectors involved.

The reflected construction builds one for every $n$. Start from the 1-bit list 0, 1. To go from $n$ bits to $n + 1$, write the list with a 0 in front, then the same list reversed with a 1 in front. This gives 00, 01, 11, 10, and then 000, 001, 011, 010, 110, 111, 101, 100, the walk of Figure 9. Inside each half neighbors differ in one bit because the shorter list did, and at the middle and at the wrap the two words differ only in the front bit.

A formula gives the word in position $b$ directly. Write $b$ in binary, with bits numbered from 0 at the right to $n - 1$ at the left, and let $b \gg 1$ be $b$ shifted right one place, dropping its last bit and putting a 0 in front. Then

Table 8 applies it to every 4-bit position and reproduces the reflected list, whose first eight entries without their leading 0 are the 3-bit list. The companion script confirms that the formula and the construction agree for every length up to 8.

Proof. Since $b < 2^n - 1$, it ends in a 0 followed by $k$ 1s. Adding 1 turns those 1s into 0s and that 0 into a 1, so $m = b \oplus (b + 1)$ is $k + 1$ 1s at the right end. Shifting distributes over XOR, so $g(b) \oplus g(b + 1) = m \oplus (m \gg 1)$, and since $m \gg 1$ is $k$ 1s at the right end, the XOR has a single 1, in bit $k$. For the wrap, $2^n - 1$ is all 1s, and $g(2^n - 1) = 11\ldots1 \oplus 01\ldots1 = 10\ldots0$, which differs from $g(0) = 0$ in the top bit only. $\blacksquare$

To convert back, run the formula from the top bit down. XORing $g_i = b_i \oplus b_{i+1}$ with $b_{i+1}$ gives

For $b = 1011$ the shift is $0101$, and $1011 \oplus 0101 = 1110$, the entry for position 11. Going back from $1110$, $b_3 = 1$, $b_2 = 1 \oplus 1 = 0$, $b_1 = 0 \oplus 1 = 1$ and $b_0 = 1 \oplus 0 = 1$, which is $1011$ again.

In the Gray code sector 3 is $010$ and sector 4 is $110$, so the boundary changes one bit and a reading mid-change returns 3 or 4. Frank Gray's 1953 patent described this reflected binary code [7], and the same property makes Gray codes common in shaft encoders and in counters read by circuits on a different clock. As a code, a Gray code has minimum distance 1 and protects nothing against noise. It uses distance the other way, placing consecutive values as close as possible, so an uncertain reading costs one step and never a jump across the range.

11.Looking Ahead

A code of minimum distance $d$ detects $d - 1$ errors, corrects $\lfloor (d - 1)/2 \rfloor$, and handles $t$ errors with $e$ erasures whenever $2t + e < d$. The same counting priced single parity through the parity detection formula, the ISBN and Luhn check digits, and the rectangular array that locates one error.

A guarantee says what a code can do, not what a system should do with it. The next chapter, Error-Control Strategies and Performance, weighs forward error correction against retransmission, prices the retransmission schemes stop-and-wait, go-back-N and selective repeat, measures decoded error rates and coding gain, and defines the reliability measures of real systems, the failure rate in FIT, silent data corruption and the detected but unrecoverable error. The undetected-error probability of Detecting Errors and the parity detection formula are its raw inputs. Hamming's paper [1] introduced much of this chapter's geometry, and Lin and Costello [4] and MacKay [8] carry it further.

12.Worked Examples

13.Exercises

References

1. [1]Hamming, Richard W. (1950). “Error Detecting and Error Correcting Codes.” Bell System Technical Journal, 29(2), pp. 147–160. doi:10.1002/j.1538-7305.1950.tb00463.x
2. [2]Gallian, Joseph A. (1991). “The Mathematics of Identification Numbers.” The College Mathematics Journal, 22(3), pp. 194–202. doi:10.1080/07468342.1991.11973381
3. [3]Gallian, Joseph A. (1996). “Error Detection Methods.” ACM Computing Surveys, 28(3), pp. 504–517. doi:10.1145/243439.243457
4. [4]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.
5. [5]Luhn, Hans Peter (1960). “Computer for Verifying Numbers.” U.S. Patent 2,950,048. https://patents.google.com/patent/US2950048A/en
6. [6]Elias, Peter (1954). “Error-free Coding.” Transactions of the IRE Professional Group on Information Theory, 4(4), pp. 29–37. doi:10.1109/TIT.1954.1057464
7. [7]Gray, Frank (1953). “Pulse Code Communication.” U.S. Patent 2,632,058. https://patents.google.com/patent/US2632058A/en
8. [8]MacKay, David J. C. (2003). “Information Theory, Inference, and Learning Algorithms.” Cambridge University Press. The author's site offers the whole book free to read on screen. https://www.inference.org.uk/itila/book.html