# Polar coding tutorial

Objectives of this tutorial:

• Explain polar coding as a black box
• 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 Fig. 1 - High-level transmission scheme, using polar encoding and successive cancellation (SC) decoding.

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.