Why Codes Exist

Every bit a computer stores or sends is a physical thing, such as a small charge on a capacitor, a voltage on a wire, a pulse of light in a fiber or the phase of a radio wave. Physical things get disturbed. A particle from space passes through a memory chip and knocks a stored 0 into a 1. Noise in a receiver pushes a voltage across the threshold that separates 0 from 1. The machine has no way of noticing. It reads the wrong bit with exactly the same confidence as the right one, and carries on.

An error correction code is the defense. Before a message is stored or sent, a few extra bits are computed from it and attached. The extra bits carry no new information. They are redundancy, chosen so that a damaged message can be recognized as damaged and, given enough redundancy, repaired. Claude Shannon proved in 1948 that reliable communication over a noisy channel is possible at all [1], and Richard Hamming published his single-error-correcting codes two years later [2]. Every phone, disk, memory module and spacecraft built since depends on what followed.

This chapter builds the idea from nothing. It starts with what one flipped bit costs, measures how often flips happen, and sets up the simplest model of a noisy channel. It then builds the simplest code there is, which sends every bit three times and decodes by majority vote, and proves exactly how much reliability that buys and how much it costs. A single parity bit shows the cheaper alternative of detecting errors rather than correcting them, and the chapter closes with a tour of the codes inside memory, networks, radio and spacecraft. Every number in the chapter is recomputed by a short Python program, ch01_why_codes_exist.py, kept in the python/ folder of the book's companion repository, ecc-book-lab, on GitHub. To run it, download the repository from that page, either with git clone https://github.com/anirbanchakraborty-dev/ecc-book-lab or as a ZIP file, and run python3 python/ch01_why_codes_exist.py from its top folder. The program needs nothing beyond Python 3.10, prints each value beside the one the text states, and stops with an error at the first disagreement. The two charts are drawn by ch01_charts.py in the same folder.

01.One Flipped Bit

Start with one byte, 01100100. Reading it as an unsigned binary number means adding up the place values of the positions that hold a 1. Numbering the bits from 0 at the right to 7 at the left, bit $i$ is worth $2^i$, and this byte has ones in bits 6, 5 and 2, so it is $64 + 32 + 4 = 100$.

Now flip one bit. If bit 0, the rightmost, flips from 0 to 1, the byte becomes 01100101 and the value becomes 101. The error is one part in a hundred, the kind of mistake a reading might survive. If instead bit 7 flips, the byte becomes 11100100. Read as unsigned, that is $128 + 64 + 32 + 4 = 228$, more than double the true value. Read as a signed number in two's complement, the format nearly every processor uses for integers, bit 7 is the sign bit and is worth $-128$ rather than $+128$, so the same pattern is $-128 + 64 + 32 + 4 = -28$. One flip has turned a positive hundred into a negative number.

The lesson of Figure 1 is that the cost of an error depends on where it lands, and the hardware has no idea where that is. The same flip that nudges a pixel's brightness by one level can, in another byte, change the sign of an account balance, send a pointer to a random address, or turn one machine instruction into another. A memory cannot store some bits more carefully than others, because it does not know which bits matter. The protection has to cover every bit equally, and it has to be cheap enough to pay on every bit.

02.Where Flips Come From

Flips have physical causes, and the first ones to worry computer designers were found in the late 1970s. Timothy May and Murray Woods traced random errors in dynamic memory to alpha particles emitted by trace radioactive elements in the chip's own packaging [3]. An alpha particle crossing the silicon frees a trail of electric charge, and if enough of it collects on a storage node, the stored value changes. In the same year James Ziegler and William Lanford showed that cosmic rays reaching the ground could do the same [4]. These are soft errors. Nothing is damaged, and writing the bit again repairs it, but whatever read the wrong value has already used it.

Field data show how common this is. A study of the memory in Google's server fleet found that more than 8% of DIMMs, the small boards that carry memory chips, saw at least one error per year, at rates of 25,000 to 70,000 errors per billion device hours per megabit [5].

Eight percent sounds small until it is multiplied out. Suppose a server holds 16 DIMMs and, as a simplifying assumption, each one independently has an 8% chance of an error in a year. The chance that one particular DIMM stays clean all year is $1 - 0.08 = 0.92$. Because the DIMMs are assumed independent, the chance that all 16 stay clean is the product of their separate chances, $0.92^{16}$, and the chance that at least one errs is

$$1 - 0.92^{16} \approx 0.7366.$$

