Binary erasure channel

From HandWiki
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:[1]

[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).[2]

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.[3]

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].[4][5] 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.[6]

History

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

See also

Notes

References