|| Correcting Two Deletions with More Reads
||Johan Chrisnata, NANYANG TECHNOLOGICAL UNIVERSITY, Singapore; Han Mao Kiah, Nanyang Technological University, Singapore|
||D6-S3-T4: Multiple Insertion/Deletion-Correcting Codes
||Monday, 19 July, 22:40 - 23:00
||Monday, 19 July, 23:00 - 23:20
A two-deletion correcting code of length n is defined to be a set of binary words such that a codeword can be uniquely identified from any one of its length-(n-2) subsequence. A two-deletion correcting code requires at least 2 log n + O(1), while the best known explicit construction uses 4 log n + o(log n) redundant bits. In this work, we study this coding problem in the framework of the sequence reconstruction problem and require the receiver to uniquely reconstruct a codeword from any N>2 of its length-(n-2) subsequences. Specifically, we provide an explicit code construction that uniquely reconstructs a codeword from any five of its length-(n-2) subsequences, using only 2 log n + o(log n) redundant bits.