CCapacity Atlas
binary-erasure-channel

Binary erasure channel

Each transmitted bit is received correctly or replaced by a visible erasure symbol.

Point-to-point Binary Finite alphabet Discrete memoryless Symmetric Erasure Capacity Exact

Channel and question

Input
\(X\in\{0,1\}\)
Output
\(Y\in\{0,1,?\}\)
Law
\(Y=X\) with probability \(1-\varepsilon\), and \(Y=?\) with probability \(\varepsilon\).
Quantity
Shannon capacity \(C_{\mathrm{BEC}}(\varepsilon)\), measured in bits per channel use.

Criterion. Average-error capacity.

  • Channel uses are independent.
  • Average decoding error vanishes with blocklength.

Parameters

\(\varepsilon\)
Erasure probability. Range: \(0\le\varepsilon\le1\).

Current status

\[C_{\mathrm{BEC}}(\varepsilon)=1-\varepsilon\]

Conditions. \(0\le\varepsilon\le1\).

Known results and bounds for Binary erasure channel
ResultRelationMethodYear
Lower\(C\ge1-\varepsilon\)Random coding or linear erasure-correcting codes.1948
Upper\(C\le1-\varepsilon\)At most one bit passes through each unerased position.1948

Formal verification

Lean coverageFormally stated

The information-capacity formula is proved from explicit output and conditional-entropy identities. The operational average-error formula follows from the formal finite-channel coding theorem.

Claims

  • For 0 ≤ e ≤ 1, the single-letter information capacity is 1-e bits per use.
    information-capacity · exact capacity · solved · Formally proved · v1
  • For 0 ≤ e ≤ 1, operational vanishing-average-error capacity is 1-e bits per use.
    operational-capacity · exact capacity · solved · Formally proved · v1
Lean declarations (4)

References

  1. Claude E. Shannon (1948). A Mathematical Theory of Communication. Bell System Technical Journal. DOI 10.1002/j.1538-7305.1948.tb01338.x.
  2. Thomas M. Cover and Joy A. Thomas (2006). Elements of Information Theory. Wiley, second edition. DOI 10.1002/047174882X.

Discussion

Find discussionStart discussion

Related problems

Binary Z-channel Z-channel

One binary symbol is transmitted perfectly while the other can flip in only one direction.

Point-to-point Binary Finite alphabet Discrete memoryless Asymmetric Capacity Exact
Solved \(C_Z(p)=\log_2\!\left(1+(1-p)p^{p/(1-p)}\right)\)
Binary memory with encoder-known stuck-at defects

Independent stuck-at defects are known noncausally to the encoder but not the decoder.

Point-to-point Binary Finite alphabet Discrete memoryless Noncausal state information Capacity Exact
Solved \(C=1-\delta\)
Binary symmetric channel BSC

Each bit is independently flipped with probability \(p\).

Point-to-point Binary Finite alphabet Discrete memoryless Symmetric Capacity Exact
Solved \(C_{\mathrm{BSC}}(p)=1-h_2(p)\)
DMC with causal state information at the encoder

An iid channel state is revealed causally to the encoder but not to the decoder.

Point-to-point Finite alphabet Discrete memoryless Causal state information Side information Capacity Exact Single-letter characterization
Solved \(C_{\mathrm{causal}}=\max_{P_U,\,x=f(U,S),\,U\perp S} I(U;Y)\)