Channel Coding and Source Coding With Increased Partial Side Information

Abstract

Let $(S_{1,i},S_{2,i})\sim \mathrm{i}.\mathrm{i}.\mathrm{d}p(s_1,s_2)$, $i=1,2,\cdots$ be a memoryless, correlated partial side information sequence. In this work, we study channel coding and source coding problems where the partial side information $(S_1,S_2)$ is available at the encoder and the decoder, respectively, and, additionally, either the encoder’s or the decoder’s side information is increased by a limited-rate description of the other’s partial side information. We derive six special cases of channel coding and source coding problems and we characterize the capacity and the rate-distortion functions for the different cases. We present a duality between the channel capacity and the rate-distortion cases we study. In order to find numerical solutions for our channel capacity and rate-distortion problems, we use the Blahut-Arimoto algorithm and convex optimization tools. Finally, we provide several examples corresponding to the channel capacity and the rate-distortion cases we presented.

1. Introduction

In this paper, we investigate point-to-point channel models and rate-distortion problem models where both users have different and correlated partial side information and where, in addition, a rate-limited description of one of the user’s side information is delivered to the other user. We then show the duality between the channel models and the rate-distortion models we investigate.

For the convenience of the reader, we refer to the state information as the side information, to the partial side information that is available to the encoder as the encoder’s side information (ESI) and to the partial side information that is available to the decoder as the decoder’s side information (DSI). We refer ro the rate-limited description of the other user’s side information as the increase in the side information. For example, if the decoder is informed with its DSI and, in addition, with a rate-limited description of the ESI, then we would say that the decoder is informed with increased DSI.

To make the motivation for this paper clear, let us look at the simple example depicted in Figure 1. In this setup, the communication between the Tx-Rx pair (the encoder-decoder) is interrupted by an undesired signal, S. The encoder and the decoder do not know S perfectly, but they each possess a version of S; the encoder knows $S_1$ (the ESI) and the decoder knows $S_2$ (the DSI). For this example, let us assume that the source of the interruption is physically located in close proximity to the encoder (potentially, both signal sources are co-located). Thus, we assume that the encoder “knows more on S” then the decoder; i.e., $H(S|S_1)<H(S|S_2)$. We assume also that the transmitter can provide a rate-limited description of the ESI, $S_1$, to the decoder, thus increasing his DSI. In these circumstances, we pose the question; what is the capacity of the channel between the encoder and the decoder? This question is of practical importance. Knowing the channel capacity allows one to analyze its communication system better, answering questions such as “how close is the communication system’s performance to the capacity?” and “how important is the quality of the side information to the throughput?”. Moreover, it allows one to design better practical codes, like polar codes and LDPC codes.

1.1. Channel Capacity in the Presence of State Information

The three problems of channel capacity in the presence of state information that we address in this paper are presented in Figure 2a. We make the assumption that the encoder is informed with partial state information, the ESI ($S_1$), and the decoder is informed with different, but correlated, partial state information, which is the DSI ($S_2$). The channel capacity problem cases are:

• Case 1: The decoder is provided with increased DSI; i.e., in addition to the DSI, the decoder is also informed with a rate-limited description of the ESI.
• Case 2: The encoder is informed with increased ESI.
• Case 2${}_C$: Similar to Case 2, with the exception that the ESI is known to the encoder in a causal manner. Notice that the rate-limited description of the DSI is still known to the encoder noncausally.

We will subsequently provide the capacity of Case 1 and Case 2${}_C$ and characterize the lower and the upper bounds on Case 2, which differ only by a Markov relation. The results for the first case under discussion, Case 1, can be concluded from Steinberg’s problem [1]. In [1], Steinberg introduced and solved the case in which the encoder is fully informed with the ESI and the decoder is informed with a rate-limited description of the ESI. Therefore, the innovation in Case 1 is that the decoder is also informed with the DSI. The solution for this problem can be derived by considering the DSI to be a part of the channel’s output in Steinberg’s solution. In the proof of the converse in his paper, Steinberg uses a new technique that involves using the Csiszár sum twice in order to get to a single-letter bound on the rate. We shall use this technique to present a duality in the converse of the Gelfand–Pinsker [2] and the Wyner-Ziv [3] problems, which, by themselves, constitute the basis for most of the results in this paper. In [3], Wyner and Ziv presented the rate-distortion function for data compression problems with side information at the decoder. We make use of their coding scheme in the achievability proof of the lower bound of Case 2 for describing the ESI with a limited rate at the decoder. In [2], Gelfand and Pinsker presented the capacity for a channel with noncausal channel state information (CSI) at the encoder. We use their coding scheme in the achievability proof of Case 1 and the lower bound of Case 2 for transmitting information over a channel where the ESI is the state information at the encoder. Therefore, we combine in our problems the Gelfand–Pinsker and the Wyner-Ziv problems. Another related paper is [4], in which Shannon presented the capacity of a channel with causal CSI at the transmitter. We make use of Shannon’s result in the achievability proof of Case 2${}_C$ for communicating over a channel with causal ESI at the encoder. We also use Shannon’s strategies [4], for developing an iterative algorithm to calculate the capacity of the cases we present in this paper.

Some related papers that can be found in the literature are mentioned herein. Heegard and El Gamal [5] presented a model of a state-dependent channel, where the transmitter is informed with the CSI at a rate limited to $R_e$ and the receiver is informed with the CSI at a rate limited to $R_d$. This result relates to Case 1, Case 2 and Case 2${}_C$ since we consider the rate-limited description of the ESI or the DSI as side information known at both the encoder and the decoder. Cover and Chiang [6] extended the Gelfand–Pinsker problem and the Wyner-Ziv problem to the case where both the encoder and the decoder are provided with different, but correlated, partial side information. They also showed a duality between the two cases, which is a topic that will be discussed later in this paper. Rozenzweig et al. [7] and Cemal and Steinberg [8] studied channels with partial state information at the transmitter. A detailed subject review on channel coding with state information was given by Keshet et al. in [9].

In addition to these three cases, we also present a more general case, where both the encoder and the decoder are informed with increased partial side information. i.e., the encoder and the decoder are each informed with partial side information, and, in addition, with a rate-limited description of the other’s side information. We provide a lower bound on the capacity for this case; however, this bound does not necessarily coincide with the capacity and, therefore, this problem remains open.

1.2. Rate-Distortion with Side Information

In this paper, we address three problems of rate-distortion with side information, as presented in Figure 2b. In common with the channel capacity problems, we assume that the encoder is informed with the ESI ($S_1$) and the decoder is informed with the DSI ($S_2$), where the source, X, the ESI and the DSI are correlated. The rate-distortion problem cases we investigate in this paper are:

• Case 1: The decoder is provided with increased DSI.
• Case 1${}_C$: Similar to Case 1, with the exception that the ESI is known to the encoder in a causal manner. The rate-limited description of the ESI is still known to the decoder noncausally.
• Case 2: The encoder is informed with increased ESI.

Case 2 is a special case of Kaspi’s [10] two-way source coding for $K=1$. In [10], Kaspi introduced a model of multistage communication between two users, where each user may transmit up to K messages to the other user, dependent on the source and the previous received messages. For Case 2, we can consider sending the rate-limited description of the DSI as the first transmission and then, sending a function of the source, the ESI and the rate-limited description of the DSI as the second transmission. This fits into Kaspi’s problem for $K=1$ and thus Kaspi’s theorem also applies to Case 2. Kaspi’s problem was later extended by Permuter et al. [11] to the case where a common rate-limited side information message is being conveyed to both users. Another strongly related paper is Wyner and Ziv’s paper [3]. In the achievability of Case 1, we use the Wyner-Ziv coding scheme twice; once for describing the ESI at the decoder where the DSI is the side information and once for the main source and the ESI where the DSI is the side information. The rate-limited description of the ESI is the side information provided to both the encoder and the decoder. In [6] there is an extension to the Wyner-Ziv problem to the case where both the encoder and the decoder are provided with correlated partial side information. Weissman and El Gamal [12] and Weissman and Merhav [13] presented source coding with causal side information at the decoder, which relates to Case 1${}_C$. In addition, we present a generalized case of rate-distortion with two-sided increased partial side information. In this problem setup the encoder and the decoder are each informed with partial side information, and, in addition, with a rate-limited description of the other’s side information. We present an upper bound on the optimal rate; however, this bound does not necessarily coincide with the optimal rate and, therefore, this problem remains open.

