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 receives a message that the bit was not received ("erased") .
![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/2/23/Binaryerasurechannel.png/220px-Binaryerasurechannel.png)
Definition
editA binary erasure channel with erasure probability is a channel with binary input, ternary output, and probability of erasure . That is, let be the transmitted random variable with alphabet . Let be the received variable with alphabet , where is the erasure symbol. Then, the channel is characterized by the conditional probabilities:[1]
Capacity
editThe channel capacity of a BEC is , attained with a uniform distribution for (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 . The channel capacity is: Observe that, for the binary entropy function (which has value 1 for input ),
as is known from (and equal to) y unless , which has probability .
By definition , so
- .
If the sender is notified when a bit is erased, they can repeatedly transmit each bit until it is correctly received, attaining the capacity . However, by the noisy-channel coding theorem, the capacity of can be obtained even without such feedback.[3]
Related channels
editIf bits are flipped rather than erased, the channel is a binary symmetric channel (BSC), which has capacity (for the binary entropy function ), which is less than the capacity of the BEC for .[4][5] If bits are erased but the receiver is not notified (i.e. does not receive the output ) then the channel is a deletion channel, and its capacity is an open problem.[6]
History
editThe BEC was introduced by Peter Elias of MIT in 1955 as a toy example.[citation needed]
See also
editNotes
edit- ^ MacKay (2003), p. 148.
- ^ a b MacKay (2003), p. 158.
- ^ Cover & Thomas (1991), p. 189.
- ^ Cover & Thomas (1991), p. 187.
- ^ MacKay (2003), p. 15.
- ^ Mitzenmacher (2009), p. 2.
References
edit- 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