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

Definition

A binary erasure channel with erasure probability P_e is a channel with binary input, ternary output, and probability of erasure P_e. That is, let X be the transmitted random variable with alphabet {0,1}. Let Y be the received variable with alphabet, where \text{e} is the erasure symbol. Then, the channel is characterized by the conditional probabilities:

Capacity

The channel capacity of a BEC is 1-P_e, attained with a uniform distribution for X (i.e. half of the inputs should be 0 and half should be 1). !Proof Observe that, for the binary entropy function (which has value 1 for input \frac{1}{2}), as X is known from (and equal to) y unless y=e, which has probability P_e. 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 1-P_e. However, by the noisy-channel coding theorem, the capacity of 1-P_e can be obtained even without such feedback.

Related channels

If bits are flipped rather than erased, the channel is a binary symmetric channel (BSC), which has capacity (for the binary entropy function ), which is less than the capacity of the BEC for 0<P_e<1/2. If bits are erased but the receiver is not notified (i.e. does not receive the output e) 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.