#  Finite-State Channels with Feedback and State Known at the Encoder
††thanks:  E. Shemuel was supported by the Ministry of Science and Technology
of Israel. This work was supported by the German Research Foundation (DFG) via
the German-Israeli Project Cooperation [DIP] and by the ISF research grant
818/17. The material in this paper was presented in part at the 56th Annual
Allerton Conference on Communication, Control, and Computing, Monticello, IL,
USA, October 2018, and at the IEEE International Symposium on Information
Theory, Los Angeles, CA, USA, June 2020. E. Shemuel and H. H. Permuter are
with the Department of Electrical and Computer Engineering, Ben-Gurion
University of the Negev, Beer-Sheva 8410501, Israel (e-mail:
<EMAIL_ADDRESS>haimp@bgu.ac.il). O. Sabag is with the School of
Engineering and Computer Science, The Hebrew University of Jerusalem,
Jerusalem, Israel (e-mail: oron.sabag@mail.huji.ac.il).

Eli Shemuel, Oron Sabag, Haim H. Permuter

###### Abstract

We consider finite state channels (FSCs) with feedback and state information
known causally at the encoder. This setting is quite general and includes: a
memoryless channel with i.i.d. state (the Shannon strategy), Markovian states
that include look-ahead (LA) access to the state and energy harvesting. We
characterize the feedback capacity of the general setting as the directed
information between auxiliary random variables with memory to the channel
outputs. We also propose two methods for computing the feedback capacity: (i)
formulating an infinite-horizon average-reward dynamic program; and (ii) a
single-letter lower bound based on auxiliary directed graphs called
$Q$-graphs. We demonstrate our computation methods on several examples. In the
first example, we introduce a channel with LA and derive a closed-form,
analytic lower bound on its feedback capacity. Furthermore, we show that the
mentioned methods achieve the feedback capacity of known unifilar FSCs such as
the trapdoor channel, the Ising channel and the input-constrained erasure
channel. Finally, we analyze the feedback capacity of a channel whose state is
stochastically dependent on the input.

###### Index Terms:

channel capacity, channels with feedback, dynamic programming, finite-state
channel, Q-graphs.

##  I Introduction

The capacity of discrete memoryless channels (DMCs) with an independent and
identically distributed (i.i.d.) state, where causal state information (SI) is
known at the encoder, was studied by Shannon [1]. Furthermore, Shannon showed
that feedback does not increase the capacity of a DMC [2], which holds also
when causal SI is available. However, this is not the case for channels with
memory. Channels with memory, which are common in wireless communication [3,
4, 5, 6, 7, 8, 9], molecular communication [10, 11] and magnetic recordings
[12], can be often described by the finite-state channel (FSC) model [13, 14,
15, 16, 17, 18]. The memory in FSCs is encapsulated in a channel state with a
finite set of values. In this paper, we generalize Shannon’s work to the case
of FSCs, i.e., we study FSCs with feedback and causal SI known at the encoder,
as depicted in Fig. 1.

This setting we study covers many interesting scenarios. One scenario is a
channel with i.i.d. state when the SI is available at the encoder in advance
with some finite look-ahead (LA) [19, 20, 21]. The question whether feedback
increases the capacity of this scenario is an open problem. Our setting covers
this scenario with feedback since an i.i.d. state with a finite LA can be
viewed as a Markovian state process causally known at the encoder.
Additionally, our setting covers scenarios in which the state is input-
dependent, that is, the state evolution depends on the channel inputs. A well-
known problem in which the state is input-dependent is the energy-harvesting
(EH) model [22, 23, 24, 25, 26, 27, 28], motivated by many emerging wireless
networks. The EH model can be viewed as a FSC where the channel state is the
current battery level governed by the channel inputs and the charging process,
thus it is covered by our setting in the presence of feedback. One more input-
dependent scenario covered by Fig. 1 is Noisy Output is the STate (NOST)
channels, i.e., channels where the state is stochastically dependent on the
channel output, with feedback and causal SI known at the encoder. The capacity
of this scenario was derived in [29] as a single-letter expression.

Figure 1:  FSCs with feedback and SI known at the encoder. Note that the
channel output at time $i$ depends on $S_{i-1}$.

We derive a multi-letter capacity formula for the general setting expressed as
the directed information between a sequence of auxiliary random variables
(RVs) and the sequence of the channel outputs. As in the case of i.i.d.
states, we show that the channel input is a function of the auxiliary RV and
the state. However, in our setting, the auxiliary RVs should have memory.
Although our capacity expression is multi-letter, we use it to propose
sequences of lower and upper bounds on the feedback capacity, whose elements
are finite-letter expressions. Furthermore, we develop two methods for
computing the feedback capacity. The first method is a formulation of the
capacity expression as an infinite-horizon dynamic programming (DP)
optimization problem. In the second method, we derive a single-letter lower
bound based on $Q$-graphs [30].

The DP framework was introduced in [31] as a tool for computing the feedback
capacity of FSCs. This paved the way for more works that formulated the
feedback capacity of certain FSCs as a DP: Markov channels [32], ISI channels
[33] and the most general class of unifilar FSCs [34]. For the latter case of
unifilar FSCs, the new state is a function of the current state, input and
output, and consequently the state is known to the encoder. Thus, even the
general class of unifilar FSCs is captured in our framework of Fig. 1.

The $Q$-graph technique, introduced in [30], is another tool for computing
lower and upper bounds on the feedback capacity. It maps the receiver’s output
sequences to a sequential quantization in a finite set of graphs represented
by a directed graph, called a $Q$-graph. In [30], single-letter lower and
upper bounds on the feedback capacity were derived for unifilar FSCs for any
$Q$-graph, while in [35] it was shown how to compute them. We implement their
method on our multi-letter capacity expression of the general setting in order
to derive a single-letter lower bound on the feedback capacity for any
$Q$-graph.

Generally, both the DP and the $Q$-graph tools can be used to compute
achievable rates, but for special cases they capture the precise feedback
capacity. We show the tightness of the $Q$-graph bound for known unifilar FSCs
such as the trapdoor channel [34], the Ising channel [36] and the binary
erasure channel (BEC) with inputs constraint [37]. We also investigate the
feedback capacity of a channel with LA SI known at the encoder, and the
feedback capacity of a generalized Ising channel whose state is stochastically
dependent on the input.

The remainder of the paper is organized as follows. Section II defines the
notation used in this paper and the setting, and provides preliminaries on DP
and $Q$-graphs. Section III presents the main results. Section IV focuses on
the DP and $Q$-graph methods. In Section V, we provide several FSCs and study
their feedback capacity. Section VI proves our main result. Finally, Section
VII concludes this work.

##  II The Communication Setup and Preliminaries

In this section, we introduce the notation and the communication setup. We
then provide preliminaries on DP and the $Q$-graphs.

###  II-A Notation

Lowercase letters denote sample values (e.g. $x,y$), and uppercase letters
denote discrete RVs (e.g. $X,Y$). Subscripts and superscripts denote vectors
in the following way: $x_{i}^{j}=(x_{i},x_{i+1},...,x_{j})$ and
$X_{i}^{j}=(X_{i},X_{i+1},...,X_{j})$ for $1\leq i\leq j$. $x^{n}$ and $X^{n}$
are shorthand for $x_{1}^{n}$ and $X_{1}^{n}$, respectively. We use
calligraphic letters (e.g. ${\mathcal{X}},{\mathcal{Y}}$) to denote alphabets,
and $|{\mathcal{X}}|$ to denote the cardinality of the alphabet. For two RVs
$X,Y$ the probability mass function (PMF) of $X$ is denoted by $P(X=x)$, the
conditional PMF of $X=x$ given $Y=y$ is denoted by $P(X=x|Y=y)$, and the joint
PMF is denoted by $P(X=x,Y=y)$; the shorthand $P(x),P(x|y),P(x,y)$ are used
for the above, respectively. The indicator function is denoted by
$\mathbbm{1}(\cdot)$. We use $\oplus$ to denote the binary XOR operation. We
define $\bar{a}=1-a$ for some $a\in[0,1]$. For a pair of integers $n\leq m$,
we define the discrete interval $[n:m]\triangleq\\{n,n+1,\dots,m\\}$. We use
logarithms to base $2$; thus the entropy is measured in bits.

The directed information (DI) between $X^{N}$ to $Y^{N}$ conditioned on $S$,
introduced by Massey [38] and employed with conditioning in [39], is defined
as

$I(X^{N}\rightarrow Y^{N}|S)\triangleq\sum_{i=1}^{N}I(X^{i};Y_{i}|Y^{i-1},S).$
(1)

The causally conditional distribution (CCD) conditioned on $s_{0}$, introduced
in [40, 41] and employed with conditioning in [34], is defined as

$P(x^{N}||y^{N-1},s)\triangleq\prod_{i=1}^{N}P(x_{i}|x^{i-1},y^{i-1},s).$ (2)

###  II-B The Setting

We consider FSCs as shown in Fig. 1. A FSC consists of finite input, output
and channel state alphabets ${\mathcal{X}},{\mathcal{Y}},{\mathcal{S}}$,
respectively. It is defined by (${\mathcal{X}}\times{\mathcal{S}}$,
$P_{Y,S^{+}|X,S}$, ${\mathcal{Y}}\times{\mathcal{S}}$) where $S,S^{+}$ are the
channel state at the beginning and at the end of the transmission,
respectively. The initial state is distributed according to $P(s_{0})$, and it
is available to the encoder but not to the decoder. At time $i$, the encoder
has access to the message $m\in\mathcal{M}$, the output feedback and the
channel state. The channel is time invariant, and at each time $i$ it has the
Markov property

$P(y_{i},s_{i}|x^{i},s_{0}^{i-1},y^{i-1.},m)=P_{Y,S^{+}|X,S}(y_{i},s_{i}|x_{i},s_{i-1}).$
(3)

The encoder’s mapping at time $i$ is denoted as

$\displaystyle
f_{i}:\mathcal{M}\times{\mathcal{S}}_{0}^{i-1}\times{\mathcal{Y}}^{i-1}\to{\mathcal{X}},$
(4)

and the decoder’s mapping is

$\displaystyle\hat{m}:{\mathcal{Y}}^{n}\to\mathcal{M}.$ (5)

An $(2^{nR},n)$ code is a pair of encoding and decoding mappings (4)-(5) with
a message set $\mathcal{M}=[1:\lceil 2^{nR}\rceil]$, and $M$ is uniformly
distributed over $\mathcal{M}$. A rate $R$ is achievable if there exists a
sequence of codes $(n,\lceil 2^{nR}\rceil)$ such that the average probability
of error defined as $P_{e}^{(n)}\triangleq\Pr(\hat{m}\neq m|\text{message $m$
was sent})$ tends to zero as $n\to\infty$. The capacity of the setting is
defined as the supremum over all achievable rates, and is denoted by
$C_{\text{fb-csi}}$. Furthermore, we assume that the FSC is strongly
connected.

######  Definition 1 (Connectivity).

[34, Def. 2] A FSC is strongly connected if for all
$s^{\prime},s\in{\mathcal{S}}$ there exist $T(s)$ and input distribution of
the form $\\{P(x_{i}|s_{i-1})\\}_{i=1}^{T(s)}$ that may depend on $s$, such
that $\sum_{i=1}^{T(s)}P(S_{i}=s|S_{0}=s^{\prime})>0$.

###  II-C Average-Reward Dynamic Programming

A DP is defined by a septuple
$(\mathcal{Z},\mathcal{U},\mathcal{W},F,P_{Z},P_{w},g)$. We consider a
discrete-time dynamic system evolving according to

$z_{i}=F(z_{i-1},a_{i},w_{i}),\ i=1,2,\dots$

Each state, $z_{i}$, takes values in a Borel space $\mathcal{Z}$. Each action,
$a_{i}$, takes values in a compact subset $\mathcal{A}$ of a Borel space. Each
disturbance, $w_{i}$, takes values in a measurable space $\mathcal{W}$, and is
drawn from a distribution $P_{w}(\cdot|z_{i-1},a_{i})$ that depends on the
state $z_{i-1}$, and action $a_{i}$. The initial state, $z_{0}$, is drawn from
a distribution $P_{Z}$. All functions considered in this section are assumed
to be measurable. The history, $h_{i}=(z_{0},w_{1}^{i-1})$, summarizes
information available to the controller at time $i$, prior to the selection of
the $i$th action. At time $i$, the controller selects the action, $a_{i}$, by
a function $\mu_{i}$ that maps histories to actions, i.e.,
$a_{i}=\mu_{i}(h_{i})$. Given a policy, denoted by
$\pi=\\{\mu_{1},\mu_{2},\dots\\}$, and the history, $h_{i}$, one can compute
the actions vector, $a^{i}$, and the past state vector of the system,
$z^{i-1}$.

Given a bounded reward function $g:\cal{Z}\times\cal{A}\rightarrow\mathbb{R}$,
the objective is to maximize the infinite-horizon average reward. For a policy
$\pi$, it is defined by

$\rho_{\pi}=\liminf_{N\to\infty}\frac{1}{N}\mathbb{E}_{\pi}\left\\{\sum_{i=1}^{N}g(Z_{i-1},\mu_{i}(H_{i}))\right\\},$
(6)

where the subscript $\pi$ indicates that actions $a_{i}$ are generated by the
policy $\pi$. The optimal average reward is defined by

$\rho^{*}=\sup_{\pi}\rho_{\pi}.$ (7)

###  II-D $Q$-graphs

Figure 2: An example of a $Q$-graph with $|\mathcal{Q}|=2$ and
$\mathcal{Y}=\\{0,1,?\\}$.

The $Q$-graph is a technique that enables us to derive a single-letter lower
and upper bounds on the feedback capacity out of a multi-letter expression,
based on Quantized-graphs ($Q$-graphs). A $Q$-graph is defined as a directed,
connected graph with a finite number of nodes. Each node takes a different
value $q\in{\mathcal{Q}}$, and it has exactly $|{\mathcal{Y}}|$ outgoing edges
that are labeled with distinct symbols from ${\mathcal{Y}}$. From the
$Q$-graph definition, it follows that given an initial node, $q_{0}$, and an
output sequence, $y^{i}$, walking along the corresponding labeled edges
determines uniquely a final node, $q_{i}$. This induced mapping can be
represented by $\Phi_{i}:{{\mathcal{Y}}}^{i}\to{\mathcal{Q}}$ as well as by a
time-invariant function, $g:{\mathcal{Q}}\times{\mathcal{Y}}\to{\mathcal{Q}}$,
where the current graph node and the channel output determine a new node. An
example of a $Q$-graph is depicted in Fig. 2.

##  III Main Results

In this section, we present our main results. The following two theorems
characterize the capacity of the setting.

######  Theorem 1.

The feedback capacity of a strongly connected FSC with SI known causally at
the encoder is given by

$\displaystyle C_{\text{fb-csi}}$
$\displaystyle=\lim_{N\to\infty}\frac{1}{N}\max_{P(u^{N}||y^{N-1})}I(U^{N}\to
Y^{N}),$ (8)

where $\\{U_{i}\\}_{i\geq 1}$ are auxiliary RVs with
$|{\mathcal{U}}|=|{\mathcal{X}}|^{|{\mathcal{S}}|}$, and the joint
distribution is given by

$\displaystyle P(x^{N},s_{0}^{N},y^{N},u^{N})$
$\displaystyle=P(s_{0})P(u^{N}||y^{N-1})\prod_{i=1}^{N}\mathbbm{1}\\{x_{i}=f(u_{i},s_{i-1})\\}P_{Y,S^{+}|X,S}(y_{i},s_{i}|x_{i},s_{i-1})\text{.}$
(9)

Each $u\in{\mathcal{U}}$ corresponds to a distinct function from the set
$\\{f_{u}(s):{\mathcal{S}}\to{\mathcal{X}}\\}$.

The feedback capacity can also be expressed as follows.

######  Theorem 2.

The feedback capacity of a strongly connected FSC with SI known causally at
the encoder is given by

$\displaystyle C_{\text{fb-csi}}$
$\displaystyle=\lim_{N\to\infty}\frac{1}{N}\max_{\begin{subarray}{c}\\{P(u_{i}|u_{i-1},y^{i-1})\\}_{i=1}^{N}\\\
x_{i}=f(u_{i},s_{i-1})\end{subarray}}\sum_{i=1}^{N}I(U_{i},U_{i-1};Y_{i}|Y^{i-1}),$
(10)

where $\\{U_{i}\\}_{i\geq 1}$ are auxiliary RVs, and the joint distribution is
given by

$\displaystyle
P(x^{N},s_{0}^{N},y^{N},u^{N})=P(s_{0})\prod_{i=1}^{N}P(u_{i}|u_{i-1},y^{i-1})\mathbbm{1}\\{x_{i}=f(u_{i},s_{i-1})\\}P_{Y,S^{+}|X,S}(y_{i},s_{i}|x_{i},s_{i-1})\text{.}$
(11)

