Sequence Reconstruction for Sticky Insertion/Deletion Channels
This work addresses a theoretical problem in coding theory for emerging data storage systems, but the results are incremental as they extend known reconstruction techniques to a specific channel model.
The paper studies the sequence reconstruction problem for sticky insertion/deletion channels, providing a recursive formula for the minimum number of distinct outputs needed to uniquely recover the transmitted vector and an efficient reconstruction algorithm.
The sequence reconstruction problem for insertion/deletion channels has attracted significant attention owing to their applications recently in some emerging data storage systems, such as racetrack memories, DNA-based data storage. Our goal is to investigate the reconstruction problem for sticky-insdel channels where both sticky-insertions and sticky-deletions occur. If there are only sticky-insertion errors, the reconstruction problem for sticky-insertion channel is a special case of the reconstruction problem for tandem-duplication channel which has been well-studied. In this work, we consider the $(t, s)$-sticky-insdel channel where there are at most $t$ sticky-insertion errors and $s$ sticky-deletion errors when we transmit a message through the channel. For the reconstruction problem, we are interested in the minimum number of distinct outputs from these channels that are needed to uniquely recover the transmitted vector. We first provide a recursive formula to determine the minimum number of distinct outputs required. Next, we provide an efficient algorithm to reconstruct the transmitted vector from erroneous sequences.