Exercises: 2. Decoding

The correct answer is (b) ★

Each detected bit is correct with probability $1-p=\tfrac45$, and the three decisions are independent because the channel is memoryless. The probability that the three bits are correct is the product $\bigl(\tfrac45\bigr)^3=\tfrac{64}{125}$, so the probability that at least one is wrong is $1-\tfrac{64}{125}=\tfrac{61}{125}$. Expanding, $1-(1-p)^3=3p-3p^2+p^3$.

Option (a) adds the error probabilities of the three bits as if the three events were disjoint, and it counts the outputs with two or three wrong bits more than once. The terms $-3p^2+p^3$ of the expansion correct this. Option (c) is the probability $p^3$ that all three bits are wrong. With $N$ uncoded bits the probability of some error is $1-(1-p)^N$, which tends to one as $N$ grows, and this is the reason for coding.

The correct answer is (a) ★

A code with $2^k$ codewords carries $k$ information bits per codeword, since each codeword identifies one of $2^k$ messages. Here $16=2^4$, so $k=4$, and the rate is $R=\tfrac kn=\tfrac47$ information bits per channel use.

Option (b) divides the number of codewords by the length, but the number of information bits is $\log_2 16=4$, not $16$. Option (c) is the inverse ratio $n/k$, which counts channel uses per information bit. For comparison, the repetition code of length $7$ has two codewords, so that $k=1$ and $R=\tfrac17$.

The correct answer is (c) ★

The binary rate counts information bits per coded bit, $r=k/n_{\rm c}=\tfrac36=\tfrac12$. Each 4-PAM symbol carries $\log_2 4=2$ coded bits, so the six coded bits take $n=3$ channel uses, and the rate per channel use is $R=\tfrac kn=\tfrac33=1$, that is, $R=r\log_2M=\tfrac12\cdot2=1$.

Option (a) identifies the binary rate with the rate per channel use, which is correct only for binary constellations, where $n_{\rm c}=n$. Option (b) divides by $\log_2M$ instead of multiplying. A symbol of a larger constellation carries more coded bits, and therefore more information bits too. Uncoded 4-PAM would have $R=2$, and this encoder halves it.

The correct answer is (a) ★

The scheme has $2^3=8$ messages and $8$ codewords of length $3$, so $R=\tfrac kn=\tfrac33=1$. Since every sequence of three bits is a codeword, the receiver always sees a codeword, whatever the channel does. It cannot notice an error, and each flipped bit becomes a wrong information bit. Errors can be noticed only if some received sequences are not codewords, which requires a rate below one.

Option (b) is the rate of the repetition code of length $3$, which has only the two codewords $000$ and $111$ and carries one information bit. Option (c) describes a code with redundancy. With the repetition code, for instance, the received sequence $010$ is not a codeword, so a single flip is noticed.

The correct answer is (b) ★

When $m=1$ is sent, the majority vote errs when at least two of the three bits are flipped. Exactly two flips can occur in three positions, each pattern with probability $p^2(1-p)=\tfrac1{25}\cdot\tfrac45=\tfrac4{125}$, and three flips have probability $p^3=\tfrac1{125}$. Hence $P_{\rm e}(1)=3\cdot\tfrac4{125}+\tfrac1{125}=\tfrac{13}{125}$, which is $p^2(3-2p)$. By symmetry $P_{\rm e}(2)=\tfrac{13}{125}$ too, and the average is $P_{\rm e}=\tfrac{13}{125}$, about half of the value $p=\tfrac{25}{125}$ of a single bit.

Option (a) forgets the output with three flips, which the majority vote also decodes wrongly. Option (c) counts only that output, as if two flips could still be corrected. With three bits, the majority vote corrects one flip and no more.

The correct answer is (c) ★

The single bit has error probability $p$, and the repetition code with the majority vote has $p^2(3-2p)$. Their difference factors as $p-p^2(3-2p)=p\,(1-3p+2p^2)=p\,(1-p)(1-2p)$, which is positive exactly when $p< \tfrac12$, since $0< p< 1$. At $p=\tfrac12$ both error probabilities are $\tfrac12$, and for $p>\tfrac12$ the majority vote makes things worse.

Option (a) comes from the approximation $P_{\rm e}\approx3p^2$, which keeps only the leading term and is accurate only for small $p$. Solving $3p^2< p$ gives $p< \tfrac13$, but at $p=\tfrac25$, for instance, the exact value is $\tfrac{44}{125}< \tfrac25$. Option (b) ignores that, when $p>\tfrac12$, a received bit is more often wrong than right, so a majority of received bits is more likely to be a majority of wrong bits.

The correct answer is (c) ★

By symmetry $P_{\rm e}(1)=P_{\rm e}(2)$, and the majority vote of five bits errs when at least three of them are flipped. Counting the positions of the flips, $$P_{\rm e}=\binom53p^3(1-p)^2+\binom54p^4(1-p)+p^5=\frac{10\cdot16+5\cdot4+1}{5^5}=\frac{181}{3125}.$$ This is about $0.058$, against $\tfrac{13}{125}\approx0.104$ for the length $3$ and $\tfrac15$ for a single bit.

Option (a) keeps only the first term, $10p^3(1-p)^2=\tfrac{160}{3125}=\tfrac{32}{625}$, and forgets the outputs with four or five flips. Option (b) assumes that two flips already cause an error, $1-(1-p)^5-5p(1-p)^4=\tfrac{821}{3125}$, but with five bits the majority vote corrects up to two flips.

The correct answer is (a) ★

