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 stud ...
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 inform ...
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 represented a ...
(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 p ...
with alphabet
. Let
be the received variable with alphabet
, where
is the erasure symbol. Then, the channel is characterized by the
conditional probabilities:
:
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 (dig ...
, 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 (BSC), which has capacity
(for the
binary entropy function ), which is less than the capacity of the BEC for