Error-Control Strategies and Performance

Distance, Detection and Correction closed on a caution: a guarantee says what a code can do, not what a system should do with it. A code with $d = 4$ can correct one error and detect two, or detect three and correct none, and the guarantee is silent on which a modem or memory controller should choose, what the choice costs, and how often an error that slips past every check still reaches the user.

Channels, Signals and Likelihoods built the binary symmetric channel $\text{BSC}(p)$, which flips each bit independently with probability $p$, and the Gaussian channel with BPSK, whose strength is the energy per information bit over the noise density, $E_b/N_0$. Distance, Detection and Correction priced detection through the undetected-error probability and the parity detection formula, and both return here as inputs.

Why Codes Exist, in its section Detect and Resend, or Correct, promised a proper comparison of the two strategies, and this chapter keeps it. It prices three retransmission protocols, finds the error rate that survives a checked link, outlines hybrid schemes, separates bit from word error rates, defines coding gain, sizes simulations with honest confidence intervals, and closes with the units of hardware reliability.

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

01.Two Ways to Spend Redundancy

A frame of $n = 1000$ bits sent over $\text{BSC}(10^{-4})$ arrives untouched with probability $(1 - 10^{-4})^{1000} = 0.904833$, so nearly one frame in ten carries a flipped bit. A designer can spend extra bits on that problem in two ways. One adds enough redundancy for the receiver to repair the flipped bits on its own, as the repetition code of Why Codes Exist did. The other adds only enough to notice the damage, 32 check bits per frame in this chapter's running example, and asks for the frame again.

Figure 1 draws both. Forward error correction, FEC, is a one-way pipeline whose decoder hands the user its best estimate, right or wrong. Automatic repeat request, ARQ, is a loop. The sender keeps a copy of each frame, the receiver runs a detector, and a short message on a return link, an acknowledgment (ACK) for a frame that passed or a negative acknowledgment (NAK) for one that failed, tells the sender whether to send it again.

The two designs fail differently. A forward-correcting decoder that meets more errors than its code handles gives up or, worse, corrects to the wrong codeword. Its cost is fixed, the same redundancy and decoding delay on every word. ARQ pays only when something goes wrong, so on a quiet channel nearly all of its capacity carries data, but its delay varies, since a damaged frame waits a round trip for its second chance, and it needs a return link.

ARQ leans on the asymmetry proved in Distance, Detection and Correction. A code of minimum distance $d$ detects every pattern of up to $d - 1$ errors but corrects only $\lfloor (d - 1)/2 \rfloor$, so the same redundancy reaches about twice as far when it only has to notice, while 30 bits spent on correction repair only three errors per frame, as Hybrid ARQ shows. Why 32 check bits make an undetected frame rare is a separate matter, settled by the $2^{-r}$ count of The Residual Error of a Checked Link.

Where a return path is missing or too slow, as for a distant space probe, a broadcast, a disk sector or a memory cell, FEC is the only choice. Where the return path is cheap and delay can be tolerated, as on most cabled networks, ARQ with a strong check is hard to beat. The PCI Express 6.0 link of Why Codes Exist, which corrects common errors and retries rare ones, sits between the two.

02.Stop-and-Wait, Go-Back-N and Selective Repeat

The running example is a link that sends bits at $R = 1$ Mbit/s in frames of $n = 1000$ bits, of which $k = 968$ carry data and $r = n - k = 32$ are check bits. One frame takes $T_f = n/R = 1$ ms to send. The round trip $T_{rt} = 10$ ms runs from the last bit of a frame leaving the sender to the arrival of its acknowledgment, which is counted as instant. The ratio $a = T_{rt}/T_f = 10$ is the number of frame times the sender waits for news of a frame. The channel is $\text{BSC}(p)$ with $p = 10^{-4}$, and a frame is damaged when any of its bits flips, which by the complement rule has probability

0.095167 here. Throughout this section the sender always has frames waiting, acknowledgments are never lost, and the check catches every damaged frame, so the only cost of an error is time. The next section drops the last assumption.

Before any algebra, Figure 2 runs the three protocols for 16 frame slots on a toy link with $a = 3$, with frame 2 damaged on its first try. Stop-and-wait idles until each acknowledgment arrives, so every attempt occupies $1 + a = 4$ slots and the 16 slots carry frames 1, 2, 2 again and 3, delivering three. Go-back-N keeps sending, up to a window of $W = 4$ unacknowledged frames. Its receiver accepts frames only in order, so it discards frames 3 to 5, and when the NAK for frame 2 returns the sender goes back and sends frames 2 to 5 again, losing four slots and delivering 12 frames. Selective repeat in its ideal form, whose sender no window limits, buffers frames 3 to 5 at the receiver and resends only frame 2, delivering 15. Held instead to a window of four sequence numbers counted from the oldest unacknowledged frame, it could not send frame 6 until frame 2 was acknowledged and would deliver 12.

