Channels with Markov Synchronization Errors: Information Stability and Capacity Bounds
For DNA storage and other applications with memory in synchronization errors, this work provides theoretical justification for capacity existence and quantifies the capacity gain from memory.
This paper proves that channels with synchronization errors (insertions, deletions, substitutions) governed by a stationary ergodic Markov chain are information-stable, establishing the existence of Shannon capacity. Numerical results for deletion channels with Markov memory show that memory increases capacity compared to memoryless channels with the same deletion probability.
Particularly motivated by DNA storage channels, we consider channels with synchronization errors modeled as insertions and deletions, along with substitutions. We focus on the case where the synchronization error process has memory and investigate the information stability of these channels, hence the existence of their Shannon capacity. We assume that the synchronization errors are governed by a stationary and ergodic finite state Markov chain and prove that such a channel is information-stable, which implies the existence of a coding scheme that achieves the limit of mutual information. This result implies the existence of the Shannon capacity for a wide range of channels with synchronization errors, with different applications, including DNA storage. We also provide specific examples of deletion channels with Markov memory and numerically evaluate their capacity bounds, thereby allowing us to quantify the capacity difference between memoryless deletion channels and those with memory with the same deletion probability and reveal that having memory increases the channel capacity.