Binary erasure channel


In coding theory and information theory, a binary erasure channel is a communications channel model. A transmitter sends a bit, and the receiver either receives the bit correctly, or with some probability receives a message that the bit was not received .

Definition

A binary erasure channel with erasure probability is a channel with binary input, ternary output, and probability of erasure. That is, let be the transmitted random variable with alphabet. Let be the received variable with alphabet, where is the erasure symbol. Then, the channel is characterized by the conditional probabilities:

Capacity

The channel capacity of a BEC is, attained with a uniform distribution for .
Observe that, for the binary entropy function ,
as is known from y unless, which has probability.
By definition, so
If the sender is notified when a bit is erased, they can repeatedly transmit each bit until it is correctly received, attaining the capacity. However, by the noisy-channel coding theorem, the capacity of can be obtained even without such feedback.

Related channels

If bits are flipped rather than erased, the channel is a binary symmetric channel, which has capacity , which is less than the capacity of the BEC for. If bits are erased but the receiver is not notified then the channel is a deletion channel, and its capacity is an open problem.

History

The BEC was introduced by Peter Elias of MIT in 1955 as a toy example.