Channels, Signals and Likelihoods

The previous chapter, Probability for Coding, treated a channel as one number, the probability $p$ that a bit flips, and closed with a voltage example in which each bit left the transmitter as a pulse of $\pm 1$ volt and arrived blurred by Gaussian noise. The receiver in that example compared each voltage with zero, kept the resulting bit and threw the voltage away. That choice was never justified. A voltage of 0.05 and a voltage of 1.9 both became the same bit, although the first is nearly a coin toss and the second is nearly certain.

This chapter asks what a receiver should do with what it sees. Three discrete channels that fail in different ways come first, with a proof that choosing the most probable input makes the fewest errors. The Gaussian channel follows, with enough geometry to prove that the matched filter is the best way to collapse a noisy pulse into one number, then the decibel scale, a measured comparison of hard and soft decisions, and the log-likelihood ratio that later decoders consume. The chapter ends with channels that remember, through the Gilbert–Elliott model of bursts, and with the faults that memory codes survive.

The tools are Bayes' rule, the Gaussian density and the Q-function from the previous chapter, plus a little vector algebra built here from nothing. Every number in the chapter is recomputed by ch03_channels_signals_and_likelihoods.py, in the python/ folder of the companion repository ecc-book-lab, which prints each value beside the one the text states and stops at the first disagreement. The charts are drawn by ch03_charts.py in the same folder.

01.Three Discrete Channels

Send the four bits 1011 through three channels, each with a fault probability of 0.1 per bit, and look at one particular output from each.

On the binary symmetric channel of the previous chapter, written $\text{BSC}(p)$, every bit flips with probability $p = 0.1$ whatever its value. The output 1001, with only the third bit flipped, has probability $0.9 \times 0.9 \times 0.1 \times 0.9 = 0.0729$. The receiver sees a word that looks perfectly valid and has no idea which bit, if any, is wrong.

On the binary erasure channel, written $\text{BEC}(\varepsilon)$, a bit is never flipped. With probability $\varepsilon = 0.1$ it is lost, and the receiver sees a third symbol, written ?, in its place. The output 1?11 has probability $0.9^3 \times 0.1 = 0.0729$, the same number, but now the receiver knows exactly where the damage is. A disk sector that fails its own internal check, or a network packet that never arrives, behaves this way.

On the Z-channel, written $\text{Z}(p)$, only one direction of fault happens. A 1 becomes 0 with probability $p = 0.1$, and a 0 always arrives as 0. It models a memory cell that stores a 1 as charge, since charge can leak away but cannot appear from nothing. The output 1001 needs the third bit, a 1, to drop, while the two other 1s survive with probability 0.9 each and the 0 survives with certainty, so its probability is $0.9 \times 1 \times 0.1 \times 0.9 = 0.081$.

The three products above are this formula with three different tables of transition probabilities, drawn in Figure 1 and listed in Table 1.

The repetition code $R_3$ of Why Codes Exist, which sends every bit three times, fares differently on each channel, and each channel calls for its own decoder. On $\text{BSC}(0.1)$ the majority vote fails when two or more copies flip, with probability $3p^2 - 2p^3 = 0.028$. On $\text{BEC}(0.1)$ a surviving copy is never wrong, so one survivor is enough, and decoding fails only when all three copies are erased, with probability $\varepsilon^3 = 0.001$. Even then a guess is right half the time, so the bit error probability is 0.0005.

On $\text{Z}(0.1)$ a received 1 can only have come from a sent 1, because a 0 never turns into a 1. The decoder that respects this outputs 1 if any copy reads 1, and 0 otherwise. It never errs on a sent 0, and it errs on a sent 1 only when all three copies drop, with probability $p^3 = 0.001$, so with equally likely bits its error probability is 0.0005. A majority vote on the same channel fails on a sent 1 whenever two or more copies drop, with probability $3p^2(1-p) + p^3 = 0.028$, or 0.014 averaged over equally likely bits. The rule that matches the channel is 28 times better.

The asymmetry also changes what a received bit means. With equally likely inputs, a received 0 on $\text{Z}(0.1)$ comes from a sent 0 with probability $0.5$ and from a dropped 1 with probability $0.5 \times 0.1 = 0.05$, so Bayes' rule gives $P(X = 1 \mid Y = 0) = 0.05/0.55 = 0.0909$. A received 1 is certain and a received 0 is doubtful.

02.Decisions by Bayes' Rule

