Fact-checked by Grok 2 weeks ago

Binary erasure channel

The binary erasure channel (BEC) is a fundamental model in information theory and coding theory that describes a discrete memoryless communication channel with binary input symbols from the alphabet {0, 1}. When a symbol is transmitted, it is received correctly with probability $1 - \epsilon, where \epsilon (with $0 \leq \epsilon \leq 1) is the fixed erasure probability, or it is erased—resulting in an output symbol from an extended alphabet {0, 1, e} (or equivalently {0, 1, ?}) that indicates the erasure to the receiver—with probability \epsilon.^[1] The channel's transition probabilities are thus P(Y = X | X) = 1 - \epsilon for X \in \{0, 1\} and P(Y = e | X) = \epsilon, ensuring that erasures are detectable but provide no information about the original bit, distinguishing the BEC from channels with undetected errors like the binary symmetric channel.^[1] Introduced by Peter Elias in 1954 as a toy example to demonstrate error-correcting coding techniques, the BEC simplifies analysis of noisy transmission while capturing essential challenges in reliable communication.^[2] Its capacity, defined as the maximum mutual information \max_{p(x)} I(X; Y) over input distributions p(x), is C = 1 - \epsilon bits per channel use, achieved when the input is uniformly distributed (P(X=0) = P(X=1) = 1/2).^[1] This linear capacity formula reflects the proportion of non-erased symbols that can be reliably decoded, making the BEC an ideal benchmark for evaluating code performance up to the Shannon limit.^[2] The BEC's tractability has made it central to the development of modern coding schemes, particularly low-density parity-check (LDPC) codes and iterative decoding algorithms like belief propagation, where erasures correspond to "stopping sets" that halt decoding if uncorrected.^[2] It models real-world scenarios such as packet loss in internet protocols or deletions in storage media, enabling the design of capacity-approaching codes via density evolution and threshold analysis—for instance, the belief-propagation threshold for certain LDPC ensembles reaches \epsilon \approx 0.429 on the BEC.^[2] Extensions include the q-ary erasure channel and feedback variants, where retransmission of erasures achieves capacity without additional complexity.^[1]

Fundamentals

Definition

The binary erasure channel (BEC) is a discrete memoryless channel model in information theory, introduced by Peter Elias as a simple example for studying coding over noisy channels.^[3] In the BEC, the input alphabet consists of binary symbols \{0, 1\}, while the output alphabet is ternary \{0, 1, ?\}, with the symbol ? indicating an erasure that signifies the transmitted bit was not received.^[3] For each transmitted bit, the receiver either obtains the correct value with probability $1 - \epsilon or receives an erasure with fixed probability \epsilon ($0 \leq \epsilon \leq 1), and these events occur independently across bits; crucially, any non-erased output matches the input exactly, with no bit errors possible.^[3] This model intuitively represents communication scenarios like packet loss in digital networks, where the receiver detects missing data but does not interpret it as a corrupted value.^[4]

Mathematical Model

The binary erasure channel (BEC) is formally defined as a discrete memoryless channel (DMC) in which each use consists of an independent transmission of a binary input symbol X \in \{0, 1\} through a noisy medium that produces an output Y \in \{0, 1, e\}, where e denotes an erasure symbol.^[3] The channel model captures scenarios where received symbols are either correctly identified or lost (erased), but never corrupted by flips.^[4] The behavior of the channel is specified by its conditional probability distribution W(y|x), which gives the transition probabilities for each possible output given the input. For x \in \{0, 1\},

\begin{align*} P(Y = x \mid X = x) &= 1 - \epsilon, \\ P(Y = e \mid X = x) &= \epsilon, \\ P(Y = 1 - x \mid X = x) &= 0, \end{align*}

where \epsilon \in [0, 1] is the fixed erasure probability, ensuring no bit flips occur. This transition matrix fully characterizes the BEC as a DMC, with successive channel uses being independent and identically distributed.^[5] As an illustration, for \epsilon = 0.5, the channel erases half of the input bits on average, transmitting the remaining half without error.

Capacity and Analysis

Capacity Formula