Proof. Each formula follows from Equation 2 once $S$ is known. In stop-and-wait every attempt occupies the frame time plus the round trip, $1 + a$ slots, and succeeds with probability $1 - P$, independently of earlier attempts. Detect and Resend, or Correct showed that a trial succeeding with probability $q$ takes $1/q$ attempts on average, so $S_{\text{SW}} = (1 + a)/(1 - P)$.

Go-back-N never idles, so a frame that passes costs one slot, and one that fails costs its own slot and the $W - 1$ discarded slots behind it, after which delivery starts over from the same frame. Averaging over the first attempt,

Collecting the $S_{\text{GBN}}$ terms gives $(1 - P) S_{\text{GBN}} = 1 - P + PW = 1 + (W - 1)P$, so $S_{\text{GBN}} = (1 + (W - 1)P)/(1 - P)$. Selective repeat loses only the failed frame's own slot, so the same reasoning with $W$ replaced by 1 gives $S_{\text{SR}} = 1/(1 - P)$. Substituting each $S$ into Equation 2 gives the three formulas. $\blacksquare$

The window $W = 1 + a$ is the smallest that keeps the sender busy, since a frame's acknowledgment arrives $a$ slots after the frame ends. Selective repeat pays in memory. One failure makes the receiver hold the $1 + a$ or so frames sent behind it until the gap fills, and each further failure of the same frame adds as many again, so a real, bounded buffer stalls the sender and costs throughput.

Table 1 puts numbers on the link. Stop-and-wait spends 11 slots per attempt and averages 1.10518 attempts, so it keeps under 8% of the raw rate. Its trouble is idleness, not errors, since even with $P = 0$ it would reach only $\frac{k}{n} \cdot \frac{1}{1 + a} = 0.088$. Go-back-N's denominator, $1 + 10 \times 0.095167 = 1.95167$, charges 11 slots per failure, and it reaches 0.44878, 5.64 times stop-and-wait. Selective repeat loses only the damaged frames and reaches 0.87588, a further factor of 1.95. A simulation of 200,000 frames per protocol averages 12.160, 2.149 and 1.105 slots per frame. It charges each failure as the proof does, so it checks only the averaging. Lin, Costello and Miller survey these protocols and their refinements [1].

Figure 3 sweeps $p$ from $10^{-6}$ to $10^{-2}$. When frames rarely fail, go-back-N and selective repeat both approach $k/n = 0.968$, while stop-and-wait stays below its ceiling. Once $p$ passes about $10^{-3}$ a 1000-bit frame is more often damaged than not, and all three collapse.

Throughput hides the cost users notice first, delay. Under stop-and-wait each retransmission adds the frame time plus the round trip, $(1 + a) T_f = 11$ ms on this link. The mean number of retries is $1/(1 - P) - 1 = P/(1 - P) = 0.10518$, so the mean extra delay is only 1.16 ms, but it comes in lumps. A frame needs at least $j$ retries exactly when its first $j$ attempts fail, with probability $P^j$, and $P^2 = 0.0090568$, so one frame in 110 waits at least 22 ms longer than a clean one. Those figures count a frame's own retries only. The faster protocols release frames in order, so an intact frame also waits behind any damaged one ahead of it. Simulated over 400,000 slots of this link, selective repeat averages 5.68 ms of extra delay, with one frame in 58 waiting at least 22 ms, and go-back-N, which resends the frames behind a failure too, has one frame in 3 waiting that long. Its mean needs no simulation. Each resend trails the previous attempt by $1 + a$ slots, and a frame is sent $S_{\text{GBN}}$ times on average, so the mean extra delay is $(1 + a)(S_{\text{GBN}} - 1) T_f = 12.7$ ms, which the simulation matches. A voice call must budget for that tail, not the mean. Forward error correction has no such tail, which is a main reason real-time links prefer it.

03.The Residual Error of a Checked Link

A real check lets some damaged frames through as correct. Take an 8-bit word protected by single parity on $\text{BSC}(0.01)$. Each transmission ends in one of three ways, drawn in Figure 4. With probability $c = 0.99^8 = 0.922745$ no bit flips and the word is accepted correctly. With probability $\alpha$ an odd number of bits flip, the check raises the alarm, and the sender tries again. With probability $s$ an even number of bits, at least two, flip and the receiver accepts a wrong word, called here a slip. The parity detection formula of Single Parity gives the alarm probability,

