{{redirect|Erasure channel|another method|Packet erasure channel}} thumb|right|The channel model for the binary erasure channel showing a mapping from channel input X to channel output Y (with known erasure symbol ''?''). The probability of erasure is <math>p_e</math>

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 <math>P_e</math> receives a message that the bit was not received ("erased") .

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

:<math>\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}</math>

== Capacity == The channel capacity of a BEC is <math>1-P_e</math>, attained with a uniform distribution for <math>X</math> (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 <math>X \sim \mathrm{Bernoulli}\left(\frac{1}{2}\right)</math>. The channel capacity is: :<math>\operatorname{I}(X;Y) = \operatorname{H}(X)-\operatorname{H}(X|Y)</math>

Observe that, for the binary entropy function <math>\operatorname{H}_\text{b}</math> (which has value 1 for input <math>\frac{1}{2}</math>), :<math>\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</math> as <math>X</math> is known from (and equal to) y unless <math>y=e</math>, which has probability <math>P_e</math>.

By definition <math>\operatorname{H}(X)=\operatorname{H}_{\text{b}}\left(\frac{1}{2}\right)=1</math>, so :<math>\operatorname{I}(X;Y) = 1-P_e</math>. |}

If the sender is notified when a bit is erased, they can repeatedly transmit each bit until it is correctly received, attaining the capacity <math>1-P_e</math>. However, by the noisy-channel coding theorem, the capacity of <math>1-P_e</math> 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 <math>1 - \operatorname H_\text{b}(P_e)</math> (for the binary entropy function <math>\operatorname{H}_\text{b}</math>), which is less than the capacity of the BEC for <math>0<P_e<1/2</math>.{{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 <math>e</math>) 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}}

== See also == * Erasure code * Packet erasure channel

== Notes == {{reflist}}

== 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