Binary erasure channel

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

receives a message that the bit was not received ("erased") .

A binary erasure channel with erasure probability

is a channel with binary input, ternary output, and probability of erasure

be the transmitted random variable with alphabet

be the received variable with alphabet

is the erasure symbol.

Then, the channel is characterized by the conditional probabilities:[1] The channel capacity of a BEC is

, attained with a uniform distribution for

[2] Observe that, for the binary entropy function

, 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.

[3] If bits are flipped rather than erased, the channel is a binary symmetric channel (BSC), which has capacity

(for the binary entropy function

[4][5] If bits are erased but the receiver is not notified (i.e. does not receive the output

) then the channel is a deletion channel, and its capacity is an open problem.

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