The capacity of the binary erasure channel with erasure probability \epsilon is C = 1 - \epsilon bits per channel use. This quantity signifies the supremum of rates at which binary information can be transmitted with arbitrarily low error probability as the block length n \to \infty.^[6] The capacity follows from Shannon's general formula C = \max_{p(x)} I(X; Y), where I(X; Y) denotes the mutual information between the binary input X \in \{0, 1\} and the ternary output Y \in \{0, 1, e\} (with e the erasure symbol), maximized over all input distributions p(x). For the binary erasure channel, I(X; Y) = H(Y) - H(Y \mid X), where H(\cdot) is the entropy in bits.^[6] The conditional entropy H(Y \mid X) = h_2(\epsilon), independent of p(x), with h_2(\epsilon) = -\epsilon \log_2 \epsilon - (1 - \epsilon) \log_2 (1 - \epsilon) the binary entropy function; this arises because, for any fixed x, Y = x with probability $1 - \epsilon or Y = e with probability \epsilon, yielding a binary distribution over outputs. The output entropy is H(Y) = h_2(\epsilon) + (1 - \epsilon) H(X), since the erasure occurs independently of X with fixed probability \epsilon (contributing h_2(\epsilon)), and conditional on no erasure Y = X (contributing (1 - \epsilon) H(X)). Thus, I(X; Y) = (1 - \epsilon) H(X), which is maximized at $1 - \epsilon when X is uniform (H(X) = 1).^[6] Special cases highlight the formula's interpretation: for \epsilon = 0, C = 1, corresponding to a perfect noiseless channel; for \epsilon = 1, C = 0, as every input is erased, rendering reliable communication impossible. The capacity depends directly on the erasure probability \epsilon from the channel model.^[6]

Achieving Capacity

The channel coding theorem establishes that the capacity C = 1 - \epsilon of the binary erasure channel (BEC) with erasure probability \epsilon is achievable, meaning that for any rate R < 1 - \epsilon, there exist codes with arbitrarily small error probability as block length n \to \infty, using maximum likelihood decoding.^[6] This result follows from Shannon's noisy channel coding theorem applied to the BEC, where the erasure locations are known to the decoder, allowing efficient recovery of the transmitted bits.^[7] Asymptotic achievability is demonstrated via the random coding argument, which shows the existence of codes with rate R < 1 - \epsilon and vanishing bit error probability under maximum likelihood decoding. In this approach, codewords are generated randomly from the uniform distribution over \{0,1\}^n, and the decoder selects the codeword that matches the non-erased received symbols; the probability of decoding error decays exponentially with block length n for rates below capacity.^[8] A simple yet inefficient scheme for low rates is repetition coding, where each information bit is repeated multiple times; for example, repeating a bit m times allows recovery if fewer than m erasures occur in those positions, but the resulting rate R = 1/m is far below capacity for moderate \epsilon, requiring excessive redundancy.^[9] More efficient rateless codes, such as Luby Transform (LT) fountain codes, approach capacity with overhead approaching zero as the number of output symbols grows, by generating encoded packets as random linear combinations of input bits over GF(2).^[10] Erasure-correcting codes, particularly linear block codes, enable practical achievement of rates near capacity. Low-density parity-check (LDPC) codes, with sparse parity-check matrices, are tailored for the BEC and achieve capacity asymptotically using irregular degree distributions optimized via density evolution; for instance, codes with rate R = 0.5 tolerate \epsilon up to 0.496, arbitrarily close to the limit $1 - R.^[9] Reed-Solomon codes over finite fields GF(2^m) can correct up to n - k erasures exactly by treating groups of m bits as symbols, supporting rates up to 1 - ε with maximum likelihood decoding when the erasure fraction is below the code's relative minimum distance.^[11] Similarly, Reed-Muller codes achieve capacity under maximum a posteriori bit decoding for any fixed rate R \in (0,1) as block length increases, leveraging their symmetric structure and sharp decoding thresholds.^[12] Decoding for these codes on the BEC often resolves erasures by solving linear equations over GF(2) from the parity-check matrix restricted to unknown positions, equivalent to maximum likelihood for linear codes. For LDPC codes, belief propagation (also known as peeling decoding) iteratively propagates erasure indicators on the Tanner graph: variable nodes send erasure status to check nodes, which resolve an erasure if connected to exactly one, propagating resolutions back until convergence or failure, achieving near-capacity performance with linear complexity.^[8] List decoding, which outputs a small list of candidate codewords consistent with non-erased symbols, can approach maximum likelihood performance for codes like Reed-Muller, ensuring low error probability near capacity.^[13]