A sensor line carries a rare alarm bit. It sends 1 with probability 0.05 and 0 otherwise, over $\text{BSC}(0.1)$, and the receiver sees a 1. Bayes' rule from Probability for Coding gives the probability that an alarm was really sent,

$$P(X = 1 \mid Y = 1) = \frac{P(Y = 1 \mid X = 1)\,P(X = 1)}{P(Y = 1)} = \frac{0.9 \times 0.05}{0.9 \times 0.05 + 0.1 \times 0.95} = \frac{0.045}{0.14} = 0.3214.$$

A received 1 is more likely a flipped 0, with probability 0.095, than a true alarm, with probability 0.045. On a received 0 the two candidates have probabilities $0.1 \times 0.05 = 0.005$ for an alarm and $0.9 \times 0.95 = 0.855$ for no alarm. A receiver that always reports the more probable input therefore says 0 whatever it sees, and it is wrong exactly when an alarm was sent, with probability 0.05. A receiver that believes the channel and reports the received bit is wrong whenever the channel flips, with probability 0.1. Always saying 0 makes half as many errors.

Proof. A decision rule is correct exactly when the input equals the decision made for the output that occurred. The events "$Y = y$ and $X = \hat{x}(y)$" for different outputs $y$ cannot happen together, so their probabilities add, and

Each term of the sum depends only on the decision made for its own $y$. The sum is therefore as large as possible when every term is as large as possible, which means choosing, for each $y$, the input $x$ that maximizes $P(y \mid x)P(x)$. That is the MAP rule. The probability of error is $1 - P(\text{correct})$, so the MAP rule minimizes it. For a continuous output such as a voltage, the sum becomes an integral and $P(y \mid x)$ becomes a density $f(y \mid x)$, and the argument is unchanged, since an integral is largest when its integrand is largest at every point. $\blacksquare$

On the binary symmetric channel the ML rule takes a familiar form. Recall from Why Codes Exist that the Hamming distance between two words of equal length is the number of positions in which they differ.

Proof. Let a codeword $\mathbf{c}$ of length $n$ differ from the received word $\mathbf{y}$ in $d$ positions. By Equation 1, those $d$ positions each contribute a factor $p$ and the other $n - d$ positions each contribute $1 - p$, so

Because $p < 1/2$, the ratio $p/(1-p)$ is less than 1, so the likelihood strictly decreases as $d$ grows. The largest likelihood belongs to the smallest distance. $\blacksquare$

The majority vote of Why Codes Exist was therefore not a rule of thumb. With equally likely inputs on a binary symmetric channel, it is the optimal decoder of $R_3$. The same reasoning applied to the likelihoods of the Z-channel produces its any-1 rule, and applied to the erasure channel it says to ignore the erased copies.

03.The Gaussian Channel and BPSK

A transmitter cannot send a bit. It sends a physical quantity, a voltage on a wire or the phase of a radio wave, and the simplest way to carry one bit is to send one of two opposite values. Binary phase-shift keying, or BPSK, sends the amplitude $+a$ or $-a$, named after the radio version, which shifts a carrier wave by half a cycle.

This book maps bit 0 to $+a$ and bit 1 to $-a$, the reverse of the voltage example in Probability for Coding. The reason is algebraic. The amplitude for bit $b$ is then $a(-1)^b$, and the exclusive-or of two bits, written $\oplus$, becomes a product of signs, $(-1)^{b_1 \oplus b_2} = (-1)^{b_1}(-1)^{b_2}$, which can be checked on the four cases. Parity checks are exclusive-ors, so they turn into products of signs when later chapters decode directly from voltages.

The received value is $y = x + n$, where $x = \pm a$ is the sent amplitude and $n$ is noise. With $a = 1$ and noise standard deviation $\sigma = 0.5$, the values of the previous chapter, a sent 0 produces a $y$ distributed as $N(1, 0.25)$ and a sent 1 produces $N(-1, 0.25)$.

The ML decision compares the two likelihoods. Their ratio is

$$\frac{f(y \mid +a)}{f(y \mid -a)} = \exp\left(\frac{(y + a)^2 - (y - a)^2}{2\sigma^2}\right) = \exp\left(\frac{2ay}{\sigma^2}\right),$$

since the constant in front cancels and $(y + a)^2 - (y - a)^2 = 4ay$. The exponential exceeds 1 exactly when its exponent is positive, so the ML receiver decides 0 when $y > 0$ and 1 when $y < 0$. The threshold at zero was the maximum likelihood rule all along. It errs on a sent 0 when the noise pushes $y$ below zero, that is when $n < -a$, which has probability $Q(a/\sigma) = Q(2) = 0.02275$, and by symmetry the same holds for a sent 1.

