Channel polarization

Binary erasure channel

Let $\epsilon$ be the erasure probability of a binary erasure channel (BEC).

	00	0?	01	?0	??	?1	10	1?	11
00	$(1-\epsilon )^{2}$	$\epsilon (1-\epsilon )$		$\epsilon (1-\epsilon )$	$\epsilon ^{2}$
01					$\epsilon ^{2}$	$\epsilon (1-\epsilon )$		$\epsilon (1-\epsilon )$	$(1-\epsilon )^{2}$
10				$\epsilon (1-\epsilon )$	$\epsilon ^{2}$		$(1-\epsilon )^{2}$	$\epsilon (1-\epsilon )$
11		$\epsilon (1-\epsilon )$	$(1-\epsilon )^{2}$		$\epsilon ^{2}$	$\epsilon (1-\epsilon )$

	00	0?	01	?0	??	?1	10	1?	11
0	$0.5(1-\epsilon )^{2}$	$0.5\epsilon (1-\epsilon )$		$0.5\epsilon (1-\epsilon )$	$\epsilon ^{2}$	$0.5\epsilon (1-\epsilon )$		$0.5\epsilon (1-\epsilon )$	$0.5(1-\epsilon )^{2}$
1		$0.5\epsilon (1-\epsilon )$	$0.5(1-\epsilon )^{2}$	$0.5\epsilon (1-\epsilon )$	$\epsilon ^{2}$	$0.5\epsilon (1-\epsilon )$	$0.5(1-\epsilon )^{2}$	$0.5\epsilon (1-\epsilon )$

Binary symmetric channel

Let $p$ be the crossover probability of a binary symmetric channel (BSC).

	00	01	10	11
00	$(1-p)^{2}$	$p(1-p)$	$p(1-p)$	$p^{2}$
01	$p^{2}$	$p(1-p)$	$p(1-p)$	$(1-p)^{2}$
10	$p(1-p)$	$p^{2}$	$(1-p)^{2}$	$p(1-p)$
11	$p(1-p)$	$(1-p)^{2}$	$1-p^{2}$	$p(1-p)$

	00	01	10	11
00	$0.5(1-2p+2p^{2})$	$p(1-p)$	$p(1-p)$	$0.5(1-2p+2p^{2})$
01	$p(1-p)$	$0.5(1-2p+2p^{2})$	$0.5(1-2p+2p^{2})$	$p(1-p)$

It turns out that the channel $W^{-}:U_{1}\rightarrow (Y_{1},Y_{2})$ reduces to another BSC. To see this, consider the case where $(Y_{1},Y_{2})=(0,0)$. To minimize the error probability, we must decide the value of $U_{1}$ that has the greater likelihood. For $0<p<0.5$, $0.5(1-2p+2p^{2})>p(1-p)$ so that the maximum-likelihood (ML) decision is $U_{1}=0$. Using the same argument, we see that the ML decision is $U_{1}=0$ for $(Y_{1},Y_{2})=(1,1)$. More generally, the receiver decision is to set ${\hat {U_{1}}}=Y_{1}\oplus Y_{2}$. Indeed, if the crossover probability is low, it is very likely that $Y_{1}=U_{2}\oplus U_{1}$ and $Y_{2}=U_{2}$. Solving for $U_{2}$ and plugging it back produces the desired result.

	00,11	01,10
00	$1-2p+2p^{2}$	$2p(1-p)$
01	$2p(1-p)$	$1-2p+2p^{2}$

We just saw that despite having a quartenary output alphabet, $W^{-}$ is equivalent to a BSC. To get the effective crossover probability of this synthetic channel, we just determine the probability that the ML decision ${\hat {U_{1}}}$ is not the same as $U_{1}$. This will happen with probability $2p(1-p)$. Intuitively, $W^{-}$ should have less mutual information compared to the original channel $W$ since an independent source $U_{2}$ interferes with $U_{1}$ on top of the effects of the BSC.

Checkpoint: Show that for $0<p<1/2$, $p<2p(1-p)$.

Now, let us consider the other synthetic channel $W^{+}:U_{2}\rightarrow (U_{1},Y_{1},Y_{2})$. This synthetic channel has a greater mutual information compared to the original BSC due to the "stolen" information about $U_{1}$. As with the previous synthetic channel, we can produce the transition probability matrix from $U_{2}$ to $(U_{1},Y_{1},Y_{2})$, which now has an eight-element output alphabet. To facilitate the discussion, the columns of the table below have been grouped according to their entries:

	000	110	001	010	100	111	011	101
0	$0.5(1-p)^{2}$	$0.5(1-p)^{2}$	$0.5p(1-p)$	$0.5p(1-p)$	$0.5p(1-p)$	$0.5p(1-p)$	$0.5p^{2}$	$0.5p^{2}$
1	$0.5p^{2}$	$0.5p^{2}$	$0.5p(1-p)$	$0.5p(1-p)$	$0.5p(1-p)$	$0.5p(1-p)$	$0.5(1-p)^{2}$	$0.5(1-p)^{2}$

In the transition probability matrix, we see that there are four columns where the receiver will not be able to tell whether $U_{2}=0$ or $U_{2}=1$. We can call such a scenario an erasure, and say that the transmitted bit is erased with probability $4\times 0.5p(1-p)=2p(1-p)$. Clearly, we cannot reduce this synthetic channel to a BSC since there are no erasures in a BSC. Regardless, we can still come up the following more manageable reduction:

	000,110	001,010,100,111	011,101
0	$(1-p)^{2}$	$2p(1-p)$	$p^{2}$
1	$p^{2}$	$2p(1-p)$	$(1-p)^{2}$

Checkpoint: Show that the mutual information is preserved after the reduction.