Technical Program

Paper Detail

Paper IDC.7.6
Paper Title Hardness of Successive-Cancellation Decoding of Linear Codes
Authors Arman Fazeli, Alexander Vardy, Hanwen Yao, University of California, San Diego, United States
Session C.7: Polar Codes II
Presentation Lecture
Track Coding for Communications
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract Successive-cancellation decoding has gained much renewed interest since the advent of polar coding a decade ago. For polar codes, successive-cancellation decoding can be accomplished in time $O(n \log n)$. However, the complexity of successive-cancellation decoding for other families of codes remains largely unexplored. Herein, we prove that successive-cancellation decoding of general binary linear codes is NP-hard. In order to establish this result, we reduce from maximum-likelihood decoding of linear codes, a well-known NP-complete problem. Unlike maximum-likelihood decoding, however, the successive-cancellation decoding problem depends on the choice of a generator matrix. Thus we further strengthen our result by showing that there exist codes for which successive-cancellation decoding remains hard for every possible choice of the generator matrix. On the other hand, we also observe that polynomial-time successive-cancellation decoding can be extended from polar codes to many other linear codes. Finally, we show that every binary linear code can be encoded as a polar code with dynamically frozen bits. This approach makes it possible to use list-decoding of polar codes in order to approximate the maximum-likelihood decoding performance of arbitrary codes.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!