| Paper ID | D6-S3-T4.3 |
| Paper Title |
Correcting Two Deletions with More Reads |
| Authors |
Johan Chrisnata, NANYANG TECHNOLOGICAL UNIVERSITY, Singapore; Han Mao Kiah, Nanyang Technological University, Singapore |
| Session |
D6-S3-T4: Multiple Insertion/Deletion-Correcting Codes |
| Chaired Session: |
Monday, 19 July, 22:40 - 23:00 |
| Engagement Session: |
Monday, 19 July, 23:00 - 23:20 |
| Abstract |
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.
|
