In
coding theory
Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are studied ...
and
information theory
Information theory is the scientific study of the quantification, storage, and communication of information. The field was originally established by the works of Harry Nyquist and Ralph Hartley, in the 1920s, and Claude Shannon in the 1940s. ...
, a binary erasure channel (BEC) is a
communications channel
A communication channel refers either to a physical transmission medium such as a wire, or to a logical connection over a multiplexed medium such as a radio channel in telecommunications and computer networking. A channel is used for informat ...
model. A transmitter sends a
bit
The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represente ...
(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") .
Definition
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
A random variable (also called random quantity, aleatory variable, or stochastic variable) is a mathematical formalization of a quantity or object which depends on random events. It is a mapping or a function from possible outcomes (e.g., the po ...
with alphabet
. Let
be the received variable with alphabet
, where
is the erasure symbol. Then, the channel is characterized by the
conditional probabilities
In probability theory, conditional probability is a measure of the probability of an event occurring, given that another event (by assumption, presumption, assertion or evidence) has already occurred. This particular method relies on event B occur ...
:
:
Capacity
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).
:
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
In information theory, the noisy-channel coding theorem (sometimes Shannon's theorem or Shannon's limit), establishes that for any given degree of noise contamination of a communication channel, it is possible to communicate discrete data (di ...
, the capacity of
can be obtained even without such feedback.
Related channels
If bits are flipped rather than erased, the channel is a
binary symmetric channel
A binary symmetric channel (or BSCp) 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 will receive a bit. The bit will be "f ...
(BSC), which has capacity
(for the
binary entropy function
In information theory, the binary entropy function, denoted \operatorname H(p) or \operatorname H_\text(p), is defined as the entropy of a Bernoulli process with probability p of one of two values. It is a special case of \Eta(X), the entropy fun ...
), which is less than the capacity of the BEC for