When $m=1$ is sent, the decoder errs for sure when three or four bits are flipped, and with probability $\tfrac12$ when exactly two are, because the vote is then tied. Hence $$P_{\rm e}(1)=\tfrac12\binom42p^2(1-p)^2+\binom43p^3(1-p)+p^4=\frac{243+36+1}{10^4}=\frac7{250},$$ and $P_{\rm e}(2)$ and the average take the same value. This is exactly the error probability $p^2(3-2p)=\tfrac{28}{1000}$ of the length $3$. The fourth copy does not help the majority vote, which is the ML decoder here, and it lowers the rate from $\tfrac13$ to $\tfrac14$.

Option (b) counts every tie as an error, $\tfrac{486+36+1}{10^4}$, and option (c) counts every tie as a correct decision, $\tfrac{36+1}{10^4}$. The coin is right half of the time.

The correct answer is (b) ★

With $p=\tfrac12$, every received sequence $\boldsymbol{y}$ of $n$ bits has the likelihood $W(\boldsymbol{y}|\boldsymbol{x})=2^{-n}$ under both codewords, so the output is independent of the message and carries no information about it. Every decoder is then an ML decoder, and with equiprobable messages every decoder has $P_{\rm e}=\tfrac12$, whatever the length. The channel is useless, and repetition cannot help.

Option (a) would require each copy to carry some information, as it does when $p< \tfrac12$. Option (c) is the error probability of the bit-erasing channel, where an unerased bit is always correct. An erased bit is known to be unreliable, whereas a received bit of this channel looks reliable and is right only half of the time.

The correct answer is (a) ★

The channel is memoryless, so the likelihood of a sequence is the product of the laws of its symbols. For $000$, the first and third bits arrive unchanged and the second is flipped, so $W(\boldsymbol{y}|000)=(1-p)\cdot p\cdot(1-p)=\tfrac45\cdot\tfrac15\cdot\tfrac45=\tfrac{16}{125}$. For $111$, the first and third bits are flipped and the second arrives unchanged, so $W(\boldsymbol{y}|111)=p\cdot(1-p)\cdot p=\tfrac4{125}$. The ratio $W(\boldsymbol{y}|111)/W(\boldsymbol{y}|000)=\tfrac p{1-p}=\tfrac14$ is below one, so the ML decoder decides $\hat m=1$, the majority of the received bits.

Option (b) multiplies only the factors of the flipped positions and forgets the factor $1-p$ of each bit that arrives unchanged. The likelihood is the probability of the whole received sequence, so every position contributes a factor. Option (c) exchanges the two codewords.

The correct answer is (c) ★

Let $d=3$ be the number of ones in $\boldsymbol{y}$. The codeword $11111$ differs from $\boldsymbol{y}$ in the $n-d=2$ positions of the zeros, and $00000$ differs from it in the $d=3$ positions of the ones, so $W(\boldsymbol{y}|\boldsymbol{x}(2))=p^2(1-p)^3$ and $W(\boldsymbol{y}|\boldsymbol{x}(1))=p^3(1-p)^2$. Their ratio is $$\frac{W(\boldsymbol{y}|\boldsymbol{x}(2))}{W(\boldsymbol{y}|\boldsymbol{x}(1))}=\frac{p^2(1-p)^3}{p^3(1-p)^2}=\frac{1-p}{p}=9,$$ and in general $\bigl((1-p)/p\bigr)^{2d-n}$. It exceeds one, so the ML decoder decides $\hat m=2$, which is the majority of the received bits.

Option (a) counts a factor $9$ in favor of $\boldsymbol{x}(2)$ for each of the three ones, $9^3=729$, and forgets that each of the two zeros counts a factor $9$ in favor of $\boldsymbol{x}(1)$. Only the difference $d-(n-d)=1$ between the two counts matters. Option (b) is the inverse ratio.

The correct answer is (b) ★

On the bit-flipping channel, a codeword that differs from $\boldsymbol{y}$ in $d$ positions has likelihood $p^d(1-p)^{n-d}=(1-p)^n\bigl(p/(1-p)\bigr)^d$, which decreases with $d$ when $p< \tfrac12$. The ML decoder therefore chooses the codeword at the smallest Hamming distance from $\boldsymbol{y}$. Here $\boldsymbol{y}=10100$ differs from $00000$ in positions $1$ and $3$, and from $11100$ only in position $2$, so the decoder decides $\hat m=2$. The two likelihoods are $p^2(1-p)^3$ and $p(1-p)^4$, with ratio $(1-p)/p>1$.

Option (a) applies the majority vote, which is the ML decoder of the repetition code only, because its codewords are constant. Here the last two positions are $0$ in both codewords, so they say nothing about the message. Option (c) is wrong because the comparison of the two distances gives the same decision for every $p$ with $0< p< \tfrac12$.

The correct answer is (a) ★

With $d$ ones in $\boldsymbol{y}$, the likelihood ratio of $111$ against $000$ is $\bigl((1-p)/p\bigr)^{2d-3}=\bigl(\tfrac14\bigr)^{2d-3}$, and its base is now smaller than one. The ratio exceeds one when $2d-3< 0$, that is, when $d\leq1$, so the ML decoder decides $\hat m=2$ when most received bits are $0$. It is the minority vote, that is, the majority vote after flipping every received bit. After that flip each bit is correct with probability $p=\tfrac45$, so the decoder faces a bit-flipping channel with flip probability $1-p=\tfrac15$, and $P_{\rm e}=(1-p)^2\bigl(3-2(1-p)\bigr)=\tfrac1{25}\cdot\tfrac{13}5=\tfrac{13}{125}$.

Option (b) is the error probability $p^2(3-2p)=\tfrac{16}{25}\cdot\tfrac75=\tfrac{112}{125}$ of the majority vote, which is not the ML decoder when $p>\tfrac12$. Option (c) treats the channel as useless, but only $p=\tfrac12$ is useless. A channel that flips with probability $\tfrac45$ is as informative as one that flips with probability $\tfrac15$, once the decoder takes it into account.

