Explicit Constructions of Two-Dimensional Reed-Solomon Codes in High Insertion and Deletion Noise Regime
Autor: | Shu Liu, Chaoping Xing, Ivan Tjuawinata, Tai Do Duc |
---|---|
Rok vydání: | 2021 |
Předmět: |
FOS: Computer and information sciences
Computer science Computer Science - Information Theory Information Theory (cs.IT) Singleton bound 020206 networking & telecommunications Data_CODINGANDINFORMATIONTHEORY 02 engineering and technology Library and Information Sciences Upper and lower bounds Computer Science Applications Reed–Solomon error correction Encoding (memory) Synchronization (computer science) Metric (mathematics) 0202 electrical engineering electronic engineering information engineering Code (cryptography) Hardware_ARITHMETICANDLOGICSTRUCTURES Algorithm Decoding methods Information Systems |
Zdroj: | IEEE Transactions on Information Theory. 67:2808-2820 |
ISSN: | 1557-9654 0018-9448 |
Popis: | Insertion and deletion (insdel for short) errors are synchronization errors in communication systems caused by the loss of positional information in the message. Reed-Solomon codes have gained a lot of interest due to its encoding simplicity, well structuredness and list-decoding capability in the classical setting. This interest also translates to the insdel metric setting, as the Guruswami-Sudan decoding algorithm can be utilized to provide a deletion correcting algorithm in the insdel metric. Nevertheless, there have been few studies on the insdel error-correcting capability of Reed-Solomon codes. Our main contributions in this article are explicit constructions of two families of 2-dimensional Reed-Solomon codes with insdel error-correcting capabilities asymptotically reaching those provided by the Singleton bound. The first construction gives a family of Reed-Solomon codes with insdel error-correcting capability asymptotic to its length. The second construction provides a family of Reed-Solomon codes with an exact insdel error-correcting capability up to its length. Both our constructions improve the previously known construction of 2-dimensional Reed-Solomon codes whose insdel error-correcting capability is only logarithmic on the code length. |
Databáze: | OpenAIRE |
Externí odkaz: |