Generalizations

The q-ary erasure channel (q-EC) generalizes the binary erasure channel to an input alphabet of size q \geq 2, where each transmitted symbol from \{0, 1, \dots, q-1\} is either received correctly with probability $1 - \epsilon or erased with probability \epsilon, resulting in an output alphabet \{0, 1, \dots, q-1, E\} where E denotes erasure.^[14] The capacity of the q-EC, achieved with uniform input distribution, is (1 - \epsilon) \log_2 q bits per channel use, reflecting the reliable transmission of \log_2 q bits per unerased symbol.^[14] Erasure channels with feedback extend the model by allowing the transmitter to receive instantaneous acknowledgments of erasures, enabling protocols like automatic repeat request (ARQ) to retransmit only erased symbols. While the Shannon capacity remains $1 - \epsilon for the binary case (and analogously scaled for q-ary), feedback facilitates achieving this capacity with simpler uncoded or low-complexity schemes, improving the delay-reliability tradeoff compared to forward error correction alone; for instance, hybrid ARQ combines incremental redundancy with retransmissions to approach capacity under finite blocklengths.^[15] In models with time-varying or correlated erasures, the erasure probability \epsilon deviates from independent and identically distributed (i.i.d.) assumptions, complicating capacity computation. For time-varying channels where \epsilon_t changes deterministically over time t, the capacity is the time average \frac{1}{n} \sum_{t=1}^n (1 - \epsilon_t) bits per channel use for blocklength n.^[16] When erasures exhibit correlation, such as in bursty patterns modeled by Markov processes, the capacity involves entropy rates of the erasure process and is generally lower than the i.i.d. case for the same marginal \epsilon, requiring numerical methods like density evolution for low-density parity-check codes to evaluate achievable rates.^[17] The compound binary erasure channel considers a set of possible erasure probabilities \mathcal{S} = \{\epsilon_1, \dots, \epsilon_m\}, where the actual channel is unknown but belongs to this set, demanding codes robust to the worst case. The capacity is \min_{\epsilon \in \mathcal{S}} (1 - \epsilon), the minimum over the individual capacities, ensuring reliable communication across all channels in \mathcal{S}.^[18] Extensions to non-binary data apply the q-EC model in storage systems, where symbols over larger alphabets represent data units like pages in flash memory, subject to partial or full erasures due to read/write wear or defects; for example, q-ary symbols stored across bit pages with varying erasure rates necessitate codes like Reed-Solomon to achieve near-capacity recovery.^[19] The binary erasure channel (BEC) is often compared to other fundamental channel models in information theory to highlight variations in error mechanisms and their implications for capacity and decoding. Unlike channels with substitution errors, the BEC explicitly signals erasures, allowing receivers to identify lost information without ambiguity. This section examines key related channels, focusing on differences in error types such as bit flips, asymmetric distortions, silent losses, and continuous noise. The binary symmetric channel (BSC) models symmetric bit-flip errors, where each transmitted bit is received incorrectly with probability p, independently of its value, resulting in a binary output alphabet without any indication of errors. In contrast to the BEC's erasure symbols, the BSC provides no such feedback, requiring codes to detect and correct flips implicitly. The capacity of the BSC is $1 - H_2(p), where H_2(p) = -p \log_2 p - (1-p) \log_2 (1-p) is the binary entropy function, which is lower than the BEC's capacity of $1 - \epsilon for comparable noise levels p = \epsilon, due to the undetected nature of errors.^[20] The Z-channel represents an asymmetric binary channel, commonly modeling optical communications where an input of 0 is always received correctly as 0, but an input of 1 is received as 0 with probability p or as 1 with probability $1-p, using a binary output alphabet. Unlike the BEC, the Z-channel lacks erasure symbols, so errors manifest solely as one-sided substitutions without notification, complicating decoding for inputs biased toward 1. This asymmetry distinguishes it from symmetric models like the BSC and erasure-based ones like the BEC, with no explicit loss indication.^[21] The binary deletion channel shares conceptual similarities with the BEC in that bits are lost with probability \delta, but deletions occur silently, shortening the output sequence without marking positions, unlike the BEC's fixed-length output with erasure indicators. For instance, a transmitted sequence like 10101010 might yield 10011 in the deletion channel if certain bits vanish, whereas the BEC would produce 10?01?1? for the same losses. This absence of position information renders the deletion channel harder to analyze and code for, with its capacity unknown in closed form—though bounded above by $1 - \delta, matching the BEC's capacity of $1 - \epsilon for \delta = \epsilon, and below by approximately (1 - \delta)/9 for small \delta.^[22] The additive white Gaussian noise (AWGN) channel, a continuous analog model, adds Gaussian noise to transmitted signals, typically analyzed with binary inputs via binary-input AWGN (BI-AWGN) for discrete comparisons. While the BEC is purely discrete with explicit erasures, the BI-AWGN produces soft outputs that can approximate erasure-like behavior at high signal-to-noise ratios, where low-confidence receptions mimic erasures in quantized discrete models. Codes performing well on the BEC often serve as benchmarks for BI-AWGN, but the continuous noise in AWGN introduces amplitude variations absent in the BEC's binary erasure mechanism.^[23] A distinguishing feature of the BEC among these models is its provision of perfect erasure feedback, which reduces uncertainty compared to undetected errors in the BSC, Z-channel, or deletion channel, and contrasts with the probabilistic noise in AWGN—effectively making the BEC "less noisy" for recovery despite equivalent loss rates. This explicit signaling enables simpler achieving of capacity via linear codes, unlike the more opaque error handling required elsewhere.^[22]

