An Analysis of RPA Decoding of Reed-Muller Codes Over the BSC
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_ | 1866918032765353984 |
|---|---|
| author | Rameshwar, V. Arvind Lalitha, V. |
| author_facet | Rameshwar, V. Arvind Lalitha, V. |
| contents | In this paper, we revisit the Recursive Projection-Aggregation (RPA) decoder, of Ye and Abbe (2020), for Reed-Muller (RM) codes. Our main contribution is an explicit upper bound on the probability of incorrect decoding, using the RPA decoder, over a binary symmetric channel (BSC). Importantly, we focus on the events where a \emph{single} iteration of the RPA decoder, in each recursive call, is sufficient for convergence. Key components of our analysis are explicit estimates of the probability of incorrect decoding of first-order RM codes using a maximum likelihood (ML) decoder, and estimates of the error probabilities during the aggregation phase of the RPA decoder. Our results allow us to show that for RM codes with blocklength $N = 2^m$, the RPA decoder can achieve vanishing error probabilities, in the large blocklength limit, for RM orders that grow roughly logarithmically in $m$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_08129 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An Analysis of RPA Decoding of Reed-Muller Codes Over the BSC Rameshwar, V. Arvind Lalitha, V. Information Theory In this paper, we revisit the Recursive Projection-Aggregation (RPA) decoder, of Ye and Abbe (2020), for Reed-Muller (RM) codes. Our main contribution is an explicit upper bound on the probability of incorrect decoding, using the RPA decoder, over a binary symmetric channel (BSC). Importantly, we focus on the events where a \emph{single} iteration of the RPA decoder, in each recursive call, is sufficient for convergence. Key components of our analysis are explicit estimates of the probability of incorrect decoding of first-order RM codes using a maximum likelihood (ML) decoder, and estimates of the error probabilities during the aggregation phase of the RPA decoder. Our results allow us to show that for RM codes with blocklength $N = 2^m$, the RPA decoder can achieve vanishing error probabilities, in the large blocklength limit, for RM orders that grow roughly logarithmically in $m$. |
| title | An Analysis of RPA Decoding of Reed-Muller Codes Over the BSC |
| topic | Information Theory |
| url | https://arxiv.org/abs/2412.08129 |