Topic 2. Decoding

2.1 Codes and rate

In Topic 1 the transmitter sent one symbol for every \log_2 M bits, and the receiver decided symbolwise. Exercise 1.6 of Topic 1 showed the weakness of this scheme: the probability that a sequence of n symbols is entirely correct is (1-P_{\rm e})^n, which vanishes as n grows however small P_{\rm e}>0 is. To send long messages reliably, we need something better than sending every bit once. The remedy is redundancy, that is, to use more symbols than strictly necessary, so that the receiver can recover from some of the errors.

Figure 2.1 shows the position of the encoder and the decoder. The uncoded transmission of Topic 1 is the special case in which every symbol carries \log_2 M bits, with M=|\mathcal X| a power of two, that is, R=\log_2 M. Coding means choosing R smaller than that, and the whole question of this topic and the next is what we obtain in exchange.

Figure 2.1. Coded transmission: k information bits become a codeword \x=(x_1,\ldots,x_n), and the decoder sees \y=(y_1,\ldots,y_n).

The simplest code is the repetition code, which has k=1 and sends the single information bit D a total of n times. With s_0 and s_1 the two points of a binary constellation, the two codewords, indexed by D\in\{0,1\}, are \begin{equation*} \x(D)=(s_D,\ldots,s_D),\tag{2.2} \end{equation*} and the rate is R=1/n. For binary constellations, an encoder first produces n coded bits c_1,\ldots,c_n from the k information bits, and then maps each coded bit to a symbol, x_i=s_{c_i}. For the repetition code, c_1=\cdots=c_n=D. On the bit-flipping and bit-erasing channels the constellation is \{0,1\}. On the Gaussian channel we take s_0=-A and s_1=A, and on the exponential channel s_0=0 and s_1=2A, with A>0. As in Topic 1, Gaussian inputs are amplitudes, whereas exponential-channel inputs are themselves energies.

When the constellation has M>2 points, the encoder produces n_{\rm c} coded bits and maps \log_2 M of them to each symbol. Its binary rate is r=k/n_{\rm c}, and the rate in bits per channel use is R=r\log_2 M. In this topic all the symbols are binary, so n_{\rm c}=n and R=r.

Let us recall how the repetition code behaves on the bit-flipping channel with flip probability p<\tfrac12, which was studied in the information theory course. The natural decoder is majority voting: decide the bit that appears most often among the n received bits, and toss a fair coin in case of a tie. For n=3, Table 2.1 lists the eight possible outputs when D=0 is sent, together with their probabilities and the decision of the majority decoder.

The table is once more an application of Table 1.1 of Topic 1. Every probability in the second column is a product, because the channel is memoryless, and the conditional error probability is the sum of the rows that lead to an error, \begin{equation*} P_{\rm e}(0)=3p^2(1-p)+p^3=p^2(3-2p).\tag{2.3} \end{equation*} By symmetry P_{\rm e}(1) is the same, so P_{\rm e}=p^2(3-2p) whatever the prior, and this is smaller than p exactly when 0<p<\tfrac12, since p-p^2(3-2p)=p(1-p)(1-2p).

In general, for odd n, the majority decoder fails when at least (n+1)/2 of the n bits are flipped, so \begin{equation*} P_{\rm e}=\sum_{i=(n+1)/2}^{n}\binom{n}{i}\,p^i(1-p)^{n-i}.\tag{2.4} \end{equation*} For n=3 the sum has the two terms of (2.3). The case of even n, with its ties, is Exercise 2.2. For p<\tfrac12 this probability goes to zero as n grows, because the fraction of flipped bits concentrates around p, which is below one half.

Hence, the repetition code makes the error probability as small as we wish. The cost is the rate, since R=1/n goes to zero at the same time. We will come back to this trade-off in Section 2.4.

2.2 Optimal decoding