The correct answer is (b) ★

Let $d$ be the number of ones in $\boldsymbol{y}$. The MAP decoder decides $\hat m=2$ when $\Pr(m=2)\,W(\boldsymbol{y}|111)>\Pr(m=1)\,W(\boldsymbol{y}|000)$, that is, when $9\,p^{3-d}(1-p)^d>p^d(1-p)^{3-d}$. Collecting the powers, the condition is $$9>\Bigl(\frac{1-p}{p}\Bigr)^{3-2d}=4^{3-2d}.$$ For $d=0$ the right-hand side is $64$, and the decoder decides $\hat m=1$. For $d=1$ it is $4$, below $9$, and for $d=2$ and $d=3$ it is smaller still, so the decoder decides $\hat m=2$ as soon as one received bit is $1$.

Option (a) is the ML decoder, which ignores the priors. At $d=1$ the two products are $\tfrac9{10}\cdot\tfrac4{125}=\tfrac{36}{1250}$ for $\boldsymbol{x}(2)$ and $\tfrac1{10}\cdot\tfrac{16}{125}=\tfrac{16}{1250}$ for $\boldsymbol{x}(1)$, so two flips of the frequent codeword are more likely than one flip of the rare one. Option (c) would need the prior odds $9$ to exceed $4^3=64$, which happens only for $\Pr(m=2)>\tfrac{64}{65}$.

The correct answer is (c) ★

By Exercise 2.14, the MAP decoder decides $\hat m=2$ unless $\boldsymbol{y}=000$. When $m=1$ is sent, it errs as soon as one bit is flipped, so $P_{\rm e}(1)=1-(1-p)^3=1-\tfrac{64}{125}=\tfrac{61}{125}$. When $m=2$ is sent, it errs only if the three bits are flipped, so $P_{\rm e}(2)=p^3=\tfrac1{125}$. Weighting with the priors, $$P_{\rm e}=\tfrac1{10}\cdot\tfrac{61}{125}+\tfrac9{10}\cdot\tfrac1{125}=\tfrac{70}{1250}=\tfrac7{125}.$$

Option (a) is the error probability $p^2(3-2p)$ of the majority vote, which is the same for every prior because its two conditional errors are equal. The MAP decoder almost halves it, at the price of a large $P_{\rm e}(1)$ for the rare message. Option (b) is the error probability of the decoder that ignores the output and always decides $\hat m=2$, which errs exactly when $m=1$ is sent. No decoder beats MAP, and both alternatives are worse.

The correct answer is (a) ★

When $m=1$ is sent, the decoder errs only if the three bits are flipped, so $P_{\rm e}(1)=p^3=\tfrac1{125}$. When $m=2$ is sent, it errs unless the three bits arrive unchanged, so $P_{\rm e}(2)=1-(1-p)^3=\tfrac{61}{125}$. With equiprobable messages, $P_{\rm e}=\tfrac12\bigl(\tfrac1{125}+\tfrac{61}{125}\bigr)=\tfrac{31}{125}$.

Option (b) is $P_{\rm e}(1)$ alone. The two conditional errors of this decoder are very different, and both enter the average. Option (c) is the error probability of the majority vote, which is the ML decoder and, with equiprobable messages, also the MAP decoder. No decoder has a smaller average error probability, and this one is more than twice as bad. The same unanimity rule is the ML decoder on the exponential channel, where the noise never lowers an output, but not on the bit-flipping channel, where both kinds of flip occur.

The correct answer is (c) ★

On the bit-erasing channel an unerased bit is always correct, so one unerased bit identifies the codeword. The decoder errs only when the three bits are erased, with probability $p^3=\tfrac1{1000}$, and the coin is wrong, with probability $\tfrac12$, so $P_{\rm e}=\tfrac12p^3=\tfrac1{2000}$. On the bit-flipping channel the ML decoder is the majority vote, which errs with two or three flips, $P_{\rm e}=p^2(3-2p)=\tfrac1{100}\cdot\tfrac{28}{10}=\tfrac7{250}$, which is $56$ times larger.

Option (a) identifies the probability $p^3$ of a total erasure with the error probability, forgetting that the coin is right half of the time. Option (b) treats an erasure as a flip. An erasure tells the decoder which position is unreliable, while a flipped bit looks like a correct one, so the same number of corrupted bits does much less harm on the erasure channel.

The correct answer is (b) ★

The ML decoder errs only when the $n$ bits are erased and the coin is wrong, so $P_{\rm e}=\tfrac12p^n=2^{-(n+1)}$. For $n=5$ this is $\tfrac1{64}>\tfrac1{100}$, and for $n=6$ it is $\tfrac1{128}\leq\tfrac1{100}$. The smallest length is $n=6$, with $R=\tfrac16$.

Option (a) requires the probability $p^n$ of a total erasure to be below $\tfrac1{100}$ and forgets the factor $\tfrac12$ of the coin, which saves one repetition here. Option (c) confuses this channel with the bit-flipping channel with $p=\tfrac12$, which is useless. Here half of the bits arrive, and each of them is correct.

The correct answer is (b) ★

An unerased bit is always correct, whatever the value of $p$, so the ML decoder follows any unerased bit and is then right for sure. It can only err when both bits are erased, which has probability $p^2=\tfrac9{16}$, and the coin is then wrong half of the time, so $P_{\rm e}=\tfrac12p^2=\tfrac9{32}$.