With unequal priors $\pi_0 = P(b = 0)$ and $\pi_1 = P(b = 1)$, the MAP rule decides 0 when $\pi_0 f(y \mid +a) > \pi_1 f(y \mid -a)$. Dividing both sides by $\pi_0 f(y \mid -a)$ and taking logarithms turns this into $2ay/\sigma^2 > \ln(\pi_1/\pi_0)$, so the threshold moves from zero to

When 0 is the more likely bit, $\pi_1 < \pi_0$, the logarithm is negative and the threshold slides toward $-a$, enlarging the region that decides 0. The shift is proportional to $\sigma^2$, so a quiet channel barely moves the threshold and a noisy one leans on the prior. Figure 2 draws the case $\pi_0 = 0.9$, which Worked Examples carries through to its error probability.

04.Signal Space and the Matched Filter

A real pulse is not a single number. Suppose bit 0 is sent as a pulse whose shape, sampled four times, is $\mathbf{s} = (0.1, 0.7, 0.7, 0.1)$, and bit 1 as $-\mathbf{s}$, and that each sample picks up independent Gaussian noise with $\sigma = 1$. The energy of the pulse, the sum of its squared samples, is $0.01 + 0.49 + 0.49 + 0.01 = 1$. The receiver must combine four noisy samples into one number before comparing it with zero, and Table 2 tries three ways.

Using only the second sample gives a signal of 0.7 against noise of standard deviation 1, and an error probability $Q(0.7) = 0.2420$. Adding all four samples gives a signal of $1.6$, but the noise variances of the four samples add too, to 4, so the noise standard deviation is 2 and the error probability is $Q(0.8) = 0.2119$. Weighting each sample by the pulse itself, so that the receiver computes $0.1y_1 + 0.7y_2 + 0.7y_3 + 0.1y_4$, gives a signal of $0.01 + 0.49 + 0.49 + 0.01 = 1$ and a noise variance of $0.01 + 0.49 + 0.49 + 0.01 = 1$, and an error probability $Q(1) = 0.1587$. The rest of this section proves that no weighting beats the pulse-weighted sum.

The proof needs two pieces of vector algebra. A vector here is an ordered list of $n$ real numbers, such as the four samples $\mathbf{y} = (y_1, y_2, y_3, y_4)$, and vectors add and scale entry by entry.

Proof. If $\mathbf{v}$ is all zeros, both sides are 0 and $\mathbf{v} = 0 \cdot \mathbf{u}$. Otherwise, for any real number $t$, a sum of squares cannot be negative, so

$$0 \le \|\mathbf{u} - t\mathbf{v}\|^2 = \sum_i (u_i - t v_i)^2 = \|\mathbf{u}\|^2 - 2t\,\langle \mathbf{u}, \mathbf{v} \rangle + t^2\,\|\mathbf{v}\|^2.$$

Choose $t = \langle \mathbf{u}, \mathbf{v} \rangle / \|\mathbf{v}\|^2$. The right side becomes $\|\mathbf{u}\|^2 - 2\langle \mathbf{u}, \mathbf{v} \rangle^2/\|\mathbf{v}\|^2 + \langle \mathbf{u}, \mathbf{v} \rangle^2/\|\mathbf{v}\|^2 = \|\mathbf{u}\|^2 - \langle \mathbf{u}, \mathbf{v} \rangle^2/\|\mathbf{v}\|^2$. Multiplying the inequality by $\|\mathbf{v}\|^2$ gives $\langle \mathbf{u}, \mathbf{v} \rangle^2 \le \|\mathbf{u}\|^2\|\mathbf{v}\|^2$, and taking square roots gives the lemma. Equality holds exactly when $\|\mathbf{u} - t\mathbf{v}\| = 0$, which means $\mathbf{u} = t\mathbf{v}$. $\blacksquare$

Proof. The output splits as $z = \pm\langle \mathbf{w}, \mathbf{s} \rangle + \langle \mathbf{w}, \mathbf{n} \rangle$. The noise part $\sum_i w_i n_i$ has mean 0, and its variance is $\sum_i w_i^2 \sigma^2 = \sigma^2\|\mathbf{w}\|^2$, because variances of independent terms add and multiplying a variable by $w_i$ multiplies its variance by $w_i^2$, two rules proved in Probability for Coding. The ratio is therefore

