# Explicit Constructions of Two-Dimensional Reed-Solomon Codes in High Insertion and Deletion Noise Regime

**Authors:** Tai Do Duc, Shu Liu, Ivan Tjuawinata, Chaoping Xing  
**arXiv:** [1909.03426](https://arxiv.org/abs/1909.03426)  
**Date:** 2019-09-08  
**Summary page:** https://www.summarizepaper.com/en/paper/1909.03426v2/

## Key points

- The paper addresses insertion and deletion errors in communication systems
- Reed-Solomon codes are simple, well-structured, and capable of list-decoding
- Guruswami-Sudan decoding algorithm can correct deletions in the insdel metric
- Two families of 2-dimensional Reed-Solomon codes are presented with improved error correction capabilities for insdel errors
- The first construction has asymptotic error correction capability up to its length
- The second construction offers exact error correction capability up to its length
- Both constructions improve upon previous constructions with only logarithmic error correction capabilities
- These new constructions provide more efficient and reliable solutions for addressing insdel errors in communication systems.

## Summary

The paper titled "Explicit Constructions of Two-Dimensional Reed-Solomon Codes in High Insertion and Deletion Noise Regime" by Tai Do Duc, Shu Liu, Ivan Tjuawinata, and Chaoping Xing addresses the issue of insertion and deletion (insdel) errors in communication systems. These errors occur when positional information is lost in a message, leading to synchronization errors. Reed-Solomon codes have gained significant interest due to their simplicity in encoding, well-structuredness, and list-decoding capability in the classical setting. This interest extends to the insdel metric setting as well. The Guruswami-Sudan decoding algorithm can be used to provide a deletion correcting algorithm in the insdel metric. This paper presents two families of 2-dimensional Reed-Solomon codes that have improved error correction capabilities for addressing insdel errors in communication systems. The first construction provides an asymptotic error correction capability up to its length while the second construction offers an exact error correction capability up to its length. Both constructions improve upon previously known constructions whose insdel error correction capabilities were only logarithmic on the code length. By achieving asymptotic or exact error correction capabilities up to their lengths, these new constructions offer more efficient and reliable solutions for addressing insdel errors in communication systems. Overall, this paper provides valuable insights and explicit constructions of Reed-Solomon codes that can effectively handle insdel errors, contributing to the advancement of error correcting capabilities in communication systems.