A transmitter sends bits to a receiver across a noisy channel. The model for the noise...

Transcribed Image Text:

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.05. 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 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, you should compare P (msg = 1 00010 observed) to P (msg = 0[00010 observed). Assume that 0 and 1 are a priori equally likely, that is P (msg = 0) = P (msg = 1) = 0.5. (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 otherwise (we will assume n is odd to avoid ambiguities). Find the probability that this strategy results in a decoding error with n = 5 and p = 0.05. (c) Fill in the missing parts of the equation below for general (but odd) repetition rate n and bit-flip probability p: P (decoding error) = (something) Σ k=(something) (some expression which depends on n, p, and k) (d) With p = 0.05, how large must n be in order for the majority-rules decoder to achieve a probability of error that is less than 10-4? 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.05. 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 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, you should compare P (msg = 1 00010 observed) to P (msg = 0[00010 observed). Assume that 0 and 1 are a priori equally likely, that is P (msg = 0) = P (msg = 1) = 0.5. (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 otherwise (we will assume n is odd to avoid ambiguities). Find the probability that this strategy results in a decoding error with n = 5 and p = 0.05. (c) Fill in the missing parts of the equation below for general (but odd) repetition rate n and bit-flip probability p: P (decoding error) = (something) Σ k=(something) (some expression which depends on n, p, and k) (d) With p = 0.05, how large must n be in order for the majority-rules decoder to achieve a probability of error that is less than 10-4? 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.05. 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 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, you should compare P (msg = 1 00010 observed) to P (msg = 0[00010 observed). Assume that 0 and 1 are a priori equally likely, that is P (msg = 0) = P (msg = 1) = 0.5. (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 otherwise (we will assume n is odd to avoid ambiguities). Find the probability that this strategy results in a decoding error with n = 5 and p = 0.05. (c) Fill in the missing parts of the equation below for general (but odd) repetition rate n and bit-flip probability p: P (decoding error) = (something) Σ k=(something) (some expression which depends on n, p, and k) (d) With p = 0.05, how large must n be in order for the majority-rules decoder to achieve a probability of error that is less than 10-4?