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 receives a message that the bit was not received ("erased") . A 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: The 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). {| class="toccolours collapsible collapsed" width="80%" style="text-align:left"
| !Proof |
|---|
| 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. |
| If 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 . 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. |
| The BEC was introduced by Peter Elias of MIT in 1955 as a toy example. |