which is 0.074618 here since $0.98^8 = 0.850763$, and the slip probability is the undetected-error probability of Detecting Errors,

where $A_i$ counts the codewords of weight $i$, which for the even-weight code are all $\binom{n}{i}$ words of each even weight. The three outcomes exhaust the possibilities, so $s = 1 - c - \alpha = 0.0026368$, and the companion script confirms all three by listing the 256 error patterns of 8 bits.

Proof. Condition on the first transmission. A clean transmission ends with a correct frame and a slip with a wrong one. An alarm starts the process again, and because the channel has no memory the fresh start has the same chance $P_{\text{res}}$ of ending wrong. So $P_{\text{res}} = s + \alpha P_{\text{res}}$, which rearranges to $P_{\text{res}} = s/(1 - \alpha)$, and $1 - \alpha = c + s$. Likewise the first transmission counts once and an alarm adds a fresh process, so $E[X] = 1 + \alpha E[X]$, giving $E[X] = 1/(1 - \alpha)$. $\blacksquare$

Retransmission never repairs a slip, it only discards alarms, so the accepted frames are the clean ones and the slipped ones in their original ratio of $c$ to $s$. Only a better check lowers $s$.

For the 8-bit word, Table 2 shows that ARQ costs about 8% more transmissions and leaves 0.0028494 of accepted words wrong, against the $1 - c = 0.077255$ wrong with no check at all. The 1000-bit frame shows why no real link relies on one parity bit. The 0.0475 of damaged frames with an even number of errors slip, so one accepted frame in 201 is wrong. A link sending 1000 frames a second accepts about 909 of them, so about 4.5 wrong frames get through every second.

Real links use a cyclic redundancy check, a CRC, with $r = 16$ or $r = 32$ check bits, built in Part IV. A heuristic gives a rough residual. Suppose the damage left a random error pattern, every one of the $2^n - 1$ nonzero patterns equally likely. A CRC is closed under XOR, so by the argument of Detecting Errors the patterns that escape are the $2^k - 1$ nonzero codewords, and the escape probability is

With $r = 32$, $2^{-32} = 2.33 \times 10^{-10}$, and the chance that a frame is both damaged and undetected is about $P \cdot 2^{-32} = 2.22 \times 10^{-11}$. At 1000 frames a second, one undetected frame then arrives on average every 1.43 years, against 4.5 every second for single parity.

04.Hybrid ARQ

Combining forward correction with retransmission is called hybrid ARQ. In type-I hybrid ARQ every frame carries a correcting code and a CRC. The receiver corrects what it can, checks the result with the CRC, and asks for a resend only when the correction has failed. Give the 1000-bit frame 938 data bits, 32 CRC bits and 30 bits of a code that corrects any 3 errors. A BCH code of Part V over a field of $2^m$ elements with $m = 10$ spends $mt = 30$ check bits to correct $t = 3$ errors, so the frame efficiency drops from 0.968 to 0.938. If the decoder succeeds whenever a frame holds at most 3 errors and the CRC catches every failure, a resend is needed only when 4 or more bits flip, with probability

and with selective repeat the efficiency is $\eta_{\text{H}} = (1 - P_f) \times 0.938$. At $p = 10^{-4}$, $P_f = 3.8 \times 10^{-6}$ and $\eta_{\text{H}} = 0.93800$, against 0.87588 for plain selective repeat. At very low error rates the 30 correcting bits are dead weight, and plain selective repeat wins below about $p = 3.1 \times 10^{-5}$.

Type-II hybrid ARQ, or incremental redundancy, is thriftier. The first transmission carries data and a CRC only. If it fails, the sender sends extra parity bits that, together with the first transmission, form a stronger code of lower rate. A third variant, Chase combining, resends the same frame and adds the soft received values of the copies, the soft repetition code of Hard and Soft Decisions spread over time. Both draw on Part VI, Soft Decisions and Concatenation, and run in the 5G NR systems of Part XII.

05.Bit and Word Error Rates

Send a 4-bit word with no code over $\text{BSC}(0.01)$ and let $J$ count its wrong bits. $J$ follows the binomial distribution of Counting Errors with the Binomial Distribution, $P(J = j) = \binom{4}{j} (0.01)^j (0.99)^{4 - j}$, and Table 3 lists its five values.

