Polar Codes With Higher-Order Memory

Abstract

We introduce the design of a set of code sequences $\{{\mathcal{C}}_n^{(m)}:n\ge 1,m\ge 1\}$, with memory order $m$ and code-length $N=O({\varphi }^n)$, where $\varphi \in (1,2]$ is the largest real root of the polynomial equation $F(m,\rho )={\rho }^m-{\rho }^{m-1}-1$ and $\varphi$ is decreasing in $m$. $\{{\mathcal{C}}_n^{(m)}\}$ is based on the channel polarization idea, where $\{{\mathcal{C}}_n^{(1)}\}$ coincides with the polar codes presented by Arıkan and can be encoded and decoded with complexity $O(N\log N)$. $\{{\mathcal{C}}_n^{(m)}\}$ achieves the symmetric capacity, $I(W)$, of an arbitrary binary-input, discrete-output memoryless channel, $W$, for any fixed $m$ and its encoding and decoding complexities decrease with growing $m$. We obtain an achievable bound on the probability of block-decoding error, $P_e$, of $\{{\mathcal{C}}_n^{(m)}\}$ and showed that $P_e=O(2^{-N^{\beta }})$ is achievable for $\beta <\frac{\varphi -1}{1+m(\varphi -1)}$.

arXiv comment15 pages, 7 figures