$$\frac{\langle \mathbf{w}, \mathbf{s} \rangle^2}{\sigma^2\,\|\mathbf{w}\|^2} \le \frac{\|\mathbf{w}\|^2\,\|\mathbf{s}\|^2}{\sigma^2\,\|\mathbf{w}\|^2} = \frac{\|\mathbf{s}\|^2}{\sigma^2}$$

by the Cauchy–Schwarz inequality, with equality exactly when $\mathbf{w}$ is a multiple of $\mathbf{s}$. $\blacksquare$

A weighted sum of independent Gaussians is again Gaussian, a standard fact proved in Grinstead and Snell [1], so the error probability of a weighting is $Q$ of the square root of this ratio, and the largest ratio gives the smallest error. Weighting by a positive multiple of the pulse is called a matched filter, a result that goes back to North's analysis of radar receivers [2]. For the four-sample pulse, $\|\mathbf{s}\|^2/\sigma^2 = 1$, the last row of the table.

The theorem compares only weighted sums, so it leaves open whether a nonlinear receiver could do better. It cannot. With independent noise, Equation 1 and Equation 5 give the density of the whole received vector as a product, and the exponents add,

This is largest when $\|\mathbf{y} - \mathbf{x}\|$ is smallest, so the ML receiver picks the signal point nearest to what was received. Expanding the two squared distances, $\|\mathbf{y} - \mathbf{s}\|^2 = \|\mathbf{y}\|^2 - 2\langle \mathbf{y}, \mathbf{s} \rangle + \|\mathbf{s}\|^2$ and $\|\mathbf{y} + \mathbf{s}\|^2 = \|\mathbf{y}\|^2 + 2\langle \mathbf{y}, \mathbf{s} \rangle + \|\mathbf{s}\|^2$, so $\|\mathbf{y} - \mathbf{s}\|^2 - \|\mathbf{y} + \mathbf{s}\|^2 = -4\langle \mathbf{y}, \mathbf{s} \rangle$. The received point is nearer to $\mathbf{s}$ exactly when $\langle \mathbf{y}, \mathbf{s} \rangle > 0$. The matched filter followed by a threshold at zero is the ML receiver among all receivers, linear or not.

Figure 3 shows the geometry with two samples. For $\mathbf{s} = (0.6, 0.8)$ and the received point $\mathbf{y} = (0.9, -0.1)$, the inner product is $0.54 - 0.08 = 0.46$, the squared distance to $\mathbf{s}$ is $0.09 + 0.81 = 0.90$ and to $-\mathbf{s}$ it is $2.25 + 0.49 = 2.74$. The difference, 1.84, is four times 0.46, and the receiver decides 0.

Continuous Time

A receiver on a wire sees a waveform $r(t) = \pm s(t) + n(t)$ over a bit interval from time 0 to time $T$, not a list of samples. Sums become integrals, $\langle r, s \rangle = \int_0^T r(t)\,s(t)\,dt$, and the pulse energy is $E_s = \int_0^T s(t)^2\,dt$. The correlator receiver multiplies the incoming waveform by a stored copy of the pulse and integrates over the bit interval, as Figure 4 shows. A filter whose impulse response is the pulse reversed in time, $h(t) = s(T - t)$, produces the same number at time $T$, because its output there is $\int r(\tau)\,h(T - \tau)\,d\tau = \int r(\tau)\,s(\tau)\,d\tau$. That filter gives the matched filter its name.

White noise in continuous time is described by its two-sided noise density $N_0/2$. For this book its meaning is what the correlator sees, a Gaussian noise term $\int_0^T n(t)\,s(t)\,dt$ with mean 0 and variance $E\,N_0/2$ for a pulse of energy $E$. Dividing the correlator output by $\sqrt{E_s}$ turns it into $y = \pm\sqrt{E_s} + n$ with noise variance $\sigma^2 = N_0/2$, and every continuous-time BPSK link reduces to the one-number channel of the previous section.

With one bit per pulse the pulse energy is the energy per bit, $E_s = E_b$, and the error probability follows in one line. The received value is $\pm\sqrt{E_b}$ plus noise of standard deviation $\sqrt{N_0/2}$, so a threshold at zero errs with probability $Q\bigl(\sqrt{E_b}/\sqrt{N_0/2}\bigr)$.