Nearly three servers in four would see a memory error within a year. Real errors are not independent, so the figure illustrates the arithmetic rather than predicting any machine. The step itself, one minus the chance of none, appears again and again in this book, because the chance of none is a product of independent chances and the chance of at least one is not.

Memory is only one source. On a wire or a fiber, thermal noise in the receiver, interference from neighboring signals and the loss of signal strength over distance all push a received voltage toward the wrong side of the decision threshold. In flash storage, the charge that represents a bit leaks away over time and is disturbed when neighboring cells are read and written. In radio, the signal fades as the receiver moves. The causes differ, but each ends the same way, with a bit that reads back wrong.

03.How Often Errors Happen

Engineers summarize a link or a storage device by its bit error rate, the long-run fraction of bits that come out wrong. High-speed serial links are commonly specified at a bit error rate of $10^{-12}$, one wrong bit in a trillion. That sounds like perfection. Multiply it by the speed of the link and it is not.

Take a link running at 8 gigabits per second, so $8 \times 10^9$ bits every second, with a bit error rate of $10^{-12}$. The expected number of errors per second is the number of bits times the chance that each is wrong, $8 \times 10^9 \times 10^{-12} = 0.008$. That is 28.8 errors an hour and 691.2 errors a day. A link that is wrong once in a trillion bits is wrong hundreds of times a day.

Now ask a different question. A file of one terabyte, $10^{12}$ bytes or $N = 8 \times 10^{12}$ bits, is read across the same link. What is the chance that at least one bit is wrong? Each bit is right with probability $1 - p$, where $p = 10^{-12}$, and if errors strike independently, all $N$ bits are right with probability $(1 - p)^N$. So

$$P(\text{at least one error}) = 1 - (1-p)^N.$$

Evaluating that directly is awkward, because $1 - p$ is so close to 1 that an ordinary calculator rounds it to exactly 1. Two inequalities pin the answer down instead, and both are worth proving because they return throughout the book.

Proof. Let $f(x) = e^{-x} - (1 - x)$. Then $f(0) = 1 - 1 = 0$. The derivative of $f$, which measures its slope, is $f'(x) = 1 - e^{-x}$. For $x > 0$, $e^{-x} < 1$, so $f'(x) > 0$ and $f$ is rising. For $x < 0$, $e^{-x} > 1$, so $f'(x) < 0$ and $f$ is falling. The function falls until $x = 0$ and rises after it, so its smallest value is $f(0) = 0$. Therefore $f(x) \ge 0$ for every $x$, which is the claim. $\blacksquare$

Proof. By induction on $n$, which means proving the claim for $n = 0$ and then showing that whenever it holds for some $n$ it also holds for $n + 1$, so that it climbs to every whole number. For $n = 0$ both sides equal 1. Now suppose $(1-p)^n \ge 1 - np$. Multiplying both sides by $1 - p$, which is not negative and so does not reverse the inequality, gives

$$(1-p)^{n+1} \ge (1 - np)(1 - p) = 1 - (n+1)p + np^2 \ge 1 - (n+1)p,$$

where the last step drops the term $np^2$, which is never negative. $\blacksquare$

Proof. $P = 1 - (1-p)^N$. Bernoulli's inequality with $n = N$ gives $(1-p)^N \ge 1 - Np$, so $P \le 1 - (1 - Np) = Np$. The exponential bound with $x = p$ gives $0 \le 1 - p \le e^{-p}$, and raising both sides of an inequality between non-negative numbers to the same power keeps it true, so $(1-p)^N \le e^{-Np}$ and $P \ge 1 - e^{-Np}$. $\blacksquare$

For the terabyte, $Np = 8 \times 10^{12} \times 10^{-12} = 8$. The upper bound says $P \le 8$, which is true and useless, since no probability exceeds 1. The lower bound says $P \ge 1 - e^{-8} = 0.999665$, and the exact value agrees with it to better than one part in a billion. Reading a terabyte across a link that errs once in a trillion bits is almost certain to deliver at least one wrong bit.

For a single 4 KiB page of memory, 4,096 bytes of 8 bits each or $N = 32{,}768$ bits, $Np = 3.2768 \times 10^{-8}$. Now the two bounds squeeze together, and $P = 3.2768 \times 10^{-8}$ to five significant figures. The two cases give the rule of thumb used throughout reliability work. When $Np$ is small, the chance of any error is about $Np$. When $Np$ is large, an error is close to certain.

