Problem 4 [20 marks]

A sequence of binary bits is transmitted in a certain communication system. Any given bit is decoded erroneously with probability p and decoded correctly with probability 1 ? p. Errors occur independently from bit to bit.

(a) Out of a sequence of n bits transmitted, what is the probability that j bits (j = 1, ..., n) are erroneously decoded? [5 marks]

2

(b) A certain error-correcting code is applied to the communication system described in part (a). The correcting code can correct a single error in any bit, but it cannot correct a run of two or more errors. What is the probability that the code can correct the errors that occur when n-digits are transmitted and j bits (j = 1, ..., n) are incorrectly decoded? [5 marks]

(c) Write a simulation in R to approximate the probability that a message decoded using the method described in part (b) is correctly decoded for n = 8, 16, 24, 32 and p = 0.01, 0.05, 0.10, 0.15. That is, you must report 4 4 = 16 different probabilities (for every possible combination of n and p). [5 marks]

(d) Suppose now that the error-correcting code can correct up to 2 consecutive bit errors, but it cannot correct a run of three or more errors. Write a simulation in R to approximate the prob- ability that a message is correctly decoded for n = 8, 16, 24, 32 and p = 0.01, 0.05, 0.10, 0.15. That is, you must report 4 4 = 16 different probabilities (for every possible combination of n and p). [5 marks]

Problem 4 [20 marks] A sequence of binary bits is transmitted in a certain communication system. Any given bit is decoded erroneously with probability p and decoded correctly with probability 1 3:). Errors occur independently from bit to bit. (a) Out of a sequence of n bits transmitted, what is the probability that 3' bits (3' = 1, ..., n) are erroneously decoded? [5 marks] (b) A certain error-correcting code is applied to the communication system described in part (a). The correcting code can correct a single error in any bit, but it cannot correct a run of two or more errors. What is the probability that the code can correct the errors that occur when ndigits are transmitted and 3' bits (j = 1, ..., n) are incorrectly decoded? [5 marks] (c) Write a simulation in R to approximate the probability that a message decoded using the method described in part (b) is correctly decoded for n = 8, 16, 24, 32 and p = 0.01, 0.05, 0.10, 0.15. That is, you must report 4 X 4 = 16 different probabilities (for every possible combination of n and p). [5 marks] (d) Suppose now that the error-correcting code can correct up to 2 consecutive bit errors, but it cannot correct a run of three or more errors. Write a simulation in R to approximate the prob- ability that a message is correctly decoded for n = 8, 16, 24, 32 and p = 001,005, 0.10, 0.15. That is, you must report 4 x 4 = 16 different probabilities (for every possible combination of n and p). [5 marks]