Channel polarization

In 2007, Erdal Arikan discovered a practical channel coding scheme that achieves the capacity of binary-input discrete memoryless channels. His method relies on a phenomenon now known as channel polarization. First, we observe that achieving the capacity of the following channels with input $X$ and output $Y$ is straightforward:

• channels where $X$ and $Y$ are one-to-one functions of each other, and
• channels where $X$ is independent of $Y$.

The first class of channels is perfect in the sense that we do not need to introduce any redundancy to transmit $X$ reliably. In other words, uncoded transmission will suffice. To transmit, five symbols from the source alphabet ${\mathcal {X}}$, we simply pass the five symbols over the channel. Since there is one-to-one correspondence between the input and output alphabets, it is always possible to recover $X$ without errors.

The second class of channels is useless in the sense that no matter how much redundancy we add, the channel output will not tell us anything about the input. Since the input and output rvs are independent, $I(X;Y)=0$ and to achieve capacity, we simply not use the channel. (In practice, we can transmit a fixed symbol every time since there is no information if the transmission is not random at all.)

Synthetic channels

Most other classes fall in the wide space between perfect channels and useless channels. Through a simple operation, we can repeatedly "polarize" a channel so that it ends up as either a near-perfect channel or a near-useless channel.

Let $W:X\rightarrow Y$ be a binary-input channel with input alphabet ${\mathcal {X}}=\{0,1\}$, and let $I(W)$ be the mutual information between $X$ and $Y$ assuming that $X$ is uniformly distributed. In other works, this quantity is referred to as the symmetric capacity. We construct two channels $W^{-}$ and $W^{+}$ schematically as shown below:

$W^{-}$ maps the input $U_{1}$ to the tuple $(Y_{1},Y_{2})$ while $W^{+}$ maps $U_{2}$ to the tuple $(U_{1},Y_{1},Y_{2})$. Since $U_{2}$ interferes with $U_{1}$, we have $I(W^{-})\leq I(W)$, and since $W^{+}$ contains extra information about the input ($U_{1}$), $I(W^{+})\geq I(W)$. In general, it can be shown that

$I(W)={\frac {I(W^{-})+I(W^{+})}{2}},$

where $I(W^{-})=I(U_{1};Y_{1},Y_{2})$ and $I(W^{+})=I(U_{2};U_{1},Y_{1},Y_{2})$.

Binary symmetric channel

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

		$(Y_{1},Y_{2})$
		00	01	10	11
$(U_{1},U_{2})$	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)$

In this section, we produce the channel matrices corresponding to $W^{-}:U_{1}\rightarrow (Y_{1},Y_{2})$ and $W^{+}:U_{2}\rightarrow (U_{1},Y_{1},Y_{2})$. Recall at the channel matrices give the conditional probabilities of the outputs given the input. For $W^{-}$, we have

$p(Y_{1},Y_{2}|U_{1})=p(U_{2}=0)p(Y_{1},Y_{2}|U_{1},U_{2}=0)+p(U_{2}=1)p(Y_{1},Y_{2}|U_{1},U_{2}=1)={\frac {1}{2}}(p(Y_{1},Y_{2}|U_{1},U_{2}=0)+p(Y_{1},Y_{2}|U_{1},U_{2}=1))$

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

Checkpoint: Verify that each row of the table for $W^{-}:U_{1}\rightarrow (Y_{1},Y_{2})$ sum to 1.

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.

		$(Y_{1},Y_{2})$
		00,11	01,10
$U_{1}$	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. For example, if $p=0.1$ for the original BSC, then the crossover probability of $W^{-}$ is $2p(1-p)=0.18$, which is worse than the original. It also has the intuitive property that it cannot make the worst possible BSC any worse: if the original BSC had $p=1/2$, then $W^{-}$ would have the same crossover probability.

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:

		$(U_{1},Y_{1},Y_{2})$
		000	110	001	010	100	111	011	101
$U_{2}$	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:

		$(U_{1},Y_{1},Y_{2})$
		000,110	001,010,100,111	011,101
$U_{2}$	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.

Binary erasure channel

Let $\epsilon$ be the erasure probability of a binary erasure channel (BEC). As with the BSC, we can start with the conditional probability of $(Y_{1},Y_{2})$ given $(U_{1},U_{2})$.

		$(Y_{1},Y_{2})$
		00	0?	01	?0	??	?1	10	1?	11
$(U_{1},U_{2})$	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 )$