The capacity expressions in Theorems 1 and 2 provide two alternative capacity
expressions for FSCs with feedback, and their corresponding joint
distributions, (9) and (11), imply that $X_{i}$ depends on $S_{i-1}$ and not
on $S^{i-2}$ via the time-invariant function
$f:{\mathcal{U}}\times{\mathcal{S}}\to{\mathcal{X}}$. To compare the objective
functions and maximization domains between (8) and (10), recall that the DI
and the CCD in the former can be written as $I(U^{N}\to
Y^{N})\triangleq\sum_{i=1}^{N}I(U^{i};Y_{i}|Y^{i-1})$ and
$P(u^{N}||y^{N-1})\triangleq\prod_{i=1}^{N}P(u_{i}|u^{i-1},y^{i-1})$,
respectively. On the other hand, (8) has a finite cardinality bound for for
all $\\{U_{i}\\}_{i\geq 1}$, while in (10) their cardinality may be unbounded.
We note that in Theorem 1, there is no maximization over the functions $f$ as
the cardinality of $|{\mathcal{U}}|=|{\mathcal{X}}|^{|{\mathcal{S}}|}$ covers
all possible mappings from ${\mathcal{S}}$ to ${\mathcal{X}}$ (called
strategies).

######  Lemma 1.

Both alternatives, i.e., Theorems 1 and 2, can be shown to be equal.

###### Proof sketch.

For distinction, we rename the auxiliary RVs of Theorem 2 with
$\\{V_{i}\\}_{i\geq 1}$, while $\\{U_{i}\\}_{i\geq 1}$ are remained to denote
the auxiliary RVs of Theorem 1. By defining $V_{i}=(V_{i-1},U_{i})$, Theorem 1
becomes Theorem 2 with
$|{\mathcal{V}}_{i}|=|{\mathcal{X}}|^{{|{\mathcal{S}}|}^{i}}$ as for all $i$,
$V_{i}$ recovers all possible strategies
$\\{f_{u}(s):{\mathcal{S}}\to{\mathcal{X}}\\}$ until time $i$, that were
encapsulated by $x_{j}=f(u_{j},s_{j-1})$ for $j=1,\dots,i$. ∎

Due to Lemma 1, we prove only Theorem 1 in Section VI. Although both Theorems
consist of a multi-letter capacity expressions, we utilize them to derive
computable lower and upper bounds as given in the following results. First, we
obtain sequences of achievable rates and upper bounds on the feedback capacity
that are computable for any positive integer $N$, as given in the next
theorem. Let $\underline{C}_{N}$ and $\overline{C}_{N}$ denote

$\displaystyle\underline{C}_{N}$
$\displaystyle=\frac{1}{N}\max_{P(u^{N}||y^{N-1})}\min_{s_{0}}I(U^{N}\to
Y^{N}|s_{0}),$ (12) $\displaystyle\overline{C}_{N}$
$\displaystyle=\frac{1}{N}\max_{P(u^{N}||y^{N-1})}\max_{s_{0}}I(U^{N}\to
Y^{N}|s_{0}),$ (13)

where $|{\mathcal{U}}|=|{\mathcal{X}}|^{|{\mathcal{S}}|}$, and the joint
distribution is

$\displaystyle P(x^{N},s^{N},y^{N},u^{N}|s_{0})$
$\displaystyle=P(u^{N}||y^{N-1})\prod_{i=1}^{N}\mathbbm{1}\\{x_{i}=f(u_{i},s_{i-1})\\}P_{Y,S^{+}|X,S}(y_{i},s_{i}|x_{i},s_{i-1}).$
(14)

######  Theorem 3.

The feedback capacity of any FSC $P_{Y,S^{+}|X,S}$ with SI known causally at
the encoder is bounded by

$\displaystyle\underline{C}_{N}-\frac{\log|{\mathcal{S}}|}{N}\leq C_{\text{fb-
csi}}\leq\overline{C}_{N}+\frac{\log|{\mathcal{S}}|}{N},\quad N=1,2,\dots$
(15)

The proof of Theorem 3 is given in Section VI. Notice that it holds for any
FSC, not necessarily connected.

From Theorem 2, we also derive computable lower bounds using the DP and the
$Q$-graph methods that were introduced in Sections II-C and II-D,
respectively, as shown in the following theorems.

######  Theorem 4 (DP Formulation).

For a fixed, finite cardinality $\left|\mathcal{U}\right|$ and a function
$f:\mathcal{U}\times\mathcal{S}\to\mathcal{X}$, the capacity expression in
(10) can be formulated as an average-reward DP (Table I).

Table I: The DP formulation DP Notations | FSC with Feedback and causal state at the encoder
---|---
DP state, $z_{i-1}$ | $P(u_{i-1},s_{i-1}|y^{i-1})$
Disturbance, $w_{i}$ |  $y_{i}$ \- the channel output
Action, $a_{i}$ | $P(u_{i}|u_{i-1},y^{i-1})$
DP state evolution, $z_{i}=F(z_{i-1},a_{i},w_{i})$ |  Eq. (16)
Reward, $g(z_{i-1},a_{i})$ | $I(U_{i},U_{i-1};Y_{i}|y^{i-1})$

$P(u_{i},s_{i}|y^{i})=\frac{\sum_{u_{i-1},s_{i-1}}\beta_{i-1}(u_{i-1},s_{i-1})a_{i}(u_{i},u_{i-1},y^{i-1})P_{Y,S^{+}|X,S}(y_{i},s_{i}|f(u_{i},s_{i-1}),s_{i-1})}{\sum_{u_{i-1},u^{\prime}_{i},s_{i-1}}\beta_{i-1}(u_{i-1},s_{i-1})a_{i}(u_{i}^{\prime},u_{i-1},y^{i-1})P_{Y|X,S}(y_{i}|f(u^{\prime}_{i},s_{i-1}),s_{i-1})}$
(16)

The proof of Theorem 4 is given in Section IV. Theorem 4 serves as a tool to
compute achievable rates for the feedback capacity either numerically or
analytically. For example, we can use the value iteration algorithm (VIA), or
solve the corresponding Bellman equation. In cases that there is a cardinality
bound $|{\mathcal{U}}_{i}|=|{\mathcal{U}}|<\infty$, the DP characterizes the
feedback capacity itself, and such examples will be given in Section V.

The next theorem provides another tool for computing lower bounds based on the
$Q$-graph method. It provides a single-letter lower bound on the feedback
capacity for any choice of a $Q$-graph. Given a $Q$-graph, cardinality
$|{\mathcal{U}}|$, a function $f:\mathcal{U}\times\mathcal{S}\to\mathcal{X}$
and conditional distribution $P(u^{+}|u,q)$, there is a transition matrix
$P(s^{+},u^{+},q^{+}|s,u,q)$ given by

$\displaystyle P(s^{+},u^{+},q^{+}|s,u,q)$
$\displaystyle=\sum_{x,y}P(s^{+},u^{+},q^{+},x,y|s,u,q)$
$\displaystyle=\sum_{x,y}P(u^{+}|u,q)\mathbbm{1}\\{x=f(u^{+},s)\\}\mathbbm{1}\\{q^{+}=g(q,y)\\}P_{Y,S^{+}|X,S}(y,s^{+}|x,s).$
(17)

######  Theorem 5 ($Q$-graph Lower Bound).

For any Q-graph, given a fixed, finite cardinality $\left|\mathcal{U}\right|$
($U^{+},U\in{\mathcal{U}}$) and a function
$f:\mathcal{U}\times\mathcal{S}\to\mathcal{X}$, the feedback capacity is lower
bounded by

$\displaystyle C_{\text{fb-csi}}\geq I(U^{+},U;Y|Q),$ (18)

for all $P(u^{+}|u,q)\in\mathcal{P}_{\pi}$ that are BCJR-invariant, where the
joint distribution is

$\displaystyle
P(s,u,q,x,y,s^{+},u^{+},q^{+})=\pi(s,u,q)P(u^{+}|u,q)\mathbbm{1}\\{x=f(u^{+},s)\\}P(y,s^{+}|x,s)\mathbbm{1}\\{q^{+}=g(q,y)\\}.$
(19)

The notation $\mathcal{P}_{\pi}$ denotes the set of distributions
$P(u^{+}|u,q)$ that induce a transition matrix $P(s^{+},u^{+},q^{+}|s,u,q)$
with a unique stationary distribution on the $(S,U,Q)$-graph, denoted by
$\pi(s,u,q)$. An input distribution is BCJR-invariant if the Markov chain
$(S^{+},U^{+})-Q^{+}-(Q,Y)$ holds. The proof of Theorem 5 is given in Section
IV.

The $Q$-graph and the DP methods are detailed in Section IV, and in Section V
we demonstrate their usefulness on several examples.

##  IV Capacity Computation

In this section, we elaborate on the DP and $Q$-graph methods of computing the
feedback capacity, and prove Theorems 4 and 5.

###  IV-A Dynamic Programming Formulation and Proof of Theorem 4

In words, the DP summarized in Table I is as follows. The DP state, $z_{i-1}$,
is chosen as the conditional joint distribution matrix whose elements are
$\beta_{i-1}(u_{i-1},s_{i-1})=P(u_{i-1},s_{i-1}|y^{i-1})$, for
$u_{i-1},s_{i-1}\in{\mathcal{U}}\times{\mathcal{S}}$. The action space,
$\mathcal{A}$, is the set of stochastic matrices $P(u_{i}|u_{i-1},y^{i-1})$.
The disturbance is taken to be the channel output, i.e., $w_{i}=y_{i}$.
Finally, the reward function at time $i$ is $I(U_{i},U_{i-1};Y_{i}|y^{i-1})$.
Now in order to prove that this is a valid DP formulation, we need to prove
the following lemma.

######  Lemma 2 (DP formulation).

The formulation presented in Table I satisfies the DP model. That is,

  1. 1.

The DP state is a time-invariant function of the previous DP state, action and
disturbance.

  2. 2.

The disturbance is conditionally dependent on the DP state and action.

  3. 3.

The reward is a time-invariant function of the state and action.

Consequently, the optimal average reward is

$\displaystyle\rho^{*}=\sup_{\pi}\liminf_{N\to\infty}\frac{1}{N}\sum_{i=1}^{N}I_{\pi}(U_{i},U_{i-1};Y_{i}|Y^{i-1}),$

where the subscript $\pi$ indicates that the mutual information corresponds to
the policy denoted by $\pi$. The proof of Theorem 4 is a direct consequence of
Lemma 2 and the following Lemma 3, whose proofs are given in Appendices A and
B, respectively.

######  Lemma 3.

The feedback capacity of a connected FSC with SI known causally at the encoder
can be expressed by

$C_{\text{fb-
csi}}=\sup\liminf_{N\to\infty}\frac{1}{N}\sum_{i=1}^{N}I(U_{i},U_{i-1};Y_{i}|Y^{i-1})\text{,}$
(20)

where the supremum is taken with respect to
${\\{P(u_{i}|u_{i-1},y^{i-1})\\}}_{i\geq 1}$, and the joint distribution is
given by (11).

We note that if the feedback capacity can be achieved with
$|{\mathcal{U}}_{i}|=|{\mathcal{U}}|<\infty$, the supremum in (20) is also
taken with respect to a time-invariant function
$f:{\mathcal{U}}\times{\mathcal{S}}\to{\mathcal{X}}$.

###  IV-B Q-Graph Technique and Proof of Theorem 5

An altrenative method to compute lower bounds on the feedback capacity,
besides the DP, is the $Q$-graph technique in Theorem 5. Here, we explain this
theorem, and prove it in the next part of this section. The main idea of the
proof is to embed an auxiliary graph into the capacity expression in (10).
Throughout this section, we assume a fixed cardinality $|{\mathcal{U}}|$ and a
fixed function $f:\mathcal{U}\times\mathcal{S}\to\mathcal{X}$.

The FSC $P_{Y,S^{+}|X,S}$ is embedded into a given $Q$-graph by constructing a
new directed, connected graph termed an $(S,U,Q)$-graph to include the
information on the $Q$-graph and on the evolution of the state and the
auxiliary RV pair, $(S,U)$. The $(S,U,Q)$-graph is constructed as follows:

  1. 1.

Each node in the $Q$-graph is split to $|{\mathcal{S}}|\times|{\mathcal{U}}|$
new nodes represented by
$(s,u,q)\in{\mathcal{S}}\times{\mathcal{U}}\times{\mathcal{Q}}$.

  2. 2.

An edge $(s,u,q)\rightarrow(s^{+},u^{+},q^{+})$, with a label $(x,y)$, exists
if and only if there exists a pair $(x,y)$ such that $x=f(u^{+},s)$,
$P_{Y,S^{+}|X,S}(y,s^{+}|x,s)>0$ and $q^{+}=g(q,y)$.

We denote by $\mathcal{P}_{\pi}$ the set of input distributions $P(u^{+}|u,q)$
that induce a unique stationary distribution on $(S,U,Q)$, i.e., their
corresponding $(S,U,Q)$-graph is irreducible and aperiodic. An input
distribution $P(u^{+}|u,q)$ is said to be aperiodic if its $(S,U,Q)$-graph is
aperiodic. An aperiodic input distribution is BCJR-invariant if it induces the
Markov chain

$(S^{+},U^{+})-Q^{+}-(Q,Y).$ (21)

For the proof of Theorem 5, we use similar ideas as in the proof of [30,
Theorem 3] based on our Lemma 3. We show that a BCJR-invariant input
distribution induces for all $i$ the Markov chain $Y_{i}-Q_{i-1}-Y^{i-1}$,
which leads to the fact that $I(U^{+},U;Y|Q)$ with the chosen input
distribution is a lower bound on the feedback capacity.

For an integer $i$ we define $q_{i}\triangleq\Phi_{i}(y^{i})$ and prove by
induction that $P(u_{i},s_{i}|y^{i},q_{i})=\pi(u_{i},s_{i}|q_{i})$ for the
choice of a BCJR-invariant input distribution. At time $i-1$, assume that
$P(u_{i-1},s_{i-1}|y^{i-1},q_{i-1})=\pi(u_{i-1},s_{i-1}|q_{i-1})$. Then, at
time $i$ we have

$\displaystyle P(u_{i},s_{i}|y^{i},q_{i})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}P(u_{i},s_{i}|q_{i-1},y_{i})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}P(u_{i},s_{i}|q_{i}).$ (22)

Eq. (a) follows from the fact that the BCJR recursive equation (16), for any
$u,s\in{\mathcal{U}}\times{\mathcal{S}}$, can be computed from
$\\{P(u_{i-1},s_{i-1}|y^{i-1})\\},\\{P(u_{i}|u_{i-1},y^{i-1})\\}$ and $y_{i}$,
while for the first distribution we use the induction hypothesis, and for the
second distribution we use the assumption that the inputs are of the form
$\\{P(u_{i}|u_{i-1},q_{i-1}(y^{i-1}))\\}$. Eq. (b) follows from
$q_{i}=g(q_{i-1},y_{i})$ and from the BCJR-invariant property. As a result,
the Markov chain $Y_{i}-Q_{i-1}-Y^{i-1}$ holds for all $i$:

$\displaystyle P(y_{i}|y^{i-1},q_{i-1})$
$\displaystyle=\sum_{s_{i-1},u_{i-1},u_{i}}P(s_{i-1},u_{i-1},u_{i},y_{i}|y^{i-1},q_{i-1})$
$\displaystyle=\sum_{s_{i-1},u_{i-1},u_{i}}P(u_{i-1},s_{i-1}|y^{i-1},q_{i-1})P(u_{i}|u_{i-1},s_{i-1},y^{i-1},q_{i-1})P(y_{i}|f(u_{i},s_{i-1}),s_{i-1})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{s_{i-1},u_{i-1},u_{i}}P(u_{i-1},s_{i-1}|y^{i-1},q_{i-1})P(u_{i}|u_{i-1},q_{i-1})P(y_{i}|f(u_{i},s_{i-1}),s_{i-1})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\sum_{s_{i-1},u_{i-1},u_{i}}\pi(u_{i-1},s_{i-1}|q_{i-1})P(u_{i}|u_{i-1},s_{i-1},q_{i-1})P(y_{i}|f(u_{i},s_{i-1}),s_{i-1})$
$\displaystyle=P(y_{i}|q_{i-1}),$ (23)

where

  1. (a)

follows from the assumption on the form of the input distribution;

  2. (b)

follows from the inductive argument shown above.

We now turn to prove Theorem 5.

###### Proof of Theorem 5.

The proof of the theorem is completed by the following chain of inequalities:

