Technical Program

Paper Detail

Paper Title Computable Upper Bounds for Unifilar Finite-State Channels
Paper IdentifierTH1.R8.1
Authors Bashar Huleihel, Oron Sabag, Haim Henry Permuter, Ben-Gurion University of the Negev, Israel; Navin Kashyap, Indian Institute of Science, India; Shlomo Shamai (Shitz), Technion - Israel Institute of Technology, Israel
Session Capacity Computation
Location Conseil, Level 5
Session Time Thursday, 11 July, 09:50 - 11:10
Presentation Time Thursday, 11 July, 09:50 - 10:10
Manuscript  Click here to download the manuscript
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 computablity 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.