TY - GEN

T1 - Parallelism versus Latency in Simplified Successive-Cancellation Decoding of Polar Codes

AU - Hashemi, Seyyed Ali

AU - Mondelli, Marco

AU - Fazeli, Arman

AU - Vardy, Alexander

AU - Cioffi, John

AU - Goldsmith, Andrea

N1 - Funding Information:
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.
Publisher Copyright:
© 2021 IEEE.

PY - 2021/7/12

Y1 - 2021/7/12

N2 - 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\left(N^{1-1/\mu}+ \frac{N}{P}\log_{2}\log_{2}\frac{N}{P}\right), where N is the block length of the code and \mu 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=\frac{N}{2}, the latency of SSC decoding is O\left(N^{1-1/\mu}\right), 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(N\, \log_{2}\log_{2}N). The multiplicative constant is also calculated: we show that the latency of SSC decoding when P=1 is given by (2+o(1))N\, \log_{2}\log_{2}N. Third, in a semi-parallel implementation, the smallest P that gives the same latency as that of the fully-parallel implementation is P=N^{1/\mu}. The tightness of our bound on SSC decoding latency and the applicability of the foregoing results is validated through extensive simulations.

AB - 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\left(N^{1-1/\mu}+ \frac{N}{P}\log_{2}\log_{2}\frac{N}{P}\right), where N is the block length of the code and \mu 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=\frac{N}{2}, the latency of SSC decoding is O\left(N^{1-1/\mu}\right), 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(N\, \log_{2}\log_{2}N). The multiplicative constant is also calculated: we show that the latency of SSC decoding when P=1 is given by (2+o(1))N\, \log_{2}\log_{2}N. Third, in a semi-parallel implementation, the smallest P that gives the same latency as that of the fully-parallel implementation is P=N^{1/\mu}. The tightness of our bound on SSC decoding latency and the applicability of the foregoing results is validated through extensive simulations.

UR - http://www.scopus.com/inward/record.url?scp=85115099401&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85115099401&partnerID=8YFLogxK

U2 - 10.1109/ISIT45174.2021.9518153

DO - 10.1109/ISIT45174.2021.9518153

M3 - Conference contribution

AN - SCOPUS:85115099401

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2369

EP - 2374

BT - 2021 IEEE International Symposium on Information Theory, ISIT 2021 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2021 IEEE International Symposium on Information Theory, ISIT 2021

Y2 - 12 July 2021 through 20 July 2021

ER -