$\displaystyle C_{\text{fb-csi}}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sup_{\begin{subarray}{c}\\{P(u_{i}|u_{i-1},y^{i-1})\\}_{i\geq
1},\\\
x_{i}=f(u_{i},s_{i-1})\end{subarray}}\liminf_{N\to\infty}\frac{1}{N}\sum_{i=1}^{N}I(U_{i},U_{i-1};Y_{i}|Y^{i-1})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\geq}}\sup_{\begin{subarray}{c}\\{P(u_{i}|u_{i-1},y^{i-1})\\}_{i\geq
1},\\\
x_{i}=f(u_{i},s_{i-1})\end{subarray}}\liminf_{N\to\infty}\frac{1}{N}\sum_{i=1}^{N}I(U_{i},U_{i-1};Y_{i}|Q_{i-1})-I(Y_{i};Y^{i-1}|Q_{i-1})$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\geq}}\liminf_{N\to\infty}\frac{1}{N}\sum_{i=1}^{N}I(U_{i},U_{i-1};Y_{i}|Q_{i-1})-I(Y_{i};Y^{i-1}|Q_{i-1})$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}\liminf_{N\to\infty}\frac{1}{N}\sum_{i=1}^{N}I(U_{i},U_{i-1};Y_{i}|Q_{i-1})$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{=}}I(U^{+},U;Y|Q),$ (24)

where

  1. (a)

follows from Lemma 3.

  2. (b)

follows from adding and subtracting $H(Y_{i}|Q_{i-1})$, and from
$H(Y_{i}|U_{i},U_{i-1},Y^{i-1})\leq H(Y_{i}|U_{i},U_{i-1},Q_{i-1})$.

  3. (c)

follows by considering BCJR input distribution
$P(u_{i}|u_{i-1},y^{i-1})=P(u^{+}|u,q)\in\mathcal{P}_{\pi}$ for all $i$.

  4. (d)

follows from the Markov chain $Y_{i}-Q_{i-1}-Y^{i-1}$.

  5. (e)

follows from the convergence of Markov chains due to the aperiodic input
distribution, and the continuity of the mutual information with respect to the
joint distribution.

∎

##  V Examples

In this section, we demonstrate the DP and the $Q$-graph methods analytically
and numerically for several examples.

###  V-A Look-Ahead State-Dependent Channels

Figure 3:  A state-dependent channel where the state is available at the
encoder with a finite look-ahead $l>0$ in the presence of feedback. Note that
the current state at time $i$ is $S_{i-1}$. Figure 4: The $ZS$ channel
topology for $P_{Y|X,S}(y_{i}|x_{i},s_{i-1})$.

Consider DMCs $P_{Y|X,S}(y_{i}|x_{i},s_{i-1})$ with memoryless states that are
distributed according to $P(s)$. When the states are available at the encoder
causally or non-causally, the capacity is achieved by the Shannon strategy
(SS) [1] or by the Gel’fand–Pinsker (GP) coding scheme [42, 43], respectively.
An intermediate situation that may occur in practice is when the states are
known at the encoder with a finite LA. That is, at time $i$ (with current
state $s_{i-1}$), the encoder has access to the states sequence
$(s_{0},\dots,s_{i-1+l})$, where $l>0$ is a finite LA parameter, as
illustrated in Fig. 3. The capacity of this problem is unknown as a computable
expression, and only sequences of lower and upper bounds are known [19].

In the LA setting, the access of the encoder to future states can be
reformulated as a causal access to states that are Markovian. For instance, if
$l=1$, at time $i$ the encoder knows $s^{i}$, that is, it has access to the
future state $s_{i}$. If we define a new state as the tuple
$\tilde{s}_{i-1}={s}_{i-1}^{i}$, we obtain a FSC characterized by
$P_{Y,\tilde{S}^{+}|X,\tilde{S}}(y_{i},\tilde{s}_{i-1}|x_{i},\tilde{s}_{i-2})=P_{Y|X,\tilde{S}}(y_{i}|x_{i},\tilde{s}_{i-2})P_{\tilde{S}^{+}|\tilde{S}}(\tilde{s}_{i-1}|\tilde{s}_{i-2})$,
that is, the states are Markovian (rather than memoryless), since both
$\tilde{s}_{i-1}$ and $\tilde{s}_{i-2}$ share the element $s_{i-1}$. This
transformation can be trivially extended to $l>1$. The advantage of this
formulation is that Markovian states are a special case of our general FSC
setting.

We consider a state-dependent channel with binary state
$S_{i}\stackrel{{\scriptstyle\text{i.i.d.}}}{{\sim}}$ Bernoulli($0.5$) and
$|{\mathcal{X}}|=|{\mathcal{Y}}|=2$, where the output depends on the input and
the state according to the $ZS$-channel topology in Fig. 4. We thus call this
channel the i.i.d. $ZS$-channel. For $l=1$, we derive a closed-form lower
bound on its feedback capacity utilizing the $Q$-graph method in Theorem 5.

######  Theorem 6.

The feedback capacity of the i.i.d. $ZS$-channel when the state is available
at the encoder with a single LA, $C_{\text{FB-LA-}1}$, is lower-bounded by

$\displaystyle C_{\text{FB-
LA-}1}\geq\textstyle\frac{1}{2}\left(1-H(\frac{1}{8})\right)=\frac{7}{16}\log(7)-1\approx
0.228217.$ (25)

Table II: Our achievable rate for the i.i.d. $ZS$-channel with $1$ LA and feedback, $R_{\text{FB-LA-}1}$, compared with the capacity of various scenarios of SI availability at the encoder and the decoder. Encoder’s SI | Decoder’s SI | Rate
---|---|---
– | – | $C=1-H(\textstyle\frac{1}{4})\approx 0.188722$
Causal ($l=0$) | – | $C_{\text{CSI-E}}=1-H(\textstyle\frac{1}{4})\approx 0.188722$
Single LA ($l=1$) | – | $R_{\text{FB-LA-}1}=\textstyle\frac{1}{2}(1-H(\frac{1}{8}))=\frac{7}{16}\log(7)-1\approx 0.228217$
Non-causal ($l=\infty$) | – | $C_{\text{SI-E}}\approx 0.271553$
Causal / Non-causal | Causal / Non-causal | $C_{\text{SI-ED}}=\textstyle H(\frac{1}{5})-\frac{2}{5}=\log(\frac{5}{4})\approx 0.321928$

The proof of Theorem 6 is given below and relies on a particular choice of
policy in Theorem 5. In Table II, we compare the achievable rate in Theorem 6,
denoted by $R_{\text{FB-LA-}1}$, with the capacities of the SS ($l=0$), the GP
111For evaluating $C_{\text{SI-E}}$, which is concave, we programmed a code
that utilizes CVX, a MATLAB-based modeling system for convex optimization. Our
code is available online in https://github.com/Eli-BGU/Gelfand-Pinsker-
capacity-computation/. ($l=\infty$), the scenario when the state is not
available at either the encoder or the decoder and the scenario when it is
available at the both parties. It can be observed that causal SI ($l=0$) known
at the encoder does not increase the capacity of this channel (see a detailed
proof in Appendix C). However, we note that even a single LA ($l=1$) increases
the feedback capacity by at least $\frac{R_{\text{FB-
LA-}1}-C_{\text{CSI-E}}}{C_{\text{SI-E}}-C_{\text{CSI-E}}}\times 100\approx
48\%$ compared to $C_{\text{SI-E}}$ ($l=\infty$).

We recall that feedback does not increase the capacity for the scenarios when
the SI is available causally/noncausally at the encoder (see, e.g., [44, Prob.
17.17]). However, it is still unknown whether feedback increases the capacity
of LA state-dependent channels. Our result does not provide an answer to this
open problem, but we suspect that the answer is yes, since the feedback is
necessary in the derivation of $R_{\text{FB-LA-}1}$ in the proof of Theorem 6.
That is, the policy is feedback-dependent and relies on a $2$-nodes $Q$-graph.
If there exists an upper bound on the non-feedback LA capacity, which is
smaller than $R_{\text{FB-LA-}1}$, it would establish our claim. The upper
bound given in [19] is represented as a function of a chosen parameter. To
obtain meaningful upper bounds, the parameter should be chosen large, but this
comes at the expense of infeasible computability.

######  Remark 1.

$R_{\text{FB-LA-}1}$ relies on an auxiliary RV with $|{\mathcal{U}}|=4$, and a
particular choice of $x=f(u^{+},\tilde{s})$. However, we were not able to
improve this achievable rate numerically. In particular, we increased
$|{\mathcal{U}}|$, optimized $x=f(u^{+},\tilde{s})$, and evaluated the lower
bound $Q$-graphs (up to size $|{\mathcal{Q}}|=7$), but all led to the same
lower bound on the feedback capacity. These simulations may indicate that
$R_{\text{FB-LA-}1}$ is actually the feedback capacity for $l=1$, but we do
not have a matching converse.

######  Remark 2.

As mentioned, causal SI does not increase the capacity in this example. This
fact is also reflected from the policy used in the proof of Theorem 6 with a
function $x_{i}=f(u_{i},\tilde{s}_{i-1})$ that only depends on $s_{i}$. That
is, the optimal strategy function is independent of $s_{i-1}$.

Figure 5: A $2$-node $Q$-graph where each node corresponds to $Y=0$ or $Y=1$.

###### Proof of Theorem 6.

The proof follows from specifying the equivalent FSC with SI known causally at
the encoder and feedback, then utilizing the $Q$-graph lower bound in Theorem
5. Since $l=1$, we have FSC states $\tilde{{\mathcal{S}}}=\\{0,1,2,3\\}$
corresponding to pairs of consecutive memoryless states
$(s_{i-1},s_{i})\in\\{(0,0),(0,1),(1,0),(1,1)\\}$, respectively. Consider the
$Q$-graph in Fig. 5, $|{\mathcal{U}}|=4$, a function $f(u^{+},\tilde{s})$
given by the following matrix whose rows and columns represent $u^{+}$ and
$s$, respectively, and matrices $P(u^{+}|u,Q=q)$ whose rows and columns
represent $u$ and $u^{+}$, respectively:

$\displaystyle\scriptstyle
x=f(u^{+},\tilde{s})=\scriptstyle\begin{bmatrix}\scriptstyle 0&\scriptstyle
0&\scriptstyle 0&\scriptstyle 0\\\ \scriptstyle 0&\scriptstyle 1&\scriptstyle
0&\scriptstyle 1\\\ \scriptstyle 1&\scriptstyle 0&\scriptstyle 1&\scriptstyle
0\\\ \scriptstyle 1&\scriptstyle 1&\scriptstyle 1&\scriptstyle 1\\\
\end{bmatrix}\ ,\ \scriptstyle P(u^{+}|u,Q=1)=\begin{bmatrix}\scriptstyle
0&\scriptstyle\alpha&\scriptstyle\bar{\alpha}&\scriptstyle 0\\\ \scriptstyle
1&\scriptstyle 0&\scriptstyle 0&\scriptstyle 0\\\ \scriptstyle 0&\scriptstyle
0&\scriptstyle 0&\scriptstyle 1\\\ \scriptstyle
0&\scriptstyle\beta&\scriptstyle\bar{\beta}&\scriptstyle 0\end{bmatrix}\ ,\
\scriptstyle P(u^{+}|u,Q=2)=\begin{bmatrix}\scriptstyle
0&\scriptstyle\beta&\scriptstyle\bar{\beta}&\scriptstyle 0\\\ \scriptstyle
0&\scriptstyle 0&\scriptstyle 0&\scriptstyle 1\\\ \scriptstyle 1&\scriptstyle
0&\scriptstyle 0&\scriptstyle 0\\\ \scriptstyle
0&\scriptstyle\alpha&\scriptstyle\bar{\alpha}&\scriptstyle 0\end{bmatrix}\ ,\
\;\alpha,\beta\in[0,1].$ (26)

The transition matrix $P(\tilde{s}^{+},u^{+},q^{+}|\tilde{s},u,q)$ (given by
Eq. (III)) for the corresponding $(\tilde{S},U,Q)$-graph has a unique
stationary distribution $\pi(\tilde{s},u,q)$ with the following conditional
distribution matrices whose rows and columns represent $u$ and $\tilde{s}$,
respectively:

$\displaystyle\scriptstyle\pi(u,\tilde{s}|Q=1)$
$\displaystyle=\begin{bmatrix}\scriptscriptstyle\frac{7}{64}&\scriptscriptstyle\frac{7}{64}&\scriptscriptstyle\frac{7}{64}&\scriptscriptstyle\frac{7}{64}\\\
\scriptscriptstyle\frac{21\alpha+3\beta}{128}&\scriptscriptstyle\frac{21\alpha+3\beta}{128}&\scriptscriptstyle\frac{7\alpha+\beta}{128}&\scriptscriptstyle\frac{7\alpha+\beta}{128}\\\
\scriptscriptstyle\frac{8-7\alpha-\beta}{128}&\scriptscriptstyle\frac{8-7\alpha-\beta}{128}&\scriptscriptstyle\frac{3(8-7\alpha-\beta)}{128}&\scriptscriptstyle\frac{3(8-7\alpha-\beta)}{128}\\\
\scriptscriptstyle\frac{1}{64}&\scriptscriptstyle\frac{1}{64}&\scriptscriptstyle\frac{1}{64}&\scriptscriptstyle\frac{1}{64}\end{bmatrix},\scriptstyle\pi(u,\tilde{s}|Q=2)=\begin{bmatrix}\scriptscriptstyle\frac{1}{64}&\scriptscriptstyle\frac{1}{64}&\scriptscriptstyle\frac{1}{64}&\scriptscriptstyle\frac{1}{64}\\\
\scriptscriptstyle\frac{7\alpha+\beta}{128}&\scriptscriptstyle\frac{7\alpha+\beta}{128}&\scriptscriptstyle\frac{21\alpha+3\beta}{128}&\scriptscriptstyle\frac{21\alpha+3\beta}{128}\\\
\scriptscriptstyle\frac{3(8-7\alpha-\beta)}{128}&\scriptscriptstyle\frac{3(8-7\alpha-\beta)}{128}&\scriptscriptstyle\frac{8-7\alpha-\beta}{128}&\scriptscriptstyle\frac{8-7\alpha-\beta}{128}\\\
\scriptscriptstyle\frac{7}{64}&\scriptscriptstyle\frac{7}{64}&\scriptscriptstyle\frac{7}{64}&\scriptscriptstyle\frac{7}{64}\end{bmatrix}.$
(27)

Furthermore, by
$P(u^{+},u,y|q)=\sum_{\tilde{s}}\pi(u,\tilde{s}|q)P(u^{+}|u,q)P_{Y|X,\tilde{S}}(y|f(u^{+},\tilde{s}),\tilde{s})$,
one can calculate that

$\displaystyle I(U^{+},U;Y|Q=1)$ $\displaystyle=I(U^{+},U;Y|Q=2)=\textstyle
H\left(\frac{44-21\alpha-3\beta}{64}\right)-\frac{1}{2}\left[H\left(\frac{1}{8}\right)+1\right].$
(28)

Recall that the BCJR-invariant property has to be satisfied. The BCJR-
invariant property has
$|{\mathcal{S}}|\times|{\mathcal{U}}|\times|{\mathcal{Y}}|\times|{\mathcal{Q}}|=64$
constraints that can be reduced to the constraints:

$\displaystyle 7\alpha+\beta-4=0,$ $\displaystyle
49\alpha^{2}+14\alpha\beta-28\alpha+\beta^{2}-4\beta=0,$ $\displaystyle
49\alpha^{2}+14\alpha\beta-84\alpha+\beta^{2}-12\beta+32=0,$

which altogether have two solutions:
$\textstyle\\{\alpha=\frac{4}{7},\beta=0\\}$ or
$\textstyle\\{\alpha=\frac{3}{7},\beta=1\\}$. It can be verified that both
solutions maximize (28). Substituting either of these solutions in (28), we
conclude that $C_{\text{FB-LA-}1}\geq\frac{1}{2}(1-H(\frac{1}{8}))$, which
completes the proof. ∎

###  V-B Unifilar FSCs

A FSC is called a unifilar FSC if for any time $i$ the new channel state is a
deterministic function of the current state, input and output, i.e.,
$s_{i}=g(s_{i-1},x_{i},y_{i})$ for some deterministic function $g(\cdot)$. The
encoder can calculate all of the states causally from $s_{0}$, by using its
sent inputs and the outputs feedback; this explains why it is a special case
of the setting. Here, we pick three examples of strongly connected unifilar
FSCs whose feedback capacity is known from the literature. For each example,
we show analytically that its feedback capacity can be achieved by any of our
two computation tools with $|{\mathcal{U}}|=2$.

####  V-B1 Trapdoor Channel

The trapdoor channel [45], is a unifilar FSC which has binary inputs, outputs
and states, and its state evolution is $s^{+}=s\oplus x\oplus y$. The channel
output depends on the input and the channel state according to the $ZS$
channel topology (see Fig. 4). The feedback capacity of the trapdoor channel
was shown in [34] to be $C_{\text{FB-Trapdoor}}=\log\phi$, where
$\phi\triangleq\frac{\sqrt{5}+1}{2}$ is the known golden ratio. Here, we
provide an alternative achievability for the feedback capacity that can be
derived using either of the tools presented, i.e., the DP formulation (Theorem
4) and the $Q$-graph (Theorem 5).