Two numbers summarize the table. The word is wrong whenever $J \ge 1$, with probability $1 - 0.96059601 = 0.03940399$. The mean number of wrong bits is $E[J] = 4 \times 0.01 = 0.04$, by the binomial mean of Expectation and Variance, so the fraction of wrong bits is $0.04/4 = 0.01$, the channel's $p$. A system that discards a packet with one bad bit cares about the first number, and a voice stream that tolerates scattered bad bits cares about the second.

Proof. Write $\mathbf{1}\{J \ge 1\}$ for the indicator that equals 1 when $J \ge 1$ and 0 otherwise. Since $J$ is a whole number from 0 to $k$, $\mathbf{1}\{J \ge 1\} \le J \le k \, \mathbf{1}\{J \ge 1\}$, as all three are 0 when $J = 0$ and $1 \le J \le k$ otherwise. Taking expectations, with $E[\mathbf{1}\{J \ge 1\}] = P(J \ge 1) = P_w$, gives $P_w \le E[J] \le k P_w$, and dividing by $k$ gives the result. $\blacksquare$

For the uncoded 4-bit word the bounds read $0.0098510 \le 0.01 \le 0.03940399$. The lower bound is nearly reached because a wrong word almost always has one wrong bit. The upper bound is approached by decoders that fail badly, replacing the sent word with a distant codeword. A fair comparison of two codes therefore states which rate it uses.

For a coded scheme the word error rate follows from the correction bound of Correcting Errors. A decoder that corrects every pattern of up to $t$ errors in $n$ bits, and nothing more, fails exactly when more than $t$ bits flip. There are $\binom{n}{i}$ patterns of exactly $i$ flips, each with probability $p^i (1 - p)^{n - i}$, and summing over every $i$ beyond $t$ gives the key result.

For $R_3$ at $p = 0.01$, $t = 1$ and the sum has two terms, $3p^2 (1 - p) = 2.97 \times 10^{-4}$ and $p^3 = 10^{-6}$, so $P_w = 2.98 \times 10^{-4}$. For $R_5$, $t = 2$ and the three terms $10 p^3 (1 - p)^2 = 9.801 \times 10^{-6}$, $5 p^4 (1 - p) = 4.95 \times 10^{-8}$ and $p^5 = 10^{-10}$ give $P_w = 9.8506 \times 10^{-6}$, 30.3 times smaller. The first term carries almost everything, because each extra flip multiplies a term by roughly $p$. A repetition code carries one data bit, so $k = 1$ and $P_b = P_w$, and the companion script confirms both sums by listing all 8 and all 32 error patterns.

06.Coding Gain

The repetition codes just cut the error rate, but by sending three or five pulses per data bit. On a power-limited channel the fair question is whether, at the same energy per data bit, the code beats sending the bit plainly. Fix a target bit error rate of $10^{-6}$ on the Gaussian channel with BPSK. The Gaussian Channel and BPSK showed that an uncoded bit is wrong with probability $Q(\sqrt{2E_b/N_0})$, so the target needs $Q(x) = 10^{-6}$, which holds at $x = 4.7534$, and then $E_b/N_0 = x^2/2 = 11.2975$, or 10.530 dB.

Hard-decision $R_3$ sends each bit as three pulses of energy $E_s = R_c E_b = E_b/3$, as Energy per Bit and the Decibel showed, and decodes by majority. Each pulse flips with probability $p = Q(\sqrt{2E_s/N_0})$, and by Equation 13 the decoded bit is wrong with probability $3p^2 (1 - p) + p^3$. Setting that to $10^{-6}$ gives $p = 5.7746 \times 10^{-4}$, then $Q(x) = p$ gives $x = 3.2498$, so $E_s/N_0 = x^2/2$ is 7.227 dB, and $E_b/N_0$ is $10 \log_{10} 3 = 4.771$ dB higher, at 11.998 dB. The code needs 1.468 dB more energy per bit than no code, and Table 4 repeats the computation for $R_5$.

Figure 5 plots the three curves. Both repetition curves sit right of the uncoded one at every useful error rate, and at 12 dB hard $R_3$ has only just reached $9.9 \times 10^{-7}$. Repetition divides a bit's energy among $n$ pulses, a loss of 4.771 dB for $R_3$ and 6.990 dB for $R_5$, and hard majority voting wins back less than that. Hard and Soft Decisions found a gain of $-1.441$ dB for $R_3$ at $10^{-5}$, and for $R_5$ it is $-1.718$ dB there and $-1.751$ dB at $10^{-6}$, so the longer code loses more.

The loss grows as the target falls, toward a limit set by exponents. Write $\gamma = E_b/N_0$ as a plain ratio, not in decibels. A code of rate $R_c$ gives each pulse the energy $E_s = R_c E_b$, so a pulse flips with probability $p = Q(x)$ at $x = \sqrt{2 R_c \gamma}$, where $x^2/2 = R_c \gamma$. Uncoded BPSK is the case $R_c = 1$.

