Decoding a polar code

Assume that we have a decoding algorithm for the $U$ and the $V$ code that uses the fact that we know for each bit $i$ of the codeword the probability $p_i$ that it is equal to $1$. Then this can be used to decode a $\left(U+V\mid V\right)$ code in the following way again under the assumption that we know for each bit $i$ of the codeword $(\mathbf{u}+\mathbf{v},\mathbf{v})$ that has been sent the probability that it is equal to $1$ given the received symbol $y_i$ for it. We number the positions of the $\left(U+V\mid V\right)$ code from 0 to $2n-1$ and assume that these probabilities are stored in an array $p[0],\dots,p[2n-1]$. We view $\mathbf{u}$ and $\mathbf{v}$ as arrays of length $n$. We assume that the received word is given by the array $y[0],\dots,y[2n-1]$. From our assumption, we know that

$$\mathbf{prob}(u[i]+v[i]=1\vert y[i]) = p[i]$$ (1)

$$\mathbf{prob}(v[i]=1\vert y[i+n]) = p[i+n]$$ (2)

We can use now the lecture on polar codes to deduce that

$$\mathbf{prob}(u[i]=1\vert y[i],y[i+n]) = \frac{1-(1-2p[i])(1-2p[i+n])}{2}$$

We can decode $U$ by using these probabilities. Once we know $\mathbf{u}$ we can use the lecture on polar codes to deduce that

$$\mathbf{prob}(v[i]=1\vert y[i],y[i+n],u[i]) = \frac{p[i]p[i+n]}{p[i]p[i+n]+(1-p[i])(1-p[i+n])} u[i]=0$$

$$\mathbf{prob}(v[i]=1\vert y[i],y[i+n],u[i]) = \frac{(1-p[i])p[i+n]}{(1-p[i])p[i+n]+p[i](1-p[i+n])} u[i]=1$$

This can be used to decode the $\left(U+V\mid V\right)$ code as follows.

The issue is now: how can we decode $U$ and $V$ ? If $U$ and $V$ were of length $1$, then the answer would be easy. For $U$ there are two cases to consider. Either $U$ is the constant code, say $U=\{0\}$ and then DecodeU would just return 0 or $U={0,1}$ and then DecodeU $(\mathbf{p})$ would return 0 if $p[0]<\frac{1}{2}$ and $1$ otherwise. The recursive $\left(U+V\mid V\right)$ structure of a polar code leads in a natural way to a recursive decoding algorithm based on these considerations. One uses here a table $\mathbf{p}[0..n-1][0..2^n-1]$ storing all the probabilities that are computed during the decoding process, where

$$n =$$ number of layers of the polar code

$$2^n =$$ length of the polar code

$$\mathbf{p}[n][i] = \mathbf{prob}(x_i=1\vert y_1)$$

$$\mathbf{p}[t][i] = i t=1 t <n$$

where the auxiliary functions are defined as

Here $\mathbf{z}$ is a table of length $2^n$ where the $2^n-k$ positions fixed to 0 at the beginning of the encoding process are also fixed to 0 in $\mathbf{z}$ and the other $k$ positions (where information was fed in during the encoding process) take the value $-1$. Decoding is performed by using the following function with the call Decode$(0,2^n,n)$.

Implement this function in Java and verify that the decoding is succesful most of the time for the polar code of length $8$ that you have found in the previous question when codewords are sent over a binary symmetric channel of crossover probability $p=0.06$.