Computable Upper Bounds on the Capacity of Finite-State Channels

DOI10.1109/TIT.2021.3091691MaRDI QIDQ4958258zbMATH OpenOpenAlexFDO

Authors Bashar Huleihel, Oron Sabag, Haim Permuter, N. Kashyap, Shlomo Shamai Shitz

Publication date 7 September 2021

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.02113

zbMATH Keywords

dynamic programming (DP) problemtest distributions

Mathematics Subject Classification ID

Channel models (including quantum) in information and communication theory (94A40)

Abstract: We consider the use of the well-known dual capacity bounding technique for deriving upper bounds on the capacity of indecomposable finite-state channels (FSCs) with finite input and output alphabets. In this technique, capacity upper bounds are obtained by choosing suitable test distributions on the sequence of channel outputs. We propose test distributions that arise from certain graphical structures called Q-graphs. As we show in this paper, the advantage of this choice of test distribution is that, for the important classes of unifilar and input-driven FSCs, the resulting upper bounds can be formulated as dynamic programming (DP) problem, which makes the bounds tractable. We illustrate this for several examples of FSCs, where we are able to solve the associated DP problems explicitly to obtain capacity upper bounds that either match or beat the best previously reported bounds. For instance, for the classical trapdoor channel, we improve the best known upper bound of 0.66$ (due to Lutz (2014)) to 0.584, shrinking the gap to the best known lower bound of 0.572, all bounds being in units of bits per channel use.

Cited in

(4)

• Upper Bounds on the Capacity of Binary Channels With Causal Adversaries
• Bounds on the number of states in encoder graphs for input-constrained channels
• A Deterministic Algorithm for the Capacity of Finite-State Channels
• Tighter Bounds on the Capacity of Finite-State Channels Via Markov Set-Chains

This page was built for publication: Computable Upper Bounds on the Capacity of Finite-State Channels

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4958258)