A transmitter sends bits to a receiver across a noisy channel. The model for the noise is simple: regardless of whether a one or a zero was transmitted, the channel flips the bit with probability p = 0:1. Furthermore, assume that the noise acts on each of the transmitted bits independently. In an attempt to combat the noise, the transmitter adopts an n-fold repetition strategy, i.e., it transmits each message bit n times. For example, with n = 5, the transmitter sends 00000 to convey a message bit of 0, and it sends 11111 to convey a message bit of 1.
a). Suppose n = 5 and the receiver observes 00010. Compare the probability that the message bit was 1 to the probability that it was 0. In other words, compare Pr[ | 00010observed] to Pr[msg = 0 | 00010observed].
b). Based on (a), a reasonable decoding strategy at the receiver is majority rules decide 0 if there are more zeros than ones received, and decide 1 if there are more ones than zeros received. Find the probability that this strategy results in a decoding error with n = 5 and p = 0.1.
c). with p = 0:1, how large must n be in order for the majority rules decoder to achieve a probability of error that is less than 10^-4