1.3. Duality

Within the scope of this work, we point out a duality relation between the channel capacity and the rate-distortion cases we discuss. The operational duality between channel coding and source coding was first mentioned by Shannon [14]. Pradhan et al. [15] and Pradhan and Ramchandran [16] studied the functional duality between some cases of channel coding and source coding, including the duality between the Gelfand–Pinsker problem and the Wyner-Ziv problem. This duality was also described by Cover and Chiang in [6], where they provided a transformation that makes duality between channel coding and source coding with two-sided state information apparent. Zamir et al. [17] and Su et al. [18] utilized the duality between channel coding and source coding with side information to develop coding schemes for the dual problems. Goldfeld, Permuter and Kramer [19] studied the duality between a two-encoder source coding with one-sided, rate-limited coordination and a semi-deterministic broadcast channel with one-sided decoder cooperation. More related works on the topic of duality can be found in the papers of Asnani et al. [20] and Gupta and Verdu [21].

In our paper, we show that the channel capacity cases and the rate-distortion cases we discuss are operational duals in a way that strongly relates to the Wyner-Ziv and Gelfand–Pinsker duality. We also provide a transformation scheme that shows this duality in a clear way. Moreover, we show a duality relation between Kaspi’s problem and Steinberg’s [1] problem by showing a duality relation between Case 2 source coding and Case 1 channel coding. Also, we show duality in the converse parts of the Gelfand–Pinsker and the Wyner-Ziv problems. We show that both converse parts can be proven in a perfectly dual way by using the Csiszár sum twice.

1.4. Computational Algorithms

Calculating channel capacity and rate-distortion problems, in general, and the Gelfand–Pinsker and the Wyner-Ziv problems, in particular, is not straightforward. Blahut [22] and Arimoto [23] suggested an iterative algorithm (to be referred to as the B-A algorithm) for numerically computing the channel capacity and the rate-distortion problems. Willems [24] and Dupuis et al. [25] presented iterative algorithms based on the B-A algorithm for computing the Gelfand–Pinsker and the Wyner-Ziv functions. We use principles from Willems’ algorithms to develop an algorithm to numerically calculate the capacity for the cases we presented. More B-A based iterative algorithms for computing channel capacity and rate-distortion with side information can be found in [26,27]. A Blahut-Arimoto based algorithm for maximizing the directed-information can be found in [28].

1.5. Organization of the Paper and Main Contributions

To summarize, the main contributions of this paper are:

• We characterize the capacity and the rate-distortion functions of new channel and source coding problems with increased partial side information. We quantify the gain in the rate that can be achieved by having the parties involved share their partial side information with each other over a rate-limited secondary channel.
• We show a duality relationship between the channel capacity cases and the rate-distortion cases that we discuss.
• We provide a B-A based algorithm to solve the channel capacity problems we describe.
• We show a duality between the Gelfand–Pinsker capacity converse and the Wyner-Ziv rate-distortion converse.

The reminder of this paper is organized as follows. In Section 2 we introduce some notations for this paper and provide the settings of three channel coding and three source coding cases with increased partial side information. In Section 3 we present the main results for coding with increased partial side information; we provide the capacity and the rate-distortion for the cases we introduced in Section 2 and we point out the duality between the cases we examined. Section 4 contains illuminating examples for the cases discussed in the paper. In Section 5 we describe the B-A based algorithm we used in order to solve the capacity examples. We conclude the paper in Section 6 and we highlight two open problems; channel capacity and rate-distortion with two-sided rate-limited partial side information. Appendix A contains the duality derivation for the converse proofs of the Gelfand–Pinsker and the Wyner-Ziv problems and Appendix B, Appendix C, Appendix D and Appendix E contain the proofs for our theorems and lemmas.

2. Problem Setting and Definitions

In this section, we describe and formally define three cases of channel coding problems and three cases of source coding problems. All six cases are presented in Figure 2a,b.

Notations. 

We use subscripts and superscripts to denote vectors in the following ways: $x^j=(x_1,\cdots ,x_j)$ and $x_i^j=(x_i,\cdots ,x_j)$ for $i\le j$. Moreover, we use the lower case x to denote sample value, the upper case X to denote a random variable, the calligraphic letter $\mathcal{X}$ to denote the alphabet of X, $|\mathcal{X}|$ to denote the cardinality of the alphabet of X and $p(x)$ to denote the probability $Pr\{X=x\}$. We use the notation ${\mathcal{T}}_{ϵ}^{(n)}(X)$ to denote the strongly typical set of the random variable X, as defined in [29] (Chapter 11).

2.1. Definitions and Problem Formulation—Channel Coding with State Information

Definition 1.

A discrete channel is defined by the set $\{\mathcal{X},{\mathcal{S}}_1,{\mathcal{S}}_2,p(s_1,s_2),p(y|x,s_1,s_2),\mathcal{Y}\}$. The channel’s input sequence, $\{X_i\in \mathcal{X},i=1,2,\cdots \}$, the ESI sequence, $\{S_{1,i}\in {\mathcal{S}}_1,i=1,2,\cdots \}$, the DSI sequence, $\{S_{2,i}\in {\mathcal{S}}_2,i=1,2,\cdots \}$, and the channel’s output sequence, $\{Y_i\in \mathcal{Y},i=1,2,\cdots \}$, are discrete random variables drawn from the finite alphabets $\mathcal{X},{\mathcal{S}}_1,{\mathcal{S}}_2,\mathcal{Y}$, respectively. Denote the message and the message space as $W\in \{1,2,\cdots ,2^{nR}\}$ and let $\widehat{W}$ be the reconstruction of the message W. The random variables $(S_{1,i},S_{2,i})$ are i.i.d. $\sim p(s_1,s_2)$ and the channel is memoryless, i.e., at time i, the output, $Y_i$, has a conditional distribution of

$$\begin{array}{c}\hfill p(y_i|x^i,s_1^i,s_2^i,y^{i-1})=p(y_i|x_i,s_{1,i},s_{2,i}).\end{array}$$

(1)

In the remainder of the paper, unless specifically mentioned otherwise, we refer to the ESI and the DSI as if they are known to the encoder and the decoder, respectively, in a noncausal manner. Also, as noted before, we use the term increased side information to indicate that the user’s side information also includes a rate-limited description of the other user’s partial side information. For example, when the decoder is informed with the DSI and with a rate-limited description of the ESI we would say that the decoder is informed with increased DSI.

Problem Formulation.

For the channel $p(y|x,s_1,s_2)$, consider the following channel coding problem cases:

• Case 1: The encoder is informed with ESI and the decoder is informed with increased DSI.
• Case 2: The encoder is informed with increased ESI and the decoder is informed with DSI.
• Case 2${}_C$: The encoder is informed with increased causal ESI ($S_1^i$ at time i) and the decoder is informed with DSI. This case is the same as Case 2, except for the causal ESI.

All cases are presented in Figure 2a.

Definition 2.

A $(n,2^{nR},2^{n{R}_j^{\prime }})$ code, $\{j\in 1,2\}$, for a channel with increased partial side information, as illustrated in Figure 2a, consists of two encoders and one decoder. The encoders are f and $f_v$, where f is the encoder for the channel’s input and $f_v$ is the encoder for the side information, and the decoder is g, as described for each case:

Case 1: Two encoders

$$\begin{array}{c}{f}_v:{\mathcal{S}}_1^n\to \{1,2,\cdots ,2^{n{R}_1^{\prime }}\},\hfill \\ f:\{1,2,\cdots ,2^{nR}\}\times {\mathcal{S}}_1^n\times \{1,2,\cdots ,2^{n{R}_1^{\prime }}\}\to {\mathcal{X}}^n,\hfill \end{array}$$

