References & Citations
Computer Science > Information Theory
Title: Shannon Capacity of Channels with Markov Insertions, Deletions and Substitutions
(Submitted on 29 Jan 2024 (v1), last revised 26 Mar 2024 (this version, v3))
Abstract: We consider channels with synchronization errors modeled as insertions and deletions. A classical result for such channels is their information stability, hence the existence of the Shannon capacity, when the synchronization errors are memoryless. In this paper, we extend this result to the case where the insertions and deletions have memory. Specifically, we assume that the synchronization errors are governed by a stationary and ergodic finite state Markov chain, and prove that such channel is information-stable, which implies the existence of a coding scheme which 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. The methods developed may also be useful to prove other coding theorems for non-trivial channel sequences.
Submission history
From: Ruslan Morozov [view email][v1] Mon, 29 Jan 2024 11:18:29 GMT (27kb)
[v2] Tue, 30 Jan 2024 10:44:21 GMT (27kb)
[v3] Tue, 26 Mar 2024 18:57:17 GMT (26kb)
Link back to: arXiv, form interface, contact.