2020/01/10 by V. Arvind Rameshwar, Rameshwar, V. Arvind, Navin Kashyap +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Cellular Automata and Applications #DNA and Biological Computing #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2001.03423
openalex publication_date 2020/01/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper studies the capacities of input-driven finite-state channels,\ni.e., channels whose current state is a time-invariant deterministic function\nof the previous state and the current input. We lower bound the capacity of\nsuch a channel using a dynamic programming formulation of a bound on the\nmaximum reverse directed information rate. We show that the dynamic\nprogramming-based bounds can be simplified by solving the corresponding Bellman\nequation explicitly. In particular, we provide analytical lower bounds on the\ncapacities of (d, k)-runlength-limited input-constrained binary symmetric and\nbinary erasure channels. Furthermore, we provide a single-letter lower bound\nbased on a class of input distributions with memory.\n