Parallelism Versus Latency in Simplified Successive-Cancellation Decoding of Polar Codes
Seyyed Ali Hashemi, Marco Mondelli, Arman Fazeli, Alexander Vardy, J.M. Cioffi, Andrea J. Goldsmith · IEEE Transactions on Wireless Communications · 2021
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.