Historical Development

Origins

The binary erasure channel (BEC) was introduced by Peter Elias in 1955 during his early research on channel coding at the Massachusetts Institute of Technology's Research Laboratory of Electronics. This work built directly on Claude E. Shannon's foundational 1948 noisy channel coding theorem, which demonstrated the theoretical possibility of reliable communication over noisy channels at rates up to the channel capacity but did not specify practical coding methods for particular noise models. Elias's contribution focused on developing concrete coding strategies for realistic error patterns beyond the binary symmetric channel emphasized in Shannon's original analysis. The BEC first appeared in Elias's paper "Coding for Two Noisy Channels," presented at the Third London Symposium on Information Theory.^[3] In this seminal work, Elias described the BEC as a simplified yet illustrative model to capture essential aspects of noisy communication, where a transmitted bit is either received correctly or erased entirely with a known probability, contrasting with substitution errors in other channels.^[3] The model's motivation stemmed from the need to address practical transmission losses, such as those occurring in radio systems where signals can fade completely due to propagation effects, rendering the symbol unavailable rather than merely distorted. Elias positioned the BEC as a "toy example" that encapsulated the core challenges and solutions in error-correcting coding, facilitating clearer exposition of capacity-achieving techniques without the complexities of probabilistic error substitution.^[24] This approach gained early traction within the information theory community, serving as a pedagogical tool for exploring channel capacity and coding bounds in subsequent analyses.

Key Contributions

