A Caltech Library Service

Computable Upper Bounds on the Capacity of Finite-State Channels

Huleihel, Bashar and Sabag, Oron and Permuter, Haim H. and Kashyap, Navin and Shamai, Shlomo (2021) Computable Upper Bounds on the Capacity of Finite-State Channels. IEEE Transactions on Information Theory, 67 (9). pp. 5674-5692. ISSN 0018-9448. doi:10.1109/tit.2021.3091691.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Huleihel, Bashar0000-0001-9962-2384
Sabag, Oron0000-0002-7907-1463
Permuter, Haim H.0000-0003-3170-3190
Kashyap, Navin0000-0001-8834-0082
Shamai, Shlomo0000-0002-6594-3371
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.
Funding AgencyGrant Number
Deutsche Forschungsgemeinschaft (DFG)UNSPECIFIED
Israel Science FoundationUNSPECIFIED
Ben-Gurion UniversityUNSPECIFIED
Minister of Economy and Science (Israel)UNSPECIFIED
European Research Council (ERC)694630
Science and Engineering Research Board (SERB)MTR/2017/000368
Subject Keywords:Channel capacity, dual capacity bound, dynamic programming (DP), finite state channels (FSCs)
Issue or Number:9
Record Number:CaltechAUTHORS:20210630-172554786
Persistent URL:
Official Citation:B. Huleihel, O. Sabag, H. H. Permuter, N. Kashyap and S. Shamai Shitz, "Computable Upper Bounds on the Capacity of Finite-State Channels," in IEEE Transactions on Information Theory, vol. 67, no. 9, pp. 5674-5692, Sept. 2021, doi: 10.1109/TIT.2021.3091691
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:109675
Deposited By: Tony Diaz
Deposited On:30 Jun 2021 18:13
Last Modified:02 Sep 2021 17:12

Repository Staff Only: item control page