Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 37 ยท Channel Capacity

The Binary Symmetric and Erasure Channels

Simulate the binary symmetric channel and the binary erasure channel in Python, derive their capacities 1 - H(p) and 1 - e, and compare noisy and erased bits.

Two channels appear in almost every information theory course because they are simple enough to solve exactly, yet they capture the two most common kinds of damage: flipped bits and lost bits. The binary symmetric channel (BSC) flips each bit with some probability. The binary erasure channel (BEC) does not flip anything, but sometimes tells you "I could not read this bit".

In this lesson you simulate both channels with NumPy, measure what they do, and derive their capacities. You will use the entropy function H(p) for a coin, called the binary entropy function, and the mutual information from the previous lesson.

The binary symmetric channel

A BSC with crossover probability p sends 0 and 1 and each bit is flipped independently with probability p:

flowchart LR
  A0["0"] -->|"1-p"| B0["0"]
  A0 -->|"p"| B1["1"]
  A1["1"] -->|"p"| B0
  A1 -->|"1-p"| B1

Each input bit is received correctly with probability 1-p and flipped with probability p.

The channel matrix is [[1-p, p], [p, 1-p]]. When p = 0 the channel is perfect. When p = 0.5 the output is pure noise. A channel with p > 0.5 is as good as one with 1 - p: you just flip every output bit, so only p <= 0.5 is interesting.

Because the noise is the same for both inputs, the best input distribution is uniform, and then H(Y) = 1 bit while H(Y|X) = H(p). So:

TEXT
C_BSC = 1 - H(p)    bits per channel use

The channel "wastes" H(p) bits per use on noise.

Python Simulating the BSC

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

At p = 0.11 the capacity is about half a bit per use, and at p = 0.5 it is zero. Notice how fast capacity falls: a channel that flips only 11% of bits has already lost half its capacity.

The binary erasure channel

On the BEC each bit is either received correctly or replaced by an erasure symbol ? with probability e. The receiver always knows which bits were lost. There are three output symbols: 0, 1 and ?.

A fraction 1 - e of the bits get through perfectly. It is tempting to guess that capacity is exactly 1 - e, and it is:

TEXT
C_BEC = 1 - e

Compare with the BSC at the same damage rate. A BEC with e = 0.11 has capacity 0.89, much better than a BSC with p = 0.11, which has capacity 0.5. The reason is that the BEC tells the receiver where the damage is. A flipped bit is damage you cannot see.

Python BEC versus BSC at the same error rate

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The line about wrong bits prints 0: erasures never cause wrong bits, they only cause missing bits.

Deriving the capacities in four lines

For the BSC, mutual information is I = H(Y) - H(Y|X). Given X, Y is a coin with probability p, so H(Y|X) = H(p) no matter what the input is. That means I = H(Y) - H(p), and H(Y) is at most 1 bit, reached when Y is uniform, which happens when X is uniform. Capacity is 1 - H(p).

For the BEC, write I = H(X) - H(X|Y). When the output is not an erasure, X is known: no uncertainty. When it is an erasure, which happens with probability e, nothing is learned and H(X|Y=?) = H(X). So H(X|Y) = e H(X) and I = (1 - e) H(X), at most 1 - e.

Python Check the formulas numerically

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Scanning the input probability confirms both formulas, and shows that the maximum occurs at the uniform input q = 0.5.

Why these two channels matter

  • BSC models hard-decision radio receivers: the demodulator picks 0 or 1 and that decision is sometimes wrong. The error-correcting codes in chapter 6 are mostly analysed on the BSC first.
  • BEC models packet networks: a packet either arrives or is lost, and the header tells you which. Codes for the erasure channel, such as the Reed-Solomon codes used in storage, are a major practical success.
  • Many real channels are in between: a soft receiver knows how sure it is, so it is partly a BEC.

When designing a system, always ask whether errors are detected. Turning flips into erasures, for example with a checksum, makes the channel much more forgiving.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the capacity of a binary symmetric channel with crossover probability p?

    Capacity is 1 - H(p), where H is the binary entropy function. The channel loses H(p) bits per use to noise.
  2. 2. What is the capacity of a binary erasure channel with erasure probability e?

    A fraction 1 - e of the bits arrives correctly and the receiver knows which ones, so capacity is 1 - e.
  3. 3. Why is a BEC with e = 0.1 better than a BSC with p = 0.1?

    Knowing the location of damage is valuable. A BSC hides its errors, so it costs H(p) bits per use, which is more than p.
  4. 4. Which input distribution maximizes mutual information for a BSC?

    The conditional entropy H(Y|X) is H(p) for either input, so the best choice maximizes H(Y), which is the uniform input.

Summary

  • The BSC flips each bit with probability p; its capacity is 1 - H(p).
  • The BEC erases each bit with probability e; its capacity is 1 - e.
  • Both are maximized by a uniform input distribution.
  • Known damage (erasure) is cheaper than hidden damage (flips).
  • Capacity falls quickly: a 11% flip rate already halves it.

Next: Channel Capacity and Shannon's Theorem