Option (a) carries over the rule of the bit-flipping channel with $p>\tfrac12$, which decides against the received bits. On the erasure channel a large $p$ means many erasures, not many wrong bits, and deciding against an unerased bit is always wrong, so that rule would err with probability $1-\tfrac12p^2=\tfrac{23}{32}$. Option (c) counts every total erasure as an error and forgets the coin.

The correct answer is (a) ★

At $\boldsymbol{y}=(?,?,?)$ both likelihoods equal $p^3$, so deciding $\hat m=1$ there is one of the ML decisions. When $m=1$ is sent the decoder is always right, because an unerased $0$ leads to $\hat m=1$, and so does a total erasure. Hence $P_{\rm e}(1)=0$. When $m=2$ is sent it errs exactly at a total erasure, so $P_{\rm e}(2)=p^3$. With equiprobable messages, $P_{\rm e}=\tfrac12\cdot0+\tfrac12p^3=\tfrac12p^3$, the same average as with the coin.

Option (b) gives the conditional errors of the coin, which splits the total erasures evenly between the two messages. Option (c) forgets the weights $\tfrac12$ of the average. A different tie-breaking rule changes the conditional errors but, with equiprobable messages, not the average, since every ML decoder is then a MAP decoder and has the smallest average error probability.

The correct answer is (c) ★

When some bit arrives, only the codeword that agrees with it has a nonzero likelihood, and the MAP decoder chooses it without error. When both bits are erased, $\boldsymbol{y}=(?,?)$ has the likelihood $p^2$ under both codewords, and the MAP decoder compares $\tfrac23p^2$ with $\tfrac13p^2$, so it decides $\hat m=1$. Hence $P_{\rm e}(1)=0$ and $P_{\rm e}(2)=p^2=\tfrac14$, and the average is $$P_{\rm e}=\tfrac23\cdot0+\tfrac13\cdot\tfrac14=\tfrac1{12},$$ which is $p^n\min\bigl(\Pr(m=1),\Pr(m=2)\bigr)$ with $n=2$.

Option (a) is the error probability $\tfrac12p^2$ of the ML decoder, which tosses a coin at a total erasure. Option (b) decides the less probable message at a total erasure, which gives $\tfrac23\cdot\tfrac14=\tfrac16$. On this channel the priors matter only when the output carries no information at all.

The correct answer is (a) ★

The constants of the Gaussian densities cancel in the ratio, and $$\frac{W(\boldsymbol{y}|\boldsymbol{x}(2))}{W(\boldsymbol{y}|\boldsymbol{x}(1))}=\exp\biggl(\frac1{2\sigma^2}\sum_{i=1}^3\bigl((y_i+A)^2-(y_i-A)^2\bigr)\biggr)=e^{2Au/\sigma^2},$$ because $(y_i+A)^2-(y_i-A)^2=4Ay_i$, where $u=y_1+y_2+y_3$. Here $u=\tfrac12-1+1=\tfrac12$, so the ratio is $e^{2\cdot\frac12}=e$. It exceeds one, and the ML decoder decides $\hat m=2$.

Option (b) forgets the factor $2$ in the denominator of the Gaussian exponent $(y-x)^2/(2\sigma^2)$ and obtains $e^{4Au/\sigma^2}$. Option (c) is the inverse ratio, $W(\boldsymbol{y}|\boldsymbol{x}(1))/W(\boldsymbol{y}|\boldsymbol{x}(2))$.

The correct answer is (b) ★

The likelihood ratio of the repetition code is $e^{2Au/\sigma^2}$, where $u$ is the sum of the outputs, so two outputs with the same sum have the same ratio. Here $u=A+A-A=A$ and $u'=3\cdot\tfrac A3=A$, so both ratios are $e^{2A^2/\sigma^2}$, and the ML decoder decides $\hat m=2$ for both, with the same confidence.

Options (a) and (c) judge the outputs symbol by symbol, by their closeness to $A$ or by their signs. The logarithm of the likelihood is a sum of scores over the symbols, and for this code the difference of the scores of the two codewords adds up to a multiple of $u$. How the sum is distributed among the three outputs does not matter.

The correct answer is (c) ★

The ML decoder decides $\hat m=2$ when the likelihood ratio $e^{2Au/\sigma^2}$ exceeds one, that is, when the sum $u=y_1+\cdots+y_5$ is positive, and $\hat m=1$ when it is negative. Here $u=4\cdot\tfrac A2-3A=-A< 0$, so $\hat m=1$. The single output $-3A$ is far below zero and outweighs four outputs that are only slightly positive.

Option (a) takes the majority of the signs, which is what a receiver with hard decisions does, not the ML decoder of the whole output. Option (b) is wrong because $\sigma^2$ only scales the exponent $2Au/\sigma^2$, whose sign, and hence the decision, is that of $u$ for every $\sigma^2>0$. The value of $\sigma^2$ matters for the error probability, not for the decision.

The correct answer is (a) ★

The sum is $U=4A+Z$, with $Z=Z_1+Z_2+Z_3+Z_4$. The means add, so $U$ has mean $4A$. The noise samples are independent, so their variances add too, and $Z$ has variance $4\sigma^2$. The sum of independent Gaussian variables is Gaussian, so the ML decoder, which errs when $U< 0$, has $P_{\rm e}(2)=\Pr(Z>4A)=\tfrac12\operatorname{erfc}\bigl(4A/(\sqrt2\cdot2\sigma)\bigr)=\tfrac12\operatorname{erfc}\bigl(\sqrt{2\,\mathrm{SNR}}\bigr)$, with $\mathrm{SNR}=A^2/\sigma^2$.

Option (b) multiplies the variance by $n^2=16$, which would be right for $4Z_1$, four copies of the same noise sample. Independent samples partly cancel, and the standard deviation of the sum grows only as $\sqrt n$, while its mean grows as $n$. Option (c) gives the mean and the variance of the average $U/4$, not of the sum.

