All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD6-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.