Seminar 3. Comparing receivers and codes
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, equiprobable, is sent with the repetition code of length n=3 and symbols 0 and 2, so the codewords are \x(1)=(0,0,0) and \x(2)=(2,2,2). The channel adds exponential noise: the output is y_i=x_i+z_i, where the three noise samples z_i\geq0 are independent and exponential with mean \mu, so that \begin{equation*} W(y|x)=\frac1\mu\,e^{-(y-x)/\mu}\,\ind{y\geq x}, \end{equation*} where the indicator function \ind{y\geq x} is 1 if y\geq x and 0 otherwise. The noise mean satisfies e^{-2/\mu}=\tfrac12. We compare two decoders. The ML decoder chooses the m with the largest likelihood W(\y|\x(m)) of the whole codeword. The suboptimal majority voting decoder first decides each symbol \hat x_i\in\{0,2\} by ML from y_i alone, and then decides \hat m by majority voting of the three symbols. The output is \y=(2.5,\,1,\,4). What do the two decoders decide?
(a) Both decide \hat m=1.
(b) ML decides \hat m=1, and majority decides \hat m=2.
(c) Both decide \hat m=2.
Show solution
The correct answer is (b) ★
The channel is memoryless, so by equation (2.9) of the lecture notes the likelihood of a codeword is the product of the laws of its three symbols. For \x(2) the product of the three indicators is \ind{2.5\geq2}\,\ind{1\geq2}\,\ind{4\geq2}=0, because the second output is below 2, so W(\y|\x(2))=0. For \x(1) every indicator is 1 and W(\y|\x(1))=\mu^{-3}e^{-7.5/\mu}>0, so the ML decoder decides \hat m=1. The majority decoder works symbol by symbol: the ratio of the two laws of one symbol is W(y_i|2)/W(y_i|0)=e^{2/\mu}\,\ind{y_i\geq2}, which is 2 or 0, so \hat x_i=2 exactly when y_i\geq2. Here \hat\x=(2,0,2) and the majority gives \hat m=2. The answer is (b). The majority decoder has lost the information that y_2=1 is impossible under \x(2).
Question 2. One of two messages, m=1 or m=2, equiprobable, is sent with the repetition code of length n=3 and symbols 0 and 2, so the codewords are \x(1)=(0,0,0) and \x(2)=(2,2,2). The channel adds exponential noise: the output is y_i=x_i+z_i, where the three noise samples z_i\geq0 are independent and exponential with mean \mu, so that \begin{equation*} W(y|x)=\frac1\mu\,e^{-(y-x)/\mu}\,\ind{y\geq x}, \end{equation*} where the indicator function \ind{y\geq x} is 1 if y\geq x and 0 otherwise. The noise mean satisfies e^{-2/\mu}=\tfrac12. We compare two decoders. The ML decoder chooses the m with the largest likelihood W(\y|\x(m)) of the whole codeword. The suboptimal majority voting decoder first decides each symbol \hat x_i\in\{0,2\} by ML from y_i alone, and then decides \hat m by majority voting of the three symbols. The output is \y=(2.5,\,3,\,4). What is the likelihood ratio W(\y|\x(2))/W(\y|\x(1)), and what do the two decoders decide?
(a) The ratio is e^{6/\mu}, and both decide \hat m=2.
(b) The ratio is e^{-9.5/\mu}, and both decide \hat m=1.
(c) The ratio is e^{-6/\mu}, and both decide \hat m=1.
Show solution
The correct answer is (a) ★
Now every output is at least 2, so the three indicators are 1 for both codewords. The exponents add up: W(\y|\x(1))=\mu^{-3}e^{-(y_1+y_2+y_3)/\mu} and W(\y|\x(2))=\mu^{-3}e^{-(y_1+y_2+y_3-6)/\mu}, with y_1+y_2+y_3=9.5. In the ratio the constants and the sum of the outputs cancel, and \begin{equation*} \frac{W(\y|\x(2))}{W(\y|\x(1))}=e^{6/\mu}. \end{equation*} The ML decoder decides \hat m=2 because the exponent is positive and the ratio exceeds 1; with the given noise mean, the ratio is \bigl(e^{-2/\mu}\bigr)^{-3}=2^3=8. The majority decoder has \hat\x=(2,2,2) and decides \hat m=2 too. The answer is (a). Option (b) keeps the likelihood of \x(1) instead of the ratio, and option (c) inverts the ratio.
Question 3. One of two messages, m=1 or m=2, equiprobable, is sent with the repetition code of length n=3 and symbols 0 and 2, so the codewords are \x(1)=(0,0,0) and \x(2)=(2,2,2). The channel adds exponential noise: the output is y_i=x_i+z_i, where the three noise samples z_i\geq0 are independent and exponential with mean \mu, so that \begin{equation*} W(y|x)=\frac1\mu\,e^{-(y-x)/\mu}\,\ind{y\geq x}, \end{equation*} where the indicator function \ind{y\geq x} is 1 if y\geq x and 0 otherwise. The noise mean satisfies e^{-2/\mu}=\tfrac12. We compare two decoders. The ML decoder chooses the m with the largest likelihood W(\y|\x(m)) of the whole codeword. The suboptimal majority voting decoder first decides each symbol \hat x_i\in\{0,2\} by ML from y_i alone, and then decides \hat m by majority voting of the three symbols. When does the ML decoder decide \hat m=2?
(a) When y_1+y_2+y_3\geq3.
(b) When at least two outputs are at least 2.
(c) When every output is at least 2.
Show solution
The correct answer is (c) ★
Questions 1 and 2 cover the two possible cases. The likelihood of \x(1) is always positive, since every y_i\geq0. The ratio is e^{6/\mu}\,\ind{y_1\geq2}\,\ind{y_2\geq2}\,\ind{y_3\geq2}, which exceeds 1 when every output is at least 2 and is 0 otherwise, whatever the value of y_1+y_2+y_3. By Theorem 2.2 of the lecture notes, the ML decoder decides \hat m=2 when the ratio exceeds 1, hence exactly when every output is at least 2, that is, when \min_i y_i\geq2, as in Example 2.4(d). The answer is (c). The sum of option (a), compared with the midpoint 3 between the sums of the codewords, is the rule of the Gaussian channel, and the majority of option (b) is the rule of the majority decoder.
Question 4. One of two messages, m=1 or m=2, equiprobable, is sent with the repetition code of length n=3 and symbols 0 and 2, so the codewords are \x(1)=(0,0,0) and \x(2)=(2,2,2). The channel adds exponential noise: the output is y_i=x_i+z_i, where the three noise samples z_i\geq0 are independent and exponential with mean \mu, so that \begin{equation*} W(y|x)=\frac1\mu\,e^{-(y-x)/\mu}\,\ind{y\geq x}, \end{equation*} where the indicator function \ind{y\geq x} is 1 if y\geq x and 0 otherwise. The noise mean satisfies e^{-2/\mu}=\tfrac12. We compare two decoders. The ML decoder chooses the m with the largest likelihood W(\y|\x(m)) of the whole codeword. The suboptimal majority voting decoder first decides each symbol \hat x_i\in\{0,2\} by ML from y_i alone, and then decides \hat m by majority voting of the three symbols. When does the majority decoder decide \hat m=2?
(a) When every output is at least 2.
(b) When at least two outputs are at least 2.
(c) When y_1+y_2+y_3\geq3.
Show solution
The correct answer is (b) ★
By the solution of question 1, the symbol decision is \hat x_i=2 exactly when y_i\geq2, since the ratio of the two laws of one symbol is e^{2/\mu}\,\ind{y_i\geq2}, which is 2 or 0. The majority of three symbols is 2 when at least two of them are 2, so the majority decoder decides \hat m=2 when at least two outputs are at least 2. The answer is (b). Option (a) is the ML rule of question 3, which is stricter: the majority decoder can decide \hat m=2 with one output below 2, as in question 1, which the ML decoder never does.
Question 5. One of two messages, m=1 or m=2, equiprobable, is sent with the repetition code of length n=3 and symbols 0 and 2, so the codewords are \x(1)=(0,0,0) and \x(2)=(2,2,2). The channel adds exponential noise: the output is y_i=x_i+z_i, where the three noise samples z_i\geq0 are independent and exponential with mean \mu, so that \begin{equation*} W(y|x)=\frac1\mu\,e^{-(y-x)/\mu}\,\ind{y\geq x}, \end{equation*} where the indicator function \ind{y\geq x} is 1 if y\geq x and 0 otherwise. The noise mean satisfies e^{-2/\mu}=\tfrac12. We compare two decoders. The ML decoder chooses the m with the largest likelihood W(\y|\x(m)) of the whole codeword. The suboptimal majority voting decoder first decides each symbol \hat x_i\in\{0,2\} by ML from y_i alone, and then decides \hat m by majority voting of the three symbols. What is the error probability P_{\rm e}(1) of the ML decoder when m=1 is sent? It may be useful that a primitive of \frac1\mu e^{-z/\mu} is -e^{-z/\mu}.
(a) 1/2
(b) 1/8
(c) 7/8
Show solution
The correct answer is (b) ★
When m=1 is sent, the outputs are the noise samples, y_i=z_i, and by question 3 the decoder errs when every sample reaches 2. One sample does so with probability \begin{equation*} \Pr(z_i\geq2)=\int_2^\infty\frac1\mu\,e^{-z/\mu}\drm z=e^{-2/\mu}=\frac12. \end{equation*} The three samples are independent, so the probabilities multiply and P_{\rm e}(1)=\bigl(\tfrac12\bigr)^3=\tfrac18. The answer is (b). Option (a) is the probability for one sample, and option (c) is the probability that at least one sample reaches 2.
Question 6. One of two messages, m=1 or m=2, equiprobable, is sent with the repetition code of length n=3 and symbols 0 and 2, so the codewords are \x(1)=(0,0,0) and \x(2)=(2,2,2). The channel adds exponential noise: the output is y_i=x_i+z_i, where the three noise samples z_i\geq0 are independent and exponential with mean \mu, so that \begin{equation*} W(y|x)=\frac1\mu\,e^{-(y-x)/\mu}\,\ind{y\geq x}, \end{equation*} where the indicator function \ind{y\geq x} is 1 if y\geq x and 0 otherwise. The noise mean satisfies e^{-2/\mu}=\tfrac12. We compare two decoders. The ML decoder chooses the m with the largest likelihood W(\y|\x(m)) of the whole codeword. The suboptimal majority voting decoder first decides each symbol \hat x_i\in\{0,2\} by ML from y_i alone, and then decides \hat m by majority voting of the three symbols. What is the error probability P_{\rm e}(1) of the majority decoder when m=1 is sent? Compare it in your answer with that of the ML decoder.
(a) 1/8
(b) 3/8
(c) 1/2
Show solution
The correct answer is (c) ★
By question 4 the majority decoder errs when at least two of the three noise samples reach 2, each with probability \tfrac12 by question 5 and independently. Exactly two samples reach 2 in three ways, with probability 3\cdot\bigl(\tfrac12\bigr)^2\cdot\tfrac12=\tfrac38, and all three with probability \tfrac18. In total P_{\rm e}(1)=\tfrac38+\tfrac18=\tfrac12. The answer is (c). The majority decoder errs four times more often than the ML decoder of question 5, because it errs as soon as two samples reach 2, while the ML decoder needs all three. The loss is due to the majority vote, not to the symbol decisions. Seen from the symbols to the detected symbols, this channel is a Z-channel: a 2 is always detected as 2, and a 0 is detected as 2 with probability \tfrac12. A smarter hard decoder would apply ML to the three detected symbols on this Z-channel, and decide \hat m=2 only when all three are 2, since a detected 0 is impossible under \x(2): that is the rule of question 3, so on this channel hard decisions followed by ML decoding lose nothing, as Section 2.3 of the lecture notes says. Option (a) is the ML value, and option (b) forgets the case of three samples.
Question 7. One of two messages, m=1 or m=2, equiprobable, is sent with the repetition code of length n=3 and symbols 0 and 2, so the codewords are \x(1)=(0,0,0) and \x(2)=(2,2,2). The channel adds exponential noise: the output is y_i=x_i+z_i, where the three noise samples z_i\geq0 are independent and exponential with mean \mu, so that \begin{equation*} W(y|x)=\frac1\mu\,e^{-(y-x)/\mu}\,\ind{y\geq x}, \end{equation*} where the indicator function \ind{y\geq x} is 1 if y\geq x and 0 otherwise. The noise mean satisfies e^{-2/\mu}=\tfrac12. We compare two decoders. The ML decoder chooses the m with the largest likelihood W(\y|\x(m)) of the whole codeword. The suboptimal majority voting decoder first decides each symbol \hat x_i\in\{0,2\} by ML from y_i alone, and then decides \hat m by majority voting of the three symbols. What is the error probability P_{\rm e}(2) of each decoder when m=2 is sent? Comment on the result.
(a) ML 0 and majority 0.
(b) ML 1/8 and majority 1/2.
(c) ML 0 and majority 1/2.
Show solution
The correct answer is (a) ★
When m=2 is sent, every output is y_i=2+z_i\geq2, because the noise is never negative. By question 3 the ML decoder then decides \hat m=2, and by question 4 so does the majority decoder, since every symbol decision is \hat x_i=2. Neither decoder errs, so P_{\rm e}(2)=0 for both, and the answer is (a). There is no symmetry between the two messages: the noise can raise a 0 to 2, and it can never lower a 2. Option (b) assumes the symmetry of the bit-flipping and Gaussian channels, where P_{\rm e}(2)=P_{\rm e}(1). With equiprobable messages, equation (2.6) of the lecture notes gives the average error probabilities P_{\rm e}=\tfrac12\cdot\tfrac18=\tfrac1{16} for ML and \tfrac12\cdot\tfrac12=\tfrac14 for majority: the majority decoder errs four times more often, because it throws away the likelihoods and keeps a vote of three symbol decisions, as in question 1, where it decided \hat m=2 from an output that was impossible under \x(2).