A link or a disk can be built better, with cleaner signals, better shielding or more charge per cell, but every improvement costs power, area or money, and none of them gets $p$ to zero. Codes take the other route. They accept that bits will flip and arrange for the flips to be caught.

04.A Model of a Noisy Channel

To reason about codes, the messy physics needs a simple model. The simplest, and the one this Part uses throughout, is the binary symmetric channel.

The word symmetric means that a 0 is as likely to become a 1 as a 1 is to become a 0, the two crossing arrows of Figure 2. Real channels are not always so even-handed, and the chapter Channels, Signals and Likelihoods builds models that are not. The binary symmetric channel still captures the two facts that matter first. Errors happen at some rate $p$, and they strike bits independently, so a long message suffers about $p$ errors per bit, scattered at random.

When $n$ bits cross the channel, the difference between what was sent and what arrived can be written as an error pattern $e$, a string of $n$ bits with a 1 wherever a bit was flipped. If 000 is sent and 010 arrives, the error pattern is 010. The number of ones in a pattern is its weight, written $w$, and it counts how many bits were flipped. Because flips are independent, the probability of one particular pattern of weight $w$ is a product with one factor per bit, $p$ for each of the $w$ flipped bits and $1 - p$ for each of the $n - w$ untouched ones.

Many patterns share a weight. The number of ways to choose which $w$ of the $n$ positions are flipped is the binomial coefficient

$$\binom{n}{w} = \frac{n!}{w!\,(n-w)!},$$

read "$n$ choose $w$", where $n! = n \times (n-1) \times \cdots \times 2 \times 1$ and $0! = 1$. The formula comes from counting. There are $n$ choices for the first flipped position, $n - 1$ for the second, and so on down to $n - w + 1$ for the last, which makes $n!/(n-w)!$ ordered choices. Each set of $w$ positions has been counted once for every order in which it could have been picked, which is $w!$ times, and dividing by $w!$ leaves the number of sets. Table 1 works the case $n = 3$ on a channel with $p = 0.1$.

The last column adds to $0.729 + 0.243 + 0.027 + 0.001 = 1$, as it must, since some pattern always occurs. It also shows the fact that makes decoding possible. One flip is far more likely than two, and two far more likely than three.

Proof. Divide the two pattern probabilities.

$$\frac{p^{w+1}(1-p)^{n-w-1}}{p^{w}(1-p)^{n-w}} = \frac{p}{1-p}.$$

When $p < 1/2$, $p < 1 - p$, so the ratio is less than 1, and each extra flip makes a pattern less likely. $\blacksquare$

So on a channel that is right more often than wrong, the best guess about what was sent is whichever allowed message differs from what arrived in the fewest positions. Every decoder in this book is built on that sentence.

05.The Repetition Code

Here is the simplest code that can repair an error. Send every bit three times, so a 0 goes out as 000 and a 1 as 111. The receiver looks at each block of three and takes a vote, and whichever value appears at least twice wins. The code is called the repetition code of length three, written $R_3$.

Follow one message through the whole chain in Figure 3. The source has four bits to send, 1011. The encoder triples each one and sends 111 000 111 111, twelve bits in all. The channel flips four of them, and 101 000 100 110 arrives. The decoder votes block by block. The block 101 holds two ones, so it decodes to 1. The block 000 decodes to 0. The block 100 holds one 1 and two zeros, so it decodes to 0. The block 110 decodes to 1. The delivered message is 1001.

Compare 1001 with the 1011 that was sent. Three of the four bits came through. The first block took one flip and the vote corrected it. The second took none. The fourth took one and was corrected. The third block took two flips, which outvoted its one surviving correct copy, and the decoder confidently delivered the wrong bit. That one example shows the whole behavior of the code. One flip in a block is always repaired, and two or more always win the vote.

Some vocabulary makes this precise. The two strings the encoder can produce, 000 and 111, are the codewords. The string the decoder sees is the received word, and it can be any of the eight 3-bit strings. Decoding means mapping each received word back to a codeword, and from there to a message bit.

Figure 4 draws all eight 3-bit words, with a line between any two at distance 1, so that moving along one line is one flip. The codewords 000 and 111 sit at opposite ends, three flips apart. Every other word is one flip from one codeword and two flips from the other, and the vote sends it to the near one. The four words 000, 001, 010 and 100 decode to 0, and the four words 111, 110, 101 and 011 decode to 1.

