Binary erasure channel

Binary erasure channel

A binary erasure channel (or BEC) is a common communications channel model used in coding theory and information theory. In this model, a transmitter sends a bit (a zero or a one), and the receiver either receives the bit or it receives a message that the bit was not received ("erased"). This channel is used frequently in information theory because it is one of the simplest channels to analyze.

Description

The BEC is a "binary channel"; that is, it can transmit only one of two symbols (usually called 0 and 1). (A non-binary channel would be capable of transmitting more than two symbols, possibly even an infinite number of choices). The channel is not perfect and sometimes the bit gets "erased"; that is, the bit gets scrambled so the receiver has no idea what the bit was.

The BEC is, in a sense, error-free. Unlike the binary symmetric channel, when the receiver gets a bit, it is 100% certain that the bit is correct. The only confusion arises when the bit is erased.

This channel is often used by theorists because it is one of the simplest noisy channels to analyze. Many problems in communication theory can be reduced to a BEC.

Definition

A binary erasure channel with erasure probability "p" is a channel with binary input, ternary output, and probability of erasure "p". That is, let "X" be the transmitted random variable with alphabet {0, 1}. Let "Y" be the received variable with alphabet {0, 1, "e"}, where "e" is the erasure symbol. Then, the channel is characterized by the conditional probabilities: Pr( "Y" = 0 | "X" = 0) = 1-"p": Pr( "Y" = "e" | "X" = 0) = "p": Pr( "Y" = 1 | "X" = 0) = 0: Pr( "Y" = 0 | "X" = 1) = 0: Pr( "Y" = "e" | "X" = 1) = "p": Pr( "Y" = 1 | "X" = 1) = 1-"p"

Capacity of the BEC

The capacity of a BEC is 1 - "p".

Intuitively 1 - "p" can be seen to be an upper bound on the channel capacity. Suppose there is an omniscient "genie" that tells the source whenever a transmitted bit gets erased. There is nothing the source can do to avoid erasure, but it can fix them when they happen. For example, the source could repeatedly transmit a bit until it gets through. There is no need for "X" to code, as "Y" will simply ignore erasures, knowing that the next successfully received bit is the one that "X" intended to send. Therefore, having a genie allows us to achieve a rate of 1 - "p" on average. This additional information is not available normally and hence 1 - "p" is an upper-bound.

References

* David J. C. MacKay. " [http://www.inference.phy.cam.ac.uk/mackay/itila/book.html Information Theory, Inference, and Learning Algorithms] " Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
* Thomas M. Cover, Joy A. Thomas. "Elements of information theory", 1st Edition. New York: Wiley-Interscience, 1991. ISBN 0-471-06259-6.

See also

* Binary symmetric channel


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Binary Erasure Channel — Der Begriff binärer Auslöschungskanal (kurz BEC von engl. binary erasure channel) wurde in der Informationstheorie erstmals von Peter Elias verwendet. Man bezeichnet damit einen gedächnisfreien informationstheoretischen Kanal, der ein Bit (0 oder …   Deutsch Wikipedia

  • Binary erasure channel — Der Begriff binärer Auslöschungskanal (kurz BEC von engl. binary erasure channel) wurde in der Informationstheorie erstmals von Peter Elias verwendet. Man bezeichnet damit einen gedächnisfreien informationstheoretischen Kanal, der ein Bit (0 oder …   Deutsch Wikipedia

  • Binary symmetric channel — A binary symmetric channel (or BSC) 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 receives a bit. It is assumed that… …   Wikipedia

  • Channel (communications) — Old telephone wires are a challenging communications channel for modern digital communications. In telecommunications and computer networking, a communication channel, or channel, refers either to a physical transmission medium such as a wire, or …   Wikipedia

  • Erasure code — In information theory, an erasure code is a forward error correction (FEC) code for the binary erasure channel, which transforms a message of k symbols into a longer message (code word) with n symbols such that the original message can be… …   Wikipedia

  • erasure code — noun A forward error correction (FEC) code for the binary erasure channel, which transforms a message of k symbols into a longer message with n symbols such that the original message can be recovered from a subset of the n symbols …   Wiktionary

  • Information theory — Not to be confused with Information science. Information theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental… …   Wikipedia

  • Low-density parity-check code — In information theory, a low density parity check code (LDPC code) is an error correcting code, a method of transmitting a message over a noisy transmission channel. [David J.C. MacKay (2003) Information theory, inference and learning algorithms …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

  • EXIT chart — An Extrinsic information transfer chart, commonly called an EXIT chart, is a technique to aid the construction of good iteratively decoded error correcting codes (in particular low density parity check (LDPC) codes and Turbo codes).EXIT charts… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”