and a decoder

$$\begin{array}{c}g:{\mathcal{Y}}^n\times {\mathcal{S}}_2^n\times \{1,2,\cdots ,2^{n{R}_1^{\prime }}\}\to \{1,2,\cdots ,2^{nR}\}.\hfill \end{array}$$

(2)

Case 2: Two encoders

$$\begin{array}{c}{f}_v:{\mathcal{S}}_2^n\to \{1,2,\cdots ,2^{n{R}_2^{\prime }}\},\hfill \\ f:\{1,2,\cdots ,2^{nR}\}\times {\mathcal{S}}_1^n\times \{1,2,\cdots ,2^{n{R}_2^{\prime }}\}\to {\mathcal{X}}^n,\hfill \end{array}$$

and a decoder

$$\begin{array}{c}g:{\mathcal{Y}}^n\times {\mathcal{S}}_2^n\times \{1,2,\cdots ,2^{n{R}_2^{\prime }}\}\to \{1,2,\cdots ,2^{nR}\}.\hfill \end{array}$$

(3)

Case 2${}_C$: Two encoders

$$\begin{array}{c}{f}_v:{\mathcal{S}}_2^n\to \{1,2,\cdots ,2^{n{R}_2^{\prime }}\},\hfill \\ f_i:\{1,2,\cdots ,2^{nR}\}\times {\mathcal{S}}_1^i\times \{1,2,\cdots ,2^{n{R}_2^{\prime }}\}\to {\mathcal{X}}_i,\hfill \end{array}$$

and a decoder

$$\begin{array}{c}g:{\mathcal{Y}}^n\times {\mathcal{S}}_2^n\times \{1,2,\cdots ,2^{n{R}_2^{\prime }}\}\to \{1,2,\cdots ,2^{nR}\}.\hfill \end{array}$$

(4)

The average probability of error, $P_e^{(n)}$, for a $(n,2^{nR},2^{n{R}_j^{\prime }})$ code is defined as

$$\begin{array}{c}\hfill P_e^{(n)}=\frac{1}{2^{nR}}\sum _{w=1}^{2^{nR}}Pr\left\{\widehat{W}\ne W|W=w\right\},\end{array}$$

(5)

where the index W is chosen according to a uniform distribution over the set $\{1,2,\cdots ,2^{nR}\}$. A rate pair $(R,R^{\prime })$ is said to be achievable if there exists a sequence of $(n,2^{nR},2^{n{R}^{\prime }})$ codes such that the average probability of error $P_e^{(n)}\to 0$ as $n\to \infty$.

Definition 3.

The capacity of the channel, $C(R^{\prime })$, is the supremum of all R such that the rate pair $(R,R^{\prime })$ is achievable.

2.2. Definitions and Problem Formulation—Source Coding with Side Information

Throughout this article we use the common definitions of rate-distortion as presented in [29].

Definition 4.

The source sequence $\{X_i\in \mathcal{X},i=1,2,\cdots \}$, the ESI sequence $\{S_{1,i}\in {\mathcal{S}}_1,i=1,2,\cdots \}$ and the DSI sequence $\{S_{2,i}\in {\mathcal{S}}_2,i=1,2,\cdots \}$ are discrete random variables drawn from the finite alphabets $\mathcal{X},{\mathcal{S}}_1$ and ${\mathcal{S}}_2$ respectively. The random variables $(X_i,S_{1,i},S_{2,i})$ are i.i.d $\sim p(x,s_1,s_2)$. Let $\widehat{\mathcal{X}}$ be the reconstruction alphabet and $d_x:\mathcal{X}\times \widehat{\mathcal{X}}\to [0,\infty )$ be the distortion measure. The distortion between sequences is defined in the usual way:

$$\begin{array}{c}\hfill d(x^n,{\widehat{x}}^n)=\frac{1}{n}\sum _{i=1}^{n}d(x_i,{\widehat{x}}_i).\end{array}$$

(6)

Problem Formulation.

For the source, X, the ESI, $S_1$, and the DSI, $S_2$, consider the following source coding problem cases:

• Case 1: The encoder is informed with ESI and the decoder is informed with increased DSI.
• Case 2: The encoder is informed with increased ESI and the decoder is informed with DSI.
• Case 1${}_C$: The encoder is informed with ESI and the decoder is informed with increased causal DSI ($S_2^i$ at time i). This case is the same as Case 1, except for the causal DSI.

All cases are presented in Figure 2b.

Definition 5.

A $(n,2^{nR},2^{n{R}_j^{\prime }},D)$ code, $\{j\in 1,2\}$, for the source X with increased partial side information, as illustrated in Figure 2b, consists of two encoders, one decoder and a distortion constraint. The encoders are f and $f_v$, where f is the encoder for the source and $f_v$ is the encoder for the side information, and the decoder is g, as described for each case:

Case 1: Two encoders

$$\begin{array}{c}{f}_v:{\mathcal{S}}_1^n\to \{1,2,\cdots ,2^{n{R}_1^{\prime }}\},\hfill \\ f:{\mathcal{X}}^n\times {\mathcal{S}}_1^n\times \{1,2,\cdots ,2^{n{R}_1^{\prime }}\}\to \{1,2,\cdots ,2^{nR}\},\hfill \end{array}$$

and a decoder

$$\begin{array}{c}g:\{1,2,\cdots ,2^{nR}\}\times {\mathcal{S}}_2^n\times \{1,2,\cdots ,2^{n{R}_1^{\prime }}\}\to {\widehat{\mathcal{X}}}^n.\hfill \end{array}$$

(7)

Case 2: Two encoders

$$\begin{array}{c}{f}_v:{\mathcal{S}}_2^n\to \{1,2,\cdots ,2^{n{R}_2^{\prime }}\},\hfill \\ f:{\mathcal{X}}^n\times {\mathcal{S}}_1^n\times \{1,2,\cdots ,2^{n{R}_2^{\prime }}\}\to \{1,2,\cdots ,2^{nR}\},\hfill \end{array}$$

and a decoder

$$\begin{array}{c}g:\{1,2,\cdots ,2^{nR}\}\times {\mathcal{S}}_2^n\times \{1,2,\cdots ,2^{n{R}_2^{\prime }}\}\to {\widehat{\mathcal{X}}}^n.\hfill \end{array}$$

(8)

Case 1${}_C$: Two encoders

$$\begin{array}{c}{f}_v:{\mathcal{S}}_1^n\to \{1,2,\cdots ,2^{n{R}_1^{\prime }}\},\hfill \\ f:{\mathcal{X}}^n\times {\mathcal{S}}_1^n\times \{1,2,\cdots ,2^{n{R}_1^{\prime }}\}\to \{1,2,\cdots ,2^{nR}\},\hfill \end{array}$$

and a decoder

$$\begin{array}{c}{g}_i:\{1,2,\cdots ,2^{nR}\}\times {\mathcal{S}}_2^i\times \{1,2,\cdots ,2^{n{R}_1^{\prime }}\}\to {\widehat{\mathcal{X}}}_i.\hfill \end{array}$$

(9)

The distortion constraint for all three cases is:

$$\begin{array}{c}\hfill \mathbb{E}\left[\frac{1}{n}\sum _{i=1}^{n}d(X_i,{\widehat{X}}_i)\right]\le D.\end{array}$$

(10)

For a given distortion, D, and for any $ϵ>0$, the rate pair $(R,R^{\prime })$ is said to be achievable if there exists a $(n,2^{nR},2^{n{R}^{\prime }},D+ϵ)$ code for the rate-distortion problem.

Definition 6.

For a given $R^{\prime }$ and distortion D, the operational rate $R^{*}(R^{\prime },D)$ is the infimum of all R, such that the rate pair $(R,R^{\prime })$ is achievable.

3. Results