We now place the decoder in the framework of Topic 1. The transmitter has a message to send, which we may think of as the k bits or, more conveniently, as an index m in a set \mathcal M of 2^k values with prior probabilities \Pr(m). For the repetition code, m is simply the bit D. The message selects the codeword \x(m), the channel produces \y=(y_1,\ldots,y_n), a realization of the random sequence \Y, and a decoder is any function g from the sequences \y to the messages, \hat m=g(\y). Its error probabilities are defined as in Topic 1. The conditional error probability when m is sent is \begin{equation*} P_{\rm e}(m)=\Pr(g(\Y)\neq m\,|\,m \text{ sent}),\tag{2.5} \end{equation*} and the average error probability is \begin{equation*} P_{\rm e}=\sum_{m\in\mathcal M} \Pr(m)\,P_{\rm e}(m).\tag{2.6} \end{equation*}

A tie between maximizers may be broken in any way, and we break it with a fair coin. Note that P_{\rm e} is the probability of a wrong message, that is, of a wrong codeword. For the repetition code the message is a single bit, so it is also the bit error probability.

The new element is the channel law of a sequence. As in Topic 1, W denotes a probability for discrete outputs and a density for continuous outputs. All our channels are memoryless, so by the last line of Table 1.1 of Topic 1, \begin{equation*} W(\y|\x)=\prod_{i=1}^n W(y_i|x_i),\tag{2.9} \end{equation*} and the ML decoder maximizes a product of n factors. Since the logarithm is increasing, with the convention \ln 0=-\infty, we may equally maximize the sum of the logarithms, \begin{equation*} g_{\rm ML}(\y)=\argmax_{m\in\mathcal M} \sum_{i=1}^n \ln W\bigl(y_i|x_i(m)\bigr).\tag{2.10} \end{equation*} In words, every channel output y_i gives a score to each candidate codeword, namely the logarithm of how likely y_i is under that codeword, and the decoder adds the scores and picks the codeword with the highest total. This sum is called the log-likelihood of the codeword. Table 2.2 lists the scores on the channels of the course. The terms that do not depend on the codeword have been dropped, since they do not affect the comparison. For the repetition code, for instance, every x_i(m) is the same symbol s_m, so the decoder compares just two numbers, \smash{\sum_{i=1}^n}\ln W(y_i|s_0) and \smash{\sum_{i=1}^n}\ln W(y_i|s_1). For MAP decoding, we add \ln\Pr(m) to the log-likelihood of each codeword. Let us see what the sums of these scores become on the channels of the course.

2.3 Hard and soft decisions

We now compare two receivers for the same repetition code on the real Gaussian channel, with equiprobable bits and \snr=A^2/\sigma^2. The ML decoder of Example 2.4(a) works with the observations y_i themselves. A different receiver, natural after Topic 1, first detects every symbol with the symbolwise detector of Topic 1, obtaining a bit \hat c_i per symbol, and then decodes from the n detected bits. Figure 2.2 shows the two receivers. The upper one is said to take hard decisions, since every observation is reduced to a bit before decoding. The lower one takes soft decisions, because the decoder sees the observations in full.

Figure 2.2. Two receivers for the repetition code on the Gaussian channel.

The hard receiver is easy to analyze with the tools we have. Each detected bit \hat c_i is wrong with the probability (1.22) of Topic 1, which we call p here, \begin{equation*} p=\tfrac12\erfc\Bigl(\sqrt{\snr/2}\Bigr),\tag{2.19} \end{equation*} and the errors in different positions are independent, since the noise samples are. In other words, seen from the coded bits to the detected bits, the Gaussian channel followed by the detector is a bit-flipping channel with flip probability p. On that channel, majority voting is the ML decoder, and for odd n its error probability is (2.4) with the value (2.19) of p. Even lengths include the tie term of Exercise 2.2. The soft receiver has the error probability (2.15).

Table 2.4 gives the error probability of both receivers for n up to 5, and Figure 2.3 plots it. The soft receiver is better at every SNR, and the difference grows with n. For n=3, for instance, the hard receiver takes the uncoded p down to p^2(3-2p), whereas the soft receiver multiplies the argument of \erfc by \sqrt3. At high SNR the loss of the hard receiver tends to 10\log_{10}\bigl(2n/(n+1)\bigr), from 1.8 dB for n=3 to 3 dB for large n, as Exercise 2.8 shows. Note that the SNR in the table and the figure is that of one symbol. Section 2.4 shows what the comparison looks like at equal energy per bit.

