An Optimal Sequence Reconstruction Algorithm for Reed-Solomon Codes
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917611709661184 |
|---|---|
| author | Singhvi, Shubhransh Con, Roni Kiah, Han Mao Yaakobi, Eitan |
| author_facet | Singhvi, Shubhransh Con, Roni Kiah, Han Mao Yaakobi, Eitan |
| contents | The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a scenario where the sender transmits a codeword from some codebook, and the receiver obtains $N$ noisy outputs of the codeword. We study the problem of efficient reconstruction using $N$ outputs that are each corrupted by at most $t$ substitutions. Specifically, for the ubiquitous Reed-Solomon codes, we adapt the Koetter-Vardy soft-decoding algorithm, presenting a reconstruction algorithm capable of correcting beyond Johnson radius. Furthermore, the algorithm uses $\mathcal{O}(nN)$ field operations, where $n$ is the codeword length. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_07754 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An Optimal Sequence Reconstruction Algorithm for Reed-Solomon Codes Singhvi, Shubhransh Con, Roni Kiah, Han Mao Yaakobi, Eitan Information Theory The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a scenario where the sender transmits a codeword from some codebook, and the receiver obtains $N$ noisy outputs of the codeword. We study the problem of efficient reconstruction using $N$ outputs that are each corrupted by at most $t$ substitutions. Specifically, for the ubiquitous Reed-Solomon codes, we adapt the Koetter-Vardy soft-decoding algorithm, presenting a reconstruction algorithm capable of correcting beyond Johnson radius. Furthermore, the algorithm uses $\mathcal{O}(nN)$ field operations, where $n$ is the codeword length. |
| title | An Optimal Sequence Reconstruction Algorithm for Reed-Solomon Codes |
| topic | Information Theory |
| url | https://arxiv.org/abs/2403.07754 |