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.


Arman Fazeli

University Of California San Diego

Alexander Vardy

University of California, San Diego

Hanwen Yao

University Of California San Diego
Private Conversation

Reach out to the speaker privately

Questions & Answers

Post a publicly available question

Questions Asked
Representation of linear codes as polar codes with dynamic frozen symbols indeed enables SCL decoding to be used. However, list size needed to obtain reasonable performance strongly depends on the structure of freezing constraints. Namely, if all codewords of the considered code can be represented as evaluation vectors of polynomials f\in GF(2)[x_0,...,x_{m-1}), then the successive cancellation decoding error probability of the code quickly decreases with SNR, and SCL decoding with small list size provides good performance. Polar, extended BCH and Reed-Muller codes were shown to have particularly nice structure of the dynamic freezing constraints. Do you know any other classes of codes with this property? [1] Trifonov, P.; Miloslavskaya, V. Polar subcodes. IEEE Journal on Selected Areas in Communications, 34(2):254-266. February 2016
Asked by Peter Trifonov - 2201 on Jun 20, 2020. 4 people subscribed to this question.
Peter, thank you for your comment. Indeed, for an arbitrary rate-profile, one may need to pick a large list-size in SCL decoding in order to achieve a reasonable error performance. We are not aware of any families of codes other than those you mention in your comment for which SCL performs well with small list sizes. Perhaps PAC codes, as discussed in another paper in this session :)
Answered by Arman Fazeli - 2124 on Jun 26, 2020
A correction for above question: ...as evaluation vectors of polynomials f\in GF(2)[x_0,...,x_{m-1}) of sufficiently low degree
Asked by Peter Trifonov - 2201 on Jun 20, 2020. 3 people subscribed to this question.

No answers yet!

Session Chair

Ido Tal

Technion - Israel Institute of Technology