2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | M.6.6 | ||
| Paper Title | Robust Indexing - Optimal Codes for DNA Storage | ||
| Authors | Jin Sima, California Institute of Technology, United States; Netanel Raviv, Washington University in Saint Louis, United States; Jehoshua Bruck, California Institute of Technology, United States | ||
| Session | M.6: Coding for Storage and Memories II | ||
| Presentation | Lecture | ||
| Track | Coding for Storage and Memories | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | The channel model of encoding data as a set of unordered strings is receiving great attention as it captures the basic features of DNA storage systems. However, the challenge of constructing optimal redundancy codes for this channel remained elusive. In this paper, we solve this open problem and present an order-wise optimal construction of codes that correct multiple substitution errors for this channel model. The key ingredient in the code construction is a technique we call robust indexing: instead of using fixed indices to create order in unordered strings, we use indices that are information dependent and thus eliminate unnecessary redundancy. In addition, our robust indexing technique can be applied to the construction of optimal deletion/insertion codes for this channel. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
