Polar codes with higher-order memory

We introduce a construction of a set of code sequences $\{C_n^{(m)}:\: n\ge 1, m\ge 1\}$ with memory order $m$ and code length $N(n)$. $\{C_n^{(m)}\}$ is a generalization of polar codes presented by Arıkan in [1], where the encoder mapping with length $N(n)$ is obtained recursively from the encoder mappings with lengths $N(n-1)$ and $N(n-m)$, and $\{C_n^{(m)}\}$ coincides with the original polar codes when $m = 1$. We show that $\{C_n^{(m)}\}$ achieves the symmetric capacity $I(W)$ of an arbitrary binary-input, discrete-output memoryless channel $W$ for any fixed $m$. We also obtain an upper bound on the probability of block-decoding error $P_e$ of $\{C_n^{(m)}\}$ and show that $P_e=O (2^{-N^\beta})$ is achievable for $\beta<1/[1+m(\phi-1)]$, where $\phi\in (1;2]$ is the largest real root of the polynomial $F(m,\rho)=\rho^m-\rho^{m-1}-1$. The encoding and decoding complexities of $\{C_n^{(m)}\}$ decrease with increasing $m$, which proves the existence of new polar coding schemes that have lower complexity than Arıkan's construction.