Successive Cancellation Sampling Decoder: An Attempt to Analyze List Decoding Theoretically
Journal
2024 IEEE International Symposium on Information Theory (ISIT)
Part Of
IEEE International Symposium on Information Theory - Proceedings
Start Page
2412
End Page
2417
ISBN (of the container)
979-835038284-6
Date Issued
2024-07-07
Author(s)
Venkatesan Guruswami
Abstract
Successive cancellation list (SCL) decoders of polar codes excel in practical performance but pose challenges for theoretical analysis. Existing works either limit their scope to erasure channels or address general channels without taking advantage of soft information. In this paper, we propose the successive cancellation sampling (SCS) decoder. SCS hires iid “agents” to sample codewords using posterior probabilities. This makes it fully parallel and amenable for some theoretical analysis. As an example, when comparing SCS with agents to any list decoder with list size , we can prove that the error probability of the former is at most more than that of the latter. In this paper, we also describe how to adjust the “temperature” of agents. Warmer agents are less likely to sample the same codewords and hence can further reduce error probability.
Publisher
IEEE
Type
conference paper