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

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\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 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 our earlier work. Second, in a fully-serial implementation where $P=1$, the latency of SSC decoding scales as $O\left(N{\log }_2{\log }_{2}N\right)$. The multiplicative constant is also calculated: we show that the latency of SSC decoding when $P=1$ is given by $\left(2+o(1)\right)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.