Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.01984 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917911216521216 |
|---|---|
| author | Riasat, Samin Mahdavifar, Hessam |
| author_facet | Riasat, Samin Mahdavifar, Hessam |
| contents | We propose an efficient algorithm to find a Reed-Solomon (RS) codeword at a distance within the covering radius of the code from any point in its ambient Hamming space. To the best of the authors' knowledge, this is the first attempt of its kind to solve the covering problem for RS codes. The proposed algorithm leverages off-the-shelf decoding methods for RS codes, including the Berlekamp-Welch algorithm for unique decoding and the Guruswami-Sudan algorithm for list decoding. We also present theoretical and numerical results on the capabilities of the proposed algorithm and, in particular, the average covering radius resulting from it. Our numerical results suggest that the overlapping Hamming spheres of radius close to the Guruswami-Sudan decoding radius centered at the codewords cover most of the ambient Hamming space. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_01984 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Covering Using Reed--Solomon Codes Riasat, Samin Mahdavifar, Hessam Information Theory Signal Processing 94B75 We propose an efficient algorithm to find a Reed-Solomon (RS) codeword at a distance within the covering radius of the code from any point in its ambient Hamming space. To the best of the authors' knowledge, this is the first attempt of its kind to solve the covering problem for RS codes. The proposed algorithm leverages off-the-shelf decoding methods for RS codes, including the Berlekamp-Welch algorithm for unique decoding and the Guruswami-Sudan algorithm for list decoding. We also present theoretical and numerical results on the capabilities of the proposed algorithm and, in particular, the average covering radius resulting from it. Our numerical results suggest that the overlapping Hamming spheres of radius close to the Guruswami-Sudan decoding radius centered at the codewords cover most of the ambient Hamming space. |
| title | Efficient Covering Using Reed--Solomon Codes |
| topic | Information Theory Signal Processing 94B75 |
| url | https://arxiv.org/abs/2502.01984 |