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 error is p_e

A binary erasure channel (or BEC) is a common communications channel model used in coding theory and information theory. In this model, a transmitter wishes to send a bit (a zero or a one), and the receiver either receives the bit or it receives a message that the bit was not received ("erased"). This channel is used frequently in information theory because it is one of the simplest channels to analyze. A Communications channel (or channel for short), models the medium through which information is transmitted from a sender (or transmitter) to a receiver. ... Coding theory is a branch of mathematics and computer science dealing with the error-prone process of transmitting data across noisy channels, via clever means, so that a large number of errors that occur can be corrected. ... A bundle of optical fiber. ... This article is about the unit of information. ...

Description

The BEC is a binary channel; that is, it can transmit only one of two symbols (usually called 0 and 1). (A non-binary channel would be capable of transmitting more than 2 symbols, possibly even an infinite number of choices) The channel is not perfect however, and sometimes the bit gets "erased"; that is, the bit gets scrambled and the receiver has no idea what the bit was. Look up binary in Wiktionary, the free dictionary. ...

Note that the BEC is, in a sense, error-free. Unlike the binary symmetric channel, when the receiver gets a bit, it is 100% certain that the bit is correct. The only confusion arises when the bit is erased. In coding theory, a binary symmetric channel (or BSC) is an idealized model of a communications channel that sends bits. ...

This channel is often used by theorists because it is one of the simplest noisy channels to analyze. Many problems in communication theory can be reduced to a BEC. In science, and especially in physics and telecommunication, noise is fluctuations in and the addition of external factors to the stream of target information (signal) being received at a detector. ... There is much discussion in the academic world of communication as to what actually constitutes communication. ... In computability theory and computational complexity theory, a reduction is a transformation of one problem into another problem. ...

Definition

A binary erasure channel with erasure probability p is a channel with binary input, ternary output, and probability of erasure p. That is, let X be the transmitted random variable with alphabet {0, 1}. Let Y be the received variable with alphabet {0, 1, e}, where e is the erasure symbol. Then, the channel is characterized by the conditional probabilities A random variable is a mathematical function that maps outcomes of random experiments to numbers. ... This article defines some terms which characterize probability distributions of two or more variables. ...

Pr( Y = 0 | X = 0) = 1-p

Pr( Y = e | X = 0) = p

Pr( Y = 1 | X = 0) = 0

Pr( Y = 0 | X = 1) = 0

Pr( Y = e | X = 1) = p

Pr( Y = 1 | X = 1) = 1-p

Capacity of the BEC

The capacity of a BEC is 1 - p. Channel capacity, is the amount of discrete information that can be reliably transmitted over a channel. ...

The converse can be explained intuitively. Suppose there is an omniscient "genie" that tells the source whenever its bit gets erased. There is nothing the source can do to avoid erasure, but it can fix them when they happen. For example, the source could repeatedly transmit a bit until it gets through. There is no need for X to code, as Y will simply ignore erasures, knowing that the next successfully received bit is the one that X intended to send. Therefore, having a genie allows us to achieve a rate of 1 - p on average. We cannot hope to do any better than this.

References

• David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
• Thomas M. Cover, Joy A. Thomas. Elements of information theory, 1st Edition. New York: Wiley-Interscience, 1991. ISBN 0-471-06259-6.

External links

• Vincent Kerbaol: Binary Erasure Channel

See also

• Binary symmetric channel