The correct answer is (b) ★

When $(-1,-1,-1)$ is sent, the sum of the outputs is $u=-3+Z$, where $Z$ is the sum of the three noise samples, Gaussian with mean zero and variance $3\sigma^2=\tfrac92$. The decoder errs when $u>0$, that is, when $Z>3$. A Gaussian variable of mean zero and variance $s^2$ exceeds $t$ with probability $\tfrac12\operatorname{erfc}\bigl(t/(\sqrt2\,s)\bigr)$, and here $t=3$ and $\sqrt2\,s=\sqrt9=3$, so $P_{\rm e}(1)=\tfrac12\operatorname{erfc}(1)$. By symmetry $P_{\rm e}(2)$ is the same, and so is the average. Equivalently, $\mathrm{SNR}=A^2/\sigma^2=\tfrac23$ and $P_{\rm e}=\tfrac12\operatorname{erfc}\bigl(\sqrt{3\,\mathrm{SNR}/2}\bigr)=\tfrac12\operatorname{erfc}(1)$.

Option (a) uses the variance $\sigma^2$ of one sample for the sum. The threshold grows as $n$ and the standard deviation as $\sqrt n$, so the argument grows as $\sqrt n$, not as $n$. Option (c) is the error probability $\tfrac12\operatorname{erfc}\bigl(\sqrt{\mathrm{SNR}/2}\bigr)$ of a single symbol, without the gain of the repetitions.

The correct answer is (c) ★

The ML decoder of the repetition code has $P_{\rm e}=\tfrac12\operatorname{erfc}\bigl(\sqrt{n\,\mathrm{SNR}/2}\bigr)$, the error probability $\tfrac12\operatorname{erfc}\bigl(\sqrt{\mathrm{SNR}/2}\bigr)$ of a single symbol with its SNR multiplied by $n=4$. A factor $4$ is $10\log_{10}4=2\cdot10\log_{10}2\approx6$ dB, twice the $3$ dB of a factor $2$, which is the gain of two repetitions.

Option (a) takes the factor $\sqrt n=2$ that multiplies the argument of $\operatorname{erfc}$ for the factor of the SNR. Option (b) uses $20\log_{10}4$, the rule for ratios of amplitudes, but the SNR is already a ratio of energies. The gain is paid with the rate, which drops to $\tfrac14$, and with the energy of four symbols per information bit.

The correct answer is (a) ★

The error probability is $\tfrac12\operatorname{erfc}\bigl(\sqrt{n\,\mathrm{SNR}/2}\bigr)=\tfrac12\operatorname{erfc}(\sqrt n)$ at $\mathrm{SNR}=2$. Since $\operatorname{erfc}$ decreases, the condition is $\sqrt n\geq2$, that is, $n\geq4$, so the smallest length is $n=4$, with rate $R=\tfrac14$.

Option (b) multiplies the argument $\sqrt{\mathrm{SNR}/2}=1$ by $n$, as if the threshold $nA$ of the sum grew against a fixed noise level, and obtains $n\geq2$. The standard deviation of the noise of the sum grows too, as $\sqrt n$, so the argument grows only as $\sqrt n$. Option (c) multiplies the SNR by $\sqrt n$ instead of $n$, which would require $n^{1/4}\geq2$.

The correct answer is (b) ★

The MAP decoder decides $\hat m=2$ when $\Pr(m=2)\,W(\boldsymbol{y}|\boldsymbol{x}(2))>\Pr(m=1)\,W(\boldsymbol{y}|\boldsymbol{x}(1))$, that is, when the likelihood ratio $e^{2Au/\sigma^2}=e^{u}$ exceeds $\Pr(m=1)/\Pr(m=2)=3$. Taking logarithms, the condition is $u>\ln 3$; at $u=\ln 3$ the two scores are equal and the tie rule gives $\hat m=1$, an event of probability zero. The threshold moves from $0$ toward the codeword $\boldsymbol{x}(2)$ of the less probable message, whose decision region shrinks.

Option (a) multiplies the threshold by $n=3$, as if each output needed its own shift. The prior enters once, not once per symbol, and in terms of the average $u/3$ the threshold is in fact divided by $n$, so the prior weighs less as the observations accumulate. Option (c) has the wrong sign, which would enlarge the region of the less probable message.

The correct answer is (c) ★

The sum of the outputs is $u=1+\tfrac12-\tfrac12=1$. The ML decoder compares $u$ with $0$ and decides $\hat m=2$. By Exercise 2.29, the MAP decoder compares $u$ with $\ln3$, and $\ln3>1$ because $e< 3$, so it decides $\hat m=1$. The likelihood ratio $e^{u}=e$ favors $\boldsymbol{x}(2)$, but not by enough to overcome the prior odds $3$ in favor of $m=1$.

Option (a) applies the ML threshold to the MAP decoder. Option (b) applies the priors to the ML decoder, which by definition ignores them. The two decoders differ exactly for the outputs with $0< u< \ln3$.

The correct answer is (b) ★

Every output is at least $2$, so all the factors of both likelihoods are positive. With $u=y_1+\cdots+y_4=18$, the likelihoods are $W(\boldsymbol{y}|\boldsymbol{x}(1))=\mu^{-4}e^{-u/\mu}$ and $W(\boldsymbol{y}|\boldsymbol{x}(2))=\mu^{-4}e^{-(u-8)/\mu}$, and their ratio is $e^{8/\mu}=\bigl(e^{-2/\mu}\bigr)^{-4}=2^4=16$. The sum $u$ cancels, so the ratio is $16$ for every output whose four values reach $2$, however far above $2$ they are, and the ML decoder decides $\hat m=2$.

