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 ${\displaystyle P_{e}}$ receives a message that the bit was not received ("erased") .

"Erasure channel" redirects here. For another method, see Packet 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 ${\displaystyle p_{e}}$

Definition

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

${\displaystyle {\begin{aligned}\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{aligned}}}$

Capacity

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

Proof[2]

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

If the sender is notified when a bit is erased, they can repeatedly transmit each bit until it is correctly received, attaining the capacity ${\displaystyle 1-P_{e}}$. However, by the noisy-channel coding theorem, the capacity of ${\displaystyle 1-P_{e}}$ can be obtained even without such feedback.[3]

Related channels

If bits are flipped rather than erased, the channel is a binary symmetric channel (BSC), which has capacity ${\displaystyle 1-\operatorname {H} _{\text{b}}(P_{e})}$ (for the binary entropy function ${\displaystyle \operatorname {H} _{\text{b}}}$), which is less than the capacity of the BEC for ${\displaystyle 0<P_{e}<1/2}$.[4][5] If bits are erased but the receiver is not notified (i.e. does not receive the output ${\displaystyle e}$) then the channel is a deletion channel, and its capacity is an open problem.[6]

History

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

See also

• Erasure code
• Packet erasure channel

Notes

1. MacKay (2003), p. 148.
2. MacKay (2003), p. 158.
3. Cover & Thomas (1991), p. 189. sfnp error: no target: CITEREFCoverThomas1991 (help)
4. Cover & Thomas (1991), p. 187. sfnp error: no target: CITEREFCoverThomas1991 (help)
5. MacKay (2003), p. 15.
6. Mitzenmacher (2009), p. 2.

References

• Thomas M. Cover; Joy A. Thomas (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.
• Mitzenmacher, Michael (2009), "A survey of results for deletion channels and related synchronization channels", Probability Surveys, 6: 1–33, doi:10.1214/08-PS141, MR 2525669