In this section, we present the main results of this paper. We will first present the results for the channel coding cases, then the main results for the source coding cases and, finally, we will present the duality between them.

3.1. Channel Coding with Side Information

For a channel with two-sided state information as presented in Figure 2a, where $(S_{1,i},S_{2,i})\sim p(s_1,s_2)$, the capacity is as follows

Theorem 1 (The capacity for the cases in Figure 2a).

For the memoryless channel $p(y|x,s_1,s_2)$, where $S_1$ is the ESI and $S_2$ is the DSI and the side information $(S_{1,i},S_{2,i})\sim p(s_1,s_2)$, the channel capacity is

Case 1: The encoder is informed with ESI and the decoder is informed with increased DSI,

$$\begin{array}{cc}\hfill C_1^{*}=& \underset{\begin{array}{c}p(v_1|s_1)p(u|s_1,v_1)p(x|u,s_1,v_1)\\ \mathrm{s}.\mathrm{t}.R^{\prime }\ge I(V_1;S_1)-I(V_1;Y,S_2)\end{array}}{max}I(U;Y,S_2|V_1)-I(U;S_1|V_1).\hfill \end{array}$$

(11)

Case 2: The encoder is informed with increased ESI and the decoder is informed with DSI;

Lower bounded by

$$\begin{array}{cc}\hfill C_2^{lb*}& =\underset{\begin{array}{c}p(v_2|s_2)p(u|s_1,v_2)p(x|u,s_1,v_2)\\ \mathrm{s}.\mathrm{t}.R^{\prime }\ge I(V_2;S_2|S_1)\end{array}}{max}I(U;Y,S_2|V_2)-I(U;S_1|V_2).\hfill \end{array}$$

(12)

Upper bounded by

$$\begin{array}{cc}\hfill C_2^{ub1*}& =\underset{\begin{array}{c}p(v_2|s_1,s_2)p(u|s_1,v_2)p(x|u,s_1,v_2)\\ \mathrm{s}.\mathrm{t}.R^{\prime }\ge I(V_2;S_2)-I(V_2;S_1)\end{array}}{max}I(U;Y,S_2|V_2)-I(U;S_1|V_2)\hfill \end{array}$$

(13)

and by

$$\begin{array}{cc}\hfill C_2^{ub2*}& =\underset{\begin{array}{c}p(v_2|s_2)p(u|s_1,s_2,v_2)p(x|u,s_1,v_2)\\ \mathrm{s}.\mathrm{t}.R^{\prime }\ge I(V_2;S_2|S_1)\end{array}}{max}I(U;Y,S_2|V_2)-I(U;S_1|V_2).\hfill \end{array}$$

(14)

Case 2${}_C$: The encoder is informed with increased causal ESI ($S_1^i$ at time i) and the decoder is informed with DSI,

$$\begin{array}{cc}\hfill C_{2C}^{*}& =\underset{\begin{array}{c}p(v_2|s_2)p(u|v_2)p(x|u,s_1,v_2)\\ R^{\prime }\ge I(V_2;S_2)\end{array}}{max}I(U;Y,S_2|V_2).\hfill \end{array}$$

(15)

For case j, $j\in \{1,2\}$, some joint distribution, $p(s_1,s_2,v_j,u,x,y)$, and $(U,V_j)$ being some auxiliary random variables with bounded cardinality.

Appendix B contains the proof.

Lemma 1.

For all three channel coding cases described in this section and for $j\in \{1,2\}$, the following statements hold,

• The function $C_j(R^{\prime })$ is a concave function of $R^{\prime }$.
• It is enough to take X to be a deterministic function of $(U,S_1,V_j)$ to evaluate $C_j$.
• The auxiliary alphabets $\mathcal{U}$ and ${\mathcal{V}}_j$ satisfy

  $$\begin{gathered} \begin{array}{c}\hfill \begin{array}{}\\ forCase1:\hfill & |{\mathcal{V}}_1|\le |\mathcal{X}||{\mathcal{S}}_1||{\mathcal{S}}_2|+1and \\ |\mathcal{U}|\le |\mathcal{X}||{\mathcal{S}}_1||{\mathcal{S}}_2|\left(|\mathcal{X}||{\mathcal{S}}_1||{\mathcal{S}}_2|+1\right),\\ forCase2:\hfill & |{\mathcal{V}}_2|\le |{\mathcal{S}}_1||{\mathcal{S}}_2|+1and \\ |\mathcal{U}|\le |\mathcal{X}||{\mathcal{S}}_1||{\mathcal{S}}_2|\left(|{\mathcal{S}}_1||{\mathcal{S}}_2|+1\right),\\ forCase{2}_C:\hfill & |{\mathcal{V}}_2|\le |{\mathcal{S}}_2|+1and \\ |\mathcal{U}|\le |\mathcal{X}||{\mathcal{S}}_2|\left(|{\mathcal{S}}_2|+1\right).\\ \end{array}\end{array} \end{gathered}$$

Appendix D contains the proof for the above lemma.

Remark 1.

Please notice that in Equation (14), the rate of the side information, $I(V_2;S_2|S_1)$, can be written as $I(V_2;S_2)-I(V_2|S_1)$. This is true since the Markov relation $V_2-S_2-S_1$ holds. Therefore, the only difference between the two upper bounds of Case 2, $C_2^{ub1*}$ (13) and $C_2^{ub2*}$ (14), is in the distribution over which we maximize. While for $C_2^{ub1*}$ we restrict the maximization to distributions which maintain the Markov chain $U-(S_1,V_2)-S_2$, for the second upper bound, $C_2^{ub2*}$, we restrict the maximization to distributions which maintain $V_2-S_2-S_1$. We should note that we cannot state with certainty that one of the bounds is tighter than the other for all distributions $p(y,x,s_1,s_2)$ and for all values of $R^{\prime }$. Notwithstanding, one bound may be tighter than the other for all distributions.

3.2. Source Coding with Side Information

For the problem of source coding with side information as presented in Figure 2b, the rate-distortion function is as follows:

Theorem 2 (The rate-distortion function for the cases in Figure 2b).

For a bounded distortion measure $d(x,\widehat{x})$, a source, X, and side information, $S_1,S_2$, where $(X_i,S_{1,i},S_{2,i})\sim p(x,s_1,s_2)$, the rate-distortion function is

Case 1: The encoder is informed with ESI and the decoder is informed with increased DSI,

$$\begin{array}{cc}\hfill R_1^{*}(D)& =\underset{\begin{array}{c}p(v_1|s_1)p(u|x,s_1,v_1)p(\widehat{x}|u,s_2,v_1)\\ \mathrm{s}.\mathrm{t}.R^{\prime }\ge I(V_1;S_1|S_2)\end{array}}{min}I(U;X,S_1|V_1)-I(U;S_2|V_1).\hfill \end{array}$$

(16)

Case 1${}_C$: The encoder is informed with ESI and the decoder is informed with increased causal DSI ($S_2^i$ at time i),

$$\begin{array}{cc}\hfill R_{1C}^{*}(D)& =\underset{\begin{array}{c}p(v_1|s_1)p(u|x,s_1,v_1)p(\widehat{x}|u,s_2,v_1)\\ \mathrm{s}.\mathrm{t}.R^{\prime }\ge I(V_1;S_1)\end{array}}{min}I(U;X,S_1|V_1).\hfill \end{array}$$

(17)

Case 2: The encoder is informed with increased ESI and the decoder is informed with DSI,

$$\begin{array}{cc}\hfill R_2^{*}(D)& =\underset{\begin{array}{c}p(v_2|s_2)p(u|x,s_1,v_2)p(\widehat{x}|u,s_2,v_2)\\ \mathrm{s}.\mathrm{t}.R^{\prime }\ge I(V_2;S_2)-I(V_2;X,S_1)\end{array}}{min}I(U;X,S_1|V_2)-I(U;S_2|V_2).\hfill \end{array}$$

(18)

