Capacity-Achieving Codes for Noisy Insertion Channels
For DNA storage systems, this work provides capacity-achieving codes for a realistic insertion error model, enabling reliable data recovery.
The paper studies a noisy insertion channel relevant to DNA storage, where insertions are complementary or identical to the original symbol with possible random mutations. It determines the channel's coding capacity and constructs codes that achieve this capacity asymptotically.
DNA storage has emerged as a promising solution for large-scale and long-term data preservation. Among various error types, insertions are the most frequent errors occurring in DNA sequences, where the inserted symbol is often identical or complementary to the original, and in practical implementations, noise can further cause the inserted symbol to mutate into a random one, which creates significant challenges to reliable data recovery. In this paper, we investigate a new noisy insertion channel, where infinitely many insertions of symbols complement or identical to the original ones and up to one insertion of random symbol may occur. We determine the coding capacity of the noisy channel and construct asymptotically optimal error-correcting codes achieving the coding capacity.