and storing the information bits in the remaining entries. Codeword $\mathbf{d} = [d_0,d_1,\ldots,d_{N-1}]$ is then calculated as $$\mathbf{d} = \mathbf{u} \cdot \mathbf{G_N}\ \text{.} \label{eq:polarGen}$$ This matrix multiplication can be performed by processing multiple $\mathbf{G_2}$ matrix multiplications in parallel, reducing the encoding complexity to $\mathcal{O}(log_2(N))$. In fact, thanks to the recursive structure of $\mathbf{G_N}$, the decoding can be performed in $log_2(N)$ steps, each one composed by $N/2$ identical basic polarization kernels. Figure \[figG8\] shows the structure of the encoder of a polar code of length $N=8$; moreover, it details the erasure probabilities of the synthetic BECs when the code is designed for a BEC of erasure probability $\delta = 1/2$, along with the frozen set $\mathcal{F} = \{ 0,1,2,4 \}$ obtained for a code of dimension $K=4$. This structure is used to encode message $\mathbf{c}=[1,0,1,1]$ in $n=3$ steps with the assistance of input vector $\mathbf{u} = [0,0,0,1,0,0,1,1]$ to obtain codeword $\mathbf{d} = [1,0,1,0,0,1,0,1]$.

Decoding
--------

In [@arikan], the decoding algorithm native to polar codes, called successive cancellation (SC), has been proposed as well. It can be represented as a depth-first binary tree search with priority to the left branch, where the leaf nodes are the $N$ bits to be estimated, and 