Proof. Let $r$ hold $k$ ones. It differs from 000 in exactly those $k$ positions, so $d(r, 000) = k$, and it differs from 111 in the other $3 - k$ positions, so $d(r, 111) = 3 - k$. The word is nearer to 000 exactly when $k < 3 - k$, that is when $k < 3/2$, and since $k$ is a whole number this means $k \le 1$. The vote decodes to 0 exactly when at most one of the three bits is a 1, which is the same condition. The two rules agree on every word, and since $k$ and $3 - k$ are never equal, there is never a tie. $\blacksquare$

Put this together with the earlier theorem. Nearest means fewest flips, and fewest flips means the most likely error pattern when $p < 1/2$, so the vote always picks the codeword that most likely explains what arrived, provided 0 and 1 are sent equally often. The chapter Channels, Signals and Likelihoods proves that this choice also gives the smallest possible probability of decoding wrongly.

06.The Majority Voter in Hardware

A vote is easy to build in logic. Call the three received copies $a$, $b$ and $c$. Write $ab$ for $a$ AND $b$, which is 1 only when both are 1, and $+$ for OR, which is 1 when at least one input is 1. Then the majority function is

Proof. If at least two inputs are 1, that pair is one of the three pairs $ab$, $bc$ or $ca$, so its AND term is 1, and an OR with any input at 1 gives 1. If at most one input is 1, every pair contains at least one 0, so all three AND terms are 0 and so is their OR. $\blacksquare$

Table 2 checks the formula on all eight inputs, which is a second proof, since eight rows cover every case.

In gates, the formula is three two-input AND gates feeding one three-input OR gate, drawn on the right of Figure 5. A signal passes through two gates on its way to the output, so the vote costs two gate delays whatever the inputs.

The same circuit protects computation as well as data. Build three copies of a module, give them the same input, and vote on their outputs. If one copy fails, the other two outvote it. This arrangement, on the left of the figure, is called triple modular redundancy, and it is the hardware form of $R_3$. John von Neumann studied it in 1956 as a way to build reliable machines from unreliable parts, and showed that repeated majority voting can make a whole computation as reliable as wanted, provided each component fails with a probability below a threshold [6].

The price is plain. Triple modular redundancy needs three times the hardware and three times the power, plus the voter, and the voter becomes a single part whose own failure no vote can catch. It is used where a wrong answer costs far more than the extra silicon.

07.What the Repetition Code Buys

A single flip in a block is repaired, and two or more are not. On $\text{BSC}(p)$, that is enough to compute the decoded error probability exactly.

Proof. The decoder is wrong exactly when two or three of the three copies are flipped. All three flipped is one pattern, 111, with probability $p^3$. Exactly two flipped is $\binom{3}{2} = 3$ patterns, 011, 101 and 110, each with probability $p^2(1-p)$. The two cases cannot happen together, so their probabilities add.

$$P_e = 3p^2(1-p) + p^3 = 3p^2 - 3p^3 + p^3 = 3p^2 - 2p^3. \qquad \blacksquare$$

Table 3 shows the improvement growing as the channel gets better. For small $p$ the term $2p^3$ is negligible beside $3p^2$, so $P_e \approx 3p^2$ and the improvement $p/P_e$ is about $1/(3p)$. Each factor of ten in channel quality buys a factor of a hundred in decoded quality. That squaring is the signature of a code that corrects one error. To fail, it needs two independent errors in the same block, and two rare events together are rarer still.

Proof. Subtract and factor.

$$p - P_e = p - 3p^2 + 2p^3 = p\,(1 - 3p + 2p^2) = p\,(1-p)\,(1-2p).$$

Multiplying out $(1-p)(1-2p) = 1 - 3p + 2p^2$ confirms the factoring. For $0 < p < 1/2$ all three factors are positive, so $p - P_e > 0$. At $p = 1/2$ the last factor is zero and the code changes nothing, and for $1/2 < p < 1$ the last factor is negative and the code makes matters worse. $\blacksquare$

The failure above one half is less strange than it looks. A channel that flips more than half of its bits is more often wrong than right, and a receiver that simply inverts every bit it gets turns it into a channel with crossover $1 - p$, which is below one half. The channel at exactly $p = 1/2$ is the truly hopeless one. Its output is a fair coin toss whatever went in, so it carries no information at all, and no code can help.

