Binary erasure channel

{{redirect|Erasure channel|another method|Packet 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$ receives a message that the bit was not received ("erased") .

Definition

A binary erasure channel with erasure probability $P_e$ is a channel with binary input, ternary output, and probability of erasure $P_e$ . That is, let $X$ be the transmitted random variable with alphabet $\{0,1\}$ . Let $Y$ be the received variable with alphabet $\{0,1,\text{e} \}$ , where $\text{e}$ is the erasure symbol. Then, the channel is characterized by the conditional probabilities:{{sfnp|MacKay|2003|p=148}}

: $\begin{align}
\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{align}$

Capacity

The channel capacity of a BEC is $1-P_e$ , attained with a uniform distribution for $X$ (i.e. half of the inputs should be 0 and half should be 1).{{sfnp|MacKay|2003|p=158}}

class="toccolours collapsible collapsed" width="80%" style="text-align:left"

!Proof{{sfnp|MacKay|2003|p=158}}

By symmetry of the input values, the optimal input distribution is

X \sim \mathrm{Bernoulli}\left(\frac{1}{2}\right)

. The channel capacity is:

: $\operatorname{I}(X;Y) = \operatorname{H}(X)-\operatorname{H}(X|Y)$

Observe that, for the binary entropy function $\operatorname{H}_\text{b}$ (which has value 1 for input $\frac{1}{2}$ ),

: $\operatorname{H}(X|Y)=\sum_y P(y)\operatorname{H}(X|y)=P_e \operatorname{H}_{\text{b}}\left(\frac{1}{2}\right) = P_e$

as $X$ is known from (and equal to) y unless $y=e$ , which has probability $P_e$ .

By definition $\operatorname{H}(X)=\operatorname{H}_{\text{b}}\left(\frac{1}{2}\right)=1$ , so

: $\operatorname{I}(X;Y) = 1-P_e$ .

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$ . However, by the noisy-channel coding theorem, the capacity of $1-P_e$ can be obtained even without such feedback.{{sfnp|Cover|Thomas|1991|p=189}}

Related channels

If bits are flipped rather than erased, the channel is a binary symmetric channel (BSC), which has capacity $1 - \operatorname H_\text{b}(P_e)$ (for the binary entropy function $\operatorname{H}_\text{b}$ ), which is less than the capacity of the BEC for $0 .{{sfnp|Cover|Thomas|1991|p=187}}{{sfnp|MacKay|2003|p=15}} If bits are erased but the receiver is not notified (i.e. does not receive the output e) then the channel is a deletion channel, and its capacity is an open problem.{{sfnp|Mitzenmacher|2009|p=2}}$

History

The BEC was introduced by Peter Elias of MIT in 1955 as a toy example.{{cn|date=July 2020}}

Notes

References

{{cite book |first1=Thomas M. |last1=Cover |first2=Joy A. |last2=Thomas |title=Elements of Information Theory |publisher=Wiley |location=Hoboken, New Jersey |isbn=978-0-471-24195-9 |year=1991}}
{{cite book |last=MacKay|first=David J.C. |author-link=David J. C. MacKay|url=http://www.inference.phy.cam.ac.uk/mackay/itila/book.html|title=Information Theory, Inference, and Learning Algorithms|publisher=Cambridge University Press|year=2003|isbn=0-521-64298-1}}
{{citation

| last = Mitzenmacher | first = Michael | authorlink = Michael Mitzenmacher

| doi = 10.1214/08-PS141

| journal = Probability Surveys

| mr = 2525669

| pages = 1–33

| title = A survey of results for deletion channels and related synchronization channels

| volume = 6

| year = 2009| doi-access = free

}}

Category:Coding theory