Optimal Two-Dimensional Reed--Solomon Codes Correcting Insertions and Deletions
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909160233238528 |
|---|---|
| author | Con, Roni Shpilka, Amir Tamo, Itzhak |
| author_facet | Con, Roni Shpilka, Amir Tamo, Itzhak |
| contents | Constructing Reed--Solomon (RS) codes that can correct insertions and deletions (insdel errors) has been considered in numerous recent works. For the special case of two-dimensional RS-codes, it is known [CST23] that an $[n,2]_q$ RS-code that can correct from $n-3$ insdel errors satisfies that $q=Ω(n^3)$. On the other hand, there are several known constructions of $[n,2]_q$ RS-codes that can correct from $n-3$ insdel errors, where the smallest field size is $q=O(n^4)$. In this short paper, we construct $[n,2]_q$ Reed--Solomon codes that can correct $n-3$ insdel errors with $q=O(n^3)$, thereby resolving the minimum field size needed for such codes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_02771 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Optimal Two-Dimensional Reed--Solomon Codes Correcting Insertions and Deletions Con, Roni Shpilka, Amir Tamo, Itzhak Information Theory Constructing Reed--Solomon (RS) codes that can correct insertions and deletions (insdel errors) has been considered in numerous recent works. For the special case of two-dimensional RS-codes, it is known [CST23] that an $[n,2]_q$ RS-code that can correct from $n-3$ insdel errors satisfies that $q=Ω(n^3)$. On the other hand, there are several known constructions of $[n,2]_q$ RS-codes that can correct from $n-3$ insdel errors, where the smallest field size is $q=O(n^4)$. In this short paper, we construct $[n,2]_q$ Reed--Solomon codes that can correct $n-3$ insdel errors with $q=O(n^3)$, thereby resolving the minimum field size needed for such codes. |
| title | Optimal Two-Dimensional Reed--Solomon Codes Correcting Insertions and Deletions |
| topic | Information Theory |
| url | https://arxiv.org/abs/2311.02771 |