|Hardness of Successive-Cancellation Decoding of Linear Codes
|Arman Fazeli, Alexander Vardy, Hanwen Yao, University of California, San Diego, United States
|C.7: Polar Codes II
|Coding for Communications
|Click here to download the manuscript
|Click here to watch in the Virtual Symposium
|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.