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.