For case j, $j\in \{1,2\}$, some joint distribution, $p(x,s_1,s_2,v_j,u,\widehat{x})$, where $\mathbb{E}\left[\frac{1}{n}{\sum }_{i=1}^{n}d(X_i,{\widehat{X}}_i)\right]\le D$ and $(U,V_j)$ being some auxiliary random variables with bounded cardinality.

Appendix C contains the proof.

Lemma 2.

For all cases of rate-distortion problems in this section and for $j\in \{1,2\}$, the following statements hold.

• The function $R_j(R^{\prime },D)$ is a convex function of $R^{\prime }$ and D.
• It is enough to take $\widehat{X}$ to be a deterministic function of $(U,S_2,V_j)$ to evaluate $R_j$.
• The auxiliary alphabets $\mathcal{U}$ and ${\mathcal{V}}_j$ satisfy

  $$\begin{gathered} \begin{array}{c}\hfill \begin{array}{}\\ forCase1:\hfill & |{\mathcal{V}}_1|\le |{\mathcal{S}}_1||{\mathcal{S}}_2|+1and \\ |\mathcal{U}|\le |\mathcal{X}||{\mathcal{S}}_1||{\mathcal{S}}_2|\left(|{\mathcal{S}}_1||{\mathcal{S}}_2|+1\right),\\ forCase{1}_C:\hfill & |{\mathcal{V}}_1|\le |{\mathcal{S}}_1|+1and \\ |\mathcal{U}|\le |\mathcal{X}||{\mathcal{S}}_1|\left(|{\mathcal{S}}_1|+1\right),\\ forCase2:\hfill & |{\mathcal{V}}_2|\le |\mathcal{X}||{\mathcal{S}}_1||{\mathcal{S}}_2|+1and \\ |\mathcal{U}|\le |\mathcal{X}||{\mathcal{S}}_1||{\mathcal{S}}_2|\left(|\mathcal{X}||{\mathcal{S}}_1||{\mathcal{S}}_2|+1\right).\\ \end{array}\end{array} \end{gathered}$$

Appendix D contains the proof for the above lemma.

3.3. Duality

We now investigate the duality between the channel coding and the source coding for the cases in Figure 2a,b. The following transformation makes the duality between the channel coding cases 1, 2, 2${}_C$ and the source coding cases 2, 1, 1${}_C$, respectively, evident. The left column corresponds to channel coding and the right column to source coding. For cases j and $\overline{j}$, where $j,\overline{j}\in \{1,2\}$ and $\overline{j}\ne j$, consider the transformation:

$$\begin{array}{cc}\hfill \mathrm{channel}\mathrm{coding}& ⟷\mathrm{source}\mathrm{coding}\hfill \\ \hfill C& ⟷R(D)\hfill \\ \hfill \mathrm{maximization}& ⟷\mathrm{minimization}\hfill \\ \hfill C_j& ⟷R_{\overline{j}}(D)\hfill \\ \hfill X& ⟷\widehat{X}\hfill \\ \hfill Y& ⟷X\hfill \\ \hfill S_j& ⟷S_{\overline{j}}\hfill \\ \hfill V_j& ⟷V_{\overline{j}}\hfill \\ \hfill U& ⟷U\hfill \\ \left(19\right)& \hfill R^{\prime }& ⟷R^{\prime }.\hfill \end{array}$$

This transformation is an extension of the transformation provided in [6,15]. Note that while the channel capacity formula in Case j and the rate-distortion function in Case $\overline{j}$ are dual to one another in the sense of maximization-minimization, the corresponding rates $R^{\prime }$ are not dual to each other in this sense; i.e., one would expect to see an opposite inequality ($\ge \leftrightarrow \le$) for dual cases, where we have an inequality that is in the same direction ($\le \leftrightarrow \le$) in the $R^{\prime }$ formulas. The duality in the side information rates, $R^{\prime }$, is then in the sense that the arguments in the formulas for the dual $R^{\prime }$ are dual. This exception is due to the fact that while the Gelfand–Pinsker and the Wyner-Ziv problems for the main channel or the main rate-distortion problems are dual, the Wyner-Ziv problem for the side information stays the same; the only difference is the input and the output.

4. Examples

In this section, we provide examples for Case 2 of the channel coding theorem and for Case 1 of the source coding theorem. The numerical iterative algorithm, which we used to numerically calculate the lower bound, $C_2^{lb}$, is provided in the next section.

Example 1 (Case 2 channel coding for a binary channel).

Consider the binary channel illustrated in Figure 3. The alphabet of the input, the output and the two states is binary $\mathcal{X}=\mathcal{Y}={\mathcal{S}}_1={\mathcal{S}}_2=\{0,1\}$ with $(S_1,S_2)\sim {\mathbf{P}}_{{\mathbf{S}}_{\mathbf{1}}{\mathbf{S}}_{\mathbf{2}}}$ being a joint probability mass function (PMF) matrix. The channel is dependent on the states $S_1$ and $S_2$, where the encoder is fully informed with $S_1$ and with $S_2$ with a rate limited to $R^{\prime }$ and the decoder is fully informed with $S_2$. The dependence of the channel on the states is illustrated in Figure 3. If $(S_1=1,S_2=0)$ then the channel is the Z channel with transition probability $ϵ$, if $(S_1=1,S_2=1)$ then the channel has no error, if $(S_1=0,S_2=0)$ then the channel is the X-channel and if $(S_1=0,S_2=1)$ then the channel is the S-channel with transition probability of $ϵ$. The side information’s joint PMF is

$$\begin{array}{c}\hfill {\mathbf{P}}_{{\mathbf{S}}_{\mathbf{1}}{\mathbf{S}}_{\mathbf{2}}}=\left(\begin{array}{cc}0.1& 0.4\\ 0.4& 0.1\end{array}\right).\end{array}$$

The expressions for the lower bound on the capacity $C_2^{lb}(R^{\prime })$ and for $R^{\prime }$ are brought in Case 2 of Theorem 1.

In Figure 4, we provide the graph from of the computation of the lower bound on the capacity for the binary channel we are testing. In the graph, we present the lower bound, $C_2^{lb}(R^{\prime })$, as a function of $R^{\prime }$. We also provide the Cover & Chiang [6] capacity (where $R^{\prime }=0$) and the Gelfand and Pinsker [2] capacity (where $R^{\prime }=0$ and the decoder is not informed with $S_2$).

Discussion:

• The algorithm that we used to calculate $C_2^{lb}(R^{\prime })$ and $R^{\prime }$ combines a grid-search and a Blahut-Arimoto-like algorithms. We first construct a grid of probabilities of the random variable $V_2$ given $S_2$, namely, $w(v_2|s_2)$. Then, for every probability $w(v_2|s_2)$ such that $I(V_2;S_2|S_1)$ is close enough to $R^{\prime }$ we calculate the maximum of $I(U;Y,S_2|V_2)-I(U;S_1|V_2)$ using the iterative algorithm described in the next section. We then choose the maximum over those maximums and declare it to be $C_2^{lb}$. By taking a fine grid of the probabilities $w(v_2|s_2)$ the operation’s result can be arbitrarily close to $C_2^{lb}$.
• For a given joint PMF matrix ${\mathbf{P}}_{{\mathbf{S}}_{\mathbf{1}}{\mathbf{S}}_{\mathbf{2}}}$, we can see that $C_2^{lb}(R^{\prime })$ is non-decreasing in $R^{\prime }$. Furthermore, since the expression $I(V_2;S_2|S_1)$ is bounded by $R_{max}={max}_{p(v_2|s_2)}I(V_2;S_2|S_1)=H(S_2|S_1)$, allowing $R^{\prime }$ to be greater than $R_{max}$ cannot improve $C_2^{lb}$ any more. i.e., $C_2^{lb}(R^{\prime }=R_{max})=C_2^{lb}(R^{\prime }>R_{max})$. Therefore, it is enough to allow $R^{\prime }=R_{max}$ to achieve $C_2^{lb}$, as if the encoder is fully informed with $S_2$.
• Although $C_2^{lb}$ is a lower bound on the capacity, it can be significantly greater than the Cover-Chiang and the Gelfand–Pinsker rates for some channel models, as can be seen in this example. Moreover, we can actually state that $C_2^{lb}$ is always greater than or equal to the Gelfand–Pinsker and the Cover-Chiang rates. This is due to the fact that when $R^{\prime }=0$, $C_2^{lb}$ coincides with the Cover-Chiang rate, which, in its turn, is always greater than or equal to the Gelfand–Pinsker rate; since $C_2^{lb}$ is also non-decreasing in $R^{\prime }$, it is obvious that our assertion holds.

