Technical Program

Paper Detail

Paper Title Coding for Deletion Channels with Multiple Traces
Paper IdentifierTU4.R8.4
Authors Mahed Abroshan, Ramji Venkataramanan, Cambridge University, United Kingdom; Lara Dolecek, University of California, Los Angeles, United States; Albert Guillén i Fàbregas, ICREA & Universitat Pompeu Fabra, Spain and University of Cambridge, United Kingdom
Session Insertion-Deletion Correcting Codes I
Location Conseil, Level 5
Session Time Tuesday, 09 July, 16:40 - 18:00
Presentation Time Tuesday, 09 July, 17:40 - 18:00
Manuscript  Click here to download the manuscript
Abstract Motivated by the sequence reconstruction problem from traces in DNA-based storage, in this paper we consider the problem of designing codes for the deletion channel when multiple observations (or traces) are available to the decoder. We propose simple binary and non-binary codes based on Varshamov-Tenengolts (VT) codes. The proposed codes split the codeword in blocks and employ a VT code in each block. The availability of multiple traces helps the decoder to identify deletion-free copies of a block, and to avoid mis-synchronization while decoding. The encoding complexity of the proposed scheme is linear in the codeword length; the decoding complexity is linear in the codeword length and quadratic in the number of deletions and the number of traces. The proposed scheme offers an explicit low-complexity technique for correcting deletions using multiple traces.