Binary erasure channel

A binary erasure channel transmits each input bit correctly with probability $1-\epsilon$ and replaces it by an erasure symbol with probability $\epsilon$. Its channel capacity is $1-\epsilon$ bits per use.

With channel feedback, resend each message bit through a binary erasure channel until a non-erased copy arrives, then move to the next bit. The channel decoder deletes erasure symbols, giving the message without error whenever transmission completes. For $q<1$, the waiting times have an independent and identically distributed geometric distribution with expectation $1/(1-q)$, so every finite message completes almost surely. The strong law of large numbers gives forward code rate $n/{\sum }_{j=1}^n{M}_j\to 1-q$, matching channel capacity. At $q=1$, transmission never completes. Independent erasure indicators, rather than independent message bits, are the essential hypothesis.

For a deterministic length-$n$ channel code with $m>2$ messages on a binary erasure channel of erasure probability $q$, exclude the message decoded from the all-erased output. Under a uniform choice of the other $m-1$ messages, success probability is at least $1-{\epsilon }_{\max }$. Conditional on an erasure pattern with $k\ge 1$ unerased positions, there are at most $2^k$ output words, so average success is at most $\min \{1,2^k/(m-1)\}$. With no unerased positions it is zero.

Put $L={\log }_{2}m-1$. The scalar bound $\min \{1,2^k/(m-1)\}\le k/L$ is immediate for $k\ge L$. Otherwise set $r=m/2^k>2$. Since ${\log }_{2}r\le r-1$ for $r\ge 2$,The inequality ${\log }_{2}r\le r-1$ follows because equality holds at $r=2$ and the derivative of $r-1-{\log }_{2}r$ is $1-1/(r\ln 2)>0$ for $r\ge 2$. Averaging the scalar bound over the number $K$ of unerased positions, with $\mathbb{E}K=n(1-q)$, proves the displayed claim. Thus ${\epsilon }_{\max }\le \delta <1$ implies code rate $R\le (1-q)/(1-\delta )+1/n$. The cases $m\le 2$ satisfy this rate bound directly.

Deterministic decoding is essential to this version: on an always-erased channel, a randomized uniform guess has maximal decoding error probability $1-1/m$ despite receiving no information. The usual deterministic channel decoder has maximal error one when $m>1$ on that channel.