Project: A Channel Simulator

Error-Control Strategies and Performance measured the word error rate of the three-fold repetition code $R_3$ on the binary symmetric channel $\text{BSC}(0.1)$ by simulation, counting 266 failures in 10,000 words against an exact rate of 0.028. Case Study: Codes in the Wild then quoted error rates from standards and products on trust. This chapter builds a simulator that produces numbers like these and asks what every simulation owes its reader, a reason to believe what it prints.

The simulator drives three channels, the binary symmetric channel, the binary erasure channel and BPSK over Gaussian noise, from nothing but seeded uniform random numbers, and it makes the Gaussian noise by the Box–Muller transform. Repetition codes with hard and soft decoding and the single parity code ride on those channels. Counted failures become an estimate, and the Wald and Wilson intervals, the rule of three and a formula for the number of trials turn the estimate into a claim with a stated chance of being wrong.

Every code here also has an exact error rate, so the simulator is checked against seven closed forms. Six of the seven 95% intervals contain the exact value and one does not. The chapter explains the miss, since a 95% interval that never missed would be a broken interval.

The simulator is ch11_project_channel_simulator.py in the python/ folder of the companion repository ecc-book-lab. Run as a script, it repeats every seeded experiment in the chapter, prints each value it computes beside the value stated here, and stops at the first disagreement. The four charts are drawn by ch11_charts.py. Both use only the Python standard library.

01.Setting Up

The simulator needs Python 3.10 or newer and git, and nothing else, no Python packages, no compiler and no Docker, since everything the scripts import ships with Python. Each step below follows the official documentation of the tool it installs and prefers the platform's own package manager. Commands are typed into a terminal, the window that accepts typed commands, which is the Terminal app on macOS, any terminal emulator on Linux and PowerShell on Windows.

macOS

Homebrew, the package manager most macOS developers use, is installed by the one-line command on its home page, brew.sh, which is best copied from there since the project changes it from time to time. Python and git are then one command each, and the last two lines confirm that both work.

Homebrew's documentation notes that the unversioned python command of its Python package is not on the default search path, so this chapter always types python3. Git's download page also names Apple's Xcode Command Line Tools, which ship their own git, as another route.

Linux

The Python documentation says that Python comes preinstalled on most Linux distributions and is packaged on all others, and it gives no install command. Check with python3 --version. If the version is older than 3.10, install the distribution's Python package as that distribution's documentation describes, since no official Python source covers this step. Git's download page gives one command per distribution, each run with administrator rights, which sudo provides.

Windows

The Python documentation installs Python on Windows through the Python install manager, published in the Microsoft Store and fetched with WinGet, the package manager built into current Windows. The second line installs a Python version, and any version from 3.10 on serves. Git's download page gives the WinGet command for git.

Python then runs as py or as python. The other route is Linux inside Windows, through the Windows Subsystem for Linux, version 2, or WSL2. Microsoft's documentation requires Windows 10 version 2004 (build 19041) or later, or Windows 11, and installs WSL2 with one command in a PowerShell window opened as administrator, followed by a restart.

That installs Ubuntu, where the Linux steps apply unchanged. wsl --list --online lists the other distributions, wsl --install -d <Distro> installs one by name, wsl --set-default-version 2 makes WSL2 the version for every distribution installed afterward, and wsl --set-version <Distro> 2 converts a distribution already installed under the first version of WSL.

ArchWSL, a community project, packages Arch Linux for WSL. Its documentation installs it by extracting the release zip from the project's GitHub page into a folder the user can write to and running Arch.exe. The first session runs as root, the administrator account. It sets a root password, lets members of the wheel group use sudo, creates an everyday user in that group and exits, with yourname standing for the chosen name.

Back in PowerShell, in the folder that holds Arch.exe, one command makes that user the default. The .\ prefix is how PowerShell runs a program from the current folder.

The documentation then initializes the keys that sign Arch's packages and updates the system, after which pacman, Arch's package manager, installs Python and git.

Cloning the Repository

The same three commands then fetch the companion repository and run the simulator on every platform.

In native Windows PowerShell the last line is py python\ch11_project_channel_simulator.py. The run takes well under a minute, prints each computed value beside the value stated here, and ends with All chapter 11 numbers reproduced. A disagreement prints a line starting MISMATCH and exits with a nonzero status, a program's way of telling the shell that it failed. The command python3 python/ch11_charts.py --out figures redraws the four charts as SVG files in a new folder named figures.

