Polar Codes with Higher-Order Memory

Abstract

We introduce a construction of a set of code sequences {C-n((m)) : n 1, m 1} with memory order m and code length N(n). {C-n((m))} is a generalization of polar codes presented by Arkan 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 Pe=O(2-N) is achievable for < 1/[1+m(phi - 1)], where phi (1, 2] is the largest real root of the polynomial F(m, ) = (m) - (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 Arkan's construction.