The four-sample example fits this formula. Its pulse energy is 1 and $\sigma^2 = 1 = N_0/2$, so $N_0 = 2$, $E_b/N_0 = 0.5$ and $P_b = Q(1) = 0.1587$, the matched row of Table 2.

A codeword sent as a sequence of BPSK pulses of energy $E_s$ is a point in a space with one coordinate per bit. Two codewords that differ in $d$ bits sit $2\sqrt{E_s}$ apart in each of those $d$ coordinates and agree in the rest, so their squared Euclidean distance is $4E_s d$. The nearest-point rule on the Gaussian channel and the minimum-distance rule on the binary symmetric channel are the same idea in two geometries.

05.Energy per Bit and the Decibel

Doubling a transmitter's power from 1 milliwatt to 2 milliwatts is a ratio of 2, which engineers report as 3.010 dB, since $10\log_{10} 2 = 3.010$.

The logarithm turns products into sums, so a chain of gains and losses becomes a sum of decibel values, and ratios from 1 to a million fit between 0 and 60 dB. Measured against the matched filter's ratio of 1, the plain sum's squared signal-over-noise ratio of $0.8^2 = 0.64$ is a loss of 1.94 dB, and the single sample's ratio of $0.7^2 = 0.49$ is a loss of 3.10 dB.

The voltage example of Probability for Coding also fits. A pulse of $a = 1$ volt carries $E_b = a^2 = 1$ in units where noise variance is measured in volts squared, and $\sigma^2 = 0.25 = N_0/2$ gives $N_0 = 0.5$. So $E_b/N_0 = 2$, which is 3.01 dB, and Equation 8 gives $Q(\sqrt{4}) = Q(2) = 0.02275$, the error probability that chapter found. Table 3 extends this to the range where practical links operate.

From 0 to 2 dB the error probability halves, while from 10 to 12 dB it falls by a factor of about 430, because the Q-function's tail decays like $e^{-x^2/2}$ and each step multiplies $x^2$. Read backward, the table answers the design question of how much $E_b/N_0$ a target error rate needs. For $P_b = 10^{-5}$, solving $Q(x) = 10^{-5}$ gives $x = 4.2649$, so $2E_b/N_0 = 18.189$, $E_b/N_0 = 9.0946$, or 9.588 dB. About 9.6 dB is the yardstick against which codes are judged.

A code charges for its redundancy in energy. A code of rate $R_c = k/n$ sends $n$ pulses for every $k$ data bits, and the transmitter's budget is fixed per data bit, so each pulse receives

$$E_s = R_c\,E_b.$$

For $R_3$, $R_c = 1/3$ is $-4.771$ dB, so each copy arrives 4.771 dB weaker than an uncoded bit would. Every comparison in this book is made at equal $E_b/N_0$, so that a code pays for every redundant bit it sends.

Signal-to-noise ratio, SNR, is signal power over noise power in a bandwidth $B$. Signal power is energy per bit times the bit rate $R_b$, and noise power is $N_0 B$, so $\text{SNR} = (E_b/N_0)(R_b/B)$. In decibels the factors add. At $R_b = 1$ Mbit/s in $B = 2$ MHz the factor $R_b/B = 1/2$ is $-3.010$ dB, and the 9.588 dB needed for $10^{-5}$ becomes an SNR of 6.578 dB.

06.Hard and Soft Decisions

Send a bit with $R_3$ at $E_b/N_0 = 4$ dB. Each copy carries $E_s = E_b/3$, so its own ratio is $4 - 4.771 = -0.771$ dB, a ratio of 0.8373, and thresholding each copy separately makes an error with probability $p = Q(\sqrt{2 \times 0.8373}) = 0.09782$. Majority voting then fails with probability $3p^2 - 2p^3 = 0.02684$. Uncoded BPSK at the same 4 dB fails with probability 0.01250, so the code has made matters worse by a factor of 2.15.

The soft ML decoder of $R_3$ receives $\mathbf{y} = (y_1, y_2, y_3)$ with each $y_i = \pm\sqrt{E_s} + n_i$. The two codewords are the points $\pm\sqrt{E_s}\,(1, 1, 1)$, and the nearest-point rule picks the codeword for 0 exactly when $y_1 + y_2 + y_3 > 0$, which is the matched filter for that pulse shape. The sum carries signal $3\sqrt{E_s}$ and noise variance $3\sigma^2$, so it errs with probability

$$Q\left(\frac{3\sqrt{E_s}}{\sqrt{3}\,\sigma}\right) = Q\left(\frac{\sqrt{3E_s}}{\sigma}\right) = Q\left(\sqrt{\frac{2E_b}{N_0}}\right),$$

