Communication Channels

Classical information theory is based on the concept of a communication channel.

Information theory is generally considered to have been founded in 1948 by Claude Shannon in his seminal work, "A Mathematical Theory of Communication." The central paradigm of classical information theory is the engineering problem of the transmission of information over a noisy channel.

In this problem, we will specifically consider one of the simplest possible noisy channels, namely the binary symmetric channel (BSC). A BSC transmits a sequence of bits, but each transmitted bit has a probability $p$ of being flipped. This is called the crossover probability, as shown in the figure. We assume different bits behave independently, so a communication of $l$ bits has probability (1 - p)^l of being transmitted correctly. One may always assume p < 1/2, since a channel with p = 1/2 is useless, and a channel with p > 1/2 can be transformed into a new channel with crossover probability 1 - p by flipping all output bits.

Of course, it is still possible to communicate over a noisy channel (in fact, you are doing it all the time)! To do this, you have to add extra bits so that the receiver can detect or even correct errors. Examples of such implementations are parity bits, Cyclic Redundancy Checks (CRC), and Golay codes. However, this is not relevant to this problem, so it will not be discussed here.

You must investigate the behaviour of a binary symmetric channel.