Polar coding gives rise to the first explicit family of codes that provably achieve capacity with efficient encoding and decoding for a wide range of channels. However, its performance at short block lengths under standard successive cancellation decoding is far from optimal. A well-known way to improve the performance of polar codes at short block lengths is CRC precoding followed by successive cancellation list decoding. This approach, along with various refinements thereof, has remained the state of the art in polar coding since it was first introduced in 2011. Last year, Arikan presented a new polar coding scheme, which he called polarization-adjusted convolutional (PAC) codes. Such PAC codes provide another dramatic improvement in performance as compared to CRC-aided list decoding. These codes are based primarily upon the following main ideas: replacing CRC precoding with convolutional precoding (under appropriate rate profiling) and replacing list decoding by sequential decoding. Arikan's simulation results show that PAC codes, resulting from the combination of these ideas, are quite close to finite-length lower bounds on the performance of any code under ML decoding. One of our main goals in this paper is to answer the following question: is sequential decoding essential for the superior performance of PAC codes? We show that similar performance can be achieved using list decoding when the list size $L$ is moderately large (say, $L \geq 128$). List decoding has distinct advantages over sequential decoding in certain scenarios, such as low-SNR regimes or situations where the worst-case complexity/latency is the primary constraint. Another objective is to provide some insights into the remarkable performance of PAC codes. We first observe that both sequential decoding and list decoding of PAC codes closely match ML decoding thereof. We then estimate the number of low weight codewords in PAC codes, using these estimates to approximate the union bound on their performance under ML decoding. These results indicate that PAC codes are superior to polar codes and Reed-Muller codes, and suggest that the goal of rate-profiling may be to optimize the weight distribution at low weights.


Hanwen Yao

University Of California San Diego

Arman Fazeli

University Of California San Diego

Alexander Vardy

University of California, San Diego
Private Conversation

Reach out to the speaker privately

Questions & Answers

Post a publicly available question

Questions Asked
Just a remark: it seems that much lower average decoding complexity can be obtained with another instance of sequential decoding, given in [1]. Indeed, Figure 1 there shows that the average complexity of sequential decoding converges to that of SCL decoding with list size 1 (i.e. SC decoding). [1] Trifonov, Peter. A score function for sequential decoding of polar codes. Proceedings of IEEE International Symposium on Information Theory, 2018
Asked by Peter Trifonov - 2201 on Jun 20, 2020. 3 people subscribed to this question.
Thanks for the comment with a pointer to your paper on the score function for sequential decoding. We agree that this approach may possibly lead to lower average decoding complexity. In our paper, we make no attempt to optimize either the codes or the sequential decoding algorithms. Rather, our goal was to follow Arıkan's work on PAC codes as closely as possible, and show that list-decoding is one reasonable alternative to Arıkan's approach.
Answered by Hanwen Yao - 2127 on Jun 25, 2020
Hanwen, thank you for the presentation! Is there a big gap in between SCL128 and PAC+list128? It will be nice to also give this comparison.
Asked by Alexey Frolov - 1559 on Jun 24, 2020. 1 person subscribed to this question.
2 Answers
Alexei, if we understand your question correctly, you are asking about L = 128 for the polar+CRC code (we show results with L = 32 for this code). We do not have simulation results for this setting at the ready, but will try to generate them soon. Intuitively, we believe the performance gap between this and PAC with L = 128 will still be significant.
Answered by Alexander Vardy - 1096 on Jun 25, 2020
Hi Alexei, we just got the simulation results. For polar+CRC with L=128, at SNR=3.00 we have FER=0.000535, and at SNR=3.50 we have SNR=0.000102. There is a clear gap between polar+CRC with L=128 and PAC with L=128. Sorry we can’t post the figure here, but we will be happy to email you the plot.
Answered by Hanwen Yao - 2127 on Jun 27, 2020

Session Chair

Ido Tal

Technion - Israel Institute of Technology