using $3E_s = E_b$ and $\sigma^2 = N_0/2$. Soft-decision $R_3$ performs exactly like uncoded BPSK. Repetition spreads the same energy over three pulses and the soft decoder gathers it back, so nothing is gained and nothing is lost. The hard decoder throws information away at the thresholds and loses ground, as Table 4 and Figure 5 show.

The gap widens as the channel improves. Hard-decision $R_3$ reaches $10^{-5}$ only at 11.029 dB, against 9.588 dB for soft decisions, a loss of 1.441 dB, which is a power ratio of $10^{0.1441} = 1.393$, or 39% more transmitted power. The threshold discards how far each voltage was from zero, and on a weak copy that distance is most of the evidence.

07.Likelihoods and Log-Likelihood Ratios

With $a = 1$ and $\sigma = 0.5$, the received values $y = 0.05$ and $y = 1.9$ both lie above the threshold and both decode to 0. Their likelihood ratios tell them apart. From the Gaussian Channel section the ratio is $f(y \mid 0)/f(y \mid 1) = \exp(2ay/\sigma^2) = e^{8y}$, which is $e^{0.4} = 1.49$ for the first value and $e^{15.2} \approx 3.99 \times 10^{6}$ for the second. The first is barely evidence at all, the second is overwhelming, and a decoder should know the difference.

For BPSK on the AWGN channel, the channel LLR comes out of Equation 5 in four steps. The constant $1/(\sqrt{2\pi}\,\sigma)$ appears above and below and cancels, and the logarithm of an exponential is its exponent,

$$L = \ln\frac{e^{-(y - a)^2/(2\sigma^2)}}{e^{-(y + a)^2/(2\sigma^2)}} = \frac{-(y - a)^2 + (y + a)^2}{2\sigma^2}.$$

Expanding both squares, the $y^2$ and $a^2$ terms cancel,

$$\frac{-(y^2 - 2ay + a^2) + (y^2 + 2ay + a^2)}{2\sigma^2} = \frac{4ay}{2\sigma^2},$$

which leaves

The LLR is the received voltage times a constant set by the channel, so the receiver computes it with one multiplication. With $a = 1$ and $\sigma = 0.5$ the constant is 8, and the two values above have LLRs 0.4 and 15.2.

Proof. Write $P_0 = P(b = 0 \mid y)$, so that $P(b = 1 \mid y) = 1 - P_0$ and $e^{L} = P_0/(1 - P_0)$. Multiplying out gives $e^{L} - e^{L}P_0 = P_0$, so $P_0(1 + e^{L}) = e^{L}$ and $P_0 = e^{L}/(1 + e^{L})$. Dividing above and below by $e^{L}$ gives $1/(1 + e^{-L})$, and $1 - P_0 = 1/(1 + e^{L})$ follows by subtraction. $\blacksquare$

For $y = 0.05$ the posterior probability of 0 is $1/(1 + e^{-0.4}) = 0.5987$, and for $y = 1.9$ it is 0.99999975. A hard decision assigns both the same confidence. After thresholding, the channel from bit to decided bit is a binary symmetric channel with $p = Q(a/\sigma) = Q(2) = 0.02275$, and on $\text{BSC}(p)$ a received 0 has LLR $\ln\bigl((1-p)/p\bigr) = 3.760$, whatever voltage produced it. Figure 6 sets the two side by side. The soft LLR $8y$ exceeds the hard value when $|y| > 0.470$ and falls short of it nearer the threshold, so the hard receiver is overconfident about the doubtful values and underconfident about the clear ones. Table 5 lists the channel LLRs of every channel in this chapter.

Proof. Bayes' rule gives $P(b \mid y_1, y_2) = P(y_1, y_2 \mid b)\,P(b)/P(y_1, y_2)$, and independence given $b$ factors the likelihood as $P(y_1 \mid b)\,P(y_2 \mid b)$. In the ratio of the posteriors for $b = 0$ and $b = 1$ the denominator cancels, leaving the product of three ratios, $\frac{P(y_1 \mid 0)}{P(y_1 \mid 1)} \cdot \frac{P(y_2 \mid 0)}{P(y_2 \mid 1)} \cdot \frac{P(b = 0)}{P(b = 1)}$. The logarithm of a product is the sum of the logarithms. $\blacksquare$