02.Why Simulate When a Formula Exists

Every error rate in this chapter has an exact formula, so why simulate at all? The first reason is that formulas run out. Repetition and single parity have short exact answers because their decoders fail in few enough ways to list, but the iterative decoders of the later Parts have no formula at the lengths and noise levels that matter. The second is that a formula describes the decoder on paper, not the code someone wrote. A simulator running the real encoder and decoder catches the off-by-one count and the swapped sign that a derivation never sees. The third is calibration. A simulator that will be trusted where no formula exists must first agree with every formula it can be checked against, and that is this chapter's job, which is why its codes are simple enough for every simulated number to have an exact partner.

Figure 1 shows the loop. A source draws random data bits, an encoder adds redundancy, a channel corrupts the codeword and a decoder makes its best guess. Each wrong guess adds one to the failure count $K$, and after $N$ words the estimate is $K/N$.

The simulator keeps two generators. The channel generator starts from the seed and supplies every draw the channel uses, and the data generator starts from the seed plus $10^9$ and supplies the data bits. Because the streams never mix, the channel sees the same draws whatever data is sent and whatever decoder is listening. Two decoders run with one seed therefore face identical noise, a technique called common random numbers, and the difference in their failure counts measures the decoders rather than luck. The worked example Hard and Soft Decoders Word by Word uses it.

03.Pseudorandom Numbers and Seeds

A computer following instructions cannot be random, but it can run a fixed recipe whose output passes the statistical tests that matter, and such a recipe is called a pseudorandom number generator. Python's is the Mersenne Twister of Matsumoto and Nishimura [1], whose sequence repeats only after $2^{19937} - 1$ steps, a number with more than 6,000 digits.

The call random.Random(17) builds a private generator started from the seed 17, and each call of .random() returns the next number of its sequence, a value in $[0, 1)$. The same seed gives the same sequence of uniforms every time the script runs. A colleague who runs the same script with the same seed and trial count therefore gets the same failure count in practice, within limits set out after the definition below, and a disagreement points at a change in the code rather than at chance.

The simulator calls only .random(), and the restriction is deliberate. The Python documentation guarantees that random() reproduces the same sequence for the same seed across Python versions, and it makes no such guarantee for the methods built on top of it, such as randint, gauss and choice. Every random quantity in the chapter is therefore built from .random() by the simulator's own code. The guarantee covers the uniforms and nothing computed from them. The counts on the discrete channels compare uniforms with fixed thresholds, so in practice they reproduce everywhere. The Gaussian counts pass the uniforms through log, cos and sin from the platform's math library and scale them by a sigma computed with pow, so they reproduce everywhere too, unless two libraries round one of those functions differently in the last bit and a sample lands on the other side of a decision. The values of .random() are whole multiples of $2^{-53}$, so $P(u < a) = a$ to within $2^{-53}$, and a comparison rng.random() < p is true with probability $p$ to within $2^{-53}$. The Mersenne Twister is unfit for cryptography, since enough of its output predicts the rest, but a simulation needs statistical quality rather than secrecy.

04.Building the Channels

Each discrete channel turns one uniform draw into one decision about one bit, and Figure 2 shows the rule. The binary symmetric channel $\text{BSC}(p)$ of Three Discrete Channels flips a bit when its draw falls below $p$, which happens with probability $p$. The binary erasure channel $\text{BEC}(\varepsilon)$ replaces a bit by a mark meaning "unknown" when its draw falls below $\varepsilon$.

In bsc the comparison gives True or False, int turns that into 1 or 0, and ^, exclusive or, flips the bit exactly when the value is 1. In bec, Python's None plays the erasure mark. Each bit consumes one draw whether or not anything happens to it, so two runs with the same seed stay aligned draw for draw.

The Gaussian channel of The Gaussian Channel and BPSK sends bit 0 as the voltage $+1$ and bit 1 as $-1$ and adds independent Gaussian noise of mean 0 and variance $\sigma^2$ to each. Energy per Bit and the Decibel tied $\sigma$ to the energy per information bit. With unit energy per transmitted symbol and code rate $R_c$, each information bit carries energy $E_b = 1/R_c$, the noise variance is $N_0/2$, and so

