| Paper ID | D6-S5-T4.3 |
| Paper Title |
Non-binary Codes for Correcting a Burst of at Most 2 Deletions |
| Authors |
Shuche Wang, University of Virginia, United States; Jin Sima, California Institute of Technology, United States; Farzad Farnoud, University of Virginia, United States |
| Session |
D6-S5-T4: Array & Burst Deletion-Correcting Codes |
| Chaired Session: |
Monday, 19 July, 23:20 - 23:40 |
| Engagement Session: |
Monday, 19 July, 23:40 - 00:00 |
| Abstract |
The problem of correcting deletions has recently received significantly increased attention, partly because of the prevalence of these errors in DNA data storage. In this paper, we study the problem of correcting a burst of at most two deletions in non-binary sequences. The problem was first studied for binary sequences by Levenshtein, who presented a construction with optimal redundancy. We propose a non-binary code correcting a burst of at most 2 deletions for $q$-ary alphabets with redundancy $\log n + O(\log q \log\log n)$ bits, for even $q$. Further, we construct codes with lower redundancy to correct a burst of exactly 2 deletions caused by a single deletion in alternating sequences that arise in terminator-free enzymatic DNA synthesis.
|