Applied repeatedly, the theorem gives the soft decoder of $R_3$ directly. With $a = 1$ and $\sigma = 0.8$ the constant is $2a/\sigma^2 = 3.125$. If 0 is sent and the three copies arrive as $(0.9, -0.2, -0.3)$, their LLRs are $2.8125$, $-0.625$ and $-0.9375$, which sum to 1.25, so the decoder says 0 with posterior probability $1/(1 + e^{-1.25}) = 0.7773$. The hard decoder sees 0, 1, 1 and votes 1, which is wrong. The LLR sum is $3.125$ times the voltage sum $0.4$, so this is the soft decoder of the previous section with the confidence attached.

08.Bursty Channels

Every channel so far has been memoryless. Real channels often remember, since a scratch on a disc or a fade on a radio link damages many consecutive bits and then stops. The simplest model gives the channel a hidden state that persists.

Take a channel that is usually in a good state, where each bit flips with probability $p_G = 0.001$, and occasionally in a bad state, where each bit flips with probability $p_B = 0.1$. After each bit, a good channel turns bad with probability $b = 0.01$ and a bad channel recovers with probability $g = 0.09$. Gilbert introduced the model with error-free good states [3], and Elliott allowed errors in both [4].

The long-run fraction of time in the bad state follows from the recursion in the next theorem.

Proof. By the law of total probability, conditioning on the current state, $\pi_B(t+1) = (1 - g)\,\pi_B(t) + b\,\bigl(1 - \pi_B(t)\bigr)$, which rearranges to Equation 13. The value $\pi^* = b/(b + g)$ is a fixed point of the recursion, since $(1 - b - g)\,b/(b + g) + b = (b - b^2 - bg + b^2 + bg)/(b + g) = b/(b + g)$. Subtracting the fixed-point equation from the recursion gives $\pi_B(t+1) - \pi^* = (1 - b - g)\bigl(\pi_B(t) - \pi^*\bigr)$, and repeating it $t$ times gives $\pi_B(t) - \pi^* = (1 - b - g)^t\bigl(\pi_B(0) - \pi^*\bigr)$, which tends to 0 when $|1 - b - g| < 1$. Finally $\pi_G = 1 - \pi_B = g/(b + g)$. $\blacksquare$

For the example, $\pi_B = 0.01/0.1 = 0.1$ and $\pi_G = 0.9$. The convergence factor is $1 - 0.01 - 0.09 = 0.9$, and after 50 bits the gap has shrunk to $0.9^{50} = 0.00515$ of its starting size, so the channel forgets its initial state within a few dozen bits. The average bit error probability is

$$\pi_G\,p_G + \pi_B\,p_B = 0.9 \times 0.001 + 0.1 \times 0.1 = 0.0109.$$

A bad spell lasts a random number of bits $T$. In each bad bit the chain leaves with probability $g$, so it stays at least $k$ bits with probability $(1 - g)^{k-1}$. For a variable that takes positive whole-number values, $E[T] = \sum_{k \ge 1} P(T \ge k)$, because $T$ equals the number of the indicators $\mathbf{1}[T \ge 1], \mathbf{1}[T \ge 2], \dots$ that are 1, and linearity of expectation turns the sum of indicators into the sum of their probabilities. Summing the geometric series, $E[T] = \sum_{k \ge 1}(1 - g)^{k-1} = 1/g = 11.11$ bits. A good spell lasts $1/b = 100$ bits on average.

The average error rate hides the clustering, and a two-bit statistic exposes it. The probability that two consecutive bits are both in error, in the long run, sums over the state of the first bit and the state it moves to,

$$\pi_G\,p_G\bigl[(1 - b)\,p_G + b\,p_B\bigr] + \pi_B\,p_B\bigl[g\,p_G + (1 - g)\,p_B\bigr] = 0.0009 \times 0.00199 + 0.01 \times 0.09109 = 0.000912691.$$

A memoryless channel with the same average rate would give $0.0109^2 = 0.00011881$, smaller by a factor of 7.68. Put another way, the probability that the bit after an error is also in error is $0.000912691/0.0109 = 0.0837$, nearly eight times the average rate. Figure 8 shows what that looks like.

Bursts defeat codes that assume independence. Send $R_3$ with the three copies of each bit back to back, so that they share the channel's state. Summing over the eight possible state sequences of three consecutive bits, the probability that two or more copies are wrong is 0.0024927. If the copies are instead spread far apart, the chain forgets its state between them and the copies see nearly independent errors at rate $q = 0.0109$, so the failure probability is $3q^2 - 2q^3 = 0.00035384$, smaller by a factor of 7.04. Rearranging the order of transmitted bits so that the symbols of one codeword travel far apart is called interleaving, and it turns a bursty channel back into one that a code for independent errors can handle.