A value in decibels becomes a ratio through $10^{\text{dB}/10}$, so 4 dB is a ratio of 2.5119. Uncoded BPSK has $R_c = 1$ and $\sigma = 1/\sqrt{2 \times 2.5119} = 0.4462$. The rate-$1/3$ code $R_3$ splits each bit's energy over three pulses, so the noise on each is relatively larger, $\sigma = \sqrt{3/(2 \times 2.5119)} = 0.7728$. Comparing codes at equal $E_b/N_0$ charges each code for the energy its redundancy spends, the fair comparison of Coding Gain.

The expression 1.0 - 2.0 * b maps bit 0 to $+1$ and bit 1 to $-1$, and noise.next() supplies one standard normal sample, with mean 0 and variance 1, which sigma scales. The uniform generator cannot supply that sample directly, and the next section builds it.

05.Gaussian Samples by Box–Muller

The Box–Muller transform [2] makes two Gaussian samples out of two uniform numbers. Take $u_1 = 0.25$ and $u_2 = 0.1$, and compute a radius $R = \sqrt{-2 \ln u_1}$ and an angle $\theta = 2\pi u_2$. Here $-2 \ln 0.25 = 2.7726$, so $R = 1.6651$, and $\theta = 0.6283$ radians, which is $36^\circ$. The point at distance $R$ from the origin in direction $\theta$ has coordinates $z_0 = R \cos\theta = 1.6651 \times 0.8090 = 1.3471$ and $z_1 = R \sin\theta = 1.6651 \times 0.5878 = 0.9787$, and those two coordinates are the samples. Figure 3 draws the step.

Why bell-curve numbers? The answer lies in how two independent standard normals look together. Take $X$ and $Y$ independent, each with the density $\varphi(x) = e^{-x^2/2}/\sqrt{2\pi}$ of The Gaussian and the Q-Function. The density of the pair is the product,

where $r = \sqrt{x^2 + y^2}$ is the distance of $(x, y)$ from the origin. The density depends on that distance alone, so a cloud of such points looks the same from every direction, and the theorem turns that symmetry into a recipe.

Proof. Describe $(X, Y)$ by its distance $R$ from the origin and its angle $\Theta$, and show that the transform builds a distance and an angle that behave the same way.

The patch of the plane between radii $r$ and $r + dr$ and between angles $\theta$ and $\theta + d\theta$ is nearly a rectangle with sides $dr$ and $r\,d\theta$, since an arc of angle $d\theta$ at radius $r$ has length $r\,d\theta$. The chance that $(X, Y)$ lands in it is the density times the area, $\frac{1}{2\pi} e^{-r^2/2} \, r\,dr\,d\theta$. Adding up the patches, the chance that the point lies within distance $\rho$ and at an angle below $\psi$ is

since the inner integral is $\bigl[-e^{-r^2/2}\bigr]_0^{\rho} = 1 - e^{-\rho^2/2}$ and the outer one multiplies it by $\psi/2\pi$.

The result is a function of $\psi$ alone times a function of $\rho$ alone. Letting $\rho$ grow without bound gives $P(\Theta \le \psi) = \psi/2\pi$, so the angle is uniform on $[0, 2\pi)$. Setting $\psi = 2\pi$ gives $P(R \le \rho) = 1 - e^{-\rho^2/2}$. The joint probability is the product of the two, which is what independence of $R$ and $\Theta$ means, and in terms of the squared distance $P(R^2 > t) = e^{-t/2}$ for every $t \ge 0$.

Now compare the transform. Its angle $2\pi U_2$ is uniform on $[0, 2\pi)$. Its squared radius $-2 \ln U_1$ exceeds $t$ exactly when $U_1 < e^{-t/2}$, which has probability $e^{-t/2}$, the law of $R^2$. The two are independent because $U_1$ and $U_2$ are. A point is fixed by its radius and angle, so $(Z_0, Z_1)$ behaves exactly like $(X, Y)$. $\blacksquare$

One consequence is that the squared radius exceeds 2 with probability $e^{-1} = 0.3679$, so about 37% of Box–Muller points land outside the circle of radius $\sqrt{2}$. The simulator's version keeps one sample in reserve, since each pair of draws gives two.

