Earlier Version

Construction of polar codes with sublinear complexity

M. Mondelli, S.H. Hassani, R. Urbanke, in:, 2017 IEEE International Symposium on Information Theory , IEEE, 2017, pp. 1853–1857.


Conference Paper | Published | English
Author
Mondelli, MarcoIST Austria ; Hassani, S. Hamed; Urbanke, Rudiger
Abstract
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. 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 N/ log 3/2 N synthetic channels. Such a set of 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 in 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 new partial order on the synthetic channels of polar codes is discovered.
Publishing Year
Date Published
2017-06-15
Proceedings Title
2017 IEEE International Symposium on Information Theory
Page
1853-1857
Conference
ISIT: International Symposium on Information Theory
Conference Location
Aachen, Germany
Conference Date
2017-06-25 – 2017-06-30
eISSN
IST-REx-ID

Cite this

Mondelli M, Hassani SH, Urbanke R. Construction of polar codes with sublinear complexity. In: 2017 IEEE International Symposium on Information Theory . IEEE; 2017:1853-1857. doi:10.1109/isit.2017.8006850
Mondelli, M., Hassani, S. H., & Urbanke, R. (2017). Construction of polar codes with sublinear complexity. In 2017 IEEE International Symposium on Information Theory (pp. 1853–1857). Aachen, Germany: IEEE. https://doi.org/10.1109/isit.2017.8006850
Mondelli, Marco, S. Hamed Hassani, and Rudiger Urbanke. “Construction of Polar Codes with Sublinear Complexity.” In 2017 IEEE International Symposium on Information Theory , 1853–57. IEEE, 2017. https://doi.org/10.1109/isit.2017.8006850.
M. Mondelli, S. H. Hassani, and R. Urbanke, “Construction of polar codes with sublinear complexity,” in 2017 IEEE International Symposium on Information Theory , Aachen, Germany, 2017, pp. 1853–1857.
Mondelli M, Hassani SH, Urbanke R. 2017. Construction of polar codes with sublinear complexity. 2017 IEEE International Symposium on Information Theory . ISIT: International Symposium on Information Theory 1853–1857.
Mondelli, Marco, et al. “Construction of Polar Codes with Sublinear Complexity.” 2017 IEEE International Symposium on Information Theory , IEEE, 2017, pp. 1853–57, doi:10.1109/isit.2017.8006850.
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

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1612.05295

Search this title in

Google Scholar
ISBN Search