2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | C.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