Figure 6 plots the decoded error of no code, $R_3$ and $R_5$ on logarithmic axes, where a power of $p$ becomes a straight line whose slope is the power. The uncoded line has slope 1, $R_3$ has slope 2 because $P_e \approx 3p^2$, and $R_5$ has slope 3, for a reason the next section derives. All three meet at $p = 1/2$.

08.The Price of Reliability

The repetition code is not free. To deliver one message bit it sends three, so a channel carries a third as much information per second, a disk stores a third as much data, and every delivered bit costs three times the energy. The measure of this cost is the code rate.

More copies buy more reliability. With $n$ copies, and $n$ odd so that the vote cannot tie, majority decoding fails exactly when more than half the copies are flipped. Adding up the probability of every losing weight, as in the proof for $R_3$, gives

For $n = 5$ the sum has three terms, for three, four and five flips, and expanding them gives

$$P_e(R_5) = 10p^3(1-p)^2 + 5p^4(1-p) + p^5 = 10p^3 - 15p^4 + 6p^5.$$

At $p = 0.01$ this is $9.8506 \times 10^{-6}$, about thirty times better than $R_3$ at the same $p$, for a rate of $1/5$ instead of $1/3$. The leading term $10p^3$ is why $R_5$ has slope 3 in Figure 6. As $n$ grows the sum becomes unwieldy, but a simple bound shows where it is heading.

Proof. Take any term of the sum in Equation 5, which has $j > n/2$. Split its probability as

$$p^{j}(1-p)^{n-j} = \bigl(p(1-p)\bigr)^{n/2} \left(\frac{p}{1-p}\right)^{j - n/2}.$$

Multiplying out the right side confirms the split, since the powers of $p$ add to $n/2 + (j - n/2) = j$ and the powers of $1 - p$ to $n/2 - (j - n/2) = n - j$. Because $p < 1/2$, the fraction $p/(1-p)$ is less than 1, and it is raised to a positive power, so the second factor is at most 1. Every term is therefore at most $\binom{n}{j}\bigl(p(1-p)\bigr)^{n/2}$. Widening the sum to include every $j$ from 0 to $n$ only makes it larger, so

$$P_e(R_n) \le \bigl(p(1-p)\bigr)^{n/2} \sum_{j=0}^{n} \binom{n}{j} = \bigl(p(1-p)\bigr)^{n/2}\, 2^n = \bigl(4p(1-p)\bigr)^{n/2}.$$

The sum of all the binomial coefficients is $2^n$ because it counts every subset of the $n$ positions, and each position is either in a subset or out of it, two choices made $n$ times. The last step writes $2^n$ as $4^{n/2}$. $\blacksquare$

At $p = 0.1$, $4p(1-p) = 0.36$, whose square root is $0.6$, so the bound is $0.6^n$ and each additional pair of copies cuts it by a factor of 0.36. The error falls exponentially in $n$. That is the good news. The bad news is the rate, $1/n$, which falls to zero just as surely. Table 4 shows the trade on a channel with $p = 0.1$.

Figure 7 draws the same trade. To reach about one error in six million bits, the repetition code needs 25 copies and runs at a twenty-fifth of the channel's raw speed.

Is that trade a law of nature? In 1948 Shannon proved that it is not [1]. Every channel has a capacity $C$, a rate measured in bits per use of the channel, and for any rate below $C$ there exist codes whose error probability is as small as anyone wants. Error can be driven toward zero without driving the rate toward zero. For the binary symmetric channel the capacity is

where $H(p)$ is the binary entropy function, a measure of how unpredictable the channel's flips are. At $p = 0.1$, $H(0.1) = 0.1\log_2 10 + 0.9\log_2(10/9) = 0.4690$, so $C = 0.5310$. Shannon's theorem says that codes exist which run this channel at a rate of one half and still deliver as few errors as wanted, where the repetition code had to slow to a rate of $1/25$ to reach one error in six million.

This chapter does not prove the theorem. The chapters Information and Entropy and Capacity and Shannon's Theorem build the entropy function from first principles and prove it, and most of the rest of the book is the story of codes that close the distance between the repetition codes and the capacity line in Figure 7. That distance is the reason coding theory exists as a subject.

09.Detecting Instead of Correcting

Correcting errors is expensive. Detecting them can be very cheap. Add one bit to a block of data, chosen so that the total number of ones is even. That bit is the parity bit, and the block with it attached is a codeword of the single parity-check code. The 7-bit block 1011001 already holds four ones, an even number, so its parity bit is 0 and the codeword is 10110010. The receiver counts the ones in what arrives. An even count passes, and an odd count means something is wrong.