Figure 6: A $Q$-graph for the trapdoor channel.

######  Corollary 1 (by Theorem 5).

The $Q$-graph in Fig. 6 with $|{\mathcal{U}}|=2$ achieves the known feedback
capacity of the trapdoor channel, i.e.,

$C_{\text{FB-
Trapdoor}}=\max_{\begin{subarray}{c}\\{P(u^{+}|u,q)\\}\in\mathcal{P}_{\text{BCJR}}\\\
x=f(u^{+},s)\end{subarray}}I(U^{+},U;Y|Q)=\log\phi,$ (29)

with specified $f(u^{+},s)=u^{+}\oplus s$ and $P_{U^{+}|U,Q}$ given by
$P_{U^{+}|U,Q}(0|0,q)=\frac{\sqrt{5}-1}{2}$ and $P_{U^{+}|U,Q}(0|1,q)=1$ for
$q=1,...,4$.

The technical proof is given in Appendix D. The policy in Corollary 1 can also
be extracted from a standard evaluation of the VIA with the choice of $|U|=2$
and $f(u^{+},s)=u^{+}\oplus s$. We also explain why this choice achieves the
feedback capacity. Recall that the feedback capacity of connected unifilar
FSCs [34, Theorem 1] is

$\displaystyle C_{\text{FB}}=\sup_{\\{P(x_{i}|s_{i-1},y^{i-1})\\}_{i\geq
1}}\liminf_{N\to\infty}\frac{1}{N}\sum_{i=1}^{N}I(X_{i},S_{i-1};Y_{i}|Y^{i-1}).$
(30)

Comparing our expression in (20) with (30) for any summand $i\geq 1$ gives:

$\displaystyle I(U_{i},U_{i-1};Y_{i}|Y^{i-1})$
$\displaystyle=H(Y_{i}|Y^{i-1})-H(Y_{i}|U_{i},U_{i-1},Y^{i-1})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}H(Y_{i}|Y^{i-1})-H(Y_{i}|X_{i}(U_{i},S_{i-1}),S_{i-1},Y^{i-1})$
$\displaystyle=I(X_{i}(U_{i},S_{i-1}),S_{i-1};Y_{i}|Y^{i-1})$ (31)

where (a) follows from the Markov chain
$Y_{i}-(X_{i},S_{i-1})-(U^{i},X^{i-1},Y^{i-1},S^{i-2})$. However, for our
choice of $|U|=2$ and $f(u_{i},s_{i-1})=u_{i}\oplus s_{i-1}$ it follows that
$u_{i}=s_{i-1}\oplus x_{i}$, and from the channel model we then have
$s_{i}=s_{i-1}\oplus x_{i}\oplus y_{i}=u_{i}\oplus y_{i}$ which implies that
$s_{i-1}=u_{i-1}\oplus y_{i-1}$, i.e., $s_{i-1}$ is a deterministic function
of $(u_{i-1},y_{i-1})$. Hence, (a) is achieved with equality since under this
choice

$\displaystyle
H(Y_{i}|U_{i},U_{i-1},Y^{i-1})=H(Y_{i}|U_{i},U_{i-1},Y^{i-1},S_{i-1})=H(Y_{i}|X_{i},S_{i-1},Y^{i-1}).$
(32)

####  V-B2 Ising Channel

The Ising channel is another unifilar FSC with
${\mathcal{X}}={\mathcal{Y}}={\mathcal{S}}=\\{0,1\\}$. This channel also has
the $ZS$-channel topology as the trapdoor channel, given in Fig. 4, but the
state evolution differs, i.e., $s^{+}=x$, therefore the feedback capacity
differs as well. Its feedback capacity was derived in [36, 46], and was shown
in [36] to be $C_{\text{FB-Ising}}=\max_{a\in[0,1]}2H(a)/(3+a)\approx 0.5755$.

######  Corollary 2 (by Theorem 5).

The $Q$-graph in Fig. 7 with $|{\mathcal{U}}|=2$ achieves the known feedback
capacity of the Ising channel, i.e.,

$C_{\text{FB-Ising}}=\max_{a\in[0,1]}\frac{2H(a)}{3+a}.$ (33)

with specified $f(u^{+},s)=u^{+}$ and $P_{U^{+}|U,Q}$ given by
$P_{U^{+}|U,Q}(0|0,i)=1$, $P_{U^{+}|U,Q}(0|1,q)=0$ for $q=1,3$, and
$P_{U^{+}|U,Q}(0|0,2)=a$, $P_{U^{+}|U,Q}(0|1,4)=\bar{a}$ for some $a\in[0,1]$.

The technical proof is given in Appendix E, where it is also clarified that
$P_{U^{+}|U,Q}(0|1,2)$ and $P_{U^{+}|U,Q}(0|0,4)$ are irrelevant due to the
fact that $P_{U|Q}(1|2)=0$, $P_{U|Q}(0|4)=0$.

Figure 7: A $Q$-graph for the Ising channel.

####  V-B3 Input-constrained BEC

This channel has a binary input sequence with the $(1,\infty)$-RLL constraint,
i.e., it contains no consecutive ones; and instead of binary output [47] it
comprises of a BEC. The input-constrained BEC, which does not fall into the
classical definition of unifilar FSCs, can be considered so by viewing the
input letter as a channel state representing the input constraint, i.e.,
$s^{+}=x$. The feedback capacity of this problem was calculated in [37] to be
$\max_{p\in[0,0.5]}\frac{H(p)}{\frac{1}{\bar{\epsilon}}+p}$, where $\epsilon$
is the erasure probability parameter, and it was generalized in [48] for the
case of the $(0,k)$-RLL when swapping ‘$0$’s and ‘$1$’s.

######  Corollary 3 (by Theorem 5).

The $Q$-graph in Fig. 8 with $|{\mathcal{U}}|=2$ achieves the known feedback
capacity of the input-constrained BEC, i.e.,

$C_{\text{FB-
cBEC}}=\max_{p\in[0,0.5]}\frac{H(p)}{\frac{1}{\bar{\epsilon}}+p}.$ (34)

with specified

$\displaystyle f(u^{+},s)=\begin{cases}1,&s=0\text{ and }u^{+}=1\\\
0,&\text{otherwise}\end{cases}$ (35)

and $P_{U^{+}|U,Q}$ given by $P_{U^{+}|U,Q}(0|1,1)=1$,
$P_{U^{+}|U,Q}(0|0,2)=\bar{p}$, $P_{U^{+}|U,Q}(0|0,3)=\frac{1-2p}{\bar{p}}$,
$P_{U^{+}|U,Q}(0|1,3)=1$, for some $p\in[0,0.5]$.

The technical proof is given in Appendix F, where it is also clarified that
$P_{U^{+}|U,Q}(0|0,1)$ and $P_{U^{+}|U,Q}(0|1,2)$ are irrelevant due to the
fact that $P_{U|Q}(0|1)=0$, $P_{U|Q}(1|2)=0$.

Figure 8: A $Q$-graph for the input constrained BEC.

Next, we focus on a generalization the Ising channel with a stochastic state
evolution rather than deterministic.

###  V-C The Noisy-Ising($\eta$) Channel

We study a generalization of the Ising channel, where the channel state is
obtained as the output of a binary symmetric channel (BSC) whose input is the
channel input. That is, $P(s_{i}|x_{i})$ is a BSC with crossover probability
$\eta\in[0,1]$; we call this generalized channel the noisy-Ising($\eta$)
channel and denote its feedback capacity given a parameter $\eta$ by
$C_{\text{fb-csi}}^{\text{n-Ising}}(\eta)$. The problem symmetry implies that
its feedback capacity is symmetric in $\eta$, i.e., $C_{\text{fb-
csi}}^{\text{n-Ising}}(\bar{\eta})=C_{\text{fb-csi}}^{\text{n-Ising}}(\eta)$,
thus our focus is limited to $\eta\in[0,0.5]$. For these values of $\eta$, we
provide an analytic, closed-form lower bound in Theorem 7 below and two
numerical lower bounds using the DP and $Q$-graph methods.

Figure 9: Lower bounds on the feedback capacity of the noisy-Ising($\eta$)
channel: $R_{\text{Analytic}}$ are analytically given in (36), $R_{\text{DP}}$
and $R_{4\text{-node}}$ are calculated numerically based on the DP tool and
the $4$-node $Q$-graph in Fig. 7, respectively.

######  Theorem 7.

The feedback capacity of the noisy-Ising($\eta$) channel with SI known
causally at the encoder is lower-bounded by

$\displaystyle C_{\text{fb-csi}}^{\text{n-Ising}}(\eta)$
$\displaystyle\geq\textstyle
H\left(\frac{(2-\eta)(a\bar{\eta}+\eta)}{a-2a\eta+2}\right)-\frac{2-a\eta-a}{a-2a\eta+2}H\left(\frac{\eta}{2}\right)-\frac{a(2-\eta)}{a-2a\eta+2}H\left(\frac{\bar{\eta}}{2}\right),\quad\eta\in[0,0.5],$
(36)

where
$a=\frac{4\eta^{2}+\sqrt{16\eta^{2}-31\eta+16}\sqrt{\eta}-5\eta}{4\eta^{2}-10\eta+4}$
for any $\eta\in[0,0.5)$, and $a=\frac{1}{3}$ if $\eta=0.5$.

Theorem 7 is a direct consequence of Theorem 5 with the $2$-node $Q$-graph in
Fig. 5 with $|{\mathcal{U}}|=2$, function $x=u^{+}$ and policy

$\displaystyle P_{U^{+}|U,Q}(1|0,1)$
$\displaystyle=P_{U^{+}|U,Q}(0|1,2)=a\in[0,1],$ $\displaystyle
P_{U^{+}|U,Q}(1|1,1)$ $\displaystyle=P_{U^{+}|U,Q}(0|0,2)=1,$ (37)

and the resulting BCJR constraints reduce to the quadratic equation in $a$:

$\displaystyle(2-5\eta+2\eta^{2})a^{2}+(5-4\eta)\eta
a-2(1-\eta)\eta=0,\quad\eta\in[0,0.5],$ (38)

whose positive solution is $a$ given in the theorem. Specifically, for
$\eta=0.5$, an i.i.d. state is obtained, and

$\displaystyle R_{\text{Analytic}}(0.5)=\textstyle
H\left(\frac{3(a+1)}{8}\right)-H\left(\frac{1}{4}\right)=\textstyle
1-H\left(\frac{1}{4}\right)\approx 0.1887,$ (39)

where $a=\frac{1}{3}$ maximizes (36) and satifies the BCJR condition (38)
simultaneously. This rate is the capacity itself, which is $C_{\text{CSI-E}}$
previously given in Table II. The lower bound in Theorem 7 for any
$\eta\in[0,0.5]$ is illustrated in Fig. 9, and denoted by
$R_{\text{Analytic}}$.

######  Remark 3.

The choice of $P_{U^{+}|U,Q}$ in (37), not only provides a simple, closed-form
achievable rate, but it also implies a simple coding scheme that utilizes the
choice of $x=u^{+}$. Using the feedback, the encoder can compare $y_{i-1}$
with the transmitted symbol $u_{i-1}=x_{i-1}$. If $y_{i-1}\neq x_{i-1}$, i.e.,
the decoder received the wrong symbol, then the encoder keeps transmitting the
same symbol until $y_{i-1}=x_{i-1}$, i.e., until the decoder received the
desired symbol. Only after the decoder receives it properly, the encoder
transmits the opposite symbol with probability $a$.

We implemented the $Q$-graph method (Theorem 5) on this channel with
$|{\mathcal{U}}|=2,3,\dots$ and noticed that increasing this cardinality
beyond $2$ does not improve the $Q$-graph lower bound. Thus, we suspect that
for this channel, the auxiliary RVs in (10) have cardinality
$|{\mathcal{U}}|=2$. Fixing $|{\mathcal{U}}|=2$, we compared the resulting
achievable rates of all the strategy functions
$f:{\mathcal{U}}\times{\mathcal{S}}\to{\mathcal{X}}$ via the DP and $Q$-graph
methods, and discovered empirically that the optimal function with the
greatest rates is, in fact, $x=u^{+}$, for any arbitrary $\eta\in[0,0.5]$ that
was examined.

After discovering the optimality of the $x=u^{+}$ function assuming
$|{\mathcal{U}}|=2$, we utilized the DP method (by the VIA) and the $Q$-graph
method with $|{\mathcal{Q}}|=4$ to evaluate numerical achievable rates for
$\eta\in[0,0.5]$, denoted by $R_{\text{DP}}$ and $R_{4-\text{node}}$,
respectively, as given in Fig. 9. For the latter, we identified that the
optimal $4$-node $Q$-graph is the same $Q$-graph for the original Ising
channel previously shown in Fig. 7. It can be shown that $R_{\text{DP}}$ and
$R_{4-\text{node}}$ are approximate for all $\eta\in[0,0.5]$, and
$R_{\text{Analytic}}$ is approximate to both of them for $\eta\in[0.15,0.5]$.

We note that if the choice $|{\mathcal{U}}|=2,x_{i}=u_{i}$ in (10) is indeed
optimal, that is, the cardinality of $|{\mathcal{U}}|$ is bounded and the
optimal strategy function is independent of the state, it implies that the SI
known causally at the encoder does not increase the feedback capacity in this
example. On the one hand, substituting $u_{i}$ by $x_{i}$ in the capacity
expression (10) gives the achievable rate

$\displaystyle R_{\text{fb-
csi}}=\lim_{N\to\infty}\frac{1}{N}\max_{\begin{subarray}{c}\\{P(x_{i}|x_{i-1},y^{i-1})\\}_{i=1}^{N}\end{subarray}}\sum_{i=1}^{N}I(X_{i},X_{i-1};Y_{i}|Y^{i-1}),$
(40)

which is the feedback capacity of the noisy-Ising($\eta$) channel with SI
known causally at the encoder (if the mentioned choice is optimal). On the
other hand, it can be shown that (40) characterizes the feedback capacity of
any connected FSC without SI where the state depends only on the input,
$P_{S^{+}|X}$, as we can define a new state $x_{i-1}$. That is, the Markov
chain
$P(y_{i}|x^{i},y^{i-1})=P(y_{i}|x_{i},x_{i-1})=\sum_{s_{i-1}}P_{S^{+}|X}(s_{i-1}|x_{i-1})Q_{Y|X,S}(y_{i}|x_{i},s_{i-1})$
holds, and the DI between $X^{N}$ to $Y^{N}$ reduces to (40).

######  Remark 4.

For each of the given examples, the corresponding choice of $|{\mathcal{U}}|$
and $f(\cdot)$ satisfies the Markov chain

$\displaystyle S_{i-1}-(U_{i-1},Y^{i-1})-U^{i-2},$ (41)

which in turn satisfies the Markov chain
$Y_{i}-(U_{i},U_{i-1},Y^{i-1})-U^{i-2}$ and renders the DI between $U^{N}$ and
$Y^{N}$ in the first capacity expression (8) the alternative capacity
expression (10) (which generally lacks a cardinality bound $|{\mathcal{U}}|$),
i.e., $I(U^{N}\to Y^{N})=\sum_{i=1}^{N}I(U_{i},U_{i-1};Y_{i}|Y^{i-1})$. The
Markov chain is shown as follows:

$\displaystyle P(y_{i}|u^{i},y^{i-1})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{s_{i-1}}P(s_{i-1}|u^{i-1},y^{i-1})P(y_{i}|u^{i},s_{i-1},y^{i-1})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\sum_{s_{i-1}}P(s_{i-1}|u_{i-1},y^{i-1})P(y_{i}|u^{i},s_{i-1},y^{i-1})$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\sum_{s_{i-1}}P(s_{i}|u_{i-1},y^{i-1})P_{Y|X,S}(y_{i}|f(u_{i},s_{i-1}),s_{i-1})$
$\displaystyle=P(y_{i}|u_{i},u_{i-1},y^{i-1}),$ (42)

where

  1. (a)

follows from the law of total probability and the Markov chain
$U_{i}-(U^{i-1},Y^{i-1})-S_{i-1}$ implied from the joint distribution in (9);

  2. (b)

follows from the choice of $|{\mathcal{U}}|$ and $f(\cdot)$ inducing the
Markov chain (41);

  3. (c)

follows from the channel mode.

##  VI Proof of the Feedback Capacity