In the 1960s and 1970s, the binary erasure channel (BEC) became integrated into broader coding theory frameworks, facilitating the analysis and design of erasure-correcting codes through established existence bounds such as the Gilbert-Varshamov bound, which provides a lower bound on the size of codes capable of correcting a specified number of erasures. This integration highlighted the BEC's utility as a tractable model for evaluating code performance against erasures, influencing early developments in linear block codes and convolutional codes for reliable data transmission. The 1990s marked significant progress with the introduction of Tornado codes in 1998 by Michael Luby and colleagues, which employed irregular sparse bipartite graphs to achieve efficient encoding and decoding for erasure recovery, approaching the BEC capacity with linear-time complexity.^[25] Building on this, Luby Transform (LT) codes, proposed by Michael Luby in 2002, extended the rateless paradigm for BEC, enabling adaptive transmission rates without prior knowledge of channel conditions and achieving near-capacity performance asymptotically with low overhead.^[26] In the 2000s, advancements like digital fountain codes, including extensions such as Raptor codes, further refined these approaches by cascading LT codes with outer codes to realize capacity on the BEC with minimal encoding/decoding overhead, typically requiring only a small constant factor above the theoretical limit. These rateless codes demonstrated practical scalability for multicast and broadcast scenarios over erasure-prone networks, reducing retransmission needs compared to fixed-rate alternatives. Post-2010 developments have extended the BEC model to quantum settings, where the quantum binary erasure channel (QBEC) has been analyzed for capacity-achieving codes; for instance, Reed-Muller codes were shown to attain the QBEC capacity under maximum a posteriori decoding in 2016. In wireless communications, the BEC serves as a model for packet erasures in 5G and emerging 6G systems, supporting rateless coding schemes for ultra-reliable low-latency links and integrating with HARQ protocols to enhance throughput under varying loss rates.^[27] Additionally, recent analyses apply the BEC to machine learning for robust training over lossy channels, modeling data erasures in semantic communication tasks to improve model resilience via joint source-channel optimization.^[28] The BEC's simplicity in decoding—reducible to solving a system of linear equations—has established it as a key benchmark for testing and validating new coding algorithms, from LDPC to polar codes, ensuring their efficacy before deployment on more complex channels.^[4] This foundational role underscores the channel's enduring impact in theoretical and applied information theory.

References

