Seminar 2. Repetition codes and likelihood
The seven questions of the session, each with three options and one correct answer. Work out your answer before opening a solution.
Question 1. One of two messages, m=1 or m=2, is sent with the repetition code of length n=3: the codewords are \x(1)=000 and \x(2)=111. The channel is the bit-erasing channel with erasure probability p, where 0<p<1. Each bit arrives intact with probability 1-p or is erased with probability p, and it is never flipped. Erasures occur independently across the three channel uses. An erased bit is written \era. In questions 1 to 4 the two messages are equiprobable. The receiver observes \y=(0,\era,0). What are the likelihoods W(\y|000) and W(\y|111) of the two codewords?
(a) W(\y|000)=p\,(1-p)^2 and W(\y|111)=0.
(b) W(\y|000)=p\,(1-p)^2 and W(\y|111)=p^2(1-p).
(c) W(\y|000)=p^2(1-p) and W(\y|111)=0.
Show solution
The correct answer is (a) ★
The channel is memoryless, so by equation (2.9) of the lecture notes the law of a sequence is the product of the laws of its symbols. By Table 1.2 of Topic 1, the bit-erasing channel has W(y|x)=1-p when y=x, W(\era|x)=p, and W(y|x)=0 when y is the other bit. For the codeword 000 the two zeros arrive intact and the middle bit is erased, so W(\y|000)=(1-p)\cdot p\cdot(1-p)=p\,(1-p)^2. For the codeword 111 the first bit would have been flipped, which never happens, so W(\y|111)=0\cdot p\cdot0=0. The answer is (a). Option (b) treats the erasure as a flipped bit and gives a positive likelihood to 111, although two zeros arrived intact, and option (c) exchanges the roles of p and 1-p.
Question 2. One of two messages, m=1 or m=2, is sent with the repetition code of length n=3: the codewords are \x(1)=000 and \x(2)=111. The channel is the bit-erasing channel with erasure probability p, where 0<p<1. Each bit arrives intact with probability 1-p or is erased with probability p, and it is never flipped. Erasures occur independently across the three channel uses. An erased bit is written \era. In questions 1 to 4 the two messages are equiprobable. The receiver observes \y=(\era,1,\era). What does the ML decoder decide?
(a) It tosses a fair coin, because two of the three bits are erased.
(b) \hat m=2 only when p<\tfrac12, as on the bit-flipping channel.
(c) \hat m=2 for every p, because W(\y|000)=0.
Show solution
The correct answer is (c) ★
By Theorem 2.2 of the lecture notes, the ML decoder chooses the codeword with the largest likelihood. As in the previous question, W(\y|000)=p\cdot0\cdot p=0 and W(\y|111)=p\cdot(1-p)\cdot p=p^2(1-p), which is positive. The decoder decides \hat m=2 whatever the value of p, and the answer is (c). As in Example 2.4(c), a single unerased bit decides, because an unerased bit is always correct. The condition p<\tfrac12 belongs to the bit-flipping channel, where a received bit may be wrong.
Question 3. One of two messages, m=1 or m=2, is sent with the repetition code of length n=3: the codewords are \x(1)=000 and \x(2)=111. The channel is the bit-erasing channel with erasure probability p, where 0<p<1. Each bit arrives intact with probability 1-p or is erased with probability p, and it is never flipped. Erasures occur independently across the three channel uses. An erased bit is written \era. In questions 1 to 4 the two messages are equiprobable. When the three bits are erased, the ML decoder tosses a fair coin. What is its error probability P_{\rm e}?
(a) P_{\rm e}=p^3
(b) P_{\rm e}=\tfrac12\,p^3
(c) P_{\rm e}=p^2(3-2p)
Show solution
The correct answer is (b) ★
When m=1 is sent, the decoder is right whenever some bit arrives, by the previous question. It errs only if the output is (\era,\era,\era), which has probability p^3 by equation (2.9), and the coin is wrong, which has probability \tfrac12. Hence P_{\rm e}(1)=\tfrac12p^3. The same argument when m=2 is sent gives P_{\rm e}(2)=\tfrac12p^3. By equation (2.6), the average is P_{\rm e}=\tfrac12P_{\rm e}(1)+\tfrac12P_{\rm e}(2)=\tfrac12p^3, as in Problem 2.6, and the answer is (b). Option (a) is the probability that the three bits are erased, which is not the error probability, and option (c) is the error probability of majority decoding on the bit-flipping channel.
Question 4. One of two messages, m=1 or m=2, is sent with the repetition code of length n=3: the codewords are \x(1)=000 and \x(2)=111. The channel is the bit-erasing channel with erasure probability p, where 0<p<1. Each bit arrives intact with probability 1-p or is erased with probability p, and it is never flipped. Erasures occur independently across the three channel uses. An erased bit is written \era. In questions 1 to 4 the two messages are equiprobable. The message is now sent with n repetitions, and p=\tfrac1{10}. What is the smallest n for which the ML decoder has P_{\rm e}\leq\tfrac1{1000}, and what is the rate of that code?
(a) n=2 and R=\tfrac12
(b) n=3 and R=\tfrac13
(c) n=4 and R=\tfrac14
Show solution
The correct answer is (b) ★
The steps of the previous questions do not depend on the length. With n repetitions the codewords are (0,\ldots,0) and (1,\ldots,1), one unerased bit decides, and the decoder errs only when the n bits are erased and the coin is wrong. Hence P_{\rm e}(1)=P_{\rm e}(2)=\tfrac12p^n and P_{\rm e}=\tfrac12p^n, as in Problem 2.6 of the lecture notes. For p=\tfrac1{10} this is \tfrac1{200} for n=2, which is too large, and \tfrac1{2000} for n=3, which is below \tfrac1{1000}. By Definition 2.1 the rate is R=k/n=\tfrac13, and the answer is (b).
Question 5. In questions 5 to 7 the length is again n=3, and the two messages are no longer equiprobable: \Pr(m=1)=\tfrac45 and \Pr(m=2)=\tfrac15. The MAP decoder chooses the message m with the largest product of the prior and the likelihood, \Pr(m)\,W(\y|\x(m)). The receiver observes \y=(\era,\era,\era). What does the MAP decoder decide?
(a) \hat m=1, because \tfrac45\,p^3 is larger than \tfrac15\,p^3.
(b) It tosses a fair coin, because the two likelihoods are equal.
(c) \hat m=2, because the less probable message is the harder one to detect.
Show solution
The correct answer is (a) ★
The two likelihoods are equal, W(\y|000)=W(\y|111)=p^3, so the output says nothing about m and the ML decoder tosses a coin. By Theorem 2.2 of the lecture notes, the MAP decoder compares \Pr(1)\,W(\y|000)=\tfrac45p^3 with \Pr(2)\,W(\y|111)=\tfrac15p^3. The first is larger, so it decides \hat m=1 and the answer is (a). As Proposition 2.3(c) says, the MAP decoder breaks the tie with the priors.
Question 6. In questions 5 to 7 the length is again n=3, and the two messages are no longer equiprobable: \Pr(m=1)=\tfrac45 and \Pr(m=2)=\tfrac15. The MAP decoder chooses the message m with the largest product of the prior and the likelihood, \Pr(m)\,W(\y|\x(m)). The receiver observes \y=(\era,1,\era). What does the MAP decoder decide?
(a) \hat m=1, because the prior \tfrac45 outweighs a single unerased bit.
(b) \hat m=1 when p is large enough, and \hat m=2 otherwise.
(c) \hat m=2 for every p, as \Pr(1)\,W(\y|000)=0.
Show solution
The correct answer is (c) ★
By Theorem 2.2 of the lecture notes, the MAP decoder compares \Pr(1)\,W(\y|000)=\tfrac45\cdot0=0 with \Pr(2)\,W(\y|111)=\tfrac15\,p^2(1-p), which is positive. It decides \hat m=2 and the answer is (c). A prior cannot outweigh a likelihood equal to zero: the codeword 000 cannot produce an unerased 1. On this channel the prior matters only when the three bits are erased.
Question 7. In questions 5 to 7 the length is again n=3, and the two messages are no longer equiprobable: \Pr(m=1)=\tfrac45 and \Pr(m=2)=\tfrac15. The MAP decoder chooses the message m with the largest product of the prior and the likelihood, \Pr(m)\,W(\y|\x(m)). What is the error probability P_{\rm e} of the MAP decoder?
(a) P_{\rm e}=\tfrac15\,p^3
(b) P_{\rm e}=\tfrac12\,p^3
(c) P_{\rm e}=\tfrac45\,p^3
Show solution
The correct answer is (a) ★
The MAP decoder is right whenever some bit arrives, by the previous question, so it can only err when the output is (\era,\era,\era), which has probability p^3 whichever message is sent. It then decides \hat m=1, so P_{\rm e}(1)=0 and P_{\rm e}(2)=p^3. By equation (2.6) of the lecture notes, the average is P_{\rm e}=\tfrac45\cdot0+\tfrac15\cdot p^3=\tfrac15p^3, and the answer is (a). This is the value p^n\min(\Pr(1),\Pr(2)) of Problem 2.6. The MAP decoder errs only when the less probable message is sent, and its error probability is \tfrac25 of the value \tfrac12p^3 of the ML decoder of question 3, which is option (b). Option (c) averages with the wrong prior.