Abstract | ||
---|---|---|
In this paper, we study the capacity of unifilar finite-state channels. We derive upper bounds that are based on the dual capacity bounding technique using test distributions with memory on directed Q-graphs. The bounds hold for any choice of graph-based test distribution and result in a multi-letter expression. The computability of the upper bound is shown via a novel dynamic programming formulation that can be efficiently evaluated. We further show that the bounds can be simplified to simple single-letter expressions by solving the corresponding Bellman equation explicitly. In particular, for the Ising and Trapdoor channels, we provide simple analytic upper bounds which outperform all previous bounds from the literature. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1109/ISIT.2019.8849776 | 2019 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT) |
Field | DocType | Citations |
Discrete mathematics,Dynamic programming,Expression (mathematics),Upper and lower bounds,Computer science,Communication channel,Computability,Bellman equation,Ising model,Bounding overwatch | Conference | 0 |
PageRank | References | Authors |
0.34 | 0 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Bashar Huleihel | 1 | 0 | 0.68 |
Oron Sabag | 2 | 25 | 6.29 |
Haim H. Permuter | 3 | 350 | 36.88 |
Navin Kashyap | 4 | 127 | 22.97 |
Shlomo Shamai | 5 | 4531 | 410.89 |