The class hands out the cosine sample at once and keeps the sine sample for the next call. The line that sets u1 subtracts the draw from 1 because random() can return exactly 0.0, and $\ln 0$ does not exist. Subtracting moves the range from $[0, 1)$ to $(0, 1]$ without changing the uniform distribution.

With seed 17 the first two draws are 0.52198 and 0.80669, so $u_1 = 0.47802$, $R^2 = -2 \ln 0.47802 = 1.4762$, $R = 1.2150$ and $\theta = 2\pi \times 0.80669 = 5.0686$ radians. Then $\cos\theta = 0.3487$ and $\sin\theta = -0.9372$, so the first two samples are $0.4237$ and $-1.1387$. Over 100,000 samples from the same seed the mean is 0.0044 and the variance 0.9981, against 0 and 1 for a true standard normal. The mean of 100,000 standard normal samples has a standard deviation, or standard error, of $1/\sqrt{100{,}000} = 0.0032$, so 0.0044 lies about 1.4 standard errors from 0, well within the spread chance allows. Of the same samples, 5,014 exceed 1.96 in size against $2Q(1.96) = 0.0500$ of them expected, and the worked example Both Intervals for a Tail Fraction shows that the two agree. Figure 4 lays the histogram over the bell curve.

Soft decoding will need one more fact, that suitably weighted sums of Gaussians are Gaussian again.

Proof. Choose the angle $\alpha$ with $\cos\alpha = a$ and $\sin\alpha = b$, which exists because $(a, b)$ lies on the unit circle. Rotating $(X, Y)$ by $-\alpha$ about the origin gives $(aX + bY, \, -bX + aY)$. A rotation changes no distance from the origin and no area, and the density Equation 3 depends on the distance alone, so the rotated point has the same density as $(X, Y)$, and its first coordinate has the same distribution as $X$. $\blacksquare$

A corollary follows by induction. The sum $S_n = Z_1 + \cdots + Z_n$ of $n$ independent standard normals has the distribution of $\sqrt{n}\,Z$, with $Z$ standard normal. It holds for $n = 1$, since $S_1 = Z_1$. If it holds for $n$, then $S_{n+1}$ behaves like $\sqrt{n+1} \bigl( \sqrt{n/(n+1)}\,Z + \sqrt{1/(n+1)}\,Z_{n+1} \bigr)$, whose two weights have squares adding to 1, so by the lemma the bracket is standard normal.

06.Encoders and Decoders

The repetition code $R_n$ sends each data bit $n$ times, and on the binary symmetric channel its decoder takes a majority vote. On the Gaussian channel there are the two ways of Hard and Soft Decisions. A hard decoder first turns each received voltage into a bit, 1 if negative and 0 otherwise, and then votes. A soft decoder adds the voltages and decides on the sign of the sum.

The two can disagree. Suppose $R_3$ receives $0.9$, $-1.4$ and $0.2$. The hard decoder sees 0, 1 and 0 and votes for 0. The soft decoder adds the voltages to $-0.3$ and decides 1, weighing the strong $-1.4$ above two weak positives, and Likelihoods and Log-Likelihood Ratios explains why that is right. The log-likelihood ratio of a bit given a received value $y$ on this channel is $2y/\sigma^2$, positive values favoring 0, and independent evidence about one bit adds, so the total evidence from three pulses is

The factor $2/\sigma^2$ is positive, so the sign of $L$ is the sign of the plain sum. The hard decoder throws away the size of each pulse before it votes, and that is where its loss comes from.

On the erasure channel a bit that arrives is certainly correct, since this channel never flips anything. A repetition decoder takes any surviving copy and fails only when all $n$ copies are erased, with probability $\varepsilon^n$.

The single parity code of Single Parity appends one bit so that the number of 1s in the codeword is even. Figure 5 follows the word 10110010, the data 1011001 with parity bit 0. One flip leaves an odd count and is detected, while two flips restore an even count and pass unseen. On the erasure channel the same parity bit does better than detect.

Proof. The bits of a codeword add to 0 modulo 2. Write the erased bit as $x$ and the sum of the others as $s$. Then $x + s \equiv 0 \pmod 2$, and since adding 1 and subtracting 1 agree modulo 2, $x \equiv s \pmod 2$. With two erased bits $x_1$ and $x_2$, the one equation $x_1 + x_2 \equiv s \pmod 2$ is met both by $x_1 = 0, \, x_2 = s$ and by $x_1 = 1, \, x_2 = 1 + s$, two codewords the arrived bits cannot tell apart. $\blacksquare$

