| Paper ID | D4-S2-T2.2 |
| Paper Title |
List Decoding of Polar Codes: How Large Should the List Be to Achieve ML Decoding? |
| Authors |
Arman Fazeli, Alexander Vardy, Hanwen Yao, University of California, San Diego, United States |
| Session |
D4-S2-T2: Decoding and Optimality |
| Chaired Session: |
Thursday, 15 July, 22:20 - 22:40 |
| Engagement Session: |
Thursday, 15 July, 22:40 - 23:00 |
| 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 ≤ 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 ≥ 2^γ, where γ 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. 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^γ decoding paths that correspond to the 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.
|