Option (a) is the inverse ratio. Option (c) is the ratio $e^{6/\mu}$ of the code of length $3$. Each symbol contributes a factor $e^{2/\mu}=2$, and here there are four of them.

The correct answer is (a) ★

One noise sample reaches $2$ with probability $\Pr(z_i\geq2)=\int_2^\infty\tfrac1\mu e^{-z/\mu}\,{\rm d}z=e^{-2/\mu}=\tfrac12$. When $m=1$ is sent, $y_i=z_i$, and the decoder errs when the four samples reach $2$, so by independence $P_{\rm e}(1)=\bigl(\tfrac12\bigr)^4=\tfrac1{16}$. When $m=2$ is sent, every output $y_i=2+z_i$ is at least $2$ and the decoder never errs, $P_{\rm e}(2)=0$. The average is $P_{\rm e}=\tfrac12\cdot\tfrac1{16}+\tfrac12\cdot0=\tfrac1{32}$, in general $\tfrac12e^{-2n/\mu}$.

Option (b) is $P_{\rm e}(1)$, which would be the average only if $P_{\rm e}(2)$ were equal to it, as on the Gaussian and bit-flipping channels. Here the noise can raise a $0$ to $2$ but never lowers a $2$. Option (c) uses the probability $1-\bigl(\tfrac12\bigr)^4$ that some sample reaches $2$, but the decoder errs only when every sample does.

The correct answer is (c) ★

On this channel the inputs are themselves energies, so the mean energy per symbol is the average of the two symbols weighted by their probabilities, $E_{\rm s}=\tfrac12\cdot0+\tfrac12\cdot2A=A$, and $\mathrm{SNR}=A/\mu$. Hence $2nA/\mu=2n\,\mathrm{SNR}$ and $P_{\rm e}=\tfrac12e^{-2n\,\mathrm{SNR}}$. As on the Gaussian channel, $n$ repetitions are worth $n$ times the SNR, and each information bit costs the energy $nA$ of $n$ symbols.

Option (a) takes the energy $2A$ of the nonzero symbol and forgets that it is sent only half of the time. Option (b) squares the inputs as amplitudes, which is the convention of the Gaussian channel, not of this one.

The correct answer is (a) ★

When the coded bit is $0$, $y_i=-1+Z_i$, and the detected bit is wrong when $Z_i>1$. When it is $1$, $y_i=1+Z_i$, and the detected bit is wrong when $Z_i< -1$. Both events have probability $p=\tfrac12\operatorname{erfc}\bigl(1/(\sqrt2\,\sigma)\bigr)=\tfrac12\operatorname{erfc}(1)$, since $\sqrt2\,\sigma=1$. In terms of $\mathrm{SNR}=A^2/\sigma^2=2$, this is $p=\tfrac12\operatorname{erfc}\bigl(\sqrt{\mathrm{SNR}/2}\bigr)$. The noise samples are independent, so the errors in different positions are independent, and the channel is a bit-flipping channel with this $p$.

Option (b) uses $\sqrt{\mathrm{SNR}}$ instead of $\sqrt{\mathrm{SNR}/2}$, which is the formula of the complex channel. Option (c) adds the two tails $Z_i>1$ and $Z_i< -1$, but each coded bit has only one error tail, on the side of the other symbol.

The correct answer is (b) ★

The detected signs are $(+,+,+,-,-)$, so the hard receiver sees three bits $1$ and two bits $0$ and decides $\hat m=2$. The soft receiver adds the outputs, $u=\tfrac A4+\tfrac A4+\tfrac A2-2A-\tfrac A2=-\tfrac32A< 0$, and decides $\hat m=1$. The three positive outputs are close to the threshold $0$ and nearly useless, while the output $-2A$ is far from it, but after the detector each of them counts as one vote.

Option (a) lets the soft receiver follow the majority of the signs, which it does not do. Option (c) exchanges the two decisions. A disagreement does not say which receiver is right for this particular output, but on average the soft receiver, which is the ML decoder of the whole observation, errs less.

The correct answer is (c) ★

Each detected bit is wrong with probability $p=\tfrac12\operatorname{erfc}\bigl(\sqrt{\mathrm{SNR}/2}\bigr)=\tfrac12\operatorname{erfc}(1)$, independently of the others, so the detected bits come from a bit-flipping channel with flip probability $p$. The majority vote errs with probability $3p^2(1-p)+p^3=3p^2-2p^3$, and with $p=\tfrac12\operatorname{erfc}(1)$ this is $\tfrac34\operatorname{erfc}^2(1)-\tfrac14\operatorname{erfc}^3(1)$, about $0.018$.

Option (a) is the error probability $\tfrac12\operatorname{erfc}\bigl(\sqrt{3\,\mathrm{SNR}/2}\bigr)\approx0.007$ of the soft receiver, which is smaller because the detector discards the magnitudes of the outputs. Option (b) is the error probability $p\approx0.079$ of a single detected bit, without the code.

The correct answer is (a) ★

An error occurs when both detected bits are wrong, with probability $p^2$, or when exactly one of them is wrong, with probability $2p(1-p)$, and the coin then chooses the wrong message, with probability $\tfrac12$. The total is $p^2+p(1-p)=p$, the error probability of sending the bit once. With hard decisions the second copy is wasted, whereas the soft receiver has $P_{\rm e}=\tfrac12\operatorname{erfc}\bigl(\sqrt{\mathrm{SNR}}\bigr)$, the gain of $3$ dB of two repetitions.

Option (b) counts only the case of two wrong bits and assumes that a disagreement is always resolved correctly. Option (c) counts every disagreement as an error, $p^2+2p(1-p)$, and forgets that the coin is right half of the time.