In the erased word 1?110010 the seven known bits hold four 1s, so the erased bit is 0. This is the smallest case of the point of Errors and Erasures Together. A code of minimum distance 2 detects one error but fills one erasure, because an erasure announces where the damage is.

Each trial sends one word and reports whether the decoder failed, and the loop around the trials is short.

Each trial draws data bits from source, encodes them, passes the word through a channel driven by channel or noise, decodes, and returns True on a failure, which Python adds as 1. For single parity on the erasure channel the trial also raises an error if a filled word ever differs from the word sent, so the lemma is checked on every word of that run.

07.The Monte Carlo Estimator

A run reports $K$ failures in $N$ words and estimates the error rate under study $P_e$, here a word error rate, by $\hat{P}_e = K/N$. Another seed gives another $K$. The coverage experiment of the next section sends $R_3$ over $\text{BSC}(0.1)$, where $P_e = 0.028$, in 1,000 runs of 1,000 words with seeds 1 to 1,000, and the failure counts range from 13 to 47. A single estimate means little until its spread is known.

Measuring Error Rates by Simulation supplies that spread. When the $N$ trials are independent and each fails with probability $P_e$, the estimate is unbiased, $E[\hat{P}_e] = P_e$, so it is right on average, and its variance is $P_e(1 - P_e)/N$, so its standard deviation shrinks as $1/\sqrt{N}$. The seeded runs bear this out. At $N = 1{,}000$ the predicted standard deviation is $\sqrt{0.028 \times 0.972/1{,}000} = 0.00522$, and the 1,000 seeded estimates have mean 0.0280 and standard deviation 0.00520.

08.Intervals That Miss

The variance gives the spread of $\hat{P}_e$ in terms of $P_e$, the one thing a simulation does not know. A confidence interval turns this around. It is a rule that takes $K$ and $N$ and returns a range, built so that over many repeated experiments the range contains the true $P_e$ a stated fraction of the time, 95% here.

Measuring Error Rates by Simulation also built the two rules this chapter uses, and a short recap is enough here. The Wald interval, $\hat{P}_e \pm z\sqrt{\hat{P}_e(1 - \hat{P}_e)/N}$ with $z = 1.96$, puts the estimate in place of the unknown rate inside the standard deviation. Wilson's interval [3] keeps the unknown rate there and collects every $P_e$ with $|\hat{P}_e - P_e| \le z\sqrt{P_e(1 - P_e)/N}$. Squaring that condition at its two ends gives the quadratic $A P_e^2 - B P_e + C = 0$ with $A = 1 + z^2/N$, $B = 2\hat{P}_e + z^2/N$ and $C = \hat{P}_e^2$, and its roots $\bigl(B \pm \sqrt{B^2 - 4AC}\bigr)/2A$ are the ends of the interval.

The simulator here repeats that section's run, $R_3$ on $\text{BSC}(0.1)$ with seed 2026 and 10,000 words, and counts the same 266 failures. The Wald interval runs from 0.02345 to 0.02975 and the Wilson interval from 0.02362 to 0.02994. Both contain 0.028, and at 266 failures they nearly agree. The difference shows when failures are few.

Here the truth is known, so coverage can be measured. The coverage experiment repeats the $R_3$ run with seeds 1 to 1,000, first at 1,000 words per run and then at 100, and counts the intervals of each kind that contain 0.028. Table 1 gives the result.

At 1,000 words per run both rules come close to the expected 950. Figure 6 draws the first 50 Wilson intervals, and two miss against 2.5 expected. Run 20 counted 45 failures, and its interval, from 0.0338 to 0.0597, lies wholly above 0.028. Run 50 counted 16, and its interval, from 0.0099 to 0.0258, lies wholly below. Neither run is broken. Each drew an unusually harsh or gentle stretch of noise, the kind a 95% rule is built to be fooled by about once in twenty runs.

