Channels with Input-Correlated Synchronization Errors
For researchers in coding theory and DNA-based data storage, this work provides a theoretical framework and explicit codes for channels with correlated synchronization errors, generalizing prior results.
The paper studies channels with input-correlated synchronization errors, identifying conditions under which information capacity equals coding capacity and is achieved by stationary ergodic sources. It then derives explicit capacity-achieving codes for multi-trace channels with runlength-dependent deletions, motivated by DNA storage.
"Independent and identically distributed" errors do not accurately capture the noisy behavior of real-world data storage and information transmission technologies. Motivated by this, we study channels with input-correlated synchronization errors, meaning that the distribution of synchronization errors (such as deletions and insertions) applied to the $i$-th input $x_i$ may depend on the whole input string $x$. We begin by identifying conditions on the input-correlated synchronization channel under which the channel's information capacity is achieved by a stationary ergodic input source and is equal to its coding capacity. These conditions capture a wide class of channels, including channels with correlated errors observed in DNA-based data storage systems and their multi-trace versions, and generalize prior work. To showcase the usefulness of the general capacity theorem above, we combine it with techniques of Pernice-Li-Wootters (ISIT 2022) and Brakensiek-Li-Spang (FOCS 2020) to obtain explicit capacity-achieving codes for multi-trace channels with runlength-dependent deletions, motivated by error patterns observed in DNA-based data storage systems.