In this section, we prove Theorem 1. In the achievability part (Sec. VI-A), we
show that any rate less than
$\lim_{N\to\infty}\frac{1}{N}\max_{P(u^{N}||y^{N-1},s_{0})}I(U^{N}\to Y^{N})$
is achievable, while in the converse part (Sec. VI-B), we show that rates
greater than $\lim_{N\to\infty}\frac{1}{N}\max_{P(u^{N}||y^{N-1})}I(U^{N}\to
Y^{N})$ are not achievable. Because the former expression is greater than the
latter due to the maximization domain that may depend on $s_{0}$, it will be
deduced that (8) characterizes the capacity of the setting. The proof will be
concluded by showing the cardinality bound
$|{\mathcal{U}}|\leq|{\mathcal{X}}|^{|{\mathcal{S}}|}$ as given in Appendix I.
In the last part (Sec. VI-C) we explain the derivation of Theorem 3 based on
the achievability and converse proofs.

###  VI-A Theorem 1 \- Proof of Achievability

We prove that every rate
$R<\lim_{N\to\infty}\frac{1}{N}\max_{\begin{subarray}{c}P(u^{N}||y^{N-1},s_{0})\end{subarray}}I(U^{N}\rightarrow
Y^{N})$, where ${\mathcal{U}}$ is the set of all strategies, is achievable.
The proof is established on the feedback capacity expression of FSCs without
SI, and comprises of three main steps shown in (45)-(47) below.

The feedback capacity of any FSC without SI was shown in [39] to be lower
bounded by

$\displaystyle C_{\text{fb}}$
$\displaystyle\geq\lim_{N\to\infty}\frac{1}{N}{\max_{\begin{subarray}{c}P(x^{N}||y^{N-1})\end{subarray}}}\min_{s_{0}}I(X^{N}\rightarrow
Y^{N}|s_{0}).$ (43)

Assuming that for such a FSC the encoder is informed of the initial state at
the beginning of each communication block, it immediately follows that the
feedback capacity is lower bounded by

$\displaystyle C_{\text{fb}}$
$\displaystyle\geq\lim_{N\to\infty}\frac{1}{N}{\max_{\begin{subarray}{c}P(x^{N}||y^{N-1},s_{0})\end{subarray}}}\min_{s_{0}}I(X^{N}\rightarrow
Y^{N}|s_{0}).$ (44)

Based on (44), we conclude that the feedback capacity of the setting, i.e.,
strongly connected FSCs with SI known causally at the encoder, is lower
bounded by

$\displaystyle C_{\text{fb-csi}}$
$\displaystyle\geq\lim_{N\to\infty}\frac{1}{N}{\max_{\begin{subarray}{c}P(u^{N}||y^{N-1},s_{0})\end{subarray}}}\min_{s_{0}}I(U^{N}\rightarrow
Y^{N}|s_{0})$ (45)
$\displaystyle=\lim_{N\to\infty}\frac{1}{N}{\max_{\begin{subarray}{c}P(u^{N}||y^{N-1},s_{0})\end{subarray}}}I(U^{N}\rightarrow
Y^{N}|S_{0})$ (46)
$\displaystyle=\lim_{N\to\infty}\frac{1}{N}{\max_{\begin{subarray}{c}P(u^{N}||y^{N-1},s_{0})\end{subarray}}}I(U^{N}\rightarrow
Y^{N}),$ (47)

where ${\mathcal{U}}$ is the set of all strategies, and for (46) $P(s_{0})$ is
arbitrary.

Figure 10: An equivalent setting for the lower bound formulation with a new
FSC $P_{Y,S^{+}|U,S}$ where the state is not available at the encoder.

Proof of Inequality (45): We introduce a new FSC $P_{Y,S^{+}|U,S}$ with input
$U$ (instead of input $X$) without SI (see Fig. 10), where the encoder is
informed of the initial state at the beginning of each communication block.
Inducing a new FSC without SI can be done as follows. Instead of directly
encoding over the input alphabet ${\mathcal{X}}$, at time $i$, the transmitter
encodes an auxiliary RV $u_{i}(m,y^{i-1})$ of alphabet ${\mathcal{U}}$, and
transmits $x_{i}=f(u_{i},s_{i-1})$, where
$f:{\mathcal{U}}\times{\mathcal{S}}\to{\mathcal{X}}$ is a time-invariant
function. The induced FSC is $P_{Y,S^{+}|U,S}=P_{Y,S^{+}|X=f(U,S),S}$, with
input $U_{i}$, current state $S_{i-1}$, output $Y_{i}$ and new state $S_{i}$.
Thus, using (44), we can replace $X_{i}$ with $U_{i}$ in this expression in
order to lower bound $C_{\text{fb-csi}}$ as in (45).

Proof of Equality (46): The proof of this step follows in the same manner as
of the proof of [34, Equality (15) and (16)] (Steps (a)-(d) there) and
considering the following modifications. Replace $X_{i}$ with $U_{i}$, and in
Step (c) use the following lemma instead of [34, Lemma 2].

######  Lemma 4.

(Analogue to [34, Lemma 2]) For a connected FSC with SI known causally at the
encoder, given any input distribution $P_{1}(u^{N}||y^{N-1},s_{0})$ and any
$s^{\prime}_{0}$, there exists an input distribution
$P_{2}(u^{N}||y^{N-1},s^{\prime}_{0})$ such that

$\displaystyle\frac{1}{N}|I_{P_{1}}(U^{N}\rightarrow
Y^{N}|s_{0})-I_{P_{2}}(U^{N}\rightarrow
Y^{N}|s^{\prime}_{0})|\leq\frac{c}{N},$ (48)

where $c$ is a constant that does not depend on $N,s_{0},s^{\prime}_{0}$. The
term $I_{P_{1}}(U^{N}\rightarrow Y^{N}|s_{0})$ denotes the DI induced by
$P_{1}(u^{N}||y^{N-1},s_{0})$, where $s_{0}$ is the initial state. Similarly,
$I_{P_{2}}(U^{N}\rightarrow Y^{N}|s_{0})$ denotes the DI induced by
$P_{2}(u^{N}||y^{N-1},s^{\prime}_{0})$, where $s^{\prime}_{0}$ is the initial
state.

The proof of Lemma 4 is given in Appendix G.

Proof of Equality (47): The last step follows from [39, Lemma 4]), i.e., for
any joint distribution $P(u^{n},y^{n},s_{0})$, $|I(U^{N}\to Y^{N})-I(U^{N}\to
Y^{N}|S_{0})|\leq\log|{\mathcal{S}}|$. Finally, we claim that the limit in
(45) exists as follows. Define
$\underline{\tilde{C}}_{N}\triangleq\frac{1}{N}\max_{P(u^{N}||y^{N-1},s_{0})}\min_{s_{0}}I(U^{N}\to
Y^{N}|s_{0})$. $\lim\underline{\tilde{C}}_{N}$ exists due to the super-
additive property of the sequence
$N(\underline{\tilde{C}}_{N}-\frac{\log{{\mathcal{S}}}}{N})$, which follows
from the proof of [39, Th. 4] when replacing $X_{i}$ with $U_{i}$ and
conditioning on $s_{0}$ in the CCD. ∎

###  VI-B Theorem 1 \- Proof of Converse

Here, we prove that an achievable rate $R$ of any FSC (not necessarily
connected) with feedback and SI known casually at the encoder must satisfy
$R\leq\lim_{N\to\infty}\frac{1}{N}\max_{P(u^{N}||y^{N-1}),{\\{x_{i}=f(u_{i},s_{i-1})\\}}_{i=1}^{N}}I(U^{N}\to
Y^{N})$.

###### Proof.

For a fixed sequence of $(2^{nR},n)$ codes such that $P_{e}^{(n)}\to 0$ as
$n\to\infty$, we bound their achievable rate as

$\displaystyle nR-n\epsilon_{n}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}I(M;Y^{n})$
$\displaystyle=\sum_{i=1}^{n}I(M;Y_{i}|Y^{i-1})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\sum_{i=1}^{n}I(U_{i};Y_{i}|Y^{i-1})$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\max_{{\\{P(u_{i}|u_{i-1},y_{i-1}),P(x_{i}|u_{i},s_{i-1})\\}}_{i=1}^{n}}\sum_{i=1}^{n}I(U_{i};Y_{i}|Y^{i-1})$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}\max_{{\\{P(u_{i}|u_{i-1},y^{i-1}),P(v_{i}),x_{i}=f_{i}(u_{i},v_{i},s_{i-1})\\}}_{i=1}^{n}}\sum_{i=1}^{n}I(U_{i};Y_{i}|Y^{i-1})$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{\leq}}\max_{{\\{P(\tilde{u}_{i}|\tilde{u}_{i-1},y^{i-1}),x_{i}=f_{i}(\tilde{u}_{i},s_{i-1})\\}}_{i=1}^{n}}\sum_{i=1}^{n}I(\tilde{U}_{i};Y_{i}|Y^{i-1})$
$\displaystyle\stackrel{{\scriptstyle(f)}}{{=}}\max_{{\\{P(\tilde{u}_{i}|\tilde{u}_{i-1},y^{i-1}),x_{i}=f(s_{i-1},\tilde{u}_{i},i)\\}}_{i=1}^{n}}\sum_{i=1}^{n}I(\tilde{U}_{i};Y_{i}|Y^{i-1})$
$\displaystyle\stackrel{{\scriptstyle(g)}}{{\leq}}\max_{{\\{P(\accentset{\approx}{u}_{i}|\accentset{\approx}{u}_{i-1},y^{i-1}),x_{i}=f(\accentset{\approx}{u}_{i},s_{i-1})\\}}_{i=1}^{n}}\sum_{i=1}^{n}I(\accentset{\approx}{U}_{i};Y_{i}|Y^{i-1})$
$\displaystyle\stackrel{{\scriptstyle(h)}}{{\leq}}\max_{P(\accentset{\approx}{u}^{n}||y^{n-1}),{\\{x_{i}=f(\accentset{\approx}{u}_{i},s_{i-1})\\}}_{i=1}^{n}}I(\accentset{\approx}{U}^{n}\to
Y^{n}),$ (49)

where $\epsilon_{n}\to 0$ as $n\to\infty$, and

  1. (a)

follows from Fano’s inequality;

  2. (b)

follows from defining $U_{i}\triangleq(M,Y^{i-1})$ for every $i\in[1:n]$. This
definition satisfies $U_{i}=(U_{i-1},Y_{i-1})$ and the Markov chain
$(Y_{i},S_{i})-(X_{i},S_{i-1})-U_{i}$ due to the assumption that the channel
is a FSC;

  3. (c)

follows because the objective is determined by
$\\{P(u_{i},y_{i},s_{i})\\}_{i=1}^{n}$ due to the definition of $U_{i}$ and
from the following lemma, whose proof appears in Appendix H:

######  Lemma 5.

For any $k$, $P(u_{k},y_{k},s_{k})$ is determined by
$\\{P(u_{i}|u_{i-1},y^{i-1})P(x_{i}|u_{i},s_{i-1})\\}_{i=1}^{k}$;

  4. (d)

follows from the Functional Representation Lemma [44, p. 626], i.e., for every
$i\in[1:n]$ there exists a RV $V_{i}$, such that $X_{i}$ can be represented as
a function of $(U_{i},S_{i-1},V_{i})$, where $V_{i}$ is of cardinality
$|\mathcal{V}_{i}|\leq|{\mathcal{U}}_{i}\times{\mathcal{S}}|(|{\mathcal{X}}|-1)+1$,
such that $V_{i}$ is independent of $(U_{i},S_{i-1})$, and the Markov chain
$(Y_{i},S_{i})-(U_{i},S_{i-1},X_{i})-V_{i}$ holds (then
$(Y_{i},S_{i})-(X_{i},S_{i-1})-(V_{i},U_{i})$ holds as well), and from the
following lemma:

######  Lemma 6.

For any $k$, $P(u_{k},y_{k},s_{k})$ is determined by
$\\{P(u_{i}|u_{i-1},y^{i-1})P(v_{i})x_{i}(v_{i},u_{i},s_{i-1})\\}_{i=1}^{k}$;

The proof of Lemma 6 is similar to that of Lemma 5 and therefore it is
omitted;

  5. (e)

follows from defining $\tilde{U_{i}}\triangleq(U_{i},V_{i})$, from the fact
that
$P(\tilde{u}_{i}|\tilde{u}_{i-1},y^{i-1})=P(v_{i}|u_{i-1},v_{i-1},y^{i-1})P(u_{i}|v_{i},u_{i-1},v_{i-1},y^{i-1})$.
$P(v_{i})$ and $P(u_{i}|v_{i},u_{i-1},v_{i-1},y^{i-1})$ are sub-domains of
$P(v_{i}|u_{i-1},v_{i-1},y^{i-1})$ and $P(u_{i}|u_{i-1},y^{i-1})$,
respectively; the mutual information increases since conditioning reduces
entropy;

  6. (f)

follows since there exists an invariant function
$f(\tilde{u},s,i)=f_{i}(\tilde{u}_{i},s_{i-1})$.

  7. (g)

follows from defining $\accentset{\approx}{U}_{i}=(\tilde{U}_{i},T=i)$, where
$T$ represents the time index.

  8. (h)

follows since conditioning reduces entropy;

Finally, we divide (49) by $n$, rename $\accentset{\approx}{U}$ by $U$, and
obtain

$\displaystyle R-\epsilon_{n}$
$\displaystyle\leq\frac{1}{n}\max_{P(u^{n}||y^{n-1}),{\\{x_{i}=f(u_{i},s_{i-1})\\}}_{i=1}^{n}}I(U^{n}\to
Y^{n}),$ (50)

which completes the proof of converse by tending $n\to\infty$. ∎

###  VI-C Proof of Theorem 3

First, we show the LHS of (15), then we show the RHS of it.

Proof of the LHS of (15): Inducing a new FSC $P_{Y,S^{+}|U,S}$ with input $U$
without SI as was explained in the proof of Ineq. (45) and using the feedback
capacity expression for such a setting as given in (43) imply that

$\displaystyle C_{\text{fb-
csi}}\geq\lim_{N\to\infty}\underline{C}_{N}=\sup_{N}\left[\underline{C}_{N}-\frac{\log{{\mathcal{S}}}}{N}\right],$
(51)

where the equality above follows from the super-additive property of the
sequence $N(\underline{C}_{N}-\frac{\log{{\mathcal{S}}}}{N})$, which follows
directly from the proof of [39, Th. 4] when replacing $X_{i}$ with $U_{i}$.

Proof of the RHS of (15): Combining (50) and Lemma 4 implies that

$\displaystyle C_{\text{fb-csi}}$
$\displaystyle\leq\frac{1}{N}\max_{P(u^{N}||y^{N-1})}I(U^{N}\to Y^{N}|S_{0})$
$\displaystyle\leq\lim_{N\to\infty}\overline{C}_{N}$
$\displaystyle=\inf_{N}\left[\underline{C}_{N}+\frac{\log{{\mathcal{S}}}}{N}\right],$
(52)

where the equality follows from the sub-additive property of the sequence
$N(\overline{C}_{N}+\frac{\log{{\mathcal{S}}}}{N})$, which follows directly
from the proof of [39, Th. 16] (by replacing $X_{i}$ with $U_{i}$).

Finally, (15) is a direct consequence of (51) and (52). ∎

##  VII Conclusions

The feedback capacity of connected FSCs with SI available causally at the
encoder was derived. It is expressed as two equivalent multi-letter
expressions which consist of a sequence of auxiliary RVs with memory. The
first expression consists of DI and have a finite cardinality bound for the
set of the auxiliary RVs, but the expression is complicated. The second
expression does not have a finite cardinality bound, yet the expression is
more simple since the auxiliary RVs constitute a first-order Markov process
given the past outputs. Although both of the capacity expressions are multi-
letter, we utilized them to provide computable lower and upper bounds on the
feedback capacity. First, sequences of lower and upper bounds were given,
i.e., for any integer $N$, finite-letter, computable bounds are obtained.
Furthermore, by fixing a finite cardinality $|{\mathcal{U}}|$ in the second
multi-letter capacity expression, which renders it an achievable rate, two
methods were given to compute lower bounds. The first method was a DP
formulation of the achievable rate expression, and the second was a single-
letter $Q$-graph lower bound. These methods were demonstrated on several
examples and were shown to be useful in deriving achievable rates both
analytically and numerically, and they were shown to be tight in some of the
examples.

##  Appendix A Proof of Lemma 2

In this proof, we show three parts regarding the state evolution, disturbance
and reward of the DP.

####  A-1 State evolution

We shall prove that given a policy $\pi=(\mu_{1},\mu_{2},\dots)$, the new DP
state is a time-invariant function of the current DP state, action and
disturbance, i.e., there exists a function $F$ such that
$z_{i}=F(z_{i-1},a_{i},w_{i})$, and in our case
$\beta_{i}=F(\beta_{i-1},a_{i},y_{i})$. For any
$u_{i},s_{i}\in{\mathcal{U}}\times{\mathcal{S}}$,