At 100 words per run the rules part ways, and the reasons explain every miss. Only about 2.8 failures are expected, and the chance of none is $0.972^{100} = 0.0584$, so about 58 runs should see $K = 0$, and 49 did. At $K = 0$ the Wald interval collapses to the point 0, since $\hat{P}_e(1 - \hat{P}_e) = 0$, and cannot contain 0.028. Those 49 runs make 49 of Wald's 50 misses, and the last is a run with nine or more failures, whose interval cannot reach down to 0.028. At $K = 1$ the Wald interval reaches below zero, to $-0.0095$, an impossible probability. Wald's 950 is a coincidence, since nearly all its misses come from one value of $K$ at which it cannot succeed.

Wilson never collapses. At $K = 0$ its interval runs from 0 to 0.0370 and contains 0.028. Its 19 misses all come from runs with 7, 8 or 9 failures, whose intervals start above 0.028, at 0.0343 for $K = 7$. Because $K$ takes only whole values, no rule hits exactly 95% at small $N$, and the exact coverage of a rule is the total binomial probability of the values of $K$ whose intervals contain the true rate. For Wilson at $P_e = 0.028$ and $N = 100$ that total is 0.9774, against the 981 in 1,000 measured, so here Wilson errs on the safe side.

It does not always. At $P_e = 0.0017$ and $N = 100$ a single failure already lifts Wilson's lower end above the true rate, to 0.0018, so only the runs with no failures cover it, and the exact coverage falls to $0.9983^{100} = 0.8435$. Brown, Cai and DasGupta [4] document such dips near 0 and 1, where the discreteness of $K$ bites hardest, and they still recommend Wilson's interval over Wald's. Agresti and Coull [5] showed that approximate intervals of this kind serve better in practice than the so-called exact ones.

09.When No Errors Appear

A good code at low noise often shows no failures at all. Send $R_5$, the five-fold repetition code, over $\text{BSC}(0.01)$ for 20,000 words with seed 18, and $K = 0$. That is no surprise. $R_5$ fails when three or more of its five bits flip, with probability $10p^3(1-p)^2 + 5p^4(1-p) + p^5 = 9.801 \times 10^{-6} + 4.95 \times 10^{-8} + 10^{-10} = 9.8506 \times 10^{-6}$, so 20,000 words expect 0.197 failures and see none with probability 0.821.

The Wald interval at $K = 0$ is the point 0, a claim that the code never fails. The honest question is the largest $P_e$ still consistent with zero failures, say the largest $P_e$ that gives zero failures at least 5% of the time. Zero failures in $N$ independent words has probability $(1 - P_e)^N$, and setting that to 0.05 gives $P_e = 1 - 0.05^{1/N}$, which for $N = 20{,}000$ is $1.4978 \times 10^{-4}$.

Proof. The curve $e^x$ lies above its tangent line at 0, so $e^x \ge 1 + x$, and with $x = -P_e$ this gives $1 - P_e \le e^{-P_e}$. Both sides are nonnegative for $P_e \le 1$, so raising them to the power $N$ keeps the order, $(1 - P_e)^N \le e^{-N P_e}$. For $P_e \ge 3/N$ the right side is at most $e^{-3} = 0.0498$, below 0.05. $\blacksquare$

The exact bound solves $(1 - P_e)^N = 0.05$, and since $-\ln 0.05 = 2.9957$, the rounded 3 works well. For the $R_5$ run the rule gives $3/20{,}000 = 1.5 \times 10^{-4}$, against the exact $1.4978 \times 10^{-4}$. Hanley and Lippman-Hand [6] made the rule popular in medicine, where a trial that sees no side effects in $N$ patients faces the same question.

The Wilson interval at $\hat{P}_e = 0$ reduces to the range from 0 to $z^2/(N + z^2)$, here $3.8416/20{,}003.8416 = 1.9204 \times 10^{-4}$, close to a rule of 3.84 rather than 3. A two-sided 95% interval leaves 2.5% at each end, so its upper end matches a one-sided bound at 97.5%, and $-\ln 0.025 = 3.6889$ gives $1.8444 \times 10^{-4}$, near Wilson's value. The rule of three answers the one-sided question of how large the rate could be, usually the question asked after a clean run.

None of this says that $R_5$ fails at a rate of $1.5 \times 10^{-4}$. It says that 20,000 clean words cannot rule out a rate that high, about 15 times the true one. Pinning the rate down takes a run long enough to see failures, about 10.2 million words for 100 of them.

10.How Many Trials to Run