The correct answer is (b) ★

If the three outputs have the same sign, their sum has that sign too, and both receivers decide the same message. If two outputs are positive and one is negative, the hard receiver decides $\hat m=2$, while the soft receiver decides $\hat m=1$ when the negative output is large enough, as for $\bigl(\tfrac A2,\tfrac A2,-2A\bigr)$, whose sum is $-A$. The same happens with the signs exchanged. The condition is sufficient but not necessary, since the decisions also agree for outputs such as $\bigl(A,A,-\tfrac A2\bigr)$.

Option (a) fails for $\bigl(A,-\tfrac A4,-\tfrac A4\bigr)$, whose sum is $\tfrac A2>0$, while the hard receiver sees two negative signs and decides $\hat m=1$. Option (c) ignores that the hard receiver keeps only the sign of each output and discards its magnitude.

The correct answer is (c) ★

For $n=3$ the factor is $\tfrac{2\cdot3}{3+1}=\tfrac32$, that is, $10\log_{10}\tfrac32\approx1.8$ dB. As $n$ grows, $2n/(n+1)$ tends to $2$, that is, $3$ dB. At high SNR the hard receiver fails when $(n+1)/2$ detected bits are wrong, and the probability of each wrong bit decays like $e^{-\mathrm{SNR}/2}$, so its error probability decays like $e^{-(n+1)\mathrm{SNR}/4}$. The soft receiver decays like $e^{-n\,\mathrm{SNR}/2}$, and the ratio of the two exponents is $2n/(n+1)$.

Option (a) is the gain $10\log_{10}3\approx4.8$ dB of the soft receiver with $n=3$ over a single symbol, which is a different comparison. Option (b) ignores that the detector keeps only the sign of each output and discards its magnitude, which the soft receiver uses.

The correct answer is (b) ★

The likelihood of $\boldsymbol{x}(1)$ is positive for every output, since the outputs are nonnegative. The likelihood of $\boldsymbol{x}(2)$ is zero as soon as one output is below $2$, because the noise never lowers a symbol, and otherwise the likelihood ratio is $e^{6/\mu}=8>1$. The ML decoder therefore decides $\hat m=2$ exactly when every output is at least $2$, while the majority decoder decides $\hat m=2$ when at least two outputs are at least $2$. The two rules differ only when exactly two outputs reach $2$.

For $\boldsymbol{y}=(4,1,3)$, the output $y_2=1$ has probability zero under $\boldsymbol{x}(2)$, so the ML decoder decides $\hat m=1$, while the majority decoder sees $(2,0,2)$ and decides $\hat m=2$. For option (a) both decide $\hat m=2$, since every output reaches $2$, and for option (c) both decide $\hat m=1$, since only one output does.

The correct answer is (a) ★

Each noise sample reaches $2$ with probability $q=e^{-2/\mu}=\tfrac14$, independently of the others. When $m=1$ is sent, the majority decoder errs when at least two of the three samples reach $2$, so $P_{\rm e}(1)=3q^2(1-q)+q^3=\tfrac9{64}+\tfrac1{64}=\tfrac{10}{64}$. When $m=2$ is sent, every output is at least $2$, every symbol decision is $2$ and the decoder never errs, $P_{\rm e}(2)=0$. The average is $P_{\rm e}=\tfrac12\cdot\tfrac{10}{64}=\tfrac5{64}$.

Option (b) is $P_{\rm e}(1)$ alone, without the average with $P_{\rm e}(2)=0$. Option (c) is the error probability $\tfrac12q^3$ of the ML decoder, which decides $\hat m=2$ only when the three outputs reach $2$. The majority decoder is ten times worse here, because it errs as soon as two samples reach $2$.

The correct answer is (c) ★

From the sent symbols to the detected symbols, a $2$ is always detected as $2$, because $y_i=2+z_i\geq2$, and a $0$ is detected as $2$ with probability $\Pr(z_i\geq2)=\tfrac12$. When some detected symbol is $0$, the likelihood of $\boldsymbol{x}(2)$ is zero, since a $2$ is never detected as $0$, and the decoder decides $\hat m=1$. When the three detected symbols are $2$, the likelihoods are $1$ for $\boldsymbol{x}(2)$ and $\bigl(\tfrac12\bigr)^3$ for $\boldsymbol{x}(1)$, and it decides $\hat m=2$. This receiver decides $\hat m=2$ exactly when every output reaches $2$, as the ML decoder of the outputs does, and $P_{\rm e}(1)=\bigl(\tfrac12\bigr)^3=\tfrac18$.

Option (a) is the conditional error of the majority decoder, which votes on the detected symbols as if the channel were symmetric. The loss of the majority decoder comes from the vote, not from the symbol decisions, because on this channel the detected symbols keep everything the ML decoder needs. Option (b) is the probability that at least one sample reaches $2$.

The correct answer is (b) ★

Each codeword has $n=7$ symbols of energy $A^2$, that is, energy $7A^2$, and it carries $k=4$ information bits, so $E_{\rm b}=\tfrac{nE_{\rm s}}k=\tfrac{E_{\rm s}}R=\tfrac74A^2$, with $R=\tfrac47$. A rate below one makes each information bit more expensive than a symbol.

Option (a) multiplies by the rate instead of dividing by it. Option (c) is the energy of a whole codeword, which is the energy per information bit only when $k=1$, as for the repetition code of length $7$.

The correct answer is (a) ★

