# 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.