Parallelism versus latency in simplified successive-cancellation decoding of polar codes

Hashemi SA, Mondelli M, Fazeli A, Vardy A, Cioffi J, Goldsmith A. 2021. Parallelism versus latency in simplified successive-cancellation decoding of polar codes. 2021 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory, 2369–2374.


Conference Paper | Published | English

Scopus indexed
Author
Hashemi, Seyyed Ali; Mondelli, MarcoIST Austria ; Fazeli, Arman; Vardy, Alexander; Cioffi, John; Goldsmith, Andrea
Department
Abstract
This paper characterizes the latency of the simplified successive-cancellation (SSC) decoding scheme for polar codes under hardware resource constraints. In particular, when the number of processing elements P that can perform SSC decoding operations in parallel is limited, as is the case in practice, the latency of SSC decoding is O(N1−1 μ+NPlog2log2NP), where N is the block length of the code and μ is the scaling exponent of polar codes for the channel. Three direct consequences of this bound are presented. First, in a fully-parallel implementation where P=N2 , the latency of SSC decoding is O(N1−1/μ) , which is sublinear in the block length. This recovers a result from an earlier work. Second, in a fully-serial implementation where P=1 , the latency of SSC decoding scales as O(Nlog2log2N) . The multiplicative constant is also calculated: we show that the latency of SSC decoding when P=1 is given by (2+o(1))Nlog2log2N . Third, in a semi-parallel implementation, the smallest P that gives the same latency as that of the fully-parallel implementation is P=N1/μ . The tightness of our bound on SSC decoding latency and the applicability of the foregoing results is validated through extensive simulations.
Publishing Year
Date Published
2021-09-01
Proceedings Title
2021 IEEE International Symposium on Information Theory
Acknowledgement
S. A. Hashemi is supported by a Postdoctoral Fellowship from the Natural Sciences and Engineering Research Council of Canada (NSERC) and by Huawei. M. Mondelli is partially supported by the 2019 Lopez-Loreta Prize. A. Fazeli and A. Vardy were supported in part by the National Science Foundation under Grant CCF-1764104.
Page
2369-2374
Conference
ISIT: International Symposium on Information Theory
Conference Location
Melbourne, Australia
Conference Date
2021-07-12 – 2021-07-20
ISSN
IST-REx-ID

Cite this

Hashemi SA, Mondelli M, Fazeli A, Vardy A, Cioffi J, Goldsmith A. Parallelism versus latency in simplified successive-cancellation decoding of polar codes. In: 2021 IEEE International Symposium on Information Theory. Institute of Electrical and Electronics Engineers; 2021:2369-2374. doi:10.1109/ISIT45174.2021.9518153
Hashemi, S. A., Mondelli, M., Fazeli, A., Vardy, A., Cioffi, J., & Goldsmith, A. (2021). Parallelism versus latency in simplified successive-cancellation decoding of polar codes. In 2021 IEEE International Symposium on Information Theory (pp. 2369–2374). Melbourne, Australia: Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/ISIT45174.2021.9518153
Hashemi, Seyyed Ali, Marco Mondelli, Arman Fazeli, Alexander Vardy, John Cioffi, and Andrea Goldsmith. “Parallelism versus Latency in Simplified Successive-Cancellation Decoding of Polar Codes.” In 2021 IEEE International Symposium on Information Theory, 2369–74. Institute of Electrical and Electronics Engineers, 2021. https://doi.org/10.1109/ISIT45174.2021.9518153.
S. A. Hashemi, M. Mondelli, A. Fazeli, A. Vardy, J. Cioffi, and A. Goldsmith, “Parallelism versus latency in simplified successive-cancellation decoding of polar codes,” in 2021 IEEE International Symposium on Information Theory, Melbourne, Australia, 2021, pp. 2369–2374.
Hashemi SA, Mondelli M, Fazeli A, Vardy A, Cioffi J, Goldsmith A. 2021. Parallelism versus latency in simplified successive-cancellation decoding of polar codes. 2021 IEEE International Symposium on Information Theory. ISIT: International Symposium on Information Theory, 2369–2374.
Hashemi, Seyyed Ali, et al. “Parallelism versus Latency in Simplified Successive-Cancellation Decoding of Polar Codes.” 2021 IEEE International Symposium on Information Theory, Institute of Electrical and Electronics Engineers, 2021, pp. 2369–74, doi:10.1109/ISIT45174.2021.9518153.
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 2012.13378

Search this title in

Google Scholar
ISBN Search