# American Institute of Mathematical Sciences

February  2017, 11(1): 1-65. doi: 10.3934/amc.2017001

## Recursive descriptions of polar codes

 School of Electrical Engineering, Tel Aviv University, Ramat Aviv 69978 Israel

Received  February 2015 Revised  June 2016 Published  February 2017

Polar codes are recursive general concatenated codes. This property motivates a recursive formalization of the known decoding algorithms: Successive Cancellation, Successive Cancellation with Lists and Belief Propagation. Using such description allows an easy development of these algorithms for arbitrary polarizing kernels. Hardware architectures for these decoding algorithms are also described in a recursive way, both for Arıkan's standard polar codes and for arbitrary polarizing kernels.

Citation: Noam Presman, Simon Litsyn. Recursive descriptions of polar codes. Advances in Mathematics of Communications, 2017, 11 (1) : 1-65. doi: 10.3934/amc.2017001
##### References:

show all references

##### References:
A GCC representation of a polar code of length $\ell^n$ symbols constructed by a homogenous kernel according to Definition 1
Example 1's GCC representation (Arıkan's construction)
Representation of a polar code with kernel of $\ell = 2$ dimensions as a layered factor graph
Representation of a polar code with kernel of $\ell = 2$ dimensions as a layered factor graph (detailed version of Figure 3-recursion unfolded)
Normal factor graph representation of the $g(\cdot)$ block from Figures 3 and 4 for Arikan's $(u+v, v)$ construction
A GCC representation of the length $N=4^n$ bits mixed-kernels polar code $g^{(n)}(\cdot)$ described in Example 3
Decoding tree for $(u+v, v)$ polar code illustrating the decision space of the SC and SCL algorithms
Representation of SC as a sequential walk on a decoding tree
SCL ($L=4$) algorithm example of $(u+v, v)$ with $N=8$ bits (see Figure 7) illustrated on the right a decoding tree on the outer-codes of the structure ($\mathcal{C}_{0}, \mathcal{C}_{1}$). The left decoding tree expands each edge of the right tree into decoding-paths on the outer-codes of $\mathcal{C}_{0}$ and $\mathcal{C}_{1}$. The labels of the edges are the values of the outer-codes.
Normal factor graphs representations of polar codes kernels
Messages of BP algorithm
Normal factor graph representation for the first kernel of Example 4. This kernel is constructed by gluing inputs $u_{1}, u_2$ of the mapping defined by the generating matrix $\bf G$
$(u+v, v)$ polar code PE block
Blocks of the $(u+v, v)$ polar code decoders of length $N$ bits
Block diagram for the SC pipeline decoder
Block diagram for the SC line decoder
Block diagram for the limited parallelism line decoder
BP line decoder components definitions
Block diagram for the BP line decoder. Details of figure appear in Figures 20, 21 and 22 corresponding to sub-figures A, B and C respectively.
Block diagram for the BP line decoder (Figure 19) -zoom-in: Sub-figure A
Block diagram for the BP line decoder (Figure 19) -zoom-in: Sub-figure B
Block diagram for the BP line decoder (Figure 19) -zoom-in: Sub-figure C
Block definitions of SC line decoder for polar code of length $N$ based on a linear $\ell$ dimensions kernel with alphabet $F$
Routing tables for OP-MUX and OP-DEMUX in Figure 18
 $c^{(opMux)}, c^{(opDeMux)}$ $c^{(BPPE)}$ $\mu^{(in)}_0$ $\mu^{(in)}_1$ $\mu^{(out)}$ Equation $0$ $0$ $\mu^{(in)}_{x_1}$ $\mu^{(in)}_{u_1}$ $\mu_{e_1\rightarrow a_0}$ (45) $1$ $1$ $\mu^{(in)}_{x_0}$ $\mu^{(in)}_{u_0}$ $\mu_{a_0 \rightarrow e_1}$ (46) $2$ $1$ $\mu^{(in)}_{x_0}$ $\mu_{e_1\rightarrow a_0}$ $\mu_{u_0}^{(out)}$ (47) $3$ $0$ $\mu^{(in)}_{x_1}$ $\mu_{a_0\rightarrow e_1}$ $\mu_{u_1}^{(out)}$ (48) $4$ $1$ $\mu^{(in)}_{u_0}$ $\mu_{e_1\rightarrow a_0}$ $\mu_{x_0}^{(out)}$ (49) $5$ $0$ $\mu^{(in)}_{u_1}$ $\mu_{a_0\rightarrow e_1}$ $\mu_{x_1}^{(out)}$ (50) $6$ $0$ or $1$ $\mu^{(ext, in)}_0$ $\mu^{(ext, in)}_1$ $\mu^{(ext, out)}$ (80)
 $c^{(opMux)}, c^{(opDeMux)}$ $c^{(BPPE)}$ $\mu^{(in)}_0$ $\mu^{(in)}_1$ $\mu^{(out)}$ Equation $0$ $0$ $\mu^{(in)}_{x_1}$ $\mu^{(in)}_{u_1}$ $\mu_{e_1\rightarrow a_0}$ (45) $1$ $1$ $\mu^{(in)}_{x_0}$ $\mu^{(in)}_{u_0}$ $\mu_{a_0 \rightarrow e_1}$ (46) $2$ $1$ $\mu^{(in)}_{x_0}$ $\mu_{e_1\rightarrow a_0}$ $\mu_{u_0}^{(out)}$ (47) $3$ $0$ $\mu^{(in)}_{x_1}$ $\mu_{a_0\rightarrow e_1}$ $\mu_{u_1}^{(out)}$ (48) $4$ $1$ $\mu^{(in)}_{u_0}$ $\mu_{e_1\rightarrow a_0}$ $\mu_{x_0}^{(out)}$ (49) $5$ $0$ $\mu^{(in)}_{u_1}$ $\mu_{a_0\rightarrow e_1}$ $\mu_{x_1}^{(out)}$ (50) $6$ $0$ or $1$ $\mu^{(ext, in)}_0$ $\mu^{(ext, in)}_1$ $\mu^{(ext, out)}$ (80)

2018 Impact Factor: 0.879