An error-correcting code is a technique for signaling and correcting errors when sending a…
An error-correcting code is a technique for signaling and correcting errors when sending a message over an unreliable communication channel. One simple example is a repetition code, in which the message is repeated a fixed number of times. If any bit differs between repetitions, it is known to be corrupted (and the true value is assumed to be the value that appears most frequently).
Suppose that for a given communication channel, the probability that any given bit is corrupted is 0.05, and the outcome for each bit is independent. As an error-correcting code, messages are repeated 4 times.
(a) Suppose a message of length 20 is sent (for a total of 80 bits after repetition). What is the probability that at least one bit is corrupted?
(b) What is the maximum-length message that can be sent such that the probability of at least one bit being corrupted is less than 0.5?
(c) The weakness of a repetition code is that if a given bit is corrupted in every repetition, there is no signal of the error. Consider again a message of length 20. What is the probability that there exists a bit that is corrupted in all 4 repetitions of the message (that is, for some value 0