Proof. Assume $\gamma \ge 1/(2R_c)$, so that $x \ge 1$, and note that $p = Q(x) \le \tfrac12$. The proof bounds the coded bit error rate $P_b$ on both sides with the bounds on the Q-function that Probability for Coding proves in The Gaussian and the Q-Function.

For the upper bound, $P_b \le P_w$ by Equation 12. In each term of Equation 13, $p^i \le p^{t+1}$ since $i \ge t + 1$, and $(1 - p)^{n-i} \le 1$, so $P_w \le p^{t+1} \sum_{i} \binom{n}{i} \le 2^n p^{t+1}$. The bound $Q(x) \le \tfrac12 e^{-x^2/2}$ gives $p \le \tfrac12 e^{-R_c \gamma}$, hence

$$P_b \le 2^{\,n - t - 1} \, e^{-(t+1) R_c \gamma} .$$

For the lower bound, $P_b \ge P_w/k$, and $P_w$ is at least its term with $i = t + 1$, which is at least $p^{t+1}(1 - p)^{n-t-1}$, and $(1 - p)^{n-t-1} \ge 2^{-n}$ because $p \le \tfrac12$. The same theorem gives $Q(x) > \frac{x}{1+x^2}\,\phi(x)$ with $\phi(x) = e^{-x^2/2}/\sqrt{2\pi}$. For $x \ge 1$, $1 + x^2 \le 2x^2$, so $\frac{x}{1+x^2} \ge \frac{1}{2x}$, and with $2x\sqrt{2\pi} = 4\sqrt{\pi R_c \gamma}$,

$$p > \frac{e^{-R_c \gamma}}{4\sqrt{\pi R_c \gamma}} , \qquad P_b > \frac{1}{k \, 2^n} \left( \frac{e^{-R_c \gamma}}{4\sqrt{\pi R_c \gamma}} \right)^{t+1} .$$

Taking natural logarithms of the two bounds,

$$-(t+1) R_c \gamma - c_1 - \tfrac{t+1}{2} \ln(\pi R_c \gamma) < \ln P_b \le -(t+1) R_c \gamma + c_2 ,$$

with $c_1 = \ln k + n \ln 2 + (t + 1) \ln 4$ and $c_2 = (n - t - 1) \ln 2$, neither of which depends on $\gamma$. So $\ln P_b = -(t+1) R_c \gamma + D(\gamma)$, where $|D(\gamma)|$ is at most a constant plus a constant times $\ln \gamma$, and $D(\gamma)/\gamma \to 0$ as $\gamma \to \infty$. The uncoded case, $R_c = 1$, $t = 0$ and $n = k = 1$, reads $\ln P_u = -\gamma + D_u(\gamma)$ with $D_u(\gamma)/\gamma \to 0$ in the same way.

Let $\gamma_u$ and $\gamma_c$ be the smallest energies at which the uncoded and coded rates reach a target $\varepsilon$. Both grow without bound as $\varepsilon \to 0$, since over any bounded range of $\gamma$ each rate stays above a fixed positive number. Setting $\ln P_u(\gamma_u) = \ln P_b(\gamma_c) = \ln \varepsilon$ and dividing by $\gamma_c$,

$$\frac{\gamma_u}{\gamma_c} \left( 1 - \frac{D_u(\gamma_u)}{\gamma_u} \right) = (t+1) R_c - \frac{D(\gamma_c)}{\gamma_c} .$$

Both fractions $D/\gamma$ tend to zero, so $\gamma_u/\gamma_c \to (t+1) R_c$, and the gain $10 \log_{10}(\gamma_u/\gamma_c)$ tends to Equation 15. $\blacksquare$

For $R_n$ with odd $n = 2t + 1$, $R_c (t + 1) = (t + 1)/(2t + 1)$, which is $2/3$ for $R_3$ and $3/5$ for $R_5$, giving $-1.761$ dB and $-2.218$ dB, and it falls toward $\tfrac12$, or $-3.010$ dB, as $n$ grows. The finite-target gains of $R_3$ creep toward $-1.761$ dB as the target falls, slowly, because $D(\gamma)/\gamma$ fades only like $\ln \gamma / \gamma$. A code gains only when $R_c (t + 1) > 1$, which repetition can never give, and the codes of Part II onward reach it by keeping a high rate while correcting several errors.