The synthetic channel $W^{-}:U_{1}\rightarrow (Y_{1},Y_{2})$ can be obtained by marginalizing $U_{2}$,

		$(Y_{1},Y_{2})$
		00	0?	01	?0	??	?1	10	1?	11
$U_{1}$	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 )$

A maximum-likelihood receiver will decide that $U_{1}=0$ if is more likely than $U_{1}=0$. If there are ties, we declare an erasure, denoted by $?$. This allows us to reduce the nine-element output alphabet into three groups. The receiver declares that ${\hat {U}}_{1}=0$ if $Y_{1}\oplus Y_{2}=0$ and ${\hat {U}}_{1}=1$ if if $Y_{1}\oplus Y_{2}=1$. This is very similar to the XOR decisions in our discussion of the BSC. The difference now is that several combinations may correspond to an erasure. From the table below, it can be seen that $W^{-}$ is equivalent to a BEC with erasure probability of $2\epsilon -\epsilon ^{2}$.

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

The other synthetic channel $W^{+}:U_{2}\rightarrow (U_{1},Y_{1},Y_{2})$ has an output alphabet of size 18. For brevity, the table below shows the reduced transition probability matrix. Upon inspection, we see that the reduced channel is equivalent to another BEC with erasure probability $\epsilon ^{2}$. For all $0<\epsilon <1$, $\epsilon ^{2}<2\epsilon -\epsilon ^{2}$ which guarantees that $W^{+}$ has higher mutual information compared to $W^{-}$.

		$(U_{1},Y_{1},Y_{2})$
		000, 00?, 0?0, 1?0, 110, 11?	0??, 1??	0?1, 01?, 011, 10?, 101, 1?1
$U_{2}$	0	$1-\epsilon ^{2}$	$\epsilon ^{2}$
	1		$\epsilon ^{2}$	$1-\epsilon ^{2}$

Finally, observe that the capacity of the original BEC is $C(W)=1-\epsilon$. Since $W^{-}$ and $W^{+}$ are also BECs, then their capacities are given by similar expressions. Adding the capacities of the synthetic channels gives twice the capacity of the original channel,

$(1-\epsilon ^{2})+(1-2\epsilon +\epsilon ^{2})=2-2\epsilon =2(1-\epsilon )$

Checkpoint: Verify that $W^{+}$ can be decoded as follows:

• If $U_{1}\oplus Y_{1}=0$ or $Y_{2}=0$, output ${\hat {U}}_{2}=0$.
• If $U_{1}\oplus Y_{1}=1$ or $Y_{2}=1$, output ${\hat {U}}_{2}=1$.
• Otherwise, declare an erasure.

Achieving capacity

We can repeat the polar transform $n$ times to produce $2^{n}$ synthetic channels. For binary-input DMCs, it has been shown that for large $n$, around $2^{n}\cdot I(W)$ of these $2^{n}$ will be close to perfect and that around $2^{n}\cdot (1-I(W))$ will be close to useless. Thus, we have a practical encoder-decoder system:

• Produce $2^{n}$ synthetic channels.
• Transmit i.i.d binary inputs $X$ to each of the near-perfect channels.
• Transmit fixed bits (usually zero) as inputs to the near-useless channels.
• Perform successive-cancellation decoding at the receiver.

The binary erasure channel is easy to play with since we know that all synthetic channels are effectively BECs. Recall that if the parent BEC has erasure probability $\epsilon$, then the two synthetic channels it can generate have erasure probabilities $\epsilon ^{-}=2\epsilon -\epsilon ^{2}$ and $\epsilon ^{+}=\epsilon ^{2}$. Here, $\epsilon ^{-}$ corresponds to the erasure due to the worse synthetic channel $W^{-}$ and $\epsilon ^{+}$ corresponds to the better synthetic channel $W^{+}$.

We can recursively apply the mapping $\epsilon \mapsto (2\epsilon -\epsilon ^{2},\epsilon ^{2})$ to produce $2^{n}$ erasure probabilities. For large $n$, around $\epsilon \cdot 2^{n}$ of these values will be close to one (which means that the transmitted symbols are completely erased!), while almost all of the rest will have erasure probabilities close to zero (which means that the channel is almost noiseless). Module 5 is a small preview for you to see that the erasure probabilities indeed polarize for large $n$. Arikan's polarization result is non-trivial and requires proof techniques beyond what we can cover in CoE 161.