- Source: Binary erasure channel
In coding theory and information theory, a binary erasure channel (BEC) is a communications channel model. A transmitter sends a bit (a zero or a one), and the receiver either receives the bit correctly, or with some probability
P
e
{\displaystyle P_{e}}
receives a message that the bit was not received ("erased") .
Definition
A binary erasure channel with erasure probability
P
e
{\displaystyle P_{e}}
is a channel with binary input, ternary output, and probability of erasure
P
e
{\displaystyle P_{e}}
. That is, let
X
{\displaystyle X}
be the transmitted random variable with alphabet
{
0
,
1
}
{\displaystyle \{0,1\}}
. Let
Y
{\displaystyle Y}
be the received variable with alphabet
{
0
,
1
,
e
}
{\displaystyle \{0,1,{\text{e}}\}}
, where
e
{\displaystyle {\text{e}}}
is the erasure symbol. Then, the channel is characterized by the conditional probabilities:
Pr
[
Y
=
0
|
X
=
0
]
=
1
−
P
e
Pr
[
Y
=
0
|
X
=
1
]
=
0
Pr
[
Y
=
1
|
X
=
0
]
=
0
Pr
[
Y
=
1
|
X
=
1
]
=
1
−
P
e
Pr
[
Y
=
e
|
X
=
0
]
=
P
e
Pr
[
Y
=
e
|
X
=
1
]
=
P
e
{\displaystyle {\begin{aligned}\operatorname {Pr} [Y=0|X=0]&=1-P_{e}\\\operatorname {Pr} [Y=0|X=1]&=0\\\operatorname {Pr} [Y=1|X=0]&=0\\\operatorname {Pr} [Y=1|X=1]&=1-P_{e}\\\operatorname {Pr} [Y=e|X=0]&=P_{e}\\\operatorname {Pr} [Y=e|X=1]&=P_{e}\end{aligned}}}
Capacity
The channel capacity of a BEC is
1
−
P
e
{\displaystyle 1-P_{e}}
, attained with a uniform distribution for
X
{\displaystyle X}
(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
1
−
P
e
{\displaystyle 1-P_{e}}
. However, by the noisy-channel coding theorem, the capacity of
1
−
P
e
{\displaystyle 1-P_{e}}
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
1
−
H
b
(
P
e
)
{\displaystyle 1-\operatorname {H} _{\text{b}}(P_{e})}
(for the binary entropy function
H
b
{\displaystyle \operatorname {H} _{\text{b}}}
), which is less than the capacity of the BEC for
0
<
P
e
<
1
/
2
{\displaystyle 0
. If bits are erased but the receiver is not notified (i.e. does not receive the output
e
{\displaystyle e}
) then the channel is a deletion channel, and its capacity is an open problem.
History
The BEC was introduced by Peter Elias of MIT in 1955 as a toy example.
See also
Erasure code
Packet erasure channel
Notes
References
Cover, Thomas M.; Thomas, Joy A. (1991). Elements of Information Theory. Hoboken, New Jersey: Wiley. ISBN 978-0-471-24195-9.
MacKay, David J.C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press. ISBN 0-521-64298-1.
Mitzenmacher, Michael (2009), "A survey of results for deletion channels and related synchronization channels", Probability Surveys, 6: 1–33, doi:10.1214/08-PS141, MR 2525669
Kata Kunci Pencarian:
- Binary erasure channel
- Erasure
- Packet erasure channel
- Communication channel
- Binary symmetric channel
- Peter Elias
- Erasure code
- Low-density parity-check code
- Channel capacity
- Deletion channel
