A Caltech Library Service

Graph-Based Encoders and their Performance for Finite-State Channels with Feedback

Sabag, Oron and Huleihel, Bashar and Permuter, Haim H. (2020) Graph-Based Encoders and their Performance for Finite-State Channels with Feedback. IEEE Transactions on Communications, 68 (4). pp. 2106-2117. ISSN 0090-6778. doi:10.1109/tcomm.2020.2965454.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


The capacity of unifilar finite-state channels in the presence of feedback is investigated. We derive a new evaluation method to extract graph-based encoders with their achievable rates, and to compute upper bounds to examine their performance. The evaluation method is built upon a recent methodology to derive simple bounds on the capacity using auxiliary directed graphs. While it is not clear whether the upper bound is convex, we manage to formulate it as a convex optimization problem using transformation of the argument with proper constraints. The lower bound is formulated as a non-convex optimization problem, yet, any feasible point to the optimization problem induces a graph-based encoder. In all examples, the numerical results show near-tight upper and lower bounds that can be easily converted to analytic results. For the non-symmetric trapdoor channel and binary fading channels (BFCs), new capacity results are established by computing the corresponding bounds. For all other instances, including the Ising channel, the near-tightness of the achievable rates is shown via a comparison with corresponding upper bounds. Finally, we show that any graph-based encoder implies a simple coding scheme that is based on the posterior matching principle and achieves the lower bound.

Item Type:Article
Related URLs:
URLURL TypeDescription
Sabag, Oron0000-0002-7907-1463
Permuter, Haim H.0000-0003-3170-3190
Additional Information:© 2019 IEEE. Manuscript received July 25, 2019; revised December 17, 2019; accepted December 20, 2019. Date of publication January 10, 2020; date of current version April 16, 2020. This work was supported in part by the Deutsche Forschungsgemeinschaft (DFG) via the Deutsch-lsraelische Projektkooperation (DIP), in part by the Israel Science Foundation, and in part by the Cyber Center and at Ben-Gurion University of the Negev. The work of Oron Sabag was supported in part by the ISEF International Fellowship. This article was presented at the 2018 International Symposium on Information Theory (ISIT) [1]. The associate editor coordinating the review of this article and approving it for publication was R. Venkataramanan. The authors would like to thank Dr. Or Ordentlich for suggesting the study of the BFC in Section IV-A. The authors would also like to thank the Associate Editor and the anonymous reviewers for their valuable and constructive comments, and to Reviewer 3 for suggesting the simple convexity argument in Appendix A.
Funding AgencyGrant Number
Deutsche Forschungsgemeinschaft (DFG)UNSPECIFIED
Israel Science FoundationUNSPECIFIED
Ben-Gurion UniversityUNSPECIFIED
Israel Scholarship Education FoundationUNSPECIFIED
Subject Keywords:Channel capacity, convex optimization, feedback capacity, posterior matching (PM), Markov decision process (MDP)
Issue or Number:4
Record Number:CaltechAUTHORS:20200116-142258005
Persistent URL:
Official Citation:O. Sabag, B. Huleihel and H. H. Permuter, "Graph-Based Encoders and Their Performance for Finite-State Channels With Feedback," in IEEE Transactions on Communications, vol. 68, no. 4, pp. 2106-2117, April 2020
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:100768
Deposited By: Tony Diaz
Deposited On:16 Jan 2020 22:32
Last Modified:16 Nov 2021 17:56

Repository Staff Only: item control page