Binary erasure channel

The channel model for the binary erasure channel showing a mapping from channel input X to channel output Y (with known erasure symbol ?). The probability of erasure is [math]\displaystyle{ p_e }[/math]

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 [math]\displaystyle{ P_e }[/math] receives a message that the bit was not received ("erased") .

Definition

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

[math]\displaystyle{ \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} }[/math]

Capacity

The channel capacity of a BEC is [math]\displaystyle{ 1-P_e }[/math], attained with a uniform distribution for [math]\displaystyle{ X }[/math] (i.e. half of the inputs should be 0 and half should be 1).

Proof

By symmetry of the input values, the optimal input distribution is [math]\displaystyle{ X \sim \mathrm{Bernoulli}\left(\frac{1}{2}\right) }[/math]. The channel capacity is: [math]\displaystyle{ \operatorname{I}(X;Y) = \operatorname{H}(X)-\operatorname{H}(X|Y) }[/math] Observe that, for the binary entropy function [math]\displaystyle{ \operatorname{H}_\text{b} }[/math] (which has value 1 for input [math]\displaystyle{ \frac{1}{2} }[/math]), [math]\displaystyle{ \operatorname{H}(X|Y)=\sum_y P(y)\operatorname{H}(X|y)=P_e \operatorname{H}_{\text{b}}\left(\frac{1}{2}\right) = P_e }[/math] as [math]\displaystyle{ X }[/math] is known from (and equal to) y unless [math]\displaystyle{ y=e }[/math], which has probability [math]\displaystyle{ P_e }[/math]. By definition [math]\displaystyle{ \operatorname{H}(X)=\operatorname{H}_{\text{b}}\left(\frac{1}{2}\right)=1 }[/math], so [math]\displaystyle{ \operatorname{I}(X;Y) = 1-P_e }[/math].

If the sender is notified when a bit is erased, they can repeatedly transmit each bit until it is correctly received, attaining the capacity [math]\displaystyle{ 1-P_e }[/math]. However, by the noisy-channel coding theorem, the capacity of [math]\displaystyle{ 1-P_e }[/math] 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 [math]\displaystyle{ 1 - \operatorname H_\text{b}(P_e) }[/math] (for the binary entropy function [math]\displaystyle{ \operatorname{H}_\text{b} }[/math]), which is less than the capacity of the BEC for [math]\displaystyle{ 0\lt P_e\lt 1/2 }[/math]. If bits are erased but the receiver is not notified (i.e. does not receive the output [math]\displaystyle{ e }[/math]) 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

• Cover, Thomas M.; Thomas, Joy A. (1991). Elements of Information Theory. Hoboken, New Jersey: Wiley. ISBN 978-0-471-24195-9. 
• MacKay, David J.C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press. ISBN 0-521-64298-1. http://www.inference.phy.cam.ac.uk/mackay/itila/book.html. 
• "A survey of results for deletion channels and related synchronization channels", Probability Surveys 6: 1–33, 2009, doi:10.1214/08-PS141