Measuring Error Rates by Simulation also turned the variance into a trial count. Asking for a 95% half-width of at most $r$ times $P_e$ gives

For 20% precision $(1.96/0.2)^2 = 96.04$, and $N P_e$ is the expected number of failures, so for small $P_e$ the formula asks for about 96 of them, the source of that section's rule of thumb of counting about 100 errors. With $K \approx N P_e$ failures and small $P_e$, the relative half-width is about $z/\sqrt{K}$. For 10% precision the factor is $(1.96/0.1)^2 = 384.16$. Precision depends on failures, not trials, which is why rare events are expensive. At $P_e = 10^{-5}$, 20% precision needs 9.60 million trials.

One rule matters more than the formula. Fix $N$ before the run. An experimenter who checks the interval after every word and stops when it contains the hoped-for value stops at a lucky moment far more often than the 95% level allows, because that level assumes a trial count chosen in advance. Jeruchim [7] surveys methods for estimating bit error rates by simulation, including ways to cut the trial count at rates too low for plain counting.

11.Checking the Closed Forms

Every experiment can now meet its exact answer. The binary channels take their closed forms from Counting Errors with the Binomial Distribution. $R_3$ on $\text{BSC}(p)$ fails when two or three bits flip, with probability $3p^2(1-p) + p^3$, which is 0.028 at $p = 0.1$. On $\text{BEC}(\varepsilon)$ it fails only when all three are erased, with probability $\varepsilon^3 = 0.008$ at $\varepsilon = 0.2$.

The Gaussian forms need $Q(x)$, the probability that a standard normal exceeds $x$. Python has no $Q$, but its math.erfc, the complementary error function, gives it through

Uncoded BPSK fails on bit 0 when $1 + \sigma Z < 0$, that is when $Z < -1/\sigma$, which by symmetry has probability $Q(1/\sigma)$, and Equation 1 with $R_c = 1$ makes this $Q(\sqrt{2E_b/N_0})$. Bit 1 is the mirror image. The hard $R_3$ decoder sees each pulse wrong with probability $p = Q(\sqrt{2E_b/3N_0})$ and fails when two or three pulses are wrong, with probability $3p^2(1-p) + p^3$. The worked example The Gaussian Closed Forms at 4 dB evaluates both. The soft decoder needs a theorem.

Proof. Take bit 0, sent as $+1$ on each of $n$ pulses, with noise variance $\sigma_n^2 = n/(2E_b/N_0)$ per pulse from Equation 1 with $R_c = 1/n$. The decoder fails when $n + \sigma_n(Z_1 + \cdots + Z_n) < 0$. By the corollary of the rotation lemma the sum of the $Z_i$ behaves like $\sqrt{n}\,Z$, so the decoder fails when $Z < -\sqrt{n}/\sigma_n$. Since $\sqrt{n}/\sigma_n = \sqrt{n \cdot 2(E_b/N_0)/n} = \sqrt{2E_b/N_0}$, the failure probability is $Q(\sqrt{2E_b/N_0})$, and bit 1 is the mirror image. $\blacksquare$

Repetition with soft decoding therefore gains nothing over sending the bit once. The $n$ pulses spend the bit's energy in pieces, and the soft decoder gathers all of it back. Hard decoding throws part of it away and does worse, more than twice the error rate of uncoded BPSK at 4 dB.

Single parity on the binary symmetric channel misses an error when an even, nonzero number of bits flip, and the binomial theorem gives that probability in closed form.

Proof. Write $q = 1 - p$. The binomial theorem expands $(q + p)^n = \sum_i \binom{n}{i} p^i q^{n-i}$, the sum over $i$ of the probabilities of exactly $i$ flips, and $(q - p)^n$ into the same terms with a minus sign on every odd $i$. Adding the two cancels the odd terms and doubles the even ones, so $2P_{\text{even}} = 1 + (1 - 2p)^n$. Zero flips, with probability $q^n$, is no error, and subtracting it leaves the undetected errors. $\blacksquare$