Proof. Each flipped bit changes the number of ones by exactly one, up or down, so it changes the count from even to odd or from odd to even. A codeword starts with an even count. After $w$ flips the count has changed between even and odd $w$ times, so it is odd when $w$ is odd and even when $w$ is even. The checker sees an odd count, and raises the alarm, exactly when $w$ is odd. $\blacksquare$

The rate of the $n$-bit parity code is $(n-1)/n$, which is $7/8$ for $n = 8$, far better than the $1/3$ of $R_3$. In exchange it corrects nothing, because an odd count says that some bit is wrong without saying which, and it is blind to every even number of flips.

In hardware, counting ones and asking whether the count is even is a job for the exclusive-OR gate. The XOR of two bits, written $a \oplus b$, is 1 when they differ and 0 when they agree. It is binary addition with the carry thrown away, so $1 \oplus 1 = 0$, which is why it is also called addition modulo 2. The XOR of a whole string of bits is 1 exactly when the string holds an odd number of ones. To see why, combine the bits in one at a time. The running result starts at 0, a 0 bit leaves it alone, and a 1 bit toggles it, so it toggles once for every 1 and ends at 1 exactly when the number of ones is odd.

How often does parity miss? On $\text{BSC}(p)$, an $n$-bit word slips through undetected when its error pattern has even, nonzero weight. Adding up those weights one by one is tedious for large $n$, but a short argument gives a closed form.

Proof. The binomial theorem says that for any numbers $a$ and $b$,

$$(a + b)^n = \sum_{w=0}^{n} \binom{n}{w}\, a^{w}\, b^{n-w}.$$

It holds because multiplying out $n$ copies of $(a + b)$ means choosing either $a$ or $b$ from each copy, and the choices that take $a$ from exactly $w$ copies number $\binom{n}{w}$, each contributing $a^w b^{n-w}$. Put $a = p$ and $b = 1 - p$. The left side is $1^n = 1$, and the right side is the total probability of every weight, which can be split as $E + O$, where $E$ collects the even weights and $O$ the odd ones. Now put $a = -p$ and $b = 1 - p$. The left side is $(1 - 2p)^n$, and on the right every odd-weight term changes sign while every even-weight term stays the same, so the sum is $E - O$. Adding the two equations gives

$$2E = 1 + (1-2p)^n, \qquad E = \frac{1 + (1-2p)^n}{2}.$$

The even weights include $w = 0$, the case of no error at all, whose probability is $(1-p)^n$. Removing it leaves exactly the undetected errors, which is the formula. $\blacksquare$

Take $n = 8$, seven data bits and one parity bit, on a channel with $p = 0.01$. The probability that the word holds any error at all is $1 - 0.99^8 = 0.077255$. The probability of an undetected error is $P_{ud} = 0.0026368$, and almost all of it, $0.0026361$, comes from the weight-2 patterns alone. So about 3.41% of the corrupted words slip through, and parity catches the other 96.6%. The misses are dominated by double flips, which is why parity works best where errors are rare and isolated, and why it fails on channels where errors arrive in bursts, a problem that later Parts answer with stronger checks.

The parity tree

To compute the parity of many bits at once, hardware arranges XOR gates in a tree. Figure 8 checks the 8-bit codeword 10110010. Four gates combine the bits in pairs, two gates combine those results, and one final gate produces the parity, 0, which says the word holds an even number of ones and passes the check.

Proof. Each two-input gate takes two signals and produces one, so it reduces the number of signals still to be combined by exactly one. Starting from $n$ signals and finishing with one takes $n - 1$ reductions, so $n - 1$ gates, however the tree is arranged. For the depth, a tree with $L$ levels of two-input gates can combine at most $2^L$ inputs, because each level at most doubles the number of inputs that can reach the output. Combining $n$ inputs therefore needs $2^L \ge n$, that is $L \ge \log_2 n$, and since $L$ is a whole number, $L \ge \lceil \log_2 n \rceil$. Pairing the signals at every level, with any odd one passed down unpaired, leaves $\lceil n / 2^L \rceil$ signals after $L$ levels, which first reaches 1 when $2^L \ge n$, so the paired tree meets the bound exactly. $\blacksquare$

For 8 inputs that is 7 gates in 3 levels, as in the figure. For a 64-bit word it is 63 gates in 6 levels, so the parity of a whole 64-bit word settles in six gate delays. The number of gates grows in step with the width, but the delay grows only with its logarithm, which is why a parity check is cheap enough to sit on every memory read.

