Binary erasure channel (original) (raw)

From Wikipedia, the free encyclopedia

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 p e {\displaystyle p_{e}}

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

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

Pr ⁡ [ Y = 0 | X = 0 ] = 1 − P e Pr ⁡ [ Y = 0 | X = 1 ] = 0 Pr ⁡ [ Y = 1 | X = 0 ] = 0 Pr ⁡ [ Y = 1 | X = 1 ] = 1 − P e Pr ⁡ [ Y = e | X = 0 ] = P e Pr ⁡ [ Y = e | X = 1 ] = P e {\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}}}

The channel capacity of a BEC is 1 − P e {\displaystyle 1-P_{e}} , attained with a uniform distribution for X {\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 X ∼ B e r n o u l l i ( 1 2 ) {\displaystyle X\sim \mathrm {Bernoulli} \left({\frac {1}{2}}\right)} . The channel capacity is: I ⁡ ( X ; Y ) = H ⁡ ( X ) − H ⁡ ( X | Y ) {\displaystyle \operatorname {I} (X;Y)=\operatorname {H} (X)-\operatorname {H} (X	Y)}  Observe that, for the binary entropy function H b {\displaystyle \operatorname {H} _{\text{b}}} (which has value 1 for input 1 2 {\displaystyle {\frac {1}{2}}} ), H ⁡ ( X

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 {\displaystyle 1-P_{e}} . However, by the noisy-channel coding theorem, the capacity of 1 − P e {\displaystyle 1-P_{e}} 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 1 − H b ⁡ ( P e ) {\displaystyle 1-\operatorname {H} _{\text{b}}(P_{e})} (for the binary entropy function H b {\displaystyle \operatorname {H} _{\text{b}}} ), which is less than the capacity of the BEC for 0 < P e < 1 / 2 {\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 e {\displaystyle e} ) 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.[_citation needed_]

• Erasure code
• Packet erasure channel

1. ^ MacKay (2003), p. 148.
2. ^ a b MacKay (2003), p. 158.
3. ^ Cover & Thomas (1991), p. 189.
4. ^ Cover & Thomas (1991), p. 187.
5. ^ MacKay (2003), p. 15.
6. ^ Mitzenmacher (2009), p. 2.

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