Construction of polar codes with sublinear complexity

M. Mondelli, H. Hassani, R. Urbanke, IEEE 65 (2019) 2782–2791.

Journal Article | Published | English
Mondelli, MarcoIST Austria ; Hassani, Hamed; Urbanke, Rudiger
Consider the problem of constructing a polar code of block length N for a given transmission channel W. Previous approaches require one to compute the reliability of the N synthetic channels and then use only those that are sufficiently reliable. However, we know from two independent works by Schürch and by Bardet et al. that the synthetic channels are partially ordered with respect to degradation. Hence, it is natural to ask whether the partial order can be exploited to reduce the computational burden of the construction problem. We show that, if we take advantage of the partial order, 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 identified by solving a maximum matching problem on a bipartite graph. Our proof technique consists of reducing the construction problem to the problem of computing the maximum cardinality 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 refined partial order on the synthetic channels of polar codes is discovered.
Publishing Year
Date Published
Journal Title

Cite this

Mondelli M, Hassani H, Urbanke R. Construction of polar codes with sublinear complexity. IEEE. 2019;65(5):2782-2791. doi:10.1109/tit.2018.2889667
Mondelli, M., Hassani, H., & Urbanke, R. (2019). Construction of polar codes with sublinear complexity. IEEE. IEEE.
Mondelli, Marco, Hamed Hassani, and Rudiger Urbanke. “Construction of Polar Codes with Sublinear Complexity.” IEEE. IEEE, 2019.
M. Mondelli, H. Hassani, and R. Urbanke, “Construction of polar codes with sublinear complexity,” IEEE, vol. 65, no. 5. IEEE, pp. 2782–2791, 2019.
Mondelli M, Hassani H, Urbanke R. 2019. Construction of polar codes with sublinear complexity. IEEE. 65(5), 2782–2791.
Mondelli, Marco, et al. “Construction of Polar Codes with Sublinear Complexity.” IEEE, vol. 65, no. 5, IEEE, 2019, pp. 2782–91, doi:10.1109/tit.2018.2889667.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access


Marked Publications

Open Data IST Research Explorer


arXiv 1612.05295

Search this title in

Google Scholar