en.wikipedia.org

Binary erasure channel - Wikipedia

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}} — 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}$

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

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,{\text{e}}\}$ , where ${\text{e}}$ is the erasure symbol. Then, the channel is characterized by the conditional probabilities:^[1]

${\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}$ , attained with a uniform distribution for $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\sim \mathrm {Bernoulli} \left({\frac {1}{2}}\right)$ . The channel capacity is: $\operatorname {I} (X;Y)=\operatorname {H} (X)-\operatorname {H} (X\|Y)$ Observe that, for the binary entropy function $\operatorname {H} _{\text{b}}$ (which has value 1 for input ${\frac {1}{2}}$ ), $\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}$ as $X$ is known from (and equal to) y unless $y=e$ , which has probability $P_{e}$ . By definition $\operatorname {H} (X)=\operatorname {H} _{\text{b}}\left({\frac {1}{2}}\right)=1$ , so $\operatorname {I} (X;Y)=1-P_{e}$ .

Proof^[2]

By symmetry of the input values, the optimal input distribution is $X\sim \mathrm {Bernoulli} \left({\frac {1}{2}}\right)$ . The channel capacity is:

$\operatorname {I} (X;Y)=\operatorname {H} (X)-\operatorname {H} (X|Y)$

Observe that, for the binary entropy function $\operatorname {H} _{\text{b}}$ (which has value 1 for input ${\frac {1}{2}}$ ),

$\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}$

as $X$ is known from (and equal to) y unless $y=e$ , which has probability $P_{e}$ .

By definition $\operatorname {H} (X)=\operatorname {H} _{\text{b}}\left({\frac {1}{2}}\right)=1$ , so

$\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 $1-P_{e}$ . However, by the noisy-channel coding theorem, the capacity of $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-\operatorname {H} _{\text{b}}(P_{e})$ (for the binary entropy function $\operatorname {H} _{\text{b}}$ ), which is less than the capacity of the BEC for $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$ ) 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]}

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