09.Fault Models for Memory

The bits of a memory do not travel anywhere, but they still pass through a channel, the interval between writing a word and reading it back. Four kinds of fault dominate, and each matches a channel model from this chapter.

A stuck-at fault is a cell or line that permanently reads 0, called stuck-at-0, or permanently reads 1, whatever is written. A stuck-at-0 cell is wrong only when a 1 is stored, and a write-and-read test can find it. Once located, its bit is no longer an unknown error but an erasure, a bit whose position is known and whose value is lost. Later chapters show that a code can fill twice as many erasures as it can correct unknown errors, which is why located faults are worth finding.

A single-event upset is a transient flip of one stored bit without damage to the cell. An alpha particle from trace radioactivity in the packaging [5], or a neutron from a cosmic-ray shower [6], deposits enough charge to flip a stored value, and rewriting the cell clears it. Each bit flips independently with a small probability, so a word between writes is a binary symmetric channel with a tiny $p$. A single-error-correcting code on a 72-bit word fails only when two bits flip before the word is rewritten. With an illustrative per-bit probability of $10^{-9}$ per interval, the union bound of Probability for Coding gives $\binom{72}{2}\times 10^{-18} = 2556 \times 10^{-18} = 2.556 \times 10^{-15}$ per word, and across $2^{30}$ words at most $2.744 \times 10^{-6}$ expected failures per interval. Scrubbing, which reads every word on a schedule, corrects it and writes it back, keeps single upsets from accumulating into double ones.

A multi-bit upset is one strike that flips several neighboring cells at once, and Baumann's review describes how shrinking cells made such upsets more common [7]. It is a burst in space rather than in time, and the defense is the same interleaving. The bits of one logical word are placed in physically separated cells, so a strike that flips four neighbors flips one bit in each of four words, and each word's single-error correction handles its share.

Charge leakage is the Z-channel. A cell that stores a 1 as charge slowly loses it, and if the charge falls too far before the cell is refreshed, the 1 reads back as 0, while a stored 0 has no charge to lose. Refreshing on a schedule bounds how far the leak can go. Table 6 collects the four, and Figure 9 shows how they land on an array of cells.

10.Looking Ahead

This chapter measured a channel by how often it causes errors and how a receiver should weigh what it sees. The next chapter, Information and Entropy, measures a channel by how much it can carry. It defines the information in an outcome as its surprise, the base-2 logarithm of one over its probability, so that a fair coin flip carries one bit and a certain outcome carries none. Entropy, the average surprise, counts how many bits a source really produces, and mutual information measures how much the output of a noisy channel says about its input. The three channels of this chapter are its first examples, because an erasure tells the receiver nothing about the lost bit while a flip misleads it, and the two cost different amounts of capacity. MacKay [8] develops this view in depth, and Lin and Costello [9] treat these channel models at greater length.

11.Worked Examples

12.Exercises

References

1. [1]Grinstead, Charles M. and Snell, J. Laurie (2006). “Grinstead and Snell's Introduction to Probability.” The CHANCE Project. Version dated 4 July 2006 of the second edition published by the American Mathematical Society, free under the GNU Free Documentation License. https://math.dartmouth.edu/~prob/prob/prob.pdf
2. [2]North, D. O. (1963). “An Analysis of the Factors Which Determine Signal/Noise Discrimination in Pulsed-Carrier Systems.” Proceedings of the IEEE, 51(7), pp. 1016–1027. Reprint of RCA Laboratories Technical Report PTR-6C, 1943. doi:10.1109/PROC.1963.2383
3. [3]Gilbert, E. N. (1960). “Capacity of a Burst-Noise Channel.” Bell System Technical Journal, 39(5), pp. 1253–1265. doi:10.1002/j.1538-7305.1960.tb03959.x
4. [4]Elliott, E. O. (1963). “Estimates of Error Rates for Codes on Burst-Noise Channels.” Bell System Technical Journal, 42(5), pp. 1977–1997. doi:10.1002/j.1538-7305.1963.tb00955.x
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]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
9. [9]Lin, Shu and Costello, Jr., Daniel J. (2004). “Error Control Coding: Fundamentals and Applications.” 2nd edition. Pearson Prentice Hall.