For the (8,7) code at $p = 0.01$, $0.98^8 = 0.850763$, so the even probability is $0.92538151$, and subtracting $0.99^8 = 0.92274469$ leaves $P_{\text{ud}} = 0.00263682$. Lin and Costello [8] derive the same quantity for every linear code through its weight distribution. The detected fraction is the odd part, $(1 - 0.850763)/2 = 0.07462$, so about 7,461.8 of 100,000 words should be flagged, and the run with seed 13 flags 7,565. On the erasure channel single parity fails to fill a word when two or more bits are erased, with probability $1 - (1 - \varepsilon)^n - n\varepsilon(1 - \varepsilon)^{n-1}$, which at $n = 8$ and $\varepsilon = 0.1$ is $1 - 0.430467 - 0.382638 = 0.18690$.

Table 2 lines up all seven experiments with their 95% Wilson intervals and exact values, and Figure 7 draws each interval divided by its exact value.

The erasure run is the miss. It counted 741 failures where 800 were expected, and with a standard deviation of $\sqrt{100{,}000 \times 0.008 \times 0.992} = 28.17$ failures, 741 lies 2.09 standard deviations low, so its interval stops at 0.007961, just short of 0.008. Nothing is wrong with the simulator. Seven 95% intervals expect $7 \times 0.05 = 0.35$ misses, and if they were independent the chance that at least one misses would be $1 - 0.95^7 = 0.3017$. They are not quite independent, since the hard and soft runs share seed 16 and fail together often, on 894 of the soft decoder's 1,250 failures, so 0.3017 is an approximation, though the expected 0.35 misses holds whatever the dependence. Two further runs confirm the diagnosis. The same seed continued to 1,000,000 words gives 7,974 failures and an interval from 0.007802 to 0.008150, which contains 0.008, and the 100,000-word run repeated with seeds 1 to 100 gives 98 intervals that contain it.

The tempting repair is to change the seed until the miss goes away. That is seed shopping, and it destroys the coverage the interval claims. The seeds here are reported with their misses, and the miss stays in the table.

Figure 8 repeats the Gaussian check from 0 to 7 dB in steps of 1 dB, with 100,000 words per point and seed $100 + \text{dB}$, for uncoded BPSK and hard and soft $R_3$. The soft points sit on the uncoded curve, as the theorem says, and the hard points on their own higher curve. Of the 24 intervals one misses, hard $R_3$ at 1 dB with seed 101, which counted 8,727 failures against 8,536.0 expected. Twenty-four intervals expect 1.2 misses, and if they were independent the chance that all 24 cover would be only $0.95^{24} = 0.2920$. The three curves share a seed at each point, and the hard and soft counts are strongly correlated, as the worked example Hard and Soft Decoders Word by Word shows at 4 dB, so 0.2920 is an approximation. One miss is unremarkable.

12.Looking Ahead

The simulator is now calibrated. It agrees with every closed form it can be checked against, its misses, one in seven intervals and one in twenty-four, sit close to the 0.35 and 1.2 a 95% rule expects, and every number it reports carries a seed and a trial count that reproduce it. With longer codes and stronger decoders in place of repetition and parity, the same loop will later measure error rates that have no formula.

The next chapter is a lab that takes single parity into hardware. It builds a parity generator and checker in SystemVerilog, simulates them with Verilator, and drives them from a cocotb testbench in Python that compares every hardware output with a software model like this one. Part II then turns to the arithmetic longer codes are built from, starting with the integers and arithmetic modulo a whole number.

13.Worked Examples

14.Exercises

References

1. [1]Matsumoto, Makoto and Nishimura, Takuji (1998). “Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator.” ACM Transactions on Modeling and Computer Simulation, 8(1), pp. 3–30. doi:10.1145/272991.272995
2. [2]Box, G. E. P. and Muller, Mervin E. (1958). “A Note on the Generation of Random Normal Deviates.” The Annals of Mathematical Statistics, 29(2), pp. 610–611. doi:10.1214/aoms/1177706645
3. [3]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
4. [4]Brown, Lawrence D. and Cai, T. Tony and DasGupta, Anirban (2001). “Interval Estimation for a Binomial Proportion.” Statistical Science, 16(2), pp. 101–133. doi:10.1214/ss/1009213286
5. [5]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
6. [6]Hanley, James A. and Lippman-Hand, Abby (1983). “If Nothing Goes Wrong, Is Everything All Right? Interpreting Zero Numerators.” JAMA, 249(13), pp. 1743–1745. doi:10.1001/jama.1983.03330370053031
7. [7]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
8. [8]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.