Consider the problem of constructing a polar code of block length $N$ for the transmission over a given channel $W$. Typically this requires to compute the reliability of all the $N$ synthetic channels and then to include those that are sufficiently reliable. However, we know from [1], [2] that there is a partial order among the synthetic channels. Hence, it is natural to ask whether we can exploit it to reduce the computational burden of the construction problem. #R##N#We show that, if we take advantage of the partial order [1], [2], we can construct a polar code by computing the reliability of roughly a fraction $1/\log^{3/2} N$ of the synthetic channels. In particular, we prove that $N/\log^{3/2} N$ is a lower bound on the number of synthetic channels to be considered and such a bound is tight up to a multiplicative factor $\log\log N$. This set of roughly $N/\log^{3/2} N$ synthetic channels is universal, in the sense that it allows one to construct polar codes for any $W$, and it can be computed by solving a maximum matching problem on a bipartite graph. #R##N#Our proof technique consists of reducing the construction problem to the problem of computing the maximum cardinality of a chain and of an antichain for a suitable partially ordered set. As such, this method is general and it can be used to further improve the complexity of the construction problem in case a new partial order on the synthetic channels of polar codes is discovered.
['Marco Mondelli', 'S. Hamed Hassani', 'Rüdiger L. Urbanke']
Construction of Polar Codes with Sublinear Complexity