Polar coding tutorial

Objectives of this tutorial:

• Explain polar coding as a black box
• Explain trade-offs between parameters
• Provide links to useful resources

Polar coding overview

Polar codes are error-correcting codes, which are able to achieve the capacity of binary-input memoryless symmetric (BMS) channels. This means that one can transmit at the highest possible rate over that class of channels. In addition, the encoding and decoding operations can be performed with low complexity, thanks to recursive techniques.
Formally, a specific polar code is fully defined by a 4-tuple (N, R, A, $u_A$) where:

• N is the block length, i.e. the total number of bits transmitted over the channel.
• R is the rate, R$\in[0, 1]$, i.e. the amount of information contained in one bit.
• A is the information set, $A\subset\{1,...,N\}$, i.e. the set of positions which contains the information bits.
• $u_{A^c}$ are the frozen bits, $u_{A^c}\in\{0,1\}^{N(1- R)}$ , i.e. bits which have fixed values, shared between the encoder and the decoder.

High-level transmission scheme

The transmission process works as follow:

• We must first choose the information set A. Note that the choice of A depends on the particular channel over which transmission takes place, i.e. different channels yield different information sets.
• We then want to transmit $N R$ information bits contained in the vector $u_A$.
• $N(1- R)$ frozen bits contained in the vector $u_{A^c}$ are fixed.
• $u_{A_c}$ and $u_A$ are combined to obtain $u_1^N$.
• $u_1^N$ is encoded into $x_1^N$ using the polar recursive encoding. This is a fast algorithm which allows to perform in O(N log N) the linear encoding $x_1^N = u_1^N G_N$, with $G_N = \begin{bmatrix} 1 & 0 \\ 1 & 0 \end{bmatrix}^{\otimes log_2 N}$ where $\otimes$ is the Kronecker product.
• $x_1^N$ is transmitted over the channel $W^N$ (which corresponds to N uses of the channel W), and $y_1^N$ is received.
• From $y_1^N$, the successive cancellation (SC) decoder produces $\hat{u}_1^N$, which is an estimate of $u_1^N$ (making use of the frozen bits values!). The complexity of this operation is O(N log N).
• Finally, only the components of $\hat{u}_1^N$ corresponding to information bits are kept, yielding $\hat{u}_A$.

Code

We provide a simple implementation in MATLAB, in order to complement the material referenced below.
The implementation contains a polar encoder-decoder pair for a binary erasure channel (BEC). Please start with the readme file as entry point.

Download zip

References and links

Polar codes have been introduced in:
[1] E. Arıkan, "Channel polarization: a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels", IEEE Trans. Inf. Theory, vol. 55, no. 7, pp. 3051-3073, July 2009.

An interactive demonstration of transmission schemes using polar coding can be found here.