[1]
[PDF] Elements of Information Theory
... information theory, and developed the duality of data compression and channel capacity. A new chapter has been added and many proofs have been simplified ...
[2]
[PDF] MODERN CODING THEORY
The title Modern Coding Theory is clearly a hyperbole. After all, there have been several other important recent developments in coding theory. To name just the.
[3]
[PDF] coding for two noisy channels - MIT
Elias has shown that it is possible to signal at rates arbitrarily close to the capacity of the binary symmetric channel with arbitrarily small probability of.
[4]
BINARY ERASURE CHANNEL (Chapter 3) - Modern Coding Theory
It was introduced by Elias as a toy example in 1954. The emergence of the Internet promoted the erasure channel into the class of “real-world” channels.
[5]
[PDF] Lecture BEC Capacity
I. Binary Erasure Channel (BEC). A Binary Erasure Channel (BEC) is a common communications channel model used in coding theory and information theory.Missing: primary sources
[6]
[PDF] Appendix B Information theory from first principles - Stanford University
Example B.5 Binary erasure channel In the erasure channel, on the other hand, the receiver knows exactly which symbols are erased. If the transmitter also ...Missing: primary sources
[7]
[PDF] ECE 587 / STA 563: Lecture 6 – Channel Coding - Galen Reeves
Aug 24, 2023 · 6.2.1 Binary Erasure Channel (BEC) . ... • The information capacity of a discrete memoryless channel is defined as.
[8]
[PDF] Capacity-approaching codes
We will analyze long LDPC codes on the binary erasure channel (BEC), where exact results can be obtained. We will also sketch how to analyze any of these codes ...
[9]
[PDF] LDPC Codes: Achieving the Capacity of the Binary Erasure Channel
Nov 30, 2009 · The proof follows from the Theorem on Total Probability. Convergence: Error-free decoding requires that the erasure probability goes down from ...
[10]
(PDF) LT codes - ResearchGate
Aug 9, 2025 · LT codes are the first realization of a class of erasure codes called universal erasure codes. LT codes are universal in the sense that they are simultaneously ...
[11]
[PDF] Tutorial on Reed-Solomon Error Correction Coding
SYMBOL. ERASING. AND. REED-SO_DMON. CODING ....... 81. RS. CODING. USING. SYMBOL. ERASURE ........... 81. RS. ENCODING. USING. SYMBOL. ERASURE.
[12]
[PDF] Reed-Muller Codes Achieve Capacity on the Binary Erasure ...
May 21, 2015 · In this paper, we show that RM codes indeed achieve the capacity for transmission over the BEC for any rate R ∈ (0, 1).
[13]
[PDF] Belief Propagation List Decoding of Polar Codes - arXiv
Jun 27, 2018 · Abstract—We propose a belief propagation list (BPL) decoder with comparable performance to the successive cancellation.
[14]
[PDF] Achieving the Capacities of Channels with Erasures Using Nested ...
This leads us to the following theorem. Theorem 2.10. The capacity of a q-ary EC with an erasure probability α can be calculated as. CEC = (1 − α)log2(q) in ...
[15]
[PDF] Balancing forward and feedback error correction for erasure ...
However, it has recently been shown that perfect feedback does allow great improvements in the asymptotic tradeoff between end-to-end delay and probability of ...
[16]
[PDF] Channel Capacity - WINLAB, Rutgers University
is identical to the binary erasure channel discussed in class, with a = 1/2. As derived in class, the capacity of this channel is 1 a 1/2 bit per transmission.
[17]
[PDF] Code Rate, Queueing Behavior and the Correlated Erasure Channel
When the channel is memoryless, the optimal rT is 80. For comparison, the capacity is 0.8 and gives an rT of roughly 91. As correlation increases, the ...
[18]
https://ieeexplore.ieee.org/document/9727111
[19]
[PDF] On Coding for Partial Erasure Channels - UNL Digital Commons
Figure 2.4: The 3-ary erasure channel with erasure probability ε. The capacity of the QEC is (1 − ε) q-ary symbols per channel use [29]. There are many ...Missing: formula | Show results with:formula<|control11|><|separator|>
[20]
[PDF] A Mathematical Theory of Communication
In the present paper we will extend the theory to include a number of new factors, in particular the effect of noise in the channel, and the savings possible ...
[21]
[PDF] ECE 515 Information Theory
Capacity of a 4-ary Symmetric Channel. 34. Page 35. Binary Errors with Erasure ... • At rates above capacity, P e. → 1 exponentially as N → ∞Missing: \log_2
[22]
[PDF] A survey of results for deletion channels and related synchronization ...
A deletion channel deletes bits independently with a fixed probability, unlike an erasure channel where a symbol is received instead. There is no sign of which ...
[23]
[PDF] Performance Comparison of Short-Length Error-Correcting Codes
Nov 7, 2016 · Abstract—We compare the performance of short-length linear binary codes on the binary erasure channel and the binary- input Gaussian channel ...
[24]
[PDF] peter elias - National Academy of Sciences
pete's next major paper, “coding for noisy channels,” in 1955, is perhaps the most influential early paper in in- formation theory after shannon's original ...Missing: Erasure | Show results with:Erasure
[25]
Exact thresholds for low-density parity-check codes over the binary ...
Jul 10, 2009 · The binary erasure channel (BEC), presented by Elias in 1955 [1], has lately become increasingly popular, as it can be used to model Internet ...
[26]
[PDF] Optimal Rate Irregular LDPC Codes in Binary Erasure Channel - arXiv
One of the classical channel models is Binary Erasure Channel (BEC), presented by Elias in. 1955 [5]. Nowadays, BEC has become popular as a communication ...
[27]
Decoding error probability of random parity-check matrix ensemble ...
Oct 16, 2024 · ... fading noise during high frequency radio transmission. One of the ... binary erasure channel. Special issue on Shannon theory ...
[28]
[PDF] Peter Elias, 1923–2001 - IEEE Information Theory Society Newsletter
His Shannon Lecture was vintage Elias. He showed that the simple binary erasure channel incorpo- rated all the essentials that are needed to understand coding.Missing: original | Show results with:original
[29]
Memory-Based LT Codes for Efficient 5G Networks and Beyond
Dec 20, 2021 · Moreover, these three links are modeled as binary erasure channels (BECs) with different erasure probabilities. Electronics 10 03169 g001 550.