On the construction of polar codes

TLDR

Efficient construction of polar codes over binary memoryless symmetric channels is hampered by exponential complexity, but approximate evaluation of polarized channels can reduce this to linear complexity, as shown by Tal and Vardy. This paper aims to develop a framework for analyzing the complexity and accuracy of polar code construction algorithms. The framework extends Tal and Vardy’s approximate evaluation approach, enabling analysis of both existing and novel algorithms. Numerical and analytical results demonstrate that all but a vanishing fraction of good channels can be identified with almost linear complexity, up to a polylogarithmic factor.

Abstract

We consider the problem of efficiently constructing polar codes over binary memoryless symmetric (BMS) channels. The complexity of designing polar codes via an exact evaluation of the polarized channels to find which ones are "good" appears to be exponential in the block length. In [3], Tal and Vardy show that if instead the evaluation if performed approximately, the construction has only linear complexity. In this paper, we follow this approach and present a framework where the algorithms of [3] and new related algorithms can be analyzed for complexity and accuracy. We provide numerical and analytical results on the efficiency of such algorithms, in particular we show that one can find all the "good" channels (except a vanishing fraction) with almost linear complexity in block-length (except a polylogarithmic factor).