Example 2 (Source coding Case 1 for a binary-symmetric source and Hamming distortion).

Consider the source $X=S_1\oplus S_2$, where $S_1,S_2\sim \mathrm{i}.\mathrm{i}.\mathrm{d}.\mathrm{Bernoulli}(0.5)$, and consider the problem setting depicted in Case 1 of the source coding problems. It is sufficient for the decoder to reconstruct $S_1$ with distortion $\mathbb{E}\left[d(S_1,{\widehat{S}}_1)\right]\le D$ in order to reconstruct X with the same distortion. Furthermore, the two rate-distortion problem settings illustrated in Figure 5 are equivalent.

For every achievable rate in Setting 1, $\mathbb{E}\left[d(S_1,{\widehat{S}}_1)\right]\le D$. Denote $\widehat{X}\triangleq {\widehat{S}}_1\oplus S_2$, then, $d(S_1,{\widehat{S}}_1)=S_1\oplus {\widehat{S}}_1=(S_1\oplus S_2)\oplus ({\widehat{S}}_1\oplus S_2)=X\oplus \widehat{X}=d(X,\widehat{X})$ and, therefore, $\mathbb{E}\left[d(S_1,{\widehat{S}}_1)\right]\le D$ in Setting 1 $\Rightarrow \mathbb{E}\left[d(X,\widehat{X})\right]\le D$ in Setting 2. In the same way, for Setting 2, denote ${\widehat{S}}_1\triangleq \widehat{X}\oplus S_2$. Then, $d(X,\widehat{X})=X\oplus \widehat{X}=S_1\oplus {\widehat{S}}_1$ and, therefore, $\mathbb{E}\left[d(X,\widehat{X})\right]\le D$ in Setting 2 $\Rightarrow \mathbb{E}\left[d(S_1,{\widehat{S}}_1)\right]\le D$ in Setting 1. Hence, we can conclude that the two settings are equivalent and, for any given $0\le D$ and $0\le R^{\prime }$, the rate-distortion function is