Parity as a spare disk

Parity has a second use that turns detection into correction. Suppose the position of a bad bit is known, because the device that held it has reported a failure. A lost bit whose position is known is an erasure, and a single parity bit can fill in one erasure, since the missing bit must be whichever value makes the count of ones even.

Disk arrays use exactly this. Figure 9 shows three data disks D1, D2 and D3 holding 1011, 0110 and 1100, and a parity disk P that holds their bitwise XOR,

$$P = 1011 \oplus 0110 \oplus 1100 = 0001.$$

Working column by column, the first bits are 1, 0 and 1, which hold two ones, so the first parity bit is 0. The second and third columns also hold two ones each, and the last column, 1, 0 and 0, holds one, so the last parity bit is 1. When D2 fails, its contents are rebuilt from the survivors.

$$D_1 \oplus D_3 \oplus P = 1011 \oplus 1100 \oplus 0001 = 0110,$$

which is D2 exactly. The reason is that XOR cancels itself. For any bit string $x$, $x \oplus x$ is all zeros and $x \oplus 0 = x$, and XORs can be taken in any order, so in $D_1 \oplus D_3 \oplus P = D_1 \oplus D_3 \oplus D_1 \oplus D_2 \oplus D_3$ every surviving disk appears twice and cancels, leaving $D_2$.

The same parity bit that could only detect one error can correct one erasure. Knowing where the damage is makes it far easier to repair, a fact that returns in force with Reed–Solomon codes, which correct twice as many erasures as errors.

10.Detect and Resend, or Correct

A detected error still has to be dealt with. If the receiver can talk back to the sender, the simplest answer is to ask for the data again. This is automatic repeat request, or ARQ. The receiver checks each frame, a block of bits sent as one unit, and when the check fails it asks for the frame to be sent again. Many network and bus protocols work this way.

How much does resending cost? Suppose a frame arrives clean with probability $q$, and attempts succeed or fail independently. Let $E$ be the expected number of transmissions per frame. The first attempt is always made. With probability $q$ it succeeds and the count stops at 1. With probability $1 - q$ it fails, and the process starts over having already spent one transmission. So

$$E = q \cdot 1 + (1 - q)(1 + E),$$

and collecting the terms in $E$ gives $E - (1-q)E = q + (1 - q)$, so $qE = 1$ and $E = 1/q$.

Take a 1000-bit frame on a channel with $p = 10^{-4}$. It arrives clean with probability $q = (1 - 10^{-4})^{1000} = 0.904833$, so on average $E = 1/q = 1.105176$ transmissions are needed, about 10.5% more than a perfect channel would need. The calculation assumes that the check catches every corrupted frame. It does not quite, as the parity calculation showed, which is why real protocols use checks far stronger than a single parity bit.

ARQ needs two things that a channel does not always offer. It needs a path back to the sender, and it needs time for the round trip. A spacecraft billions of kilometers away waits hours for a reply. A broadcast has no single sender to ask. A disk that stored a bit wrongly years ago cannot be asked what it meant to store, because reading it again returns the same wrong bit. In those cases the receiver must repair errors itself, from redundancy sent in advance, which is forward error correction, or FEC.

Modern systems often combine the two. PCI Express 6.0 corrects the common errors in each flit, its fixed-size unit of transfer, with a light forward error correcting code, and catches the rarer ones with a cyclic redundancy check and a retry [7]. The chapter Error-Control Strategies and Performance compares the strategies properly, including what each one does to delay.

11.Where Codes Live

Codes are everywhere a bit can be damaged, which is everywhere. Table 5 lists some of the systems this book visits, and every code in it is built and analyzed in a later Part.

The table runs from the simplest ideas of this chapter to the frontier. The memory code refines the Hamming codes of Part II. The CRC is a cyclic code built on polynomial arithmetic. Reed–Solomon codes [15] rest on finite fields. LDPC and polar codes come from the modern theory of codes on graphs and of channel polarization, and surface codes carry the whole subject into quantum mechanics. Each one is a different answer to the trade this chapter met in its simplest form, how much reliability a given amount of redundancy can buy, and how cheaply hardware can deliver it.

12.Looking Ahead

