Binary erasure channel explained

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 \{ 0 , 1 , e \} , where e is the erasure symbol. Then, the channel is characterized by the conditional probabilities:\begin{align} \operatorname {Pr} [ Y = 0 | X = 0 ] & = 1 - P _{e} \\ \operatorname {Pr} [ Y = 0 | X = 1 ] & = 0 \\ \operatorname {Pr} [ Y = 1 | X = 0 ] & = 0 \\ \operatorname {Pr} [ Y = 1 | X = 1 ] & = 1 - P _{e} \\ \operatorname {Pr} [ Y = e | X = 0 ] & = P _{e} \\ \operatorname {Pr} [ Y = e | X = 1 ] & = P _{e \end{align}}

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

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

1 - \operatorname H _{b(P} _{e)} (for the binary entropy function \operatorname{H} _{b} ), 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.

See also

• Erasure code
• Packet erasure channel

References

• Book: Thomas M. . Cover . Joy A. . Thomas . Elements of Information Theory . Wiley . Hoboken, New Jersey . 978-0-471-24195-9 . 1991.
• Book: MacKay, David J.C. . David J. C. MacKay. Information Theory, Inference, and Learning Algorithms. Cambridge University Press. 2003. 0-521-64298-1.