Soft decisions lift repetition, though only back to zero. Add the three received values instead of voting on their signs. Each value is $\pm\sqrt{E_s}$ plus Gaussian noise of variance $N_0/2$, so the sum has mean $\pm 3\sqrt{E_s}$ and, since independent variances add, variance $3N_0/2$. It lands on the wrong side of zero with probability $Q\bigl(3\sqrt{E_s}/\sqrt{3N_0/2}\bigr) = Q(\sqrt{6E_s/N_0})$, and since $3E_s = E_b$ that is $Q(\sqrt{2E_b/N_0})$, the uncoded error rate exactly. Soft $R_3$ has a coding gain of exactly 0 dB at every target, as Hard and Soft Decisions found, and a simulation of 200,000 bits at 2 dB agrees. A soft decoder gathers back all the energy repetition spread out, while a hard decoder throws information away at the threshold.

How much gain is there to find? By Capacity and Shannon's Theorem a rate one half code with BPSK cannot work below 0.19 dB with soft decisions or 1.77 dB with hard ones. Uncoded BPSK needs 10.530 dB for $10^{-6}$, so such a code could save up to about $10.530 - 0.19 = 10.34$ dB soft, or 8.76 dB hard. The codes of Parts VII to X close much of that gap.

07.Measuring Error Rates by Simulation

Most real decoders have no formula like Equation 13, so their error rate is measured by counting failures among random words sent through a simulated channel. Take $R_3$ on $\text{BSC}(0.1)$, where the exact answer is known, $P_w = 3(0.1)^2(0.9) + (0.1)^3 = 0.028$. The companion script sends 10,000 words through a seeded random channel and sees $K = 266$ failures, an estimate of 0.0266. Figure 6 follows the estimate as trials accumulate, 0.01 after 100, 0.02 after 300, 0.022 after 1000 and 0.026333 after 3000. The question is how far to trust any one of these numbers.

Proof. $K$ counts failures in $N$ independent trials, so it is binomial, with $E[K] = N P_e$ and $\operatorname{Var}(K) = N P_e (1 - P_e)$ by Expectation and Variance. Dividing by $N$ scales the mean by $1/N$ and, by the rule $\operatorname{Var}(cX) = c^2 \operatorname{Var}(X)$, the variance by $1/N^2$. $\blacksquare$

The estimator is unbiased, and its standard error, $\sqrt{P_e (1 - P_e)/N}$, shrinks as $1/\sqrt{N}$, so halving the error bar takes four times the trials. For the run above the true standard error is $\sqrt{0.028 \times 0.972/10000} = 0.0016497$, and 0.0266 sits 0.85 standard errors below the truth. In a real simulation $P_e$ is unknown, and putting $\hat{P}_e$ in its place estimates the standard error as 0.0016091.

By the central limit theorem of The Gaussian and the Q-Function, $\hat{P}_e$ is close to Gaussian for large $N$, so it lands within $z$ standard errors of $P_e$ with probability about $1 - 2Q(z)$, and $z = 1.96$ makes that 0.95. Turning the statement around, with the estimated standard error, gives the textbook interval.

For the run above the half-width is $1.96 \times 0.0016091 = 0.0031539$, and the interval runs from 0.023446 to 0.029754, which contains 0.028. The Wald interval breaks down where error-rate simulation lives, at small $K$. With $K = 0$ it shrinks to the point 0, claiming certainty from silence, and with a few failures its lower end can drop below zero.

The repair, due to Wilson [2], keeps the unknown $P_e$ inside the standard error. It collects every value of $P_e$ for which the observed $\hat{P}_e$ lies within $z$ true standard errors, $|\hat{P}_e - P_e| \le z \sqrt{P_e (1 - P_e)/N}$. The endpoints are where equality holds, and squaring gives

Expanding both sides and collecting powers of $P_e$ gives a quadratic,

In the quadratic formula, the discriminant $(2\hat{P}_e + z^2/N)^2 - 4(1 + z^2/N)\hat{P}_e^2$ simplifies to $4 z^2 \hat{P}_e (1 - \hat{P}_e)/N + z^4/N^2$, and halving top and bottom leaves the Wilson interval.

For the run above the Wilson interval runs from 0.023623 to 0.029940. Its center, 0.026782, sits a little above $\hat{P}_e$, pulled toward one half by the $z^2/2N$ terms, most strongly when $K$ is small. Agresti and Coull found the score interval far more dependable than the Wald interval at small counts [3], and Jeruchim surveys bit error rate estimation in communication simulations [4]. Table 5 collects the numbers.

