All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD5-S6-T2.2
Paper Title Parallelism versus Latency in Simplified Successive-Cancellation Decoding of Polar Codes
Authors Seyyed Ali Hashemi, Stanford University, United States; Marco Mondelli, Institute of Science and Technology (IST) Austria, Austria; Arman Fazeli, Alexander Vardy, University of California San Diego, United States; John Cioffi, Stanford University, United States; Andrea Goldsmith, Princeton University, United States
Session D5-S6-T2: Polar Codes: Successive Cancellation Decoding
Chaired Session: Friday, 16 July, 23:40 - 00:00
Engagement Session: Saturday, 17 July, 00:00 - 00:20
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(N^{1-1/u} + N/P log2 log2(N/P)), where N is the block length of the code and u 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=N/2, the latency of SSC decoding is O(N^{1-1/u}), 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 log2 log2 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 log2 log2 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/u}. The tightness of our bound on SSC decoding latency and the applicability of the foregoing results is validated through extensive simulations.