6.5a Binary Channel Coding

Binary Channels

The Binary Erasure Channel (BEC) is a discrete channel with an input alphabet $\mathcal{X}=\{0,1\}$ and an output alphabet $\mathcal{Y}=\{0,1,e\}$, where $e$ represents an erasure symbol, indicating that the transmitted bit was lost with probability $p\in [0,1]$:

\begin{document}
\begin{tikzpicture}[scale=0.75]
 % Draw Input nodes
 \draw[->, thick] (0,3) -- (3,3) node[left, at start]{$0$} node[right]{$0$} node[above, midway]{$1-p$};
 \draw[->, thick] (0,2.9) -- (3, 1.55) node[midway, below]{$p$};
 \draw[->, thick] (0,0.1) -- (3, 1.45) node[midway, above]{$p$};
 \draw[->, thick] (0, 0) -- (3, 0) node[left, at start]{$1$} node[right]{$1$} node[below, midway]{$1-p$};
 \node at (3.3, 1.5) {$e$};
\end{tikzpicture}
\end{document}

In an abstract communications system, the pipeline can be outlined as follows:
$M^{(L)}\underset{f_n:{\mathcal{M}}^L\to {\mathcal{X}}^n}{\overset{\text{Encoder}}{\to }}{X}^{(n)}\stackrel{\text{(Noisy) Channel}}{\to }{Y}^{(n)}\underset{g_n:{\mathcal{Y}}^n\to {\mathcal{M}}^L}{\overset{\text{Decoder}}{\to }}{\hat{M}}^{(L)}$

1. A message $M^{(L)}$ of binary length $L$ goes through an encoder $f_n:{\mathcal{M}}^L\to {\mathcal{X}}^n$, and is transformed into a codeword $X^{(n)}$ of length $n$ in channel symbols (i.e., in bits if the channel is binary).
2. It then goes through the channel, which outputs the random map $Y$ (also of length $n$).
3. Finally, the output is ran through a decoder $g_n:{\mathcal{Y}}^n\to {\mathcal{M}}^L$, which yields the output $\hat{M}$ of length $L$.

The rate at which the message is conveyed through the channel is given as $R=L/n$ bits per channel symbols (i.e, decoded bits per encoded bits). In binary channels, $R\in [0,1]$. The capacity of a channel is the maximum asymptotic rate at which it can reliably communicate a symbol, given as
$C={\max }_{p_X}I(X;Y)\text{ bits/symbol},$
where $C_{\text{BEC}}=1-p$, and $C_{\text{BSC}}=1-H_b(p)$. In other words, the channel is stable if $R<C$.

For a BEC, the maximum probability of erasure is given as the worst-case probability that the decoder fails to recover the original message:
$P_e(n)=\mathbb{P}(\hat{M}\ne M)={\max }_{x\in {\mathcal{X}}^L}\mathbb{P}(g(Y^n)\ne x^n\mid X^n=f_n(x^n)).$

Together, these quantities yield the Shannon Channel Coding Theorem, which states that as $n\to \infty$, there exists a rate-$R$ communication scheme that achieves
$P_e(n)\to \{\begin{array}{ll}0& R<C,\\ c\in (0,1)& R=C\\ 1& R>C.\end{array}$

Proof

Examples

I. Sending a Message

Consider a binary erasure channel (BEC), which erases channel input with probability $p\in (0,1)$. We wish to send a message of length $L$ bits, and we encode to a codeword of length $n$, where $n,L$ are positive integers and $n>L$. Define $R=L/n$ (in bits per symbol) as the rate of the channel.

Now, recall Shannon’s random codebook argument: we flip $n{2}^L$ fair coins independently, and populate a $2L\times n$ codebook accordingly ($2L$ codewords, each with length $n$). Suppose that the first codeword is sent through the BEC.

A) Give a tight upper bound on the number of bits that can be sent reliably over the channel.

A) Solution. $C=1-p$ per symbol. Using the channel $n$ times, the most information that can be conveyed is therefore $n(1-p)$.

Since we are considering a BEC, the tight upper bound is

B) Assume that your answer for part A) is the actual number of unerased bits sent over the BEC. If $p=0.1$, $n=500$, and $L=400$, what is the tightest upper bound on $P_e$?

Let $c_1$ be the transmitted codeword, and let $c_i$ ($i\ge 2$) be any of the following codewords. Then,
$\mathbb{P}\left(\bigcup _{i=1}^n\right)$