Figure 2.3. The curves of Table 2.4. Dashed lines are hard decisions, solid lines soft decisions.

The loss has a simple origin. The symbolwise detector keeps only the sign of each y_i and discards its magnitude. An observation close to the threshold is nearly useless, and one far from it is nearly certain, but after the detector both count as one vote. The soft decoder adds the observations, so a large y_i can outweigh two small ones of the opposite sign. For instance, with \y=(2,\,-\tfrac12,\,-\tfrac12)A the hard receiver sees (+,-,-) and decides 0, while the soft receiver computes \smash{\sum_{i=1}^3} y_i=A>0 and decides 1.

This is the general lesson of the section. The part of the receiver that processes the channel output should not take decisions. It should pass the observations, or the scores of (2.10), to the decoder. Modern receivers do exactly this, and the scores are then called soft information.

2.4 Rate and reliability

Repetition drives the error probability to zero as n grows: on the bit-flipping channel with fixed p<\tfrac12, by (2.4), on the erasure channel with fixed p<1 and on the Gaussian and exponential channels with fixed symbol energy and noise level, by Problem 2.6 and (2.15). The only exceptions are the useless channels, the BSC with p=\tfrac12 and the BEC with p=1, where P_{\rm e}=\tfrac12 for every n. The price is the rate, since R=1/n vanishes too, and on the Gaussian and exponential channels each information bit costs the energy of n symbols. Table 2.5 shows the price on the bit-flipping channel with p=\tfrac1{10}. To send k bits reliably we need nk channel uses, and n has to grow without bound. The table gives the error probability of each repeated bit, and the errors of the k bits accumulate along the message as in Section 1.6 of Topic 1.

The capacity of this channel, from the information theory course, is \begin{equation*} C=1-h_2\Bigl(\frac1{10}\Bigr)\approx0.53\quad\text{bits per channel use},\tag{2.20} \end{equation*} where h_2 is the binary entropy function. Repetition needs n=23 to reach P_{\rm e}<10^{-6}, at rate R=\tfrac1{23}, more than ten times smaller than the capacity. Topic 3 says what that number promises.

On the Gaussian channel there is a second way of looking at the price, in terms of energy. With \Es the mean energy per channel use, a code of rate R=k/n spends on each information bit \begin{equation*} \Eb=\frac{n\Es}{k}=\frac{\Es}{R}.\tag{2.21} \end{equation*} For the repetition code with 2-PAM symbols, \Eb=nA^2. Writing (2.15) in terms of \Eb, \begin{equation*} P_{\rm e}=\tfrac12\erfc\biggl(\sqrt{\frac{nA^2}{2\sigma^2}}\biggr)=\tfrac12\erfc\biggl(\sqrt{\frac{\Eb}{2\sigma^2}}\biggr),\tag{2.22} \end{equation*} which is exactly the error probability of uncoded 2-PAM with the same energy per bit, given by equation (1.22) of Topic 1. In other words, at equal energy per bit, the repetition code with soft decisions gains nothing at all. It is equivalent to sending each bit once with n times the energy, and the hard receiver is worse than that. The reduction in error probability is paid entirely with energy and rate.

Not every code is so limited. The minimum distance of a code is the smallest Euclidean distance between two of its codewords, and the following problem shows the simplest code whose minimum distance, at equal energy per bit, is larger than that of repetition.

Figure 2.4. The eight sequences of three 2-PAM symbols are the vertices of a cube of side 2A. The four codewords of the parity code (filled) are pairwise at distance 2\sqrt2\,A, the diagonal of a face. The empty vertices are the sequences of odd parity.

This leads to the question that Topic 3 answers, namely whether there is a code whose rate stays above a fixed positive value while the error probability goes to zero, and which does better than repetition at equal energy per bit.

Shannon’s answer is yes to both. Every channel has a capacity C, and for every rate below C there are codes whose error probability is as small as we wish. The capacity is strictly positive for every channel of Table 1.2 of Topic 1, except in useless cases such as the bit-flipping channel with p=\tfrac12 or the erasure channel with p=1. Such codes are not repetition codes. Their codewords are spread out in a way that the decoder can exploit, as the parity code of Problem 2.9 begins to show.