Noisy Channels

Meet the BSC and BEC: the two toy channels that make entropy and decoding feel concrete.

The idea

A channel is a probabilistic rule carrying an input symbol $X$ to an output symbol $Y$, specified by the conditional probabilities $\mathbb{P}(Y = y \mid X = x)$ — one distribution over outputs for each possible input. Those probabilities describe the noise completely. Two one-bit channels are the standard examples, and they model different kinds of noise.

The binary symmetric channel, BSC($p$), transmits a bit, flipping it with probability $p$ and delivering it unchanged with probability $1 - p$. The output is always a bit, and the receiver is not told which bits were flipped.

The binary erasure channel, BEC($\varepsilon$), delivers the bit exactly with probability $1 - \varepsilon$; with probability $\varepsilon$ it outputs a third symbol, an erasure written $?$, marking that bit as lost. Every non-erased output is correct.

The two channels leave the receiver in different positions. After an erasure the receiver knows exactly which positions are missing and can direct its effort there. After a flip it does not know which bits are wrong.

Ways to work on it

• Walkthrough. Learn the flip channel and the erasure channel, and connect them to uncertainty and error.
• Practice. Translate a one-parameter channel model directly into a decoding error rate.
• Hardest. Compute conditional entropy on an erasure channel and read off what it says about decoding.

Not sure where to start? Take the ten-question placement test.