List Decoding of Polar Codes: How Large Should the List Be to Achieve ML Decoding?

Abstract

Successive-cancellation list (SCL) decoding is a widely used and studied decoding algorithm for polar codes. For short blocklengths, empirical evidence shows that SCL decoding with moderate list sizes (say,$L \leq 32$) closely matches the performance of maximum-likelihood (ML) decoding. Hashemi et al. proved that on the binary erasure channel (BEC), SCL decoding actually coincides with ML decoding for list sizes$L \geq 2^{\gamma}$, where$\gamma$is a new parameter we call the mixing factor. Loosely speaking, the mixing factor counts the number of information bits mixed-in among the frozen bits; more precisely$\gamma=\vert\{i\in \mathcal{F}^{c}:i\leq \max\{\mathcal{F}\}\}\vert$, where$\mathcal{F}\subset [n]$denotes the set of frozen indices. Herein, we extend the aforementioned result of Hashemi et al. from the BEC to arbitrary binary-input memoryless symmetric channels. Our proof is based on capturing all$2^{\gamma}$decoding paths that correspond to the$\gamma$information bits appearing before the last frozen bit, and then finding the most-likely extension for each of these paths efficiently using a nearest coset decoding algorithm introduced herein. Furthermore, we present a hybrid successive-cancellation list (H -SCL) decoding algorithm, which is a hybrid between conventional SCL decoding and nearest coset decoding. We believe that the hybrid algorithm can outperform the conventional SCL decoder with lower decoding complexity.