This chapter used probability informally, multiplying the chances of independent events and adding the chances of events that exclude each other. The next chapter, Probability for Coding, makes those rules precise and adds the tools the rest of Part I needs, among them random variables, expectation and the binomial distribution behind every table above. Channels, Signals and Likelihoods replaces the binary symmetric channel with the noisy voltages it stands for, and shows how a receiver turns a voltage into a bit and a measure of confidence in it.

Information and Entropy defines the entropy function that appeared in the capacity formula, and the two chapters after it, Source Coding and Prefix Codes and Compression in Practice, show what entropy means for squeezing redundancy out of data before a channel code puts redundancy back in. Capacity and Shannon's Theorem then proves the result previewed here. Distance, Detection and Correction turns the Hamming distance of the cube picture into the single number that decides what any code can detect and correct, and Error-Control Strategies and Performance compares detection, correction and retransmission properly. The Part ends with a case study of codes in deployed systems, a project that builds a channel simulator, and a lab that runs the companion repository's parity checker as hardware in simulation.

Two textbooks cover this ground at greater length, Lin and Costello [16] and MacKay [17], whose first chapter also starts from the repetition code. The reader who has worked through this chapter can now compute the chance of an error over any number of bits, decode the repetition code by hand and by circuit, prove its error probability, and explain why parity detects odd numbers of errors and misses even ones.

13.Worked Examples

14.Exercises

References

1. [1]Shannon, Claude E. (1948). “A Mathematical Theory of Communication.” Bell System Technical Journal, 27(3), pp. 379–423. The paper concludes in the October issue, volume 27, number 4, pages 623 to 656. doi:10.1002/j.1538-7305.1948.tb01338.x
2. [2]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
3. [3]May, T. C. and Woods, M. H. (1979). “Alpha-Particle-Induced Soft Errors in Dynamic Memories.” IEEE Transactions on Electron Devices, 26(1), pp. 2–9. doi:10.1109/T-ED.1979.19370
4. [4]Ziegler, J. F. and Lanford, W. A. (1979). “Effect of Cosmic Rays on Computer Memories.” Science, 206(4420), pp. 776–788. doi:10.1126/science.206.4420.776
5. [5]Schroeder, Bianca and Pinheiro, Eduardo and Weber, Wolf-Dietrich (2009). “DRAM Errors in the Wild: A Large-Scale Field Study.” In Proceedings of the Eleventh International Joint Conference on Measurement and Modeling of Computer Systems (SIGMETRICS '09), pp. 193–204. doi:10.1145/1555349.1555372
6. [6]von Neumann, John (1956). “Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components.” In Automata Studies, pp. 43–98. doi:10.1515/9781400882618-003
7. [7]PCI-SIG (2022). “PCI Express Base Specification, Revision 6.0.” https://pcisig.com/specifications
8. [8]Hsiao, M. Y. (1970). “A Class of Optimal Minimum Odd-weight-column SEC-DED Codes.” IBM Journal of Research and Development, 14(4), pp. 395–401. doi:10.1147/rd.144.0395
9. [9]ISO/IEC (2015). “Information Technology, Automatic Identification and Data Capture Techniques, QR Code Bar Code Symbology Specification.” ISO/IEC 18004:2015. https://www.iso.org/standard/62021.html
10. [10]DENSO WAVE “Error Correction Feature.” QRcode.com. Read 2026-11-13. https://www.qrcode.com/en/about/error_correction.html
11. [11]IEEE (2022). “IEEE Standard for Ethernet.” IEEE Std 802.3-2022. IEEE. doi:10.1109/IEEESTD.2022.9844436
12. [12]3GPP (2017). “NR; Multiplexing and Channel Coding.” 3GPP Technical Specification 38.212. First issued in Release 15; later releases revise it. https://www.3gpp.org/dynareport/38212.htm
13. [13]Consultative Committee for Space Data Systems “TM Synchronization and Channel Coding.” CCSDS 131.0-B-5, Blue Book. Issue 5. https://public.ccsds.org/Pubs/131x0b5.pdf
14. [14]Fowler, Austin G. and Mariantoni, Matteo and Martinis, John M. and Cleland, Andrew N. (2012). “Surface Codes: Towards Practical Large-Scale Quantum Computation.” Physical Review A, 86(3), pp. 032324. doi:10.1103/PhysRevA.86.032324
15. [15]Reed, Irving S. and Solomon, Gustave (1960). “Polynomial Codes over Certain Finite Fields.” Journal of the Society for Industrial and Applied Mathematics, 8(2), pp. 300–304. doi:10.1137/0108018
16. [16]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.
17. [17]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