Math @ Duke

Publications [#324463] of Henry Pfister
Papers Published
 Sabag, O; Permuter, HH; Pfister, HD, A singleletter upper bound on the feedback capacity of unifilar finitestate channels,
Ieee Transactions on Information Theory, vol. 63 no. 3
(March, 2017),
pp. 13921409, Institute of Electrical and Electronics Engineers (IEEE) [doi]
(last updated on 2019/07/20)
Abstract: © 19632012 IEEE. An upper bound on the feedback capacity of unifilar finitestate channels (FSCs) is derived. A new technique, called the Qcontext mapping, is based on a construction of a directed graph that is used for a sequential quantization of the receiver's output sequences to a finite set of contexts. For any choice of Qgraph, the feedback capacity is bounded by a singleletter expression, Cfb ≤ sup I (X, S; YQ), where the supremum is over p(xs, q) and the distribution of (S, Q) is their stationary distribution. It is shown that the bound is tight for all unifilar FSCs, where feedback capacity is known: channels where the state is a function of the outputs, the trapdoor channel, Ising channels, the noconsecutiveones inputconstrained erasure channel, and the memoryless channel. Its efficiency is also demonstrated by deriving a new capacity result for the dicode erasure channel; the upper bound is obtained directly from the abovementioned expression and its tightness is concluded with a general sufficient condition on the optimality of the upper bound. This sufficient condition is based on a fixed point principle of the BCJR equation and, indeed, formulated as a simple lower bound on feedback capacity of unifilar FSCs for arbitrary Qgraphs. This upper bound indicates that a singleletter expression might exist for the capacity of finitestate channels with or without feedback based on a construction of auxiliary random variable with specified structure, such as the Qgraph, and not with i.i.d distribution. The upper bound also serves as a nontrivial bound on the capacity of channels without feedback, a problem that is still open.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