$$\begin{array}{c}\hfill R(D)=\left\{\begin{array}{cc}1-H(D)-R^{\prime }\hfill & \hfill 1-H(D)-R^{\prime }\ge 0\\ 0\hfill & \hfill 1-H(D)-R^{\prime }<0\end{array}\right..\end{array}$$

(20)

In Figure 6 we present the plot resulting for this example. It is easy to verify that the Wyner and Ziv rate and the Cover and Chiang rate for this setting are $R_{WZ}(D)=R_{CC}(D)=max\left\{1-H(D),0\right\}$.

5. Semi-Iterative Algorithm

In this section, we provide algorithms that numerically calculate the lower bound on the capacity of Case 2 of the channel coding problems. The calculation of the Gelfand–Pinsker and the Wyner-Ziv problems has been addressed in many papers in the past, including [5,24,25,26]. All these algorithms are based on Arimoto’s [23] and Blahut’s [22] algorithms and on the fact that the Wyner-Ziv and the Gelfand–Pinsker problems can be presented as convex optimization problems. On the contrary, our problems are not convex in all of their optimization variables and, therefore, cannot be presented as convex optimization problems. In order to solve our problems we devised a different approach which combines a grid-search and a Blauhut-Arimoto-like algorithm. In this section, we provide the mathematical justification for those two algorithms. Other algorithms to numerically compute the channel capacity or the rate-distortion of the rest of the cases presented in this paper can be derived using the principles that we describe in this section.

5.1. An Algorithm for Computing the Lower Bound on the Capacity of Case 2

Consider the channel in Figure 7 described by $p(y|x,s_1,s_2)$ and consider the joint PMF $p(s_1,s_2)$. The capacity of this channel is lower bounded by $maxI(U;Y,S_2|V_2)-I(U;S_1|V_2)$, where the maximization is over all PMFs $p(s_1,s_2)w(v_2|s_2)p(u|s_1,v_2)p(x|s_1,v_2,u)p\left(y|x,s_1,s_2\right)$ such that $R^{\prime }\ge I(V_2;S_2|S_1)$. Notice that the lower bound expression is not concave in $w(v_2|s_2)$, which is the main difficulty with the computation of it. We first present an outline of the semi-iterative algorithm we developed, then we present the mathematical background and justification for the algorithm and, finally, we present the detailed algorithm.

For any fixed PMF $w(v_2|s_2)$ denote

$$\begin{array}{cc}\hfill R_w& \triangleq I(V_2;S_2|S_1),\hfill \end{array}$$

(21)

$$\begin{array}{cc}\hfill C_{2,w}^{lb}& \triangleq \underset{p(u|s_1,v_2)p(x|u,s_1,v_2)}{max}I(U;Y,S_2|V_2)-I(U;S_1|V_2).\hfill \end{array}$$

(22)

Then, the lower bound on the capacity , $C_2^{lb}(R^{\prime })$, can be expressed as

$$\begin{array}{c}\hfill C_2^{lb}(R^{\prime })=\underset{\begin{array}{c}w(v_2|s_2)\\ \mathrm{s}.\mathrm{t}.R^{\prime }\ge R_w\end{array}}{max}\underset{p(u|s_1,v_2)p(x|u,s_1,v_2)}{max}[I(U;Y,S_2|V_2)-I(U;S_1|V_2)]\triangleq \underset{\begin{array}{c}w(v_2|s_2)\\ \mathrm{s}.\mathrm{t}.R^{\prime }\ge R_w\end{array}}{max}{C}_{2,w}^{lb}.\end{array}$$

(23)

The outline of the algorithm is as follows: for any given rate $R^{\prime }\le H(S_2|S_1)$, $ϵ>0$ and $\delta >0$,

• Establish a fine and uniformly spaced grid of legal PMFs, $w(v_2|s_2)$, and denote the set of all of those PMFs as $\mathcal{W}$.
• Establish the set ${\mathcal{W}}^{*}:=\{w(v_2|s_2)|w(v_2|s_2)\in \mathcal{W}$ and $R^{\prime }-ϵ\le R_w\le R^{\prime }\}$. This set is the set of all PMFs $w(v_2|s_2)$ such that $R_w$ is $ϵ$-close to $R^{\prime }$ from below. If ${\mathcal{W}}^{*}$ is empty, go back to step 1 and make the grid finer. Otherwise, continue.
• For every $w(v_2|s_2)\in {\mathcal{W}}^{*}$, perform a Blahut-Arimoto-like optimization to find $C_{2,w}^{lb}$ with accuracy of $\delta$.
• Declare $C_2^{lb}(R^{\prime })={max}_{w(v_2|s_2)\in {\mathcal{W}}^{*}}{C}_2^{lb(ϵ,\delta ,\mathcal{W})}(R^{\prime })$.

Remark 2.

1. 

We considered only those $R^{\prime }$s such that $R^{\prime }\le H(S_2|S_1)$ since $H(S_2|S_1)$ is the maximal value that $I(V_2;S_2|S_1)$ takes. The interpretation of this is that if the encoder is informed with $S_1$, we cannot increase its side information about $S_2$ in more than $H(S_2|S_1)$. Therefore, for any $H(S_2|S_1)\le R^{\prime }$, we can limit $R^{\prime }$ to be equal to $H(S_2|S_1)$ in order to compute the capacity;

2. 

Since $C_{2,w}^{lb}(R^{\prime })$ is continuous in $w(v_2|s_2)$ and bounded (for example, by $I(X;Y|S_1,S_2)$ from above and by $I(X;Y)$ from below), $C_2^{(ϵ,\delta ,\mathcal{W})}(R^{\prime })$ can be arbitrarily close to $C_2^{lb}(R^{\prime })$ for $ϵ\to 0,\delta \to 0$ and $|\mathcal{W}|\to \infty$.

5.1.1. Mathematical background and justification

Here we focus on finding the lower bound on the capacity of the channel for a fixed distribution $w(v_2|s_2)$, i.e., finding $C_{2,w}^{lb}$. Note that the mutual information expression $I(U;Y,S_2|V_2)-I(U;S_1|V_2)$ is concave in $p(u|s_1,v_2)$ and convex in $p(x|u,s_1,v_2)$. Therefore, a standard convex maximization technique is not applicable for this problem. However, according to Dupuis, Yu and Willems [25], we can write the expression for the lower bound as $C_{2,w}^{lb}={max}_{q(t|s_1,v_2)}I(T;Y,S_2|V_2)-I(T;S_1|V_2)$, where $q(t|s_1,v_2)$ is a probability distribution over the set of all possible strategies $t:{\mathcal{S}}_1\times {\mathcal{V}}_2\to \mathcal{X}$, the input symbol X is selected using $x=t(s_1,v_2)$ and $p(y|x,s_1,s_2)=p(y|x,s_1,s_2,v_2)=p\left(y|t(s_1,v_2),s_1,s_2,v_2\right)$. Now, since $I(T;Y,S_2|V_2)-I(T;S_1|V_2)$ is concave in $q(t|s_1,v_2)$, we can use convex optimization methods to derive $C_{2,w}^{lb}$.

Denote the PMF

$$\begin{array}{cc}\hfill p(s_1,s_2,v_2,t,y)& \triangleq p(s_1,s_2)w(v_2|s_2)q(t|s_1,v_2)p(y|t,s_1,s_2,v_2),\hfill \end{array}$$

(24)

and denote also

$$\begin{array}{cc}\hfill J_w(q,Q)& \triangleq \sum _{s_1,s_2,v_2,t,y}p(s_1,s_2,v_2,t,y)log\frac{Q(t|y,s_2,v_2)}{q(t|s_1,v_2)},\hfill \end{array}$$

(25)

$$\begin{array}{cc}\hfill Q^{*}(t|y,s_2,v_2)& \triangleq \frac{{\sum }_{s_1}p(s_1,s_2,v_2,t,y)}{{\sum }_{s_1,t^{\prime }}p(s_1,s_2,v_2,t^{\prime },y)}.\hfill \end{array}$$

(26)

Notice that $Q^{*}(t|y,s_2,v_2)$ is a marginal distribution of $p(s_1,s_2,v_2,t,y)$ and that $J_w(q,Q^{*})=I(T;Y,S_2|V_2)-I(T;S_1|V_2)$ for the joint PMF $p(s_1,s_2,v_2,t,y)$.

The following lemma is the key for the iterative algorithm.

Lemma 3.

$$\begin{array}{c}\hfill C_{2,w}^{lb}=\underset{q^{\prime }(t|s_1,v_2)}{sup}\underset{Q^{\prime }(t|y,s_2,v_2)}{max}{J}_w(q^{\prime },Q^{\prime }).\end{array}$$

(27)

The proof for this is brought by Yeung in [30]. In addition, Yeung shows that the two-step alternating optimization procedure converges monotonically to the global optimum if the optimization function is concave. Hence, if we show that $J_w(q,Q)$ is concave, we can maximize it using an alternating maximization algorithm over q and Q.

Lemma 4.

The function $J_w(q,Q)$ is concave in q and Q simultaneously.

We can now proceed to calculate the steps in the iterative algorithm.

Lemma 5.

For a fixed $q,J_w(q,Q)$ is maximized for $Q=Q^{*}$.

Proof. 

The above follows from the fact that $Q^{*}$ is a marginal distribution of $p(s_1,s_2)w(v_2|s_2)q(t|s_1,v_2)p(y|t,s_1,s_2,v_2)$ and the property of the K-L divergence $D(Q^{*}\parallel Q^{\prime })\ge 0$. ☐

Lemma 6.

For a fixed $Q,J_w(q,Q)$ is maximized for $q=q^{*}$, where $q^{*}$ is defined by

$$\begin{array}{c}\hfill q^{*}(t|s_1,v_2)=\frac{{\prod }_{s_2,y}Q{(t|y,s_2,v_2)}^{p(s_2|s_1,v_2)p(y|t,s_1,s_2,v_2)}}{{\sum }_{t^{\prime }}{\prod }_{s_2,y}Q{(t|y,s_2,v_2)}^{p(s_2|s_1,v_2)p(y|t^{\prime },s_1,s_2,v_2)}},\end{array}$$

(28)

and

$$\begin{array}{c}\hfill p(s_2|s_1,v_2)=\frac{p(s_1,s_2)w(v_2|s_2)}{{\sum }_{s_2^{\prime }}p(s_1,s_2^{\prime })w(v_2|s_2^{\prime })}.\end{array}$$

(29)

Define $U_w(q)$ in the following way

$$\begin{array}{c}\hfill U_w(q)=\sum _{s_1,v_2}p(s_1,v_2)\underset{t}{max}\sum _{s_2,y}p(s_2|s_1,v_2)p(y|t,s_1,s_2,v_2)log\frac{Q^{*}(t|y,s_2,v_2)}{q(t|s_1,v_2)},\end{array}$$

(30)

where $Q^{*}$ is given in (26), $p(s_1,v_2)$ and $p(s_2|s_1,v_2)$ are marginal distributions of the joint PMF $p(s_1,s_2,v_2,t,y)=p(s_1,s_2)w(v_2|s_2)q(t|s_1,v_2)p(y|t,s_1,s_2,v_2)$. The following lemma will help us to define a termination condition for the algorithm.

Lemma 7.

For every $q(t|s_1,v_2)$ the function $U_w(q)$ is an upper bound on $C_{w,2}^{lb}$ and converges to $C_{2,w}^{lb}$ for a large enough number of iterations.

5.2. Semi-Iterative Algorithm

The the algorithm for finding $C_2^{lb}(R^{\prime })$ is brought in Algorithm 1. Notice that the result of this algorithm, $C_2^{(ϵ,\delta ,\mathcal{W})}(R^{\prime })$, can be arbitrarily close to $C_2^{lb}(R^{\prime })$ for $ϵ\to 0,\delta \to 0$ and $|\mathcal{W}|\to \infty$.

Algorithm 1 Numerically calculating $C_2^{lb}(R^{\prime })$

1: Chose $ϵ>0$, $\delta >0$  2: Set $R^{\prime }\leftarrow min\{R^{\prime },H(S_2|S_1)\}$ {the amount of information needed for the encoder to know $S_2$ given $S_1$}  3: Set $C\leftarrow -\infty$  4: Establish a fine and uniformly spaced grid of legal PMFs $w(v_2|s_2)$ and name it $\mathcal{W}$  5: for all w in $\mathcal{W}$ do  6:  Compute $R_w$ using $$\begin{array}{c}\hfill R_w=I(V_2;S_2)-I(V_2;S_1)\end{array}$$  7:  if $R^{\prime }-ϵ\le R_w\le R^{\prime }$ then  8:   Set $Q(t|y,s_2,v_2)$ to be a uniform distribution over $\{1,2,\cdots ,|\mathcal{T}|\}$, where $\mathcal{T}$ is the alphabet of t.  i.e., $Q(t|y,s_2,v_2)=\frac{1}{|\mathcal{T}|},\forall t,y,s_2,v_2$  9:   repeat 10:     Set $q(t|s_1,v_2)\leftarrow q^{*}(t|s_1,v_2)$ using $$\begin{array}{c}\hfill q^{*}(t|s_1,v_2)=\frac{{\prod }_{s_2,y}Q{(t|y,s_2,v_2)}^{p(s_2|s_1,v_2)p(y|t,s_1,s_2,v_2)}}{{\sum }_{t^{\prime }}{\prod }_{s_2,y}Q{(t^{\prime }|y,s_2,v_2)}^{p(s_2|s_1,v_2)p(y|t^{\prime },s_1,s_2,v_2)}}\end{array}$$ 11:     Set $(Q(t|y,s_2,v_2)\leftarrow Q^{*}(t|y,s_2,v_2)$ using $$\begin{array}{c}\hfill Q^{*}(t|y,s_2,v_2)=\frac{{\sum }_{s_1}p(s_1,s_2,v_2,t,y)}{{\sum }_{s_1,t^{\prime }}p(s_1,s_2,v_2,t^{\prime },y)}\end{array}$$ 12:     Compute $J_w(q,Q)$ using $$\begin{array}{c}\hfill J_w(q,Q)=\sum _{s_1,s_2,v_2,t,y}p(s_1,s_2,v_2,t,y)log\frac{Q(t|y,s_2,v_2)}{q(t|s_1,v_2)}\end{array}$$ 13:     Compute $U_w(q)$ using $$\begin{array}{c}\hfill U_w(q)=\sum _{s_1,v_2}p(s_1,v_2)\underset{t}{max}\sum _{s_2,y}p(s_2|s_1,v_2)p(y|t,s_1,s_2,v_2)log\frac{Q^{*}(t|y,s_2,v_2)}{q(t|s_1,v_2)}\end{array}$$ 14:   until $U_w(q)-J(q,Q)<\delta$ 15:   if $C\le J_w(q,Q)$ then 16:     Set $C\leftarrow J_w(q,Q)$ 17:   end if 18:  end if 19: end for 20: if $C<0$ then {there is no PMF $w(v_2|s_2)\in \mathcal{W}$ such that $R_w$ is $ϵ$-close to $R^{\prime }$ from below} 21:  go to line 4 and make the grid finer 22: end if 23: Declare $C_2^{lb(ϵ,\delta ,\mathcal{W})}(R^{\prime })=C$

6. Open Problems

In this section, we discuss the generalization of the channel capacity and the rate-distortion problems that we presented in Section 3. We now consider the cases where the encoder and the decoder are simultaneously informed with a rate-limited description of both the ESI and the DSI, as illustrated in Figure 8. A lower bound on the capacity and an upper bound on the rate-distortion are suggested. Achievability schemes for the presented bounds can be easily derived using the same techniques that we used in the proofs for Theorems 1 and 2, and, hence, are omitted. We were unable to prove that the suggested bounds are tight, nor did we encounter any other such proofs in the published literature; therefore, we believe these problems to be open.

6.1. A Lower Bound on the Capacity of a Channel with Two-Sided Increased Partial Side Information

Consider the channel illustrated in Figure 8, where $(S_{1,i},S_{2,i})\mathrm{i}.\mathrm{i}.\mathrm{d}.\sim p(s_1,s_2)$. The encoder is informed with the ESI $(S_1^n)$ and rate-limited DSI and the decoder is informed with the DSI $(S_2^n)$ and rate-limited ESI. An $(n,2^{nR},2^{n{R}_1^{\prime }},2^{n{R}_2^{\prime }})$ code for the discussed channel consists of three encoding maps:

$$\begin{array}{c}{f}_{v1}:{\mathcal{S}}_1^n\to \{1,2,\cdots ,2^{n{R}_1^{\prime }}\},\hfill \\ f_{v2}:{\mathcal{S}}_2^n\to \{1,2,\cdots ,2^{n{R}_2^{\prime }}\},\hfill \\ f:\{1,2,\cdots ,2^{nR}\}\times {\mathcal{S}}_1^n\times \{1,2,\cdots ,2^{n{R}_2^{\prime }}\}\to {\mathcal{X}}^n,\hfill \end{array}$$

and a decoding map:

$$\begin{array}{c}g:{\mathcal{Y}}^n\times {\mathcal{S}}_2^n\times \{1,2,\cdots ,2^{n{R}_1^{\prime }}\}\to \{1,2,\cdots ,2^{nR}\}.\hfill \end{array}$$

Fact 1: The channel capacity, $C_{12}^{*}$, of this channel coding setup is bounded from below as follows:

$$\begin{array}{cc}\hfill C_{12}^{*}& \ge \underset{\begin{array}{c}p(v_1|s_1)p(v_2|s_2)p(u|s_1,v_1,v_2)p(x|u,s_1,v_1,v_2)\\ \mathrm{s}.\mathrm{t}.R_1^{\prime }\ge I(V_1;S_1)-I(V_1;Y,S_2,V_2)\\ R_2^{\prime }\ge I(V_2;S_2)-I(V_2;S_1)\end{array}}{max}I(U;Y,S_2|V_1,V_2)-I(U;S_1|V_1,V_2),\hfill \end{array}$$

(31)

for some joint distribution $p(s_1,s_2,v_1,v_2,u,x,y)$ and $U,V_1$ and $V_2$ are some auxiliary random variables.

The proof for the achievability follows closely the proofs given in Appendix B and, therefore, is omitted.

6.2. An Upper Bound on the Rate-Distortion with Two-Sided Increased Partial Side Information

Consider the rate-distortion problem illustrated in Figure 9, where the source X and the side information $S_1,S_2$ are distributed $(X_i,S_{1,i},S_{2,i})\sim \mathrm{i}.\mathrm{i}.\mathrm{d}.p(x,s_1,s_2)$. The encoder is informed with the ESI $(S_1^n)$ and rate-limited DSI and the decoder is informed with the DSI $(S_2^n)$ and rate-limited ESI. An $(n,2^{nR},2^{n{R}_1^{\prime }},2^{n{R}_2^{\prime }},D)$ code for the discussed rate-distortion problem consists of three encoding maps:

$$\begin{array}{c}{f}_{v1}:{\mathcal{S}}_1^n\to \{1,2,\cdots ,2^{n{R}_1^{\prime }}\},\hfill \\ f_{v2}:{\mathcal{S}}_2^n\to \{1,2,\cdots ,2^{n{R}_2^{\prime }}\},\hfill \\ f:{\mathcal{X}}^n\times {\mathcal{S}}_1^n\times \{1,2,\cdots ,2^{n{R}_2^{\prime }}\}\to \{1,2,\cdots ,2^{nR}\},\hfill \end{array}$$

and a decoding map:

$$\begin{array}{c}g:\{1,2,\cdots ,2^{nR}\}\times {\mathcal{S}}_2^n\times \{1,2,\cdots ,2^{n{R}_1^{\prime }}\}\to {\widehat{\mathcal{X}}}^n.\hfill \end{array}$$

Fact 2: For a given distortion, D, and a given distortion measure, $d(X,\widehat{X}):\mathcal{X}\times \widehat{\mathcal{X}}\to {\mathbb{R}}^{+}$, the rate-distortion function $R_{12}^{*}(D)$ of this setup is bounded from above as follows:

$$\begin{array}{cc}\hfill R_{12}^{*}(D)& \le \underset{\begin{array}{c}p(v_1|s_1)p(v_2|s_2)p(u|x,s_1,v_1,v_2)p(\widehat{x}|u,s_2,v_1,v_2)\\ \mathrm{s}.\mathrm{t}.R_1^{\prime }\ge I(V_1;S_1)-I(V_1;S_2,V_2)\\ R_2^{\prime }\ge I(V_2;S_2)-I(V_2;X,S_1,V_1)\end{array}}{min}I(U;X,S_1|V_1,V_2)-I(U;S_2|V_1,V_2),\hfill \end{array}$$

(32)

for some joint distribution $p(x,s_1,s_2,v_1,v_2,u,\widehat{x})$ where $\mathbb{E}\left[\frac{1}{n}{\sum }_{i=1}^{n}d(X_i,{\widehat{X}}_i)\right]\le D$ and $U,V_1$ and $V_2$ are some auxiliary random variables.

The proof for the achievability follows closely the proofs given in Appendix C and, therefore, is omitted.