The 95% does not say that $P_e$, a fixed number, has a 95% chance of lying in this particular interval. It says that the recipe, repeated over many experiments, produces intervals that contain $P_e$ about 95% of the time. Figure 7 runs it at five flip probabilities with 10,000 trials each. At $p = 0.02$ only 9 words fail, against an exact rate of 0.001184, and at $p = 0.3$, 2155 fail against 0.216. Every interval contains its exact value.

The width also says how many trials a simulation needs. Aim for a relative half-width $r$, an interval of $\hat{P}_e \pm r P_e$. The Gaussian half-width is $z \sqrt{P_e (1 - P_e)/N}$, and requiring it to be at most $r P_e$, then squaring and solving for $N$, gives the trial count.

$N P_e$ is the expected number of failures, so Equation 22 asks for about 96 of them, and with 100 failures the relative half-width is about $z/\sqrt{100} = 0.196$. Table 6 checks the rule without the Gaussian approximation. For each rate it takes $N = \lceil 100/P_e \rceil$ trials and sums the exact binomial probabilities of every count $K$ that puts $\hat{P}_e$ within 20% of $P_e$.

The exact chance is 0.95767 in the first row. In the other two $N P_e = 100$ exactly, so the counts $K = 80$ and $K = 120$ sit on the 20% boundary, and the 0.960 includes them. Without them it is 0.949, just under 0.95, so the rule delivers about what it promises, with no margin to spare. Of 400 seeded runs of 3,572 trials at $P_e = 0.028$, 381 landed within 20%. Chebyshev's inequality from The Law of Large Numbers gives a guarantee with no Gaussian approximation, $P(|\hat{P}_e - P_e| \ge r P_e) \le \operatorname{Var}(\hat{P}_e)/(r P_e)^2 = (1 - P_e)/(N r^2 P_e)$. Making the right side 0.05 needs $N \ge (1 - P_e)/(0.05 \, r^2 P_e)$, which rounds up to 17,358 trials at $P_e = 0.028$, 5.2 times the Gaussian count, because $1/(0.05 \, r^2) = 500$ replaces $(z/r)^2 = 96.04$.

A rate of $10^{-6}$ needs about $10^8$ trials, and a storage system promising $10^{-15}$ is far beyond direct simulation. Such rates are reached by analysis, or by importance sampling, which makes failures artificially common and corrects for the distortion, as Jeruchim's survey describes.

08.Reliability in FIT, SDC and DUE

Memories and processors face the same trade-off with no sender to ask, since a flipped stored bit is wrong in the only copy. Suppose one server's memory suffers bit flips at 40,000 FIT, where a FIT is one failure in $10^9$ device-hours, so 40,000 FIT is $4 \times 10^{-5}$ flips per hour. These are the single-event upsets of Fault Models for Memory, caused by alpha particles from packaging materials [5] and by cosmic-ray particles [6], and Baumann reviews how their rate depends on the process technology [7].

Figure 8 follows one flip to its end: masked if nothing reads it, fixed if the code corrects it, a stopped program if a check notices but cannot correct it, and wrong data flowing on if no check notices.

The vocabulary follows Mukherjee, Emer and Reinhardt [8], and it maps onto ARQ. A DUE is an alarm and an SDC is a slip, except that a memory cannot resend, so every alarm costs a crash or a recovery from another copy. Designers accept a higher DUE rate to keep the SDC rate tiny, because a DUE stops the work while an SDC lets wrong answers spread.

Suppose failures arrive at a constant rate of $\lambda$ per hour, so that in any short interval of length $\Delta$ the chance of a failure is $\lambda \Delta$, independently of other intervals. In this section $t$ stands for time, not a number of correctable errors. Split the time from 0 to $t$ into $m$ equal pieces. The device survives the stretch only if it survives every piece, with probability $(1 - \lambda t/m)^m$, and as the pieces shrink the limit $(1 + x/m)^m \to e^x$ gives

where $T$ is the time to the first failure.

Proof. For any time $T \ge 0$, $T = \int_0^\infty \mathbf{1}\{T > t\} \, dt$, since the integrand is 1 for $t < T$ and 0 afterward. Taking expectations inside the integral, $E[T] = \int_0^\infty P(T > t) \, dt = \int_0^\infty e^{-\lambda t} \, dt = 1/\lambda$. A rate of $F$ FIT is $\lambda = F \times 10^{-9}$ per hour, so $1/\lambda = 10^9/F$ hours. When a failed device is restored at once, the mean time between failures equals the mean time to failure. $\blacksquare$

FIT suits budgets for two more reasons. A system that fails when any part fails survives only if all parts survive, and $e^{-\lambda_1 t} e^{-\lambda_2 t} = e^{-(\lambda_1 + \lambda_2) t}$ shows that rates in series add. A fleet of $D$ identical devices is such a system, so its rate is $D$ times one device's rate.