For the repetition code $E_{\rm b}=nE_{\rm s}$, so at fixed $E_{\rm b}$ each of the four symbols has energy $E_{\rm s}=E_{\rm b}/4$, and the SNR per symbol is divided by $4$. The error probability is $\tfrac12\operatorname{erfc}\bigl(\sqrt{n\,\mathrm{SNR}/2}\bigr)$, and $n\,\mathrm{SNR}=nE_{\rm s}/\sigma^2=E_{\rm b}/\sigma^2$ does not depend on $n$, so $P_{\rm e}=\tfrac12\operatorname{erfc}\bigl(\sqrt{E_{\rm b}/(2\sigma^2)}\bigr)$ for every length.

Option (b) keeps the energy per symbol fixed, which is the comparison at fixed $E_{\rm s}$, where the gain is paid with $n$ times more energy per information bit. Option (c) forgets that the decoder collects the energy of the four symbols. At equal energy per information bit, repetition gains nothing, and it divides the rate by $4$.

The correct answer is (c) ★

Sent once with $\pm2$, the bit has $\mathrm{SNR}=\tfrac42=2$ and $P_{\rm e}=\tfrac12\operatorname{erfc}\bigl(\sqrt{\mathrm{SNR}/2}\bigr)=\tfrac12\operatorname{erfc}(1)$. With four repetitions of $\pm1$, the SNR per symbol is $\tfrac12$, and $P_{\rm e}=\tfrac12\operatorname{erfc}\bigl(\sqrt{4\cdot\tfrac12/2}\bigr)=\tfrac12\operatorname{erfc}(1)$ too. In both cases $P_{\rm e}=\tfrac12\operatorname{erfc}\bigl(\sqrt{E_{\rm b}/(2\sigma^2)}\bigr)$ with $E_{\rm b}=4$.

Option (a) multiplies by $n=4$ the SNR of the uncoded symbol $\pm2$, but the repetition code does not send four symbols of that energy. Option (b) forgets the factor $n$ and uses the SNR of a single symbol $\pm1$.

The correct answer is (b) ★

At fixed $A$ and $\sigma^2$, $P_{\rm e}=\tfrac12\operatorname{erfc}\bigl(\sqrt{n\,\mathrm{SNR}/2}\bigr)$ decreases to zero as $n$ grows, because $\operatorname{erfc}$ decreases to zero. The price is the rate $R=\tfrac1n$, which also tends to zero, and the energy, since each information bit costs $E_{\rm b}=nA^2$, the energy of $n$ symbols.

Option (a) confuses the energy per symbol with the energy per information bit. Option (c) is right that the noise of the sum grows, with variance $n\sigma^2$, but the signal part $nA$ grows faster. The ratio of the squared mean to the variance of the sum is $n^2A^2/(n\sigma^2)=n\,\mathrm{SNR}$, which grows with $n$.

The correct answer is (a) ★

Shannon's answer, which Topic 3 develops, is that every channel has a capacity $C$ and that, for every rate below $C$, there are codes whose error probability is as small as we wish. Since $\tfrac12< 0.53$, some code of rate $\tfrac12$, more than ten times the rate of repetition, has an error probability below $10^{-6}$. Such codes are long, and they are not repetition codes.

Option (b) extends to every code the behavior of repetition, whose reliability is paid with a vanishing rate. Option (c) turns a statement about the existence of good codes into a statement about every code. The repetition code of length $3$, for instance, has rate $\tfrac13< C$ and error probability $\tfrac7{250}$.

The correct answer is (c) ★

The code carries $k=2$ information bits in $n=3$ bits, so $R=\tfrac23$. Its four codewords are $000$, $011$, $101$ and $110$, the sequences of three bits with an even number of ones. Changing a single bit changes the parity, so no two codewords differ in exactly one position, and comparing them shows that any two differ in exactly two positions. A single flipped bit therefore produces a sequence that is not a codeword, and it is noticed, although it cannot be located.

Option (a) inverts the rate, which counts information bits per channel use. Codewords that differ in a single position, as in option (b), occur in the code of all eight sequences of three bits, which has rate $1$ and no redundancy, not in the parity code.

The correct answer is (a) ★

Two codewords differ in exactly two positions, and in each of them the symbols are $-A$ and $+A$, at squared distance $(2A)^2=4A^2$. Hence $d_{\min}^2=2\cdot4A^2=8A^2$. A codeword has energy $3A^2$ and carries two information bits, so $E_{\rm b}=\tfrac32A^2$. The ratio $d_{\min}^2/E_{\rm b}=\tfrac{16}3$ is larger than the value $4$ of uncoded 2-PAM and of the repetition code, by a factor $\tfrac43$ at equal energy per information bit.

Option (b) takes the squared distance $4A^2$ between two symbols, as if two codewords could differ in a single position. Option (c) divides the energy of a codeword by one information bit, as for the repetition code, instead of by two.

The correct answer is (b) ★

On the Gaussian channel the ML decoder chooses the codeword nearest to $\boldsymbol{y}$ in Euclidean distance. The squared distances from $\boldsymbol{y}=\bigl(1,\tfrac12,1\bigr)A$ are $\bigl(4+\tfrac94+4\bigr)A^2=\tfrac{41}4A^2$ to $(-A,-A,-A)$, $\bigl(4+\tfrac14+0\bigr)A^2=\tfrac{17}4A^2$ to $(-A,+A,+A)$, $\bigl(0+\tfrac94+0\bigr)A^2=\tfrac94A^2$ to $(+A,-A,+A)$ and $\bigl(0+\tfrac14+4\bigr)A^2=\tfrac{17}4A^2$ to $(+A,+A,-A)$. The nearest is $(+A,-A,+A)$, the information bits $10$. The weak second output is outvoted by the other two through the parity.

Option (a) is the sequence of the signs of the outputs, which has odd parity and is not a codeword. Option (c) detects the first two symbols and recomputes the parity symbol, ignoring the third output, which is strong evidence against it.