Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published September 2021 | Submitted
Journal Article Open

Computable Upper Bounds on the Capacity of Finite-State Channels

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 sub-classes of unifilar and input-driven FSCs, the resulting upper bounds can be formulated as a 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.661 (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.

Additional Information

© 2021 IEEE. Manuscript received November 10, 2019; revised March 15, 2021; accepted June 7, 2021. Date of publication June 23, 2021; date of current version August 25, 2021. This work was supported in part by the DFG through the German Israeli Project Cooperation (DIP), in part by the Israel Science Foundation (ISF), in part by the Cyber Center at Ben-Gurion University of the Negev, and in part by the WIN Consortium through the Israel Minister of Economy and Science. The work of Oron Sabag was supported in part by the ISEF Postdoctoral Fellowship. The work of Shlomo Shamai was supported by the European Union's Horizon 2020 Research and Innovation Program under Grant 694630. The work of Navin Kashyap was supported in part by the MATRICS scheme administered by the Science and Engineering Research Board (SERB), Government of India, under Grant MTR/2017/000368. This article was presented in part at the 2019 IEEE International Symposium on Information Theory [1]. The authors would like to thank the Associate Editor and the anonymous reviewers for their valuable and constructive comments, which helped to improve this paper.

Attached Files

Submitted - 1911.02113.pdf

Files

1911.02113.pdf
Files (473.5 kB)
Name Size Download all
md5:88d2c0cbe4d1925a9ffe99deb3f82de6
473.5 kB Preview Download

Additional details

Created:
August 20, 2023
Modified:
October 23, 2023