Now spend the server's 40,000 FIT, a raw mean time between flips of $10^9/40000 = 25{,}000$ hours, or 2.85 years. Suppose the code corrects 99.75% of flips, leaving 100 FIT uncorrected, and detects 95% of those, a DUE rate of 95 FIT, while 5% slip through as SDC at 5 FIT. These shares are illustrative, and Part XI analyzes the real split. Table 7 converts each rate with Equation 24, at 8760 hours to a year.

One server's 1,202 and 22,831 years invite complacency, but a hundred thousand servers flip a bit every 15 minutes, stop on an uncorrectable error every 4.39 days and absorb a silent corruption every 83.3 days. Schroeder, Pinheiro and Weber found DRAM errors in Google's servers far more common than earlier reports suggested [9], and Hochschild and colleagues at Google [10] and Dixit and colleagues at Meta [11] report processors that silently compute wrong results, rare on one machine and routine across a fleet.

09.Looking Ahead

Selective repeat runs close to $k/n$, stop-and-wait is crippled by idleness, and the check alone sets the residual error, $P_{\text{res}} = s/(1 - \alpha)$. Forward correction buys a fixed delay and a coding gain that repetition cannot deliver. Bit and word error rates bracket each other within a factor of $k$, simulation measures them with the Wilson interval after about $100/P_e$ trials, and hardware reliability splits into the loud DUE and the quiet SDC.

The next chapter follows these ideas into real systems, each taught properly later. Parity in early memories leads to Part XI, and Hamming's code [12] and the Reed–Muller code of the Mariner probes to Part II. Voyager's convolutional and Reed–Solomon codes belong to Parts VII and V, and their pairing, later standardized for space missions [13], to Part VI. The compact disc draws on Parts IV and V, QR codes are Reed–Solomon codes again [14], Hsiao's memory codes [15] come from Parts II and XI, and 5G NR [16] uses the LDPC, polar and hybrid ARQ schemes of Parts IX, X and XII. The project chapter then builds a channel simulator around the estimator and interval defined here.

10.Worked Examples

11.Exercises

References

1. [1]Lin, Shu and Costello, Daniel J. and Miller, Michael J. (1984). “Automatic-Repeat-Request Error-Control Schemes.” IEEE Communications Magazine, 22(12), pp. 5–17. doi:10.1109/MCOM.1984.1091865
2. [2]Wilson, Edwin B. (1927). “Probable Inference, the Law of Succession, and Statistical Inference.” Journal of the American Statistical Association, 22(158), pp. 209–212. doi:10.1080/01621459.1927.10502953
3. [3]Agresti, Alan and Coull, Brent A. (1998). “Approximate is Better than "Exact" for Interval Estimation of Binomial Proportions.” The American Statistician, 52(2), pp. 119–126. doi:10.1080/00031305.1998.10480550
4. [4]Jeruchim, Michel C. (1984). “Techniques for Estimating the Bit Error Rate in the Simulation of Digital Communication Systems.” IEEE Journal on Selected Areas in Communications, 2(1), pp. 153–170. doi:10.1109/JSAC.1984.1146031
5. [5]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
6. [6]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
7. [7]Baumann, R. C. (2005). “Radiation-Induced Soft Errors in Advanced Semiconductor Technologies.” IEEE Transactions on Device and Materials Reliability, 5(3), pp. 305–316. doi:10.1109/TDMR.2005.853449
8. [8]Mukherjee, Shubhendu S. and Emer, Joel and Reinhardt, Steven K. (2005). “The Soft Error Problem: An Architectural Perspective.” In Proceedings of the 11th International Symposium on High-Performance Computer Architecture (HPCA-11), pp. 243–247. doi:10.1109/HPCA.2005.37
9. [9]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
10. [10]Hochschild, Peter H. and Turner, Paul and Mogul, Jeffrey C. and Govindaraju, Rama and Ranganathan, Parthasarathy and Culler, David E. and Vahdat, Amin (2021). “Cores that Don't Count.” In Proceedings of the Workshop on Hot Topics in Operating Systems (HotOS '21), pp. 9–16. doi:10.1145/3458336.3465297
11. [11]Dixit, Harish Dattatraya and Pendharkar, Sneha and Beadon, Matt and Mason, Chris and Chakravarthy, Tejasvi and Muthiah, Bharath and Sankar, Sriram (2021). “Silent Data Corruptions at Scale.” arXiv:2102.11245. https://arxiv.org/abs/2102.11245
12. [12]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
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]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
15. [15]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
16. [16]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