A binary erasure channel (or BEC) is a common communications channel model used in coding theory

Coding theory

Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...

 and information theory

Information theory

Information theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental limits on signal processing operations such as compressing data and on reliably storing and...

. In this model, a transmitter sends a bit

Bit

A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...

 (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. The BEC was introduced by Peter Elias

Peter Elias

Peter Elias was a pioneer in the field of information theory. Born in New Brunswick, New Jersey, he was a member of the Massachusetts Institute of Technology faculty from 1953 to 1991....

 of MIT in 1954 as a toy example.

Closely related to the binary erasure channel is the packet erasure channel

Packet erasure channel

The packet erasure channel is a communication channel model where sequential packets are either received or lost . This channel model is closely related to the binary erasure channel....

 which shares many similar theoretical results with the binary erasure channel.

Description

The BEC is a binary

Binary numeral system

The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...

 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 two symbols, possibly even an infinite number of choices.) The channel is not perfect and sometimes the bit gets "erased"; that is, the bit gets scrambled so the receiver has no idea what the bit was.

The BEC is, in a sense, error-free. Unlike the binary symmetric channel

Binary symmetric channel

A binary symmetric channel is a common communications channel model used in coding theory and information theory. In this model, a transmitter wishes to send a bit , and the receiver receives a bit. It is assumed that the bit is usually transmitted correctly, but that it will be "flipped" with a...

, when the receiver gets a bit, it is 100% certain that the bit is correct. The only confusion arises when the bit is erased.

This channel is often used by theorists because it is one of the simplest noisy channels to analyze. Many problems in communication theory

Communication theory

Communication theory is a field of information and mathematics that studies the technical process of information and the human process of human communication.- History :- Origins :...

 can be reduced

Reduction (complexity)

In computability theory and computational complexity theory, a reduction is a transformation of one problem into another problem. Depending on the transformation used this can be used to define complexity classes on a set of problems....

 to a BEC.

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

Random variable

In probability and statistics, a random variable or stochastic variable is, roughly speaking, a variable whose value results from a measurement on some type of random process. Formally, it is a function from a probability space, typically to the real numbers, which is measurable functionmeasurable...

 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

Conditional probability

In probability theory, the "conditional probability of A given B" is the probability of A if B is known to occur. It is commonly notated P, and sometimes P_B. P can be visualised as the probability of event A when the sample space is restricted to event B...

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

Channel capacity

In electrical engineering, computer science and information theory, channel capacity is the tightest upper bound on the amount of information that can be reliably transmitted over a communications channel...

of a BEC is 1 - p.

Intuitively 1 - p can be seen to be an upper bound on the channel capacity. Suppose there is an omniscient "genie" that tells the source whenever a transmitted 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. This additional information is not available normally and hence 1 - p is an upper bound.