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 computer data storage, data sto ...
and
information theory
Information theory is the mathematical study of the quantification (science), quantification, Data storage, storage, and telecommunications, communication of information. The field was established and formalized by 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 communication. 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 as ...
(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 Mathematics, mathematical formalization of a quantity or object which depends on randomness, random events. The term 'random variable' in its mathema ...
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
Channel capacity, in electrical engineering, computer science, and information theory, is the theoretical maximum rate at which information can be reliably transmitted over a communication channel.
Following the terms of the noisy-channel coding ...
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 (in theory) to communicate discrete ...
, 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 ...
(BSC), which has capacity
(for the
binary entropy function
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two values (0 and 1) for each digit
* Binary function, a function that takes two arguments
* Binary operation, a mathematical op ...
), which is less than the capacity of the BEC for