Technical Program

Paper Detail

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

Visit Website!