Successive Cancellation Sampling Decoder: An Attempt to Analyze List Decoding Theoretically
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913363858030592 |
|---|---|
| author | Wang, Hsin-Po Guruswami, Venkatesan |
| author_facet | Wang, Hsin-Po Guruswami, Venkatesan |
| contents | 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 $a$ agents to any list decoder with list size $\ell$, we can prove that the error probability of the former is at most $\ell/ae$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_16373 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Successive Cancellation Sampling Decoder: An Attempt to Analyze List Decoding Theoretically Wang, Hsin-Po Guruswami, Venkatesan Information Theory 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 $a$ agents to any list decoder with list size $\ell$, we can prove that the error probability of the former is at most $\ell/ae$ 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. |
| title | Successive Cancellation Sampling Decoder: An Attempt to Analyze List Decoding Theoretically |
| topic | Information Theory |
| url | https://arxiv.org/abs/2405.16373 |