Optimally Decoding Two-Dimensional Reed-Solomon Codes Against Deletion Errors

2024/12/30 by Shubhransh Singhvi, Singhvi, Shubhransh · 1 citation
Computer Science · #Coding theory and cryptography #FOS: Computer and information sciences #Information Theory (cs.IT) #Quantum Computing Algorithms and Architecture #Quantum-Dot Cellular Automata

paper · pdf · doi:10.48550/arxiv.2412.20771

openalex publication_date 2024/12/30 · openalex created_date 2025/01/01 · openalex updated_date 2026/07/28

Abstract

Constructing Reed-Solomon (RS) codes that can correct insertion and deletion (ins-del) errors has been the focus of several recent studies. However, efficient decoding algorithms for such codes have received less attention and remain a significant open problem. In this work, we take a first step toward addressing this problem by designing a decoding algorithm for the case of 2-dimensional RS codes that can correct deletions up to the half-Singleton bound and is optimal in terms of field operations.

Cited by

• Decoding Insertions/Deletions via List Recovery

Related

• Reed-Solomon Codes Against Insertions and Deletions: Full-Length and Rate-1/2 Codes
• Optimal Two-Dimensional Reed--Solomon Codes Correcting Insertions and Deletions
• Explicit Constructions of Two-Dimensional Reed-Solomon Codes in High Insertion and Deletion Noise Regime
• Reed Solomon Codes Against Adversarial Insertions and Deletions
• Improved Singleton bound on insertion-deletion codes and optimal constructions