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

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(N^{1-1/\mu })$
, 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(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.