Paper 3, Section I, G

Coding and Cryptography
Part II, 2019

What does it mean to transmit reliably at rate RR through a binary symmetric channel (BSC)(\mathrm{BSC}) with error probability pp ?

Assuming Shannon's second coding theorem (also known as Shannon's noisy coding theorem), compute the supremum of all possible reliable transmission rates of a BSC. Describe qualitatively the behaviour of the capacity as pp varies. Your answer should address the following cases,

(i) pp is small,

(ii) p=1/2p=1 / 2,

(iii) p>1/2p>1 / 2.