$\displaystyle\beta_{i}(u_{i},s_{i})$ $\displaystyle=P(u_{i},s_{i}|y^{i})$
$\displaystyle=\sum_{u_{i-1},s_{i-1}}P(u_{i},s_{i},u_{i-1},s_{i-1}|y^{t})$
$\displaystyle=\frac{\sum\limits_{u_{i-1},s_{i-1}}P(u_{i},s_{i},u_{i-1},s_{i-1},y_{i}|y^{i-1})}{P(y_{i}|y^{i-1})}$
$\displaystyle=\frac{\sum\limits_{u_{i-1},s_{i-1}}P(u_{i},s_{i},u_{i-1},s_{i-1},y_{i}|y^{i-1})}{\sum\limits_{u^{\prime}_{i},u_{i-1},s_{i-1}}P(u^{\prime}_{i},u_{i-1},s_{i-1},y_{i}|y^{i-1})}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\frac{\sum_{u_{i-1},s_{i-1}}P(u_{i-1},s_{i-1}|y^{i-1})P(u_{i}|u_{i-1},y^{i-1})P_{Y,S^{+}|X,S}(y_{i},s_{i}|f(u_{i},s_{i-1}),s_{i-1})}{\sum_{u_{i-1},u^{\prime}_{i},s_{i-1}}P(u_{i-1},s_{i-1}|y^{i-1})P(u^{\prime}_{i}|u_{i-1},y^{i-1})P_{Y|X,S}(y_{i}|f(u^{\prime}_{i},s_{i-1}),s_{i-1})}$
(53)
$\displaystyle=\frac{\sum_{u_{i-1},s_{i-1}}\beta_{i-1}(u_{i-1},s_{i-1})a_{i}(u_{i},u_{i-1},y^{i-1})P_{Y,S^{+}|X,S}(y_{i},s_{i}|f(u_{i},s_{i-1}),s_{i-1})}{\sum_{u_{i-1},u^{\prime}_{i},s_{i-1}}\beta_{i-1}(u_{i-1},s_{i-1})a_{i}(u_{i}^{\prime},u_{i-1},y^{i-1})P_{Y|X,S}(y_{i}|f(u^{\prime}_{i},s_{i-1}),s_{i-1})}\text{,}$
(54)

where (a) follows from the channel model and the Markov chain
$U_{i}-(U_{i-1},Y^{i-1})-S_{i-1}$ implied from the joint distribution in (11).
Hence, there exists such a function $F$, i.e.,
$\beta_{i}=F(\beta_{i-1},a_{i},y_{i})$. ∎

####  A-2 Disturbance

We need to show that the disturbance satisfies the Markov chain
$y_{i}-(\beta_{i-1},a_{i})-(\beta^{i-2},a^{i-1},y^{i-1})$. Consider:

$\displaystyle P(y_{i}|\beta^{i-1},y^{i-1},a^{i})$
$\displaystyle=\sum_{u_{i-1},s_{i-1},u_{i}}P(y_{i},u_{i},u_{i-1},s_{i-1}|\beta^{i-1},y^{i-1},a^{i})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{u_{i-1},s_{i-1},u_{i}}P(u_{i-1},s_{i-1}|\beta_{i-1},a_{i})P(u_{i}|u_{i-1},s_{i-1},\beta_{i-1},a_{i})P(y_{i}|u_{i},u_{i-1},s_{i-1},\beta_{i-1},a_{i})$
$\displaystyle=\sum_{u_{i-1},s_{i-1},u_{i}}P(y_{i},u_{i},u_{i-1},s_{i-1}|\beta_{i-1},a_{i})$
$\displaystyle=P(y_{i}|\beta_{i-1},a_{i}){,}$

where (a) follows due to $x_{i}=f(u_{i},s_{i-1})$ and the channel model. ∎

####  A-3 Reward

Finally, we show that the reward is a time-invariant function of the current
DP state and action. Note that the reward depends only on the joint
distribution $P(u_{i},u_{i-1},y_{i}|y^{i-1})$. Consider:

$\displaystyle P(u_{i},u_{i-1},y_{i}|y^{i-1})$
$\displaystyle=\sum_{s_{i-1}}P(u_{i},u_{i-1},y_{i},s_{i-1}|y^{i-1})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{s_{i-1}}P(u_{i-1},s_{i-1}|y^{i-1})P(u_{i}|u_{i-1},y^{i-1})P(y_{i}|f(u_{i},s_{i-1}),s_{i-1})$
$\displaystyle=\sum_{s_{i-1}}\beta_{i-1}(u_{i-1},s_{i-1})a_{i}(u_{i},u_{i-1},y^{i-1})P(y_{i}|f(u_{i},s_{i-1}),s_{i-1})\text{,}$
(55)

where (a) follows from the Markov chain $U_{i}-(U_{i-1},Y^{i-1})-S_{i-1}$ and
the channel model. Therefore,
$g(\beta_{i-1},a_{i})=I(U_{i},U_{i-1};Y_{i}|\beta_{i-1},a_{i})\text{.}$ ∎

##  Appendix B Proof of Lemma 3

The following lemma is technical and will help to establish the proof of Lemma
3.

######  Lemma 7.

(Analogue to [34, Lemma 4]) For any FSC with SI known causally at the encoder,
the following equality holds:

$\displaystyle\lim_{N\to\infty}\frac{1}{N}\max_{P(u^{N}||y^{N-1},s_{0})}\min_{s_{0}}I(U^{N}\to
Y^{N}|s_{0})=\sup_{\\{P(u_{i}|u^{i-1},y^{i-1},s_{0})\\}_{i\geq
1}}\liminf_{N\to\infty}\frac{1}{N}\min_{s_{0}}I(U^{N}\to Y^{N}|s_{0}).$ (56)

The proof of Lemma 7 follows directly from the proof of [34, Lemma 4], which
relies on the super-additive property of the sequence
$N(\underline{C}_{N}-\frac{\log{{\mathcal{S}}}}{N})$. In our case, the super-
additive property follows straightforwardly from the proof of [39, Th. 4] by
replacing $X_{i}$ with $U_{i}$.

Proof of Lemma 3: The proof consists of two parts. In the first part we show
that

$C_{\text{fb-csi}}=\sup_{{\\{P(u_{i}|u^{i-1},y^{i-1})\\}}_{i\geq
1}}\liminf_{N\to\infty}\frac{1}{N}I(U^{N}\to Y^{N}),$ (57)

where $|{\mathcal{U}}|=|{\mathcal{X}}|^{|{\mathcal{S}}|}$. In the second part,
we use a transformation in order to render (57) to (20) for completing the
proof.

In the capacity proof of Theorem 1 (Eqs. (45)-(47) in the achievability proof
and Ineq. (50) in the converse proof), it is shown that for the case of a
connected FSC with SI known causally at the encoder, the LHS of (56)
characterizes the capacity and is equal to
$\lim_{N\to\infty}\frac{1}{N}\max_{P(u^{N}||y^{N-1})}I(U^{N}\to Y^{N})$. By
following the same arguments of (45)-(47) and (50), an equality between the
RHS of (56) and the RHS of (57) also holds. Therefore, using Lemma 7 we obtain
(57).

It is possible to render (57) to (20), i.e., with
$|{\mathcal{U}}_{i}|=|{\mathcal{X}}|^{{|{\mathcal{S}}|}^{i}}$ instead of
$|{\mathcal{U}}|=|{\mathcal{X}}|^{|{\mathcal{S}}|}$ and $(U_{i},U_{i-1})$
shown in the expression instead of $U^{i}$, simply by the transformation given
after Theorem 2 in Section III. ∎

##  Appendix C The SS Does Not Increase The Capacity of the I.I.D.
$ZS$-Channel

######  Theorem 8.

For the i.i.d. $ZS$-channel, SI available causally at the encoder does not
increase the capacity.

###### Proof of Theorem 8.

Recall the SS capacity formula: $C_{\text{CSI-E}}=\max_{p(u),x(u,s)}I(U;Y)$.
Consider $|{\mathcal{U}}|=|{\mathcal{X}}|^{|{\mathcal{S}}|}=4$ with all
possible strategies as detailed in Table III.

Table III: All the strategies of binary input and binary state alphabets, ${\mathcal{S}}={\mathcal{X}}=\\{0,1\\}$. $x(u,s)$ | $s=0$ | $s=1$
---|---|---
$u_{0}$ | $0$ | $0$
$u_{1}$ | $0$ | $1$
$u_{2}$ | $1$ | $0$
$u_{3}$ | $1$ | $1$

Assume that $I_{P_{1}}(U;Y)$ is the capacity of this channel with SI available
causally at the encoder, induced by some input distribution $P_{1}(u)$ with
the corresponding joint distribution

$\displaystyle
P_{1}(u,x,y)=\sum_{s}P(s)P_{1}(u)\mathbbm{1}\\{x=f(u,s)\\}P(y|x,s),$

We construct an input distribution $P_{2}(x)$ with the corresponding
conditional mutual information satisfying $I_{P_{2}}(X;Y)=I_{P_{1}}(U;Y)$
induced by the joint distribution

$\displaystyle P_{2}(x,y)$ $\displaystyle=P_{2}(x)\sum_{s}P(s)P(y|x,s),$ (58)

that is, $X$ is independent of $S$. Clearly, $I_{P_{1}}(U;Y)\geq
I_{P_{2}}(X;Y)$; thus, our goal is to show that $I_{P_{1}}(U;Y)\leq
I_{P_{2}}(X;Y)$. In the construction of $P_{2}(x)$, we only demand that it
satisfies

$\displaystyle P_{2}(x)=P_{1}(x)\quad\forall x\in{\mathcal{X}},$ (59)

where $P_{1}(x)$ is the input distribution induced by $P_{1}(u)$, and given by

$\displaystyle P_{1}(x)$
$\displaystyle=\sum_{u,s}P_{1}(u,s,x)=\sum_{s}P(s)\sum_{u}P_{1}(u)\mathbbm{1}\\{x=f(u,s)\\}.$

Hence, for our channel we obtain

$\displaystyle P_{2}(X=1)$
$\displaystyle\triangleq\textstyle\frac{1}{2}[P_{1}(u_{1})+P_{1}(u_{2})]+P_{1}(u_{3}),$
(60)

From the construction in (59), it follows that the output distributions are
also equal, i.e., $P_{2}(y)=P_{1}(y)$:

$\displaystyle P_{2}(Y=1)$
$\displaystyle=\sum_{s,x}P(s)P_{2}(x)P(y|x,s)=\textstyle\frac{1}{4}P_{2}(x=0)+\frac{3}{4}P_{2}(x=1)=\frac{1}{2}P_{2}(x=1)+\frac{1}{4}$
$\displaystyle=\textstyle\frac{1}{4}P_{1}(u_{1})+\frac{1}{4}P_{1}(u_{2})+\frac{1}{2}P_{1}(u_{3})+\frac{1}{4}$
$\displaystyle=\textstyle\frac{1}{4}P_{1}(u_{0})+\frac{1}{2}P_{1}(u_{1})+\frac{1}{2}P_{1}(u_{2})+\frac{3}{4}P_{1}(u_{3})$
$\displaystyle=\sum_{s,u,x}P(s)P_{1}(u)\mathbbm{1}\\{x=f(u,s)\\}P(y|x,s)$
$\displaystyle=P_{1}(Y=1)$ (61)

Consequently, $H_{P_{2}}(Y)=H_{P_{1}}(Y)$ hold; thus,

$\displaystyle I_{P_{1}}(U;Y)$ $\displaystyle=H_{P_{2}}(Y)-H_{P_{1}}(Y|U)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}H_{P_{2}}(Y)-H_{P_{2}}(Y|X)$
$\displaystyle=I_{P_{2}}(X;Y),$

where (a) follows from defining $q\triangleq H_{P_{1}}(Y|U)-H_{P_{2}}(Y|X)\geq
0$. We show that $q\geq 0$ by applying the channel model as follows:

$\displaystyle H_{P_{1}}(Y|U)$
$\displaystyle=\textstyle[P_{1}(u_{0})+P_{1}(u_{3})]H(\frac{1}{4})+P_{1}(u_{1})+P_{1}(u_{2})$
$\displaystyle=\textstyle[1-P_{1}(u_{1})-P_{1}(u_{2})]H(\frac{1}{4})+P_{1}(u_{1})+P_{1}(u_{2})$
$\displaystyle H_{P_{2}}(Y|X)$ $\displaystyle=\textstyle
P_{2}(x=0)H(\frac{1}{4})+P_{2}(x=1)H(\frac{3}{4})=H(\frac{1}{4}).$ (62)

Hence, we deduce that

$\displaystyle q$
$\displaystyle=\textstyle[P_{1}(u_{1})+P_{1}(u_{2})](1-H(\frac{1}{4}))\geq 0.$
(63)

To conclude, $I_{P_{2}}(X;Y)=I_{P_{1}}(U;Y)$, which implies that causal SI
available at the encoder does not increase the capacity of the i.i.d.
$ZS$-channel. ∎

##  Appendix D Proof of Corollary 1

###### Proof.

Define $b_{1}\triangleq\sqrt{5}-2$, $b_{2}\triangleq\frac{3-\sqrt{5}}{2}$,
$b_{3}\triangleq\frac{\sqrt{5}-1}{2}$, $b_{4}\triangleq 3-\sqrt{5}$. The proof
follows by application of Theorem 5. Constructing the corresponding
$(S,U,Q)$-graph and straightforward calculation of Eq. (III) give the
transition matrix $P(s^{+},u^{+},q^{+}|s,u,q)$, which has a unique stationary
distribution $\pi(s,u,q)$ with the marginal distribution of the $Q$-graph:

$\displaystyle\mu\triangleq[\pi(Q=1),\pi(Q=2),\pi(Q=3),\pi(Q=4)]=\bigg{[}\frac{b_{2}}{b_{4}+2},\frac{1}{b_{4}+2},\frac{b_{2}}{b_{4}+2},\frac{1}{b_{4}+2}\bigg{]}$

and the conditional distribution:

$\displaystyle[\pi_{U,S|Q}(0,0|1),\pi_{U,S|Q}(1,0|1),\pi_{U,S|Q}(0,1|1),\pi_{U,S|Q}(1,1|1)]=[0,b_{2},b_{3},0]$
$\displaystyle[\pi_{U,S|Q}(0,0|2),\pi_{U,S|Q}(1,0|2),\pi_{U,S|Q}(0,1|2),\pi_{U,S|Q}(1,1|2)]=[0,b_{1},b_{4},0]$
$\displaystyle[\pi_{U,S|Q}(0,0|3),\pi_{U,S|Q}(1,0|3),\pi_{U,S|Q}(0,1|3),\pi_{U,S|Q}(1,1|3)]=[b_{3},0,0,b_{2}]$
$\displaystyle[\pi_{U,S|Q}(0,0|4),\pi_{U,S|Q}(1,0|4),\pi_{U,S|Q}(0,1|4),\pi_{U,S|Q}(1,1|4)]=[b_{4},0,0,b_{1}],$

and the BCJR-invariant property for each node can be verified. The reward of
each node, i.e., $I(U^{+},U;Y|Q=i)$ for $i=1,2,...,|{\mathcal{Q}}|$, is
induced from

$\displaystyle P(u^{+},u,y|q)$
$\displaystyle=\sum_{s_{i-1}}\pi(u,s|q)P(u^{+}|u,q)P(y|f(u^{+},s),s)\text{,}$
(64)

yielding:
$r\triangleq[I(U^{+},U;Y|Q=1),I(U^{+},U;Y|Q=2),I(U^{+},U;Y|Q=3),I(U^{+},U;Y|Q=4)]$,
where $I(U^{+},U;Y|Q=i)=1-b_{2}b_{3}$ for $i=1,3$, and
$I(U^{+},U;Y|Q=j)=H\big{(}b_{2}(b_{3}+1)\big{)}-b_{2}b_{4}$ for $j=2,4$.
Finally, $\mu\cdot r^{T}=\log\phi$ is a lower bound on the capacity. ∎

##  Appendix E Proof of Corollary 2

###### Proof.

Constructing the corresponding $(S,U,Q)$-graph and straightforward calculation
of Eq. (III) give the transition matrix $P(s^{+},u^{+},q^{+}|s,u,q)$, which
has a unique stationary distribution $\pi(s,u,q)$ with the marginal
distribution of the $Q$-graph:

$\displaystyle\mu\triangleq[\pi(Q=1),\pi(Q=2),\pi(Q=3),\pi(Q=4)]=\bigg{[}\frac{a+1}{2(a+3)},\frac{1}{a+3},\frac{a+1}{2(a+3)},\frac{1}{a+3}\bigg{]}$

and the conditional distribution:

$\displaystyle[\pi_{U,S|Q}(0,0|1),\pi_{U,S|Q}(1,0|1),\pi_{U,S|Q}(0,1|1),\pi_{U,S|Q}(1,1|1)]=\bigg{[}\frac{\bar{a}}{a+1},0,0,\frac{2a}{a+1}\bigg{]}$
$\displaystyle[\pi_{U,S|Q}(0,0|2),\pi_{U,S|Q}(1,0|2),\pi_{U,S|Q}(0,1|2),\pi_{U,S|Q}(1,1|2)]=[1,0,0,0]$
$\displaystyle[\pi_{U,S|Q}(0,0|3),\pi_{U,S|Q}(1,0|3),\pi_{U,S|Q}(0,1|3),\pi_{U,S|Q}(1,1|3)]=\bigg{[}\frac{2a}{a+1},0,0,\frac{\bar{a}}{a+1}\bigg{]}$
$\displaystyle[\pi_{U,S|Q}(0,0|4),\pi_{U,S|Q}(1,0|4),\pi_{U,S|Q}(0,1|4),\pi_{U,S|Q}(1,1|4)]=[0,0,0,1],$

and the BCJR-invariant property for each node can be verified. The reward of
each node, i.e., $I(U^{+},U;Y|Q=i)$ for $i=1,2,\dots,|{\mathcal{Q}}|$, is

$\displaystyle r\triangleq$
$\displaystyle[I(U^{+},U;Y|Q=1),I(U^{+},U;Y|Q=2),I(U^{+},U;Y|Q=3),I(U^{+},U;Y|Q=4)],$

where $I(U^{+},U;Y|Q=i)=H\big{(}\frac{2a}{a+1}\big{)}$ for $i=1,3$, and
$I(U^{+},U;Y|Q=j)=H\big{(}\frac{a+1}{2}\big{)}+a-1$ for $j=2,4$. Finally,
$\mu\cdot r^{T}=\frac{2H(a)}{a+3}$ is a lower bound on the capacity. ∎

##  Appendix F Proof of Corollary 3

###### Proof.

Throughout the proof, we use the notations
$H_{2}(\alpha),H_{3}(\alpha_{1},\alpha_{2})$ for the distinction between the
binary and ternary entropies (since $|{\mathcal{Y}}|=3$), respectively, where
$\alpha,\alpha_{1},\alpha_{2}\in[0,1]$ and $\alpha_{1}+\alpha_{2}\leq 1$. The
proof follows by application of Theorem 5 with $\left|\mathcal{U}\right|=2$,
function (which respects the input constraint) the $Q$-graph from Fig. 7 and
the auxiliary conditional distribution Constructing the corresponding
$(S,U,Q)$-graph and straightforward calculation of Eq. (III) give the
transition matrix $P(s^{+},u^{+},q^{+}|s,u,q)$, which has a unique stationary
distribution $\pi(s,u,q)$ with the marginal distribution of the $Q$-graph:

$\displaystyle\mu\triangleq[\pi(Q=1),\pi(Q=2),\pi(Q=3)]=\bigg{[}\frac{p\bar{\epsilon}}{1+p\bar{\epsilon}},\frac{\bar{\epsilon}}{1+p\bar{\epsilon}},\frac{\epsilon}{1+p\bar{\epsilon}}\bigg{]}$

and the conditional distribution:

$\displaystyle[\pi_{U,S|Q}(0,0|1),\pi_{U,S|Q}(1,0|1),\pi_{U,S|Q}(0,1|1),\pi_{U,S|Q}(1,1|1)]=[0,0,0,1]$
$\displaystyle[\pi_{U,S|Q}(0,0|2),\pi_{U,S|Q}(1,0|2),\pi_{U,S|Q}(0,1|2),\pi_{U,S|Q}(1,1|2)]=[1,0,0,0]$
$\displaystyle[\pi_{U,S|Q}(0,0|3),\pi_{U,S|Q}(1,0|3),\pi_{U,S|Q}(0,1|3),\pi_{U,S|Q}(1,1|3)]=[\bar{p},0,0,p]$

where $\pi_{U,S|Q}(u,s|q)=\pi_{U,S|Q}(U=u,S=s|Q=q)$, and the BCJR-invariant
property for each node can be verified. The reward of each node, i.e.,
$I(U^{+},U;Y|Q=i)$ for $i=1,2,\dots,|{\mathcal{Q}}|$, is

$\displaystyle r\triangleq$
$\displaystyle[I(U^{+},U;Y|Q=1),I(U^{+},U;Y|Q=2),I(U^{+},U;Y|Q=3)],$

where $I(U^{+},U;Y|Q=1)=0$,
$I(U^{+},U;Y|Q=i)=H_{3}(P(\bar{\epsilon}),\epsilon)-H_{2}(\epsilon)$ for
$i=2,3$. Finally, $\mu\cdot r^{T}=\frac{H(p)}{\frac{1}{\bar{\epsilon}}+p}$ is
a lower bound on the capacity for any $p$. ∎

##  Appendix G Proof of Lemma 4

The proof follows exactly in the same steps of [34, Lemma 2], yet with the
following modifications. Replace each occurrence of $X_{i}$ with $U_{i}$, and
construct $P_{2}(u^{N}||y^{N-1},s^{\prime}_{0})$ as follows. First, construct
$P_{2}(u^{N}||y^{N-1},s^{\prime}_{0})$ due to an input distribution of the
form $\\{P(x_{i}|s_{i-1})\\}_{i=1}^{T}$ with positive probability of reaching
$s_{0}$ in $T$ time epochs, i.e.,
$\sum_{i=1}^{T}P(S_{i}=s_{0}|S_{0}=\tilde{s})>0,\tilde{s}\in{\mathcal{S}}$,
denoted by $\tilde{P}$ 222Such an input distribution $\tilde{P}$ exists
because the FSC is assumed to be strongly connected., repeatedly, until the
time epoch that the channel first reaches $s_{0}$, denoted by time $L$. In
particular, until time $L$, the encoder uses only the $|{\mathcal{X}}|$
strategies $u$ that map all states to a specific input $x$. After each time
epoch within a time-window $T$, the encoder observes the next reached state
$s_{i-1}$ and constructs $P(u_{i})=P(u_{i}|s_{i-1})$ exactly according to the
next time epoch in $\tilde{P}$. This is operatively possible because of the SI
known causally at the encoder at each time epoch. After time $L$, construct
$P_{2}$ exactly as $P_{1}$ would (had time started then), i.e., for $i>L$:

$\displaystyle
P_{2}(u_{i}|u^{i-1},y^{i-1},s_{0})=P_{1}(u_{i-L}|u^{i-1-L},y^{i-1-L},s_{0}).$
(65)

The proof is concluded by following [34, Inequality (13)].

##  Appendix H Proof of lemma 5.

We need to show that for a FSC with feedback and SI known causally at the
encoder, for any $k$, the joint distribution $P(u_{k},y_{k},s_{k})$, where
$u_{i}\triangleq(m,y^{i-1}),i\in[1:k]$, is determined by
$\\{P(u_{i}|u_{i-1},y^{i-1})P(x_{i}|u_{i},s_{i-1})\\}_{i=1}^{k}$. We prove it
by induction. For $n=1$ we have:

$\displaystyle
P(u_{1},y_{1},s_{1})=\sum_{s_{0},x_{1}}P(y_{1},s_{1}|x_{1},s_{0})P(x_{1}|u_{1},s_{0})P(u_{1})P(s_{0}),$

because from the definition $U_{i}\triangleq(M,Y^{i-1})$ it follows that
$U_{1}=M$ is independent of $S_{0}$, and $(Y_{1},S_{1})-(X_{1},S_{0})-U_{1}$
form a Markov chain due to the FSC definition. Assume
$P(u_{k-1},y_{k-1},s_{k-1})$ is determined by
$\\{P(u_{i}|u_{i-1},y^{i-1}),P(x_{i}|u_{i},s_{i-1})\\}_{i=1}^{k-1}$, we have

$\displaystyle
P(u_{k},y_{k},s_{k})=\sum_{s_{k-1}}P(u_{k},y_{k},s_{k}|u_{k-1},y_{k-1},s_{k-1})P(u_{k-1},y_{k-1},s_{k-1}),$

and it is sufficient to show that
$P(u_{k},y_{k},s_{k}|u_{k-1},y_{k-1},s_{k-1})$ depends on
$\\{P(u_{i}|u_{i-1},y_{i-1}),P(x_{i}|u_{i},s_{i-1})\\}_{i=1}^{k}$:

$\displaystyle P(u_{k},y_{k},s_{k}|u_{k-1},y_{k-1},s_{k-1})$
$\displaystyle=\sum_{x_{k}}P(u_{k},y_{k},s_{k},x_{k}|u_{k-1},y_{k-1},s_{k-1})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{x_{k}}P(u_{k}|u_{k-1},y_{k-1})P(x_{k}|u_{k},s_{k-1})P(y_{k},s_{k}|x_{k},s_{k-1},u_{k})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\sum_{x_{k}}P(u_{k}|u_{k-1},y_{k-1})P(x_{k}|u_{k},s_{k-1})P(y_{k},s_{k}|x_{k},s_{k-1})$

where

  1. (a)

follows from $U_{k}=(U_{k-1},Y_{k-1})$ due to the definition of $U_{k}$.

  2. (b)

follows from the Markov chain $(Y_{k},S_{k})-(X_{k},S_{k-1})-U_{k}$ that holds
due to the definition of $U_{k}$ and the fact that the channel is a FSC.

∎

##  Appendix I Proof of $|{\mathcal{U}}|=|{\mathcal{X}}|^{|{\mathcal{S}}|}$

###### Proof.

Let
$T=\\{x_{u}(s):{\mathcal{S}}\to{\mathcal{X}}|u\in\\{0,1,\dots,|{\mathcal{X}}|^{|{\mathcal{S}}|}-1\\}\\}$
be the set of all $|{\mathcal{X}}|^{|{\mathcal{S}}|}$ different functions.
Assume, to the contrary, that (8) is achieved with distribution
$P_{1}(\tilde{u}^{N},y^{N})$ where at least one variable $U_{i},i\in[1:N]$ has
cardinality greater than $|\mathcal{T}|$ (i.e.,
$|{\mathcal{U}}_{i}|>|{\mathcal{X}}|^{|{\mathcal{S}}|}$ for some $i$), and
that it is greater than the objective induced by any distribution
$P(u^{N},y^{N})$ with
$|{\mathcal{U}}_{i}|=|\mathcal{T}|=|{\mathcal{X}}|^{|{\mathcal{S}}|},\forall
i\in[1:N]$. Our goal is to construct such distribution $P_{2}(u^{N},y^{N})$
that achieves (8) as well. The DI induced by $P_{1}(\tilde{u}^{N},y^{N})$ can
be written as

$\displaystyle I_{P_{1}}(U^{N}\to Y^{N}|s_{0})$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}I_{P_{1}}(U^{i};Y_{i}|Y^{i-1},s_{0})$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}H_{P_{1}}(Y_{i}|Y^{i-1})-H_{P_{1}}(Y_{i}|Y^{i-1},U^{i}),$
(66)

where, using the definition of conditional entropy, the entropies in (66) can
explicitly be written as

$\displaystyle
H_{P_{1}}(Y_{i}|Y^{i-1})=-\sum_{y^{i}}\sum_{\tilde{u}^{i}\in{{\mathcal{U}}}^{i}}P_{1}(\tilde{u}^{i},y^{i})\log
P_{1}(y_{i}|y^{i-1}),$ (67) $\displaystyle
H_{P_{1}}(Y_{i}|Y^{i-1},U^{i})=-\sum_{y^{i}}\sum_{\tilde{u}^{i}\in{{\mathcal{U}}}^{i}}P_{1}(\tilde{u}^{i},y^{i})\log
P_{1}(y_{i}|\tilde{u}^{i},y^{i-1}).$ (68)

We are going to show that a legitimate distribution $P_{2}(u^{N},y^{N})$
satisfies $H_{P_{2}}(Y_{i}|Y^{i-1})=H_{P_{1}}(Y_{i}|Y^{i-1})$ and
$H_{P_{2}}(Y_{i}|Y^{i-1},U^{i})=H_{P_{1}}(Y_{i}|Y^{i-1},U^{i})$. We focus on
(68) first, in which

$\displaystyle P_{1}(y_{i}|\tilde{u}^{i},y^{i-1})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{s_{i-1}}P_{1}(s_{i-1}|\tilde{u}^{i},y^{i-1})P_{1}(y_{i}|\tilde{u}^{i},s_{i-1},y^{i-1})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\sum_{s_{i-1}}P_{1}(s_{i-1}|\tilde{u}^{i},y^{i-1})P(y_{i}|f(\tilde{u}_{i},s_{i-1}),s_{i-1})$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}\sum_{s_{i-1}}P_{1}(s_{i-1}|\tilde{u}^{i-1},y^{i-1})P(y_{i}|f(\tilde{u}_{i},s_{i-1}),s_{i-1})$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{=}}\sum_{s_{i-1}}\frac{\sum_{s^{i-2}}\prod_{j=1}^{i-1}P(y_{j},s_{j}|f(\tilde{u}_{j},s_{j-1}),s_{j-1})P(y_{i}|f(\tilde{u}_{i},s_{i-1}),s_{i-1})}{\sum_{s^{i-2}}\big{(}\prod_{j=1}^{i-2}P(y_{j},s_{j}|f(\tilde{u}_{j},s_{j-1}),s_{j-1})\big{)}P(y_{i-1}|f(\tilde{u}_{i-1},s_{i-2}),s_{i-2})},$
(69)

where

  1. (a)

follows follows from the law of total probability;

  2. (b)

follows from the channel model;

  3. (c)

follows from the Markov chain $U_{i}-(U^{i-1},Y^{i-1})-S_{i-1}$;

  4. (d)

follows since
$P_{1}(s_{i-1}|\tilde{u}^{i-1},y^{i-1})=\frac{P_{1}(s_{i-1},\tilde{u}^{i-1},y^{i-1})}{P_{1}(\tilde{u}^{i-1},y^{i-1})}$
where

$\displaystyle P_{1}(s_{i-1},\tilde{u}^{i-1},y^{i-1})$
$\displaystyle=(\prod_{j=1}^{i-1}P_{1}(\tilde{u}_{j}|\tilde{u}^{j-1},y^{j-1}))\sum_{s^{i-2}}\prod_{j=1}^{i-1}P(y_{j},s_{j}|f(\tilde{u}_{j},s_{j-1}),s_{j-1}),$
$\displaystyle P_{1}(\tilde{u}^{i-1},y^{i-1})$
$\displaystyle=(\prod_{j=1}^{i-1}P_{1}(\tilde{u}_{j}|\tilde{u}^{j-1},y^{j-1}))\sum_{s^{i-2}}\prod_{j=1}^{i-2}P(y_{j},s_{j}|f(\tilde{u}_{j},s_{j-1}),s_{j-1})$
$\displaystyle\quad\times P(y_{i-1}|f(\tilde{u}_{i-1},s_{i-2}),s_{i-2}).$

That is, $P_{1}(y_{i}|\tilde{u}^{i},y^{i-1})$ does not depend on the actual
symbols of $\tilde{u}^{i}$; rather, it depends on the strategies
$(f(\tilde{u}_{1},s_{0}),f(\tilde{u}_{2},s_{1}),\dots,f(\tilde{u}_{i},s_{i-1}))$
for all $s_{0}^{i-1}\in{\mathcal{S}}^{i}$. Hence, it has a single, specific
$u^{i}$ of all different $|{\mathcal{X}}|^{{|{\mathcal{S}}|}^{i}}$ vectors
such that $P_{1}(y_{i}|\tilde{u}^{i},y^{i-1})=P_{2}(y_{i}|u^{i},y^{i-1})$,
where the latter is defined similarly to (69) as

$\displaystyle P_{2}(y_{i}|u^{i},y^{i-1})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{s_{i-1}}\frac{\sum_{s^{i-2}}\prod_{j=1}^{i-1}P(y_{j},s_{j}|f(u_{j},s_{j-1}),s_{j-1})P(y_{i}|f(u_{i},s_{i-1}),s_{i-1})}{\sum_{s^{i-2}}\big{(}\prod_{j=1}^{i-2}P(y_{j},s_{j}|f(u_{j},s_{j-1}),s_{j-1})\big{)}P(y_{i-1}|f(u_{i-1},s_{i-2}),s_{i-2})}.$
(70)

Here, we denote the $j$-th vector of strategies by $u^{i}_{(j)}$ (in this
context, it is unimportant how we index the vectors, but it is important to
note that $u^{i}_{(j)}$ and $u^{i}_{(k)}$ are two different vector for $j\neq
k$). Further, we denote some $\tilde{u}^{i}$ with the same strategies as of a
specific $u^{i}_{(j)}$ by $\tilde{u}_{(j)}^{i}$. Consequently, by constructing
$P_{2}(u^{i}_{(k)},y^{i})\triangleq\sum_{\tilde{u}^{i}_{(k)}}P_{1}(\tilde{u}^{i}_{(k)},y^{i})$
for a fixed $y^{i}$ and for all
$k=1,2,\dots,|{\mathcal{X}}|^{{|{\mathcal{S}}|}^{i}}$, we obtain that any term
in (68) satisfies

