| Session: | 1.1.8 - List Decoding of Codes |
| Session Time: | Monday, July 10, 09:40 - 11:00 |
| Paper Time: | Monday, July 10, 09:40 - 10:00 |
| Title: |
List decoding of Reed-Muller codes up to the Johnson bound with almost linear complexity |
| Authors: |
Ilya Dumer; University of California, Riverside | | |
| | Grigory Kabatiansky; Institute for Information Transmission Problems | | |
| | Cedric Tavernier; THALES Communications | | |
| Abstract: |
A new deterministic list decoding algorithm is proposed for general Reed-Muller codes $RM(s,m)$ of length $n=2^{m}$ and distance $d=2^{m-s}$. Given $n$ and $d$, the algorithm performs beyond the bounded distance threshold of $d/2$ and has a low complexity order of $nm^{s-1}$ for any decoding radius $T$ that is less than the Johnson bound. |