$\displaystyle\sum_{\tilde{u}^{i}}P_{1}(\tilde{u}^{i},y^{i})\log
P_{1}(y_{i}|\tilde{u}^{i},y^{i-1})$
$\displaystyle=\sum_{k=1}^{|{\mathcal{X}}|^{{|{\mathcal{S}}|}^{i}}}\sum_{\tilde{u}_{(k)}^{i}}P_{1}(\tilde{u}_{(k)}^{i},y^{i})\log
P_{1}(y_{i}|\tilde{u}_{(k)}^{i},y^{i-1})$
$\displaystyle=\sum_{k=1}^{|{\mathcal{X}}|^{{|{\mathcal{S}}|}^{i}}}\sum_{\tilde{u}_{(k)}^{i}}P_{1}(\tilde{u}_{(k)}^{i},y^{i})\log
P_{2}(y_{i}|u_{(k)}^{i},y^{i-1})$
$\displaystyle=\sum_{k=1}^{|{\mathcal{X}}|^{{|{\mathcal{S}}|}^{i}}}\log
P_{2}(y_{i}|u_{(k)}^{i},y^{i-1})\sum_{\tilde{u}_{(k)}^{i}}P_{1}(\tilde{u}_{(k)}^{i},y^{i})$
$\displaystyle=\sum_{k=1}^{|{\mathcal{X}}|^{{|{\mathcal{S}}|}^{i}}}P_{2}(u_{(k)}^{i},y^{i})\log
P_{2}(y_{i}|u_{(k)}^{i},y^{i-1}).$ (71)

Further, the construction of $P_{2}(u^{i}_{(k)},y^{i})$ for all $k$ and all
$y^{i}$ fully attains a constructed joint distribution $P_{2}(u^{i},y^{i})$.
We repeat this construction for all $i\in[1,\dots,N]$, and then we uniquely
get the conditional distribution $P_{2}(u_{i}|u^{i-1},y^{i-1})$ by the
relation

$\displaystyle
P_{2}(u^{i},y^{i})=P_{2}(u^{i-1},y^{i-1})P_{2}(u_{i}|u^{i-1},y^{i-1})P_{2}(y_{i}|u^{i},y^{i-1}),$
(72)

where $P_{2}(u^{i},y^{i}),P(u^{i-1},y^{i-1})$ are known from the previously
described construction, and $P_{2}(y_{i}|u^{i},y^{i-1})$ is given by (70). As
a result, we have a legitimate distribution $P_{2}(u^{N},y^{N})$ with
$|{\mathcal{U}}|=|{\mathcal{X}}|^{|{\mathcal{S}}|}$ that induces the same
value of $H(Y_{i}|Y^{i-1},U^{i})$ as induced by $P_{1}(\tilde{u}^{N},y^{N})$
in (68), for all $i\in[1,\dots,N]$.

It remains to prove that $P_{2}(u^{N},y^{N})$ induces
$H_{P_{2}}(Y_{i}|Y^{i-1})=H_{P_{1}}(Y_{i}|Y^{i-1})$. Now,

$\displaystyle P_{1}(y_{i}|y^{i-1})$
$\displaystyle=\frac{P_{1}(y^{i})}{P_{1}(y^{i-1})}$
$\displaystyle=\frac{\sum_{\tilde{u}^{i}\in{\mathcal{U}}^{i}}P_{1}(\tilde{u}^{i},y^{i})}{\sum_{\tilde{u}^{i-1}\in{\mathcal{U}}^{i-1}}P_{1}(\tilde{u}^{i-1},y^{i})}$
$\displaystyle=\frac{\sum_{k=1}^{|{\mathcal{X}}|^{{|{\mathcal{S}}|}^{i}}}\sum_{\tilde{u}^{i}_{(k)}}P_{1}(\tilde{u}^{i}_{(k)},y^{i})}{\sum_{k=1}^{|{\mathcal{X}}|^{{|{\mathcal{S}}|}^{i-1}}}\sum_{\tilde{u}^{i-1}_{(k)}}P_{1}(\tilde{u}^{i-1}_{(k)},y^{i})}$
$\displaystyle=\frac{\sum_{k=1}^{|{\mathcal{X}}|^{{|{\mathcal{S}}|}^{i}}}P_{2}(u^{i}_{(k)},y^{i})}{\sum_{k=1}^{|{\mathcal{X}}|^{{|{\mathcal{S}}|}^{i-1}}}P_{2}(u^{i-1}_{(k)},y^{i})}$
$\displaystyle=\frac{P_{2}(y^{i})}{P_{2}(y^{i-1})}$
$\displaystyle=P_{2}(y_{i}|y^{i-1}).$ (73)

Hence, for a fixed $y^{i}$, any term in (67) satisfies

$\displaystyle\sum_{\tilde{u}^{i}\in{\mathcal{U}}^{i}}P_{1}(\tilde{u}^{i},y^{i})\log
P_{1}(y_{i}|y^{i-1})$
$\displaystyle=\sum_{k=1}^{|{\mathcal{X}}|^{{|{\mathcal{S}}|}^{i}}}\sum_{\tilde{u}^{i}_{(k)}}P_{1}(\tilde{u}^{i}_{(k)},y^{i})\log
P_{1}(y_{i}|y^{i-1})$
$\displaystyle=\sum_{k=1}^{|{\mathcal{X}}|^{{|{\mathcal{S}}|}^{i}}}P_{2}(u^{i}_{(k)},y^{i})\log
P_{1}(y_{i}|y^{i-1})$
$\displaystyle=\sum_{k=1}^{|{\mathcal{X}}|^{{|{\mathcal{S}}|}^{i}}}P_{2}(u^{i}_{(k)},y^{i})\log
P_{2}(y_{i}|y^{i-1}),$ (74)

and it holds for all $i\in[1:N]$. Finally, $P_{2}(u^{N},y^{N})$ achieves (8)
as well, and the supposition is false. ∎

## References

  * [1] C. E. Shannon, “Channels with side information at the transmitter,” _IBM J. Res. Devel._ , vol. 2, pp. 289–293, Oct. 1958.
  * [2] C. Shannon, “The zero error capacity of a noisy channel,” _IEEE Trans. Inf. Theory_ , vol. 2, no. 3, pp. 8–19, Sep. 1956.
  * [3] P. Sadeghi, R. A. Kennedy, P. B. Rapajic, and R. Shams, “Finite-state Markov modeling of fading channels - a survey of principles and applications,” _IEEE Signal Processing Mag._ , vol. 25, no. 5, pp. 57–80, Sep. 2008.
  * [4] Qinqing Zhang and S. A. Kassam, “Finite-state Markov model for rayleigh fading channels,” _IEEE Trans. Commun._ , vol. 47, no. 11, pp. 1688–1692, Nov. 1999.
  * [5] W. Turin, _Performance analysis of digital transmission systems_. Computer Science Press, Inc., Mar. 1990.
  * [6] M. Hassan, M. M. Krunz, and I. Matta, “Markov-based channel characterization for tractable performance analysis in wireless packet networks,” _IEEE Trans. Commun._ , vol. 3, no. 3, pp. 821–831, May 2004\.
  * [7] H. S. Wang and N. Moayeri, “Finite-state Markov channel-a useful model for radio communication channels,” _IEEE Trans. Veh. Technol._ , vol. 44, no. 1, pp. 163–171, Feb. 1995.
  * [8] C. Pimentel, T. H. Falk, and L. Lisbôa, “Finite-state Markov modeling of correlated Rician-fading channels,” _IEEE Trans. Veh. Technol._ , vol. 53, no. 5, pp. 1491–1501, Sep. 2004.
  * [9] L. Zhong, F. Alajaji, and G. Takahara, “A model for correlated rician fading channels based on a finite queue,” _IEEE Trans. Veh. Technol._ , vol. 57, no. 1, pp. 79–89, 2008.
  * [10] L. Galluccio, A. Lombardo, G. Morabito, S. Palazzo, C. Panarello, and G. Schembra, “Capacity of a binary droplet-based microfluidic channel with memory and anticipation for flow-induced molecular communications,” _IEEE Trans. Commun._ , vol. 66, no. 1, pp. 194–208, Jan. 2018.
  * [11] N. Farsad, H. B. Yilmaz, A. Eckford, C. Chae, and W. Guo, “A comprehensive survey of recent advancements in molecular communication,” _IEEE Communications Surveys Tutorials_ , vol. 18, no. 3, pp. 1887–1919, thirdquarter 2016.
  * [12] K. E. Schouhamer Immink, P. H. Siegel, and J. K. Wolf, “Codes for digital recorders,” _IEEE Trans. Inf. Theory_ , vol. 44, no. 6, pp. 2260–2299, Oct. 1998.
  * [13] L. B. D. Blackwell and A. Thomasian, “Proof of Shannon’s transmission theorem for finite-state indecomposable channels,” _Ann. Math. Stat_ , vol. 29, pp. 1209–1220, Dec. 1958.
  * [14] R. G. Gallager, _Information theory and reliable communication_. New-York, NY, USA: Wiley, 1968.
  * [15] P. O. Vontobel, A. Kavcic, D. M. Arnold, and H. Loeliger, “A generalization of the blahut–arimoto algorithm to finite-state channels,” _IEEE Trans. Inf. Theory_ , vol. 54, no. 5, pp. 1887–1918, May 2008.
  * [16] J. Ziv, “Universal decoding for finite-state channels,” _IEEE Trans. Inf. Theory_ , vol. 31, no. 4, pp. 453–460, Jul. 1985.
  * [17] H. D. Pfister, J. B. Soriaga, and P. H. Siegel, “On the achievable information rates of finite state ISI channels,” in _GLOBECOM IEEE Global Telecommun. Conf._ , Nov. 2001, pp. 2992–2996.
  * [18] R. Gray, M. Dunham, and R. Gobbi, “Ergodicity of Markov channels,” _IEEE Trans. Inf. Theory_ , vol. 33, no. 5, pp. 656–664, Sep. 1987.
  * [19] T. Weissman and A. El Gamal, “Source coding with limited-look-ahead side information at the decoder,” _IEEE Trans. Inf. Theory_ , vol. 52, no. 12, pp. 5218–5239, 2006.
  * [20] A. Das and P. Narayan, “Capacities of time-varying multiple-access channels with side information,” _IEEE Trans. Inf. Theory_ , vol. 48, no. 1, pp. 4–25, 2002.
  * [21] U. Erez, S. Shamai, and R. Zamir, “Capacity and lattice strategies for canceling known interference,” _IEEE Trans. Inf. Theory_ , vol. 51, no. 11, pp. 3820–3833, 2005.
  * [22] O. Ozel, J. Yang, and S. Ulukus, “Optimal broadcast scheduling for an energy harvesting rechargeable transmitter with a finite capacity battery,” _IEEE Trans. Commun._ , vol. 11, no. 6, pp. 2193–2203, 2012.
  * [23] K. Tutuncuoglu and A. Yener, “Optimum transmission policies for battery limited energy harvesting nodes,” _IEEE Trans. Commun._ , vol. 11, no. 3, pp. 1180–1189, 2012.
  * [24] W. Mao and B. Hassibi, “On the capacity of a communication system with energy harvesting and a limited battery,” in _2013 IEEE Int. Symp. Inf. Theory (ISIT)_. IEEE, 2013, pp. 1789–1793.
  * [25] Y. Dong and A. Özgür, “Approximate capacity of energy harvesting communication with finite battery,” in _2014 IEEE Int. Symp. Inf. Theory (ISIT)_. IEEE, 2014, pp. 801–805.
  * [26] V. Jog and V. Anantharam, “An energy harvesting awgn channel with a finite battery,” in _2014 IEEE Int. Symp. Inf. Theory (ISIT)_. IEEE, 2014, pp. 806–810.
  * [27] D. Shaviv, P.-M. Nguyen, and A. Özgür, “Capacity of the energy-harvesting channel with a finite battery,” _IEEE Trans. Inf. Theory_ , vol. 62, no. 11, pp. 6436–6458, 2016.
  * [28] K. Tutuncuoglu, O. Ozel, A. Yener, and S. Ulukus, “The binary energy harvesting channel with a unit-sized battery,” _IEEE Trans. Inf. Theory_ , vol. 63, no. 7, pp. 4240–4256, 2017.
  * [29] E. Shemuel, O. Sabag, and H. H. Permuter, “The feedback capacity of noisy output is the state (nost) channels,” _IEEE Trans. Inf. Theory_ , vol. 68, no. 8, pp. 5044–5059, 2022.
  * [30] O. Sabag, H. H. Permuter, and H. D. Pfister, “A single-letter upper bound on the feedback capacity of unifilar finite-state channels,” _IEEE Trans. Inf. Theory_ , vol. 63, no. 3, pp. 1392–1409, Mar. 2017.
  * [31] S. Tatikonda and S. K. Mitter, “Control under communication constraints,” _IEEE Trans. Automatic Control_ , vol. 49, pp. 1056–1068, 2000.
  * [32] S. Tatikonda and S. Mitter, “The capacity of channels with feedback,” _IEEE Trans. Inf. Theory_ , vol. 55, no. 1, pp. 323–349, Jan. 2009.
  * [33] S. Yang, A. Kavcic, and S. Tatikonda, “Feedback capacity of finite-state machine channels,” _IEEE Trans. Inf. Theory_ , vol. 51, no. 3, pp. 799–810, 2005.
  * [34] H. H. Permuter, P. W. Cuff, B. Van-Roy, and T. Weissman, “Capacity of the trapdoor channel with feedback,” _IEEE Trans. Inf. Theory_ , vol. 54, pp. 3150–3165, Jul. 2008.
  * [35] O. Sabag, B. Huleihel, and H. H. Permuter, “Graph-based encoders and their performance for finite-state channels with feedback,” _IEEE Trans. Commun._ , vol. 68, no. 4, pp. 2106–2117, Apr. 2020.
  * [36] O. Elishco and H. Permuter, “Capacity and coding for the Ising channel with feedback,” _IEEE Trans. Inf. Theory_ , vol. 60, no. 9, pp. 5138–5149, 2014\.
  * [37] O. Sabag, H. Permuter, and N. Kashyap, “The feedback capacity of the binary erasure channel with a no-consecutive-ones input constraint,” _IEEE Trans. Inf. Theory_ , vol. 62, no. 1, pp. 8–22, Jan. 2016.
  * [38] J. Massey, “Causality, feedback and directed information,” in _Proc. Citeseer Int. Symp. Inf. Theory Applic. (ISITA)_ , Nov. 1990, pp. 303–305.
  * [39] H. H. Permuter, T. Weissman, and A. J. Goldsmith, “Finite state channels with time-invariant deterministic feedback,” _IEEE Trans. Inf. Theory_ , vol. 55, no. 2, pp. 644–662, Feb. 2009.
  * [40] G. Kramer, “Capacity results for the discrete memoryless network,” _IEEE Trans. Inf. Theory_ , vol. 49, no. 1, pp. 4–21, Jan. 2003.
  * [41] H. Permuter, T. Weissman, and A. Goldsmith, “Capacity of finite-state channels with time-invariant deterministic feedback,” in _Proc. IEEE Int. Symp. Inf. Theory (ISIT)_ , Jul. 2006, pp. 64–68.
  * [42] S. I. Gel’fand and M. S. Pinsker, “Coding for channels with random parameters,” _Prob. Contr. and Inf. Theory_ , vol. 9, no. 1, pp. 19–31, 1980\.
  * [43] C. Heegard and A. A. E. Gamal, “On the capacity of computer memory with defects,” _IEEE Trans. Inf. Theory_ , vol. 29, no. 5, pp. 731–739, Sep. 1983\.
  * [44] A. El Gamal and Y.-H. Kim, _Network Information Theory_. Cambridge, U.K.: Cambridge Univ. Press, 2011.
  * [45] D. Blackwell, “Information theory, ser. modern mathematics for the engineer: Second series,” pp. 183–193, 1961.
  * [46] A. Sharov and R. M. Roth, “On the capacity of generalized Ising channels,” _IEEE Trans. Inf. Theory_ , vol. 63, no. 4, pp. 2338–2356, 2017.
  * [47] O. Sabag, H. H. Permuter, and N. Kashyap, “Feedback capacity and coding for the BIBO channel with a no-repeated-ones input constraint,” _IEEE Trans. Inf. Theory_ , vol. 64, no. 7, pp. 4940–4961, Jul. 2018.
  * [48] O. Peled, O. Sabag, and H. H. Permuter, “Feedback capacity and coding for the $(0,k)$-RLL input-constrained bec,” _IEEE Trans. Inf. Theory_ , vol. 65, no. 7, pp. 4097–4114, Jul. 2019.