The Arbitrarily Varying Relay Channel ^†

Abstract

We study the arbitrarily varying relay channel, which models communication with relaying in the presence of an active adversary. We establish the cutset bound and partial decode-forward bound on the random code capacity. We further determine the random code capacity for special cases. Then, we consider conditions under which the deterministic code capacity is determined as well. In addition, we consider the arbitrarily varying Gaussian relay channel with sender frequency division under input and state constraints. We determine the random code capacity, and establish lower and upper bounds on the deterministic code capacity. Furthermore, we show that as opposed to previous relay models, the primitive relay channel has a different behavior compared to the non-primitive relay channel in the arbitrarily varying scenario.

1. Introduction

The relay channel was first introduced by van der Meulen [1] to describe point-to-point communication with the help of a relay, which receives a noisy version of the transmitter signal and transmits a signal of its own to the destination receiver. The relay channel is generally perceived as a fundamental building block for multihop networks (see e.g., [2,3], Chapter 16), where some nodes receive and transmit in order to assist the information flow between other nodes. The capacity of the relay channel is not known in general, however, Cover and El Gamal established the cutset upper bound, the decode-forward lower bound, and the partial decode-forward lower bound [4]. It was also shown in [4] that for the reversely degraded relay channel, direct transmission is capacity achieving. For the degraded relay channel, the decode-forward lower bound and the cutset upper bound coincide, thus characterizing the capacity for this model [4].

In general, the partial decode-forward lower bound is tighter than both direct transmission and decode-forward lower bounds. El Gamal and Zahedi [5] determined the capacity of the relay channel with orthogonal sender components, by showing that the partial decode-forward lower bound and cutset upper bound coincide. A variation of the relay channel, referred to as the primitive relay channel, was introduced by Kim [2], and attracted a lot of attention (see e.g., [6,7,8,9,10,11,12] and references therein). Recently, there has also been a growing interest in the Gaussian relay channel, as e.g., in [5,7,9,13,14,15,16] and references therein. In particular, El Gamal and Zahedi [5] introduced the Gaussian relay channel with sender frequency division (SFD), as a special case of a relay channel with orthogonal sender components. There are many other relaying scenarios, including secrecy [17,18], networking [15,19,20,21,22], parallel relaying [23,24,25], diamond channels [26,27,28], side information [29,30,31,32,33], etc.

In practice, the channel statistics are not necessarily known in exact, and they may even change over time. The arbitrarily varying channel (AVC) is an appropriate model to describe such a situation [34]. In real systems, such variations are caused by fading in wireless communication [35,36,37,38,39,40,41,42], memory faults in storage [43,44,45,46,47], malicious attacks on identification and authorization systems [48,49], etc. It is especially relevant to communication in the presence of an adversary, or a jammer, attempting to disrupt communication. Jamming attacks are not limited to point-to-point communication, and cause a major security concern for cognitive radio networks [50] and wireless sensor networks [42,51,52,53,54], for instance.

Considering the AVC without a relay, Blackwell et al. determined the random code capacity [34], i.e., the capacity achieved by stochastic-encoder stochastic-decoder coding schemes with common randomness. It was also demonstrated in [34] that the random code capacity is not necessarily achievable using deterministic codes. A well-known result by Ahlswede [55] is the dichotomy property of the AVC. Specifically, the deterministic code capacity either equals the random code capacity or else, it is zero. Subsequently, Ericson [56] and Csiszár and Narayan [57] established a simple single-letter condition, namely non-symmetrizability, which is both necessary and sufficient for the capacity to be positive. Ahlswede’s Robustification Technique (RT) is a useful technique for the AVC analysis, developed and applied to classical AVC settings [58,59]. Essentially, the RT uses a reliable code for the compound channel to construct a random code for the AVC applying random permutations to the codeword symbols. A continuing line of works on arbitrarily varying networks includes among others the arbitrarily varying broadcast channel [60,61,62,63,64,65], multiple-access channel [60,66,67,68,69,70,71,72,73,74,75], and wiretap channel [76,77,78,79,80,81,82,83,84]. The reference lists here are far from being exhaustive.

In this work, we introduce a new model, namely, the arbitrarily varying relay channel (AVRC). The AVRC combines the previous models, i.e., the relay channel and the AVC, and we believe that it is a natural problem to consider, in light of the jamming attacks on current and future networks, as mentioned above. In the analysis, we incorporate the block Markov coding schemes of [4] in Ahlswede’s Robustification and Elimination Techniques [55,59]. A straightforward application of Ahlswede’s RT fails to comply with the strictly causal relay transmission. In a recent work [85,86], by the authors of this paper, a modified RT technique was presented and applied to the point-to-point AVC with causal side information under input and state constraints, without a relay. This was the first time where the application of the RT exploited the structure of the original compound channel code to construct a random code for the AVC, as opposed to earlier work where the original code is treated as a “black box”. Here, we present another modification of the RT, which also exploits the structure of the original compound channel code, but in a different manner. The analysis also requires to redefine the compound channel, and we refer to the newly defined channel as the block-compound relay channel.

We establish the cutset upper bound and the full/partial decode-forward lower bound on the random code capacity of the AVRC. The random code capacity is determined in special cases of the degraded AVRC, the reversely degraded AVRC, and the AVRC with orthogonal sender components. Then, we give extended non-symmetrizability conditions under which the deterministic code capacity coincides with the random code capacity. We show by example that the deterministic code capacity can be strictly lower than the random code capacity of the AVRC. Then, we consider the Gaussian AVRC with SFD, under input and state constraints. The random code capacity is determined using the previous results, whereas the deterministic code capacity is lower and upper bounded using an independent approach. Specifically, we extend the techniques from [87], where Csiszár and Narayan determine the capacity of the Gaussian AVC under input and state constraint. It is shown that for low values on the input constraint, the deterministic code capacity can be strictly lower than the random code capacity, but yet non-zero.

Furthermore, we give similar bounds for the primitive AVRC, where there is a noiseless link between the relay and the receiver of limited capacity [2]. We find the capacity of the primitive counterpart of the Gaussian AVRC with SFD, in which case the deterministic and random code capacities coincide, regardless of the value of the input constraint. We deduce that Kim’s assertion—that “the primitive relay channel captures most essential features and challenges of relaying, and thus serves as a good testbed for new relay coding techniques” [2]—is not true in the arbitrarily varying scenario.

This work is organized as follows. In Section 2, the basic definitions and notation are provided. In Section 3, we give the main results on the general AVRC. The Gaussian AVRC with SFD is introduced in Section 4, and the main results are given in Section 5. The definition and results on the primitive AVRC are in Section 6.

2. Definitions

2.1. Notation

We use the following notation conventions throughout. Calligraphic letters $\mathcal{X},\mathcal{S},\mathcal{Y},\dots$ are used for finite sets. Lowercase letters $x,s,y,\dots$ stand for constants and values of random variables, and uppercase letters $X,S,Y,\dots$ stand for random variables. The distribution of a random variable X is specified by a probability mass function (pmf) $P_X(x)=p(x)$ over a finite set $\mathcal{X}$. The set of all pmfs over $\mathcal{X}$ is denoted by $\mathcal{P}(\mathcal{X})$. We use $x^j=(x_1,x_2,\dots ,x_j)$ to denote a sequence of letters from $\mathcal{X}$. A random sequence $X^n$ and its distribution $P_{X^n}(x^n)=p(x^n)$ are defined accordingly. For a pair of integers i and j, $1\le i\le j$, we define the discrete interval $[i:j]=\{i,i+1,\dots ,j\}$. The notation $\mathbf{x}=(x_1,x_2,\dots ,x_n)$ is used when it is understood from the context that the length of the sequence is n, and the ${\ell }^2$-norm of $\mathbf{x}$ is denoted by $∥\mathbf{x}∥$.

2.2. Channel Description

A state-dependent discrete memoryless relay channel $(\mathcal{X},{\mathcal{X}}_1,\mathcal{S},W_{Y,Y_1|X,X_1,S},\mathcal{Y},{\mathcal{Y}}_1)$ consists of five sets, $\mathcal{X}$, ${\mathcal{X}}_1$, $\mathcal{S}$, $\mathcal{Y}$ and ${\mathcal{Y}}_1$, and a collection of conditional pmfs $W_{Y,Y_1|X,X_1,S}$. The sets stand for the input alphabet, the relay transmission alphabet, the state alphabet, the output alphabet, and the relay input alphabet, respectively. The alphabets are assumed to be finite, unless explicitly said otherwise. The channel is memoryless without feedback, and therefore

$$\begin{array}{c}\hfill W_{Y^n,Y_1^n|X^n,X_1^n,S^n}(y^n,y_1^n|x^n,x_1^n,s^n)=\prod _{i=1}^n{W}_{Y,Y_1|X,X_1,S}(y_i,y_{1,i}|x_i,x_{1,i},s_i).\end{array}$$

(1)

Communication over a relay channel is depicted in Figure 1. Following [29], a relay channel $W_{Y,Y_1|X,X_1,S}$ is called degraded if the channel can be expressed as

$$\begin{array}{c}\hfill W_{Y,Y_1|X,X_1,S}(y,y_1|x,x_1,s)=W_{Y_1|X,X_1,S}(y_1|x,x_1,s)W_{Y|Y_1,X_1,S}(y|y_1,x_1,s),\end{array}$$

(2)

and it is called reversely degraded if

$$\begin{array}{c}\hfill W_{Y,Y_1|X,X_1,S}(y,y_1|x,x_1,s)=W_{Y|X,X_1,S}(y|x,x_1,s)W_{Y_1|Y,X_1,S}(y_1|y,x_1,s).\end{array}$$

(3)

We say that the relay channel is strongly degraded or reversely degraded, if the respective definition holds such that the sender-relay marginal is independent of the state. That is, $W_{Y,Y_1|X,X_1,S}$ is strongly degraded if $W_{Y,Y_1|X,X_1,S}=W_{Y_1|X,X_1}{W}_{Y|Y_1,X_1,S}$, and similarly, $W_{Y,Y_1|X,X_1,S}$ is strongly reversely degraded if $W_{Y,Y_1|X,X_1,S}=W_{Y|X,X_1,S}{W}_{Y_1|Y,X_1}$. For example, if $Y_1=X+Z$ and $Y=Y_1+X_1+S$, where Z is an independent additive noise, then $W_{Y,Y_1|X,X_1,S}$ is strongly degraded. Whereas, if $Y=X+X_1+S$ and $Y_1=Y+Z$, then $W_{Y,Y_1|X,X_1,S}$ is strongly reversely degraded.

The arbitrarily varying relay channel (AVRC) is a discrete memoryless relay channel $(\mathcal{X},{\mathcal{X}}_1,\mathcal{S},W_{Y,Y_1|X,X_1,S},\mathcal{Y},{\mathcal{Y}}_1)$ with a state sequence of unknown distribution, not necessarily independent nor stationary. That is, $S^n\sim q(s^n)$ with an unknown joint pmf $q(s^n)$ over ${\mathcal{S}}^n$. In particular, $q(s^n)$ can give mass 1 to some state sequence $s^n$. We use the shorthand notation $\mathcal{L}=\{W_{Y,Y_1|X,X_1,S}\}$ for the AVRC, where the alphabets are understood from the context.

To analyze the AVRC, we consider the compound relay channel. Different models of compound relay channels have been considered in the literature [30,88]. Here, we define the compound relay channel as a discrete memoryless relay channel $(\mathcal{X},{\mathcal{X}}_1,\mathcal{S},$ $W_{Y,Y_1|X,X_1,S},\mathcal{Y},{\mathcal{Y}}_1)$ with a discrete memoryless state, where the state distribution $q(s)$ is not known in exact, but rather belongs to a family of distributions $\mathcal{Q}$, with $\mathcal{Q}\subseteq \mathcal{P}(\mathcal{S})$. That is, $S^n\sim {\prod }_{i=1}^{n}q(s_i)$, with an unknown pmf $q\in \mathcal{Q}$ over $\mathcal{S}$. We use the shorthand notation ${\mathcal{L}}^{\mathcal{Q}}$ for the compound relay channel, where the transition probability $W_{Y,Y_1|X,X_1,S}$ and the alphabets are understood from the context.

In the analysis, we also use the following model. Suppose that the user transmits $B>0$ blocks of length n, and the jammer is entitled to use a different state distribution $q_b(s)\in \mathcal{Q}$ for every block $b\in [1:B]$, while the encoder, relay and receiver are aware of this jamming scheme. In other words, every block is governed by a different memoryless state. We refer to this channel as the block-compound relay channel, denoted by ${\mathcal{L}}^{\mathcal{Q}\times B}$. Although this is a toy model, it is a useful tool for the analysis of the AVRC.

2.3. Coding

We introduce some preliminary definitions, starting with the definitions of a deterministic code and a random code for the AVRC $\mathcal{L}$. Note that in general, the term ‘code’, unless mentioned otherwise, refers to a deterministic code.

Definition 1 

(A code, an achievable rate and capacity). A $(2^{nR},n)$ code for the AVRC $\mathcal{L}$ consists of the following; a message set $[1:2^{nR}]$, where it is assumed throughout that $2^{nR}$ is an integer, an encoder $f:[1:2^{nR}]\to {\mathcal{X}}^n$, a sequence of n relaying functions $f_{1,i}:{\mathcal{Y}}_1^{i-1}\to {\mathcal{X}}_{1,i}$, $i\in [1:n]$, and a decoding function $g:{\mathcal{Y}}^n\to [1:2^{nR}]$.

Given a message $m\in [1:2^{nR}]$, the encoder transmits $x^n=f(m)$. At time $i\in [1:n]$, the relay transmits $x_{1,i}=f_{1,i}(y_1^{i-1})$ and then receives $y_{1,i}$. The relay codeword is given by $x_1^n=f_1^n(y_1^n)\triangleq {\left(f_{1,i}(y_1^{i-1})\right)}_{i=1}^n$. The decoder receives the output sequence $y^n$, and finds an estimate of the message $\widehat{m}=g(y^n)$ (see Figure 1). We denote the code by $\mathcal{C}=\left(f(·),f_1^n(·),g(·)\right)$. Define the conditional probability of error of the code $\mathcal{C}$ given a state sequence $s^n\in {\mathcal{S}}^n$ by

$$\begin{array}{c}\hfill P_{e|s^n}^{(n)}(\mathcal{C})=\frac{1}{2^{nR}}\sum _{m=1}^{2^{nR}}\sum _{\begin{array}{c}(y^n,y_1^n):g(y^n)\ne m\end{array}}\left[\prod _{i=1}^n{W}_{Y,Y_1|X,X_1,S}(y_i,y_{1,i}|f_i(m),f_{1,i}(y_1^{i-1}),s_i)\right].\end{array}$$

(4)

Now, define the average probability of error of $\mathcal{C}$ for some distribution $q(s^n)\in \mathcal{P}({\mathcal{S}}^n)$,

$$\begin{array}{c}\hfill P_e^{(n)}(q,\mathcal{C})=\sum _{s^n\in {\mathcal{S}}^n}q(s^n)·P_{e|s^n}^{(n)}(\mathcal{C}).\end{array}$$

(5)

Observe that $P_e^{(n)}(q,\mathcal{C})$ is linear in q, and thus continuous. We say that $\mathcal{C}$ is a $(2^{nR},n,\epsilon )$ code for the AVRC $\mathcal{L}$ if it further satisfies

$$\begin{array}{c}\hfill P_e^{(n)}(q,\mathcal{C})\le \epsilon ,\mathit{for}\mathit{all}q(s^n)\in \mathcal{P}({\mathcal{S}}^n).\end{array}$$

(6)

A rate R is called achievable if for every $\epsilon >0$ and sufficiently large n, there exists a $(2^{nR},n,\epsilon )$ code. The operational capacity is defined as the supremum of the achievable rates and it is denoted by $\mathbb{C}(\mathcal{L})$. We use the term ‘capacity’ referring to this operational meaning, and in some places we call it the deterministic code capacity in order to emphasize that achievability is measured with respect to deterministic codes.

We proceed now to define the parallel quantities when using stochastic-encoders stochastic-decoder triplets with common randomness. The codes formed by these triplets are referred to as random codes.

Definition 2 

(Random code). A $(2^{nR},n)$ random code for the AVRC $\mathcal{L}$ consists of a collection of $(2^{nR},n)$ codes ${\{{\mathcal{C}}_{\gamma }=(f_{\gamma },f_{1,\gamma }^n,g_{\gamma })\}}_{\gamma \in \mathsf{\Gamma }}$, along with a probability distribution $\mu (\gamma )$ over the code collection Γ. We denote such a code by ${\mathcal{C}}^{\mathsf{\Gamma }}=(\mu ,\mathsf{\Gamma },{\{{\mathcal{C}}_{\gamma }\}}_{\gamma \in \mathsf{\Gamma }})$. Analogously to the deterministic case, a $(2^{nR},n,\epsilon )$ random code has the additional requirement

$$\begin{array}{cc}\hfill P_e^{(n)}(q,{\mathcal{C}}^{\mathsf{\Gamma }})=\sum _{\gamma \in \mathsf{\Gamma }}\mu (\gamma )P_e^{(n)}(q,{\mathcal{C}}_{\gamma })\le \epsilon ,\mathit{for}\mathit{all}q(s^n)\in \mathcal{P}({\mathcal{S}}^n)& .\hfill \end{array}$$

(7)

The capacity achieved by random codes is denoted by ${\mathbb{C}}^{\star }(\mathcal{L})$, and it is referred to as the random code capacity.

3. Main Results—General AVRC

We present our results on the compound relay channel and the AVRC.

3.1. The Compound Relay Channel

We establish the cutset upper bound and the partial decode-forward lower bound for the compound relay channel. Consider a given compound relay channel ${\mathcal{L}}^{\mathcal{Q}}$. Let

$$\begin{array}{cc}\hfill {\mathsf{R}}_{CS}({\mathcal{L}}^{\mathcal{Q}})\triangleq & \underset{q\in \mathcal{Q}}{\inf }\underset{p(x,x_1)}{\max }\min \left\{I_q(X,X_1;Y),I_q(X;Y,Y_1|X_1)\right\},\hfill \end{array}$$

(8)

and

$$\begin{array}{c}{\mathsf{R}}_{PDF}({\mathcal{L}}^{\mathcal{Q}})\triangleq \underset{p(u,x,x_1)}{\max }\min \{\underset{q\in \mathcal{Q}}{\inf }{I}_q(U,X_1;Y)+\underset{q\in \mathcal{Q}}{\inf }{I}_q(X;Y|X_1,U),\hfill \\ \underset{q\in \mathcal{Q}}{\inf }{I}_q(U;Y_1|X_1)+\underset{q\in \mathcal{Q}}{\inf }{I}_q(X;Y|X_1,U)\},\hfill \end{array}$$

(9)

where the subscripts ‘$CS$’ and ‘$DF$’ stand for ‘cutset’ and ‘partial decode-forward’, respectively.

Lemma 1.

The capacity of the compound relay channel ${\mathcal{L}}^{\mathcal{Q}}$ is bounded by

$$\begin{array}{c}\mathbb{C}({\mathcal{L}}^{\mathcal{Q}})\ge {\mathsf{R}}_{PDF}({\mathcal{L}}^{\mathcal{Q}}),\hfill \end{array}$$

(10)

$$\begin{array}{c}{\mathbb{C}}^{\star }({\mathcal{L}}^{\mathcal{Q}})\le {\mathsf{R}}_{CS}({\mathcal{L}}^{\mathcal{Q}}).\hfill \end{array}$$

(11)

Specifically, if $R<{\mathsf{R}}_{PDF}({\mathcal{L}}^{\mathcal{Q}})$, then there exists a $(2^{nR},n,e^{-an})$ block Markov code over ${\mathcal{L}}^{\mathcal{Q}}$ for sufficiently large n and some $a>0$.

The proof of Lemma 1 is given in Appendix A. The achievability proof is based on block Markov coding interlaced with the partial decode-forward scheme. That is, the encoder sends a sequence of messages over multiple blocks. The message in each block consists of two components, a decode-forward component, and a direct transmission component, where only the former is decoded by the relay. The name ‘decode-forward component’ stands for the fact that the relay decodes this message component and sends its estimation forwards, to the destination receiver. Once the decoder has received all blocks, the decode-forward components are decoded backwards, i.e., starting with the message in the last block going backwards. Using the estimation of the decode-forward components, the direct transmission components are decoded forwards, i.e., starting with the message in the first block going forwards. The ambiguity of the state distribution needs to be dealt with throughout all of those estimations. In both decoding stages, the receiver performs joint typicality decoding using a set of types that “quantizes” the set $\mathcal{Q}$ of state distributions.

Remark 1.

If the set of state distributions $\mathcal{Q}$ is convex, then the upper bound expression in the RHS of Equation (8) has a $\min \max$ form. On the other hand, in the lower bound expression in the RHS of Equation (9), the maximum comes first, and then we have multiple min terms, which makes this expression a lot more complicated than the classical partial decode-forward bound [4] (see also [3], Theorem 16.3), where Markov properties lead to a simpler expression. We note that this phenomenon (or one might say, disturbance) where the lower bound has multiple min terms is not exclusive to the AVRC. A noteworthy example is the arbitrarily varying wiretap channel [76,89], where the lower bound has the form of $\max [\min I_q(U;Y)-\max I_q(U;Z)]$. While the capacity of the classical wiretap channel is known, the arbitrarily varying counterpart has remained an open problem for several years.

Observe that taking $U=\varnothing$ in (9) gives the direct transmission lower bound,

$$\begin{array}{cc}\hfill \mathbb{C}({\mathcal{L}}^{\mathcal{Q}})\ge & {\mathsf{R}}_{PDF}({\mathcal{L}}^{\mathcal{Q}})\ge \underset{p(x,x_1)}{\max }\underset{q\in \mathcal{Q}}{\inf }{I}_q(X;Y|X_1).\hfill \end{array}$$

(12)

Taking $U=X$ in (9) results in a full decode-forward lower bound,

$$\begin{array}{cc}\hfill \mathbb{C}({\mathcal{L}}^{\mathcal{Q}})\ge & {\mathsf{R}}_{PDF}({\mathcal{L}}^{\mathcal{Q}})\ge \underset{p(x,x_1)}{\max }\underset{q\in \mathcal{Q}}{\inf }\min \left\{I_q(X,X_1;Y),I_q(X;Y_1|X_1)\right\}.\hfill \end{array}$$

(13)

This yields the following corollary. The corollary uses the terms of a strongly degraded relay channel, for which $W_{Y,Y_1|X,X_1,S}=W_{Y_1|X,X_1}{W}_{Y|Y_1,X_1,S}$, and a strongly reversely degraded relay channel, for which $W_{Y,Y_1|X,X_1,S}=W_{Y|X,X_1,S}{W}_{Y_1|Y,X_1}$, as defined in Section 2.2.

Corollary 1.

Let ${\mathcal{L}}^{\mathcal{Q}}$ be a compound relay channel, where $\mathcal{Q}$ is a compact convex set.

1. 

If $W_{Y,Y_1|X,X_1,S}$ is strongly reversely degraded, then

$$\begin{array}{c}\hfill \mathbb{C}({\mathcal{L}}^{\mathcal{Q}})={\mathsf{R}}_{PDF}({\mathcal{L}}^{\mathcal{Q}})={\mathsf{R}}_{CS}({\mathcal{L}}^{\mathcal{Q}})=\underset{q\in \mathcal{Q}}{\min }\underset{p(x,x_1)}{\max }{I}_q(X;Y|X_1).\end{array}$$

(14)

2. 

If $W_{Y,Y_1|X,X_1,S}$ is strongly degraded, then

$$\begin{array}{c}\hfill \mathbb{C}({\mathcal{L}}^{\mathcal{Q}})={\mathsf{R}}_{PDF}({\mathcal{L}}^{\mathcal{Q}})={\mathsf{R}}_{CS}({\mathcal{L}}^{\mathcal{Q}})=\underset{p(x,x_1)}{\max }\min \left\{\underset{q\in \mathcal{Q}}{\min }{I}_q(X,X_1;Y),I(X;Y_1|X_1)\right\}.\end{array}$$

(15)

The proof of Corollary 1 is given in Appendix B. Part 1 follows from the direct transmission and cutset bounds, (12) and (8), respectively, while part 2 is based on the full decode-forward and cutset bounds, (13) and (8), respectively, along with the convexity considerations in the remark below.

Remark 2.

On a technical level, there are two purposes for considering the strongly degraded relay channel, for which the marginal channel to the relay is independent of the state, i.e., $W_{Y_1|X,X_1,S}=W_{Y_1|X,X_1}$ (see Section 2.2). First, this ensures that $X-(X_1,Y_1)-Y$ form a Markov chain, without conditioning on S. Secondly, as pointed out in Remark 1, there is a difference between the order of the min and max in the lower and upper bounds (cf. (8) and (9)). Thereby, proving the capacity results of Corollary 1 above, we apply the minimax theorem. In general, a pointwise minimum of two convex functions may not necessarily yield a convex function. Nevertheless, having assumed that the relay channel is strongly degraded, the functional $G(p,q)=\min \{I_q(X,X_1;Y),I(X;Y_1|X_1)\}$ is quasi-convex in the state distribution, i.e.,

$$\begin{array}{c}\hfill G(p,(1-\alpha )q_1+\alpha q_2))\le \max \left(G(p,q_1),G(p,q_2)\right),\end{array}$$

(16)

for every $p\in \mathcal{P}(\mathcal{X}\times {\mathcal{X}}_1)$, $q_1,q_2\in \mathcal{Q}$, and $0\le \alpha \le 1$. The quasi-convex shape is illustrated in Figure 2, which depicts $G(p,q)$ for an example given in the sequel. By [90] (Theorem 3.4), the minimax theorem applies to quasi-convex functions as well, which alleviates the proof of Corollary 1.

The following corollary is a direct consequence of Lemma 1 and it is significant for the random code analysis of the AVRC.

Corollary 2.

The capacity of the block-compound relay channel ${\mathcal{L}}^{\mathcal{Q}\times B}$ is bounded by

$$\begin{array}{c}\mathbb{C}({\mathcal{L}}^{\mathcal{Q}\times B})\ge {\mathsf{R}}_{PDF}({\mathcal{L}}^{\mathcal{Q}}),\hfill \end{array}$$

(17)

$$\begin{array}{c}{\mathbb{C}}^{\star }({\mathcal{L}}^{\mathcal{Q}\times B})\le {\mathsf{R}}_{CS}({\mathcal{L}}^{\mathcal{Q}}).\hfill \end{array}$$

(18)

Specifically, if $R<{\mathsf{R}}_{PDF}({\mathcal{L}}^{\mathcal{Q}})$, then there exists a $(2^{nR},n,e^{-an})$ block Markov code over ${\mathcal{L}}^{\mathcal{Q}\times B}$ for sufficiently large n and some $a>0$.

The proof of Corollary 2 is given in Appendix C.

3.2. The AVRC

We give lower and upper bounds, on the random code capacity and the deterministic code capacity, for the AVRC $\mathcal{L}$.

3.2.1. Random Code Lower and Upper Bounds

The random code bounds below are obtained through a modified version of Ahlswede’s RT, using our results on the block-compound relay channel in Corollary 2. Define

$$\begin{array}{c}\hfill {\mathsf{R}}_{PDF}^{\star }(\mathcal{L})\triangleq {\mathsf{R}}_{PDF}({\mathcal{L}}^{\mathcal{Q}}){|}_{\mathcal{Q}=\mathcal{P}(S)},{\mathsf{R}}_{CS}^{\star }(\mathcal{L})\triangleq {\mathsf{R}}_{CS}({\mathcal{L}}^{\mathcal{Q}}){|}_{\mathcal{Q}=\mathcal{P}(S)}.\end{array}$$

(19)

Theorem 1.

The random code capacity of an AVRC $\mathcal{L}$ is bounded by

$$\begin{array}{c}\hfill {\mathsf{R}}_{PDF}^{\star }(\mathcal{L})\le {\mathbb{C}}^{\star }(\mathcal{L})\le {\mathsf{R}}_{CS}^{\star }(\mathcal{L}).\end{array}$$

(20)

The proof of Theorem 1 is given in Appendix D. To prove Theorem 1 we modify Ahlswede’s RT. A straightforward application of Ahlswede’s RT fails to comply with the strictly causal relay transmission. Essentially, the RT uses a reliable code for the compound channel code to construct a random code for the AVC, applying random permutations to the transmitted codeword. However, the relay cannot apply permutations to its transmission, since at time $i\in [1:n]$, the relay cannot compute $f_{1,j}(y_1^{j-1})$, for $j>i$, as the relay encoder only knows the past received symbols $y_{1,1},\dots ,y_{1,i-1}$, and does not have access to the symbols $y_{1,i},\dots ,y_{1,j-1}$ which will be received in the future. To resolve this difficulty, we use a block Markov code for the block compound channel. In a block Markov coding scheme, the relay sends $x_{1,b}^n$ in block b, using the sequence of symbols $y_{1,b-1}^n$ received in the previous block. Since the entire sequence $y_{1,b-1}^n$ is known to the relay encoder, permutations can be applied to the transmission in each block separately. Hence, our proof exploits the structure of the original block-compound channel code to construct a random code for the AVRC, as opposed to classical works where the RT is used such that the original code is treated as a “black box” [59].

Remark 3.

Block Markov coding with partial decode-forward is not a simple scheme by itself, and thus, using the RT requires careful attention. In particular, by close inspection of the proof of Theorem 1, one may recognize that the necessity of using the block-compound relay channel, rather than the standard compound channel, stems from the fact that for the AVRC, the state sequences may have completely different types in each block. For each block, we use the RT twice. First, the RT is applied to the probability of the backward decoding error, for the message component which is decoded by the relay. Then, it is applied to the probability of forward decoding error, for the message component which is transmitted directly.

Together with Corollary 1, the theorem above yields another corollary.

Corollary 3.

Let $\mathcal{L}$ be an AVRC.

1. 

If $W_{Y,Y_1|X,X_1,S}$ is strongly reversely degraded,

$$\begin{array}{c}\hfill {\mathbb{C}}^{\star }(\mathcal{L})={\mathsf{R}}_{PDF}^{\star }(\mathcal{L})={\mathsf{R}}_{CS}^{\star }(\mathcal{L})=\underset{q(s)}{\min }\underset{p(x,x_1)}{\max }{I}_q(X;Y|X_1).\end{array}$$

(21)

2. 

If $W_{Y,Y_1|X,X_1,S}$ is strongly degraded,

$$\begin{array}{c}\hfill {\mathbb{C}}^{\star }(\mathcal{L})={\mathsf{R}}_{PDF}^{\star }(\mathcal{L})={\mathsf{R}}_{CS}^{\star }(\mathcal{L})=\underset{p(x,x_1)}{\max }\min \left\{\underset{q(s)}{\min }{I}_q(X,X_1;Y),I(X;Y_1|X_1)\right\}.\end{array}$$

(22)

Before we proceed to the deterministic code capacity, we note that Ahlswede’s Elimination Technique [55] can be applied to the AVRC as well. Hence, the size of the code collection of any reliable random code can be reduced to polynomial size.

3.2.2. Deterministic Code Lower and Upper Bounds

In the next statements, we characterize the deterministic code capacity of the AVRC $\mathcal{L}$. We consider conditions under which the deterministic code capacity is positive, and it coincides with the random code capacity, and conditions under which it is lower. For every $x_1\in {\mathcal{X}}_1$, let ${\mathcal{W}}_1(x_1)$ and $\mathcal{W}(x_1)$ denote the marginal AVCs from the sender to the relay and from the sender to the destination receiver, respectively,

$$\begin{array}{c}\hfill {\mathcal{W}}_1(x_1)=\{W_{Y_1|X,X_1,S}(·|·,x_1,·)\},\mathcal{W}(x_1)=\{W_{Y|X,X_1,S}(·|·,x_1,·)\}.\end{array}$$

(23)

See Figure 3.

Lemma 2 gives a condition under which the deterministic code capacity is the same as the random code capacity. The condition is given in terms of the marginal AVCs ${\mathcal{W}}_1(x_1)$ and $\mathcal{W}(x_1)$.

Lemma 2.

If the marginal sender-relay and sender-reciever AVCs have positive capacities, i.e., $\mathbb{C}({\mathcal{W}}_1(x_{1,1}))>0$ and $\mathbb{C}(\mathcal{W}(x_{1,2}))$ $>0$, for some $x_{1,1},x_{1,2}\in {\mathcal{X}}_1$, then the capacity of the AVRC $\mathcal{L}$ is positive, and it coincides with the random code capacity, i.e.,$\mathbb{C}(\mathcal{L})={\mathbb{C}}^{\star }(\mathcal{L})>0$.

The proof of Lemma 2 is given in Appendix E, extending Ahlswede’s Elimination Technique [55].

Next, we give a computable sufficient condition, under which the deterministic code capacity coincides with the random code capacity. For the point to point AVC, this occurs if and only if the channel is non-symmetrizable [56,57] (Definition 2). Our condition here is given in terms of an extended definition of symmetrizability, akin to [67] (Definition 3.2).

Definition 3.

A state-dependent relay channel $W_{Y,Y_1|X,X_1,S}$ is said to be symmetrizable-$\mathcal{X}|{\mathcal{X}}_1$ if for some conditional distribution $J(s|x)$,

$$\begin{array}{c}\sum _{s\in \mathcal{S}}{W}_{Y,Y_1|X,X_1,S}(y,y_1|x,x_1,s)J(s|\tilde{x})=\sum _{s\in \mathcal{S}}{W}_{Y,Y_1|X,X_1,S}(y,y_1|\tilde{x},x_1,s)J(s|x),\hfill \\ \hfill \forall x,\tilde{x}\in \mathcal{X},x_1\in {\mathcal{X}}_1,y\in \mathcal{Y},y_1\in {\mathcal{Y}}_1.\end{array}$$

(24)

Equivalently, for every given $x_1\in {\mathcal{X}}_1$, the channel $W_{\overline{Y}|X,X_1,S}(·|·,x_1,·)$ is symmetrizable, where $\overline{Y}=(Y,Y_1)$.

A similar definition applies to the marginals $W_{Y|X,X_1,S}$ and $W_{Y_1|X,X_1,S}$. Note that symmetrizability of each of these marginals can be checked, without reference to whether the channel is degraded or strongly degraded.

Corollary 4.

Let $\mathcal{L}$ be an AVRC.

1. 

If $W_{Y|X,X_1,S}$ and $W_{Y_1|X,X_1,S}$ are non-symmetrizable-$\mathcal{X}|{\mathcal{X}}_1$, then $\mathbb{C}(\mathcal{L})={\mathbb{C}}^{\star }(\mathcal{L})>0$. In this case,

$$\begin{array}{c}\hfill {\mathsf{R}}_{PDF}^{\star }(\mathcal{L})\le \mathbb{C}(\mathcal{L})\le {\mathsf{R}}_{CS}^{\star }(\mathcal{L}).\end{array}$$

(25)

2. 

If $W_{Y,Y_1|X,X_1,S}$ is strongly reversely degraded, where $W_{Y_1|X,X_1,S}$ is non-symmetrizable-$\mathcal{X}|{\mathcal{X}}_1$, then

$$\begin{array}{c}\hfill \mathbb{C}(\mathcal{L})={\mathbb{C}}^{\star }(\mathcal{L})={\mathsf{R}}_{PDF}^{\star }(\mathcal{L})={\mathsf{R}}_{CS}^{\star }(\mathcal{L})=\underset{q(s)}{\min }\underset{p(x,x_1)}{\max }{I}_q(X;Y|X_1).\end{array}$$

(26)

3. 

If $W_{Y,Y_1|X,X_1,S}$ is strongly degraded, where $W_{Y|X,X_1,S}$ is non-symmetrizable-$\mathcal{X}|{\mathcal{X}}_1$ and $W_{Y_1|X,X_1}(y_1|x,x_1)\ne W_{Y_1|X,X_1}(y_1|\tilde{x},x_1)$ for some $x,\tilde{x}\in \mathcal{X}$, $x_1\in {\mathcal{X}}_1$ and $y_1\in {\mathcal{Y}}_1$, then

$$\begin{array}{c}\hfill \mathbb{C}(\mathcal{L})={\mathbb{C}}^{\star }(\mathcal{L})={\mathsf{R}}_{PDF}^{\star }(\mathcal{L})={\mathsf{R}}_{CS}^{\star }(\mathcal{L})=\underset{p(x,x_1)}{\max }\min \left\{\underset{q(s)}{\min }{I}_q(X,X_1;Y),I(X;Y_1|X_1)\right\}.\end{array}$$

(27)

The proof of Corollary 4 is given in Appendix F.

Remark 4.

By Corollary 4, we have that non-symmetrizability of the marginal AVCs, ${\mathcal{W}}_1(x_{1,1})$ and $\mathcal{W}(x_{1,2})$, for some $x_{1,1},x_{1,2}\in {\mathcal{X}}_1$, is a sufficient condition for positive capacity (see Figure 3). This raises the question whether it is a necessary condition as well. In other words: If ${\mathcal{W}}_1(x_1)$ and $\mathcal{W}(x_1)$ are symmetrizable for all $x_1\in {\mathcal{X}}_1$, does that necessarily imply that the capacity is zero? The answer is no. We show this using a very simple example. Suppose that $Y_1=S$ and $Y=(X_1,X+S)$, where all variables are binary. It is readily seen that for both $Y_1$ and Y, the input and the state are symmetric, for every given $X_1=x_1$. Hence, ${\mathcal{W}}_1(x_1)$ and $\mathcal{W}(x_1)$ are symmetrizable for all $x_1\in {\mathcal{X}}_1$. Nevertheless, we note that since the relay can send $X_1=Y_1=S$, this is equivalent to an AVC with state information at the decoder. As the decoder can use $X_1$ to eliminate the state, the capacity of this AVRC is $\mathbb{C}(\mathcal{L})=1$. In Lemma 3 below, we give a stronger condition which is a necessary condition for positive capacity.

Remark 5.

Note that there are 4 symmetrizability cases in terms of the sender-relay channel $W_{Y_1|X,X_1,S}$ and the sender-receiver channel $W_{Y|X,X_1,S}$. For the case where $W_{Y_1|X,X_1,S}$ and $W_{Y|X,X_1,S}$ are both non-symmetrizable-$\mathcal{X}|{\mathcal{X}}_1$, the lemma above asserts that the capacity coincides with the random code capacity. In other cases, one may expect the capacity to be lower than the random code capacity. For instance, if $W_{Y|X,X_1,S}$ is non-symmetrizable-$\mathcal{X}|{\mathcal{X}}_1$, while $W_{Y_1|X,X_1,S}$is symmetrizable-$\mathcal{X}|{\mathcal{X}}_1$, then the capacity is positive by direct transmission. Furthermore, in this case, if the channel is reversely degraded, then the capacity coincides with the random code capacity. However, it remains in question whether this is true in general, when the channel is not reversely degraded.

Next, we consider conditions under which the capacity is zero. Observe that if $W_{Y,Y_1|X,X_1,S}$ is symmetrizable-$\mathcal{X}|{\mathcal{X}}_1$ then so are $W_{Y|X,X_1,S}$ and $W_{Y_1|X,X_1,S}$. Intuitively, if the AVRC is symmetrizable-$\mathcal{X}|{\mathcal{X}}_1$, then it is a poor channel. For example, say $Y_1=X+X_1+S$ and $Y=X·X_1·S$, with $\mathcal{S}=\mathcal{X}$. Then, the jammer can confuse the decoder by taking the state sequence $S^n$ to be some codeword. The following lemma validates this intuition.

Lemma 3.

If the AVRC $\mathcal{L}$ is symmetrizable-$\mathcal{X}|{\mathcal{X}}_1$, then it has zero capacity, i.e., $\mathbb{C}(\mathcal{L})=0$. Equivalently, non-symmetrizability-$\mathcal{X}|{\mathcal{X}}_1$ of the AVRC $\mathcal{L}$ is a necessary condition for positive capacity.

Lemma 3 is proved in Appendix G, using an extended version of Ericson’s technique [56]. For a strongly degraded AVRC, we have a simpler symmetrizability condition under which the capacity is zero.

Definition 4.

Let $W_{Y,Y_1|X,X_1,S}=W_{Y_1|X,X_1}{W}_{Y|Y_1,X_1,S}$ be a strongly degraded relay channel. We say that $W_{Y,Y_1|X,X_1,S}$ is symmetrizable-${\mathcal{X}}_1\times {\mathcal{Y}}_1$ if for some conditional distribution $J(s|x_1,y_1)$,

$$\begin{array}{c}\sum _{s\in \mathcal{S}}{W}_{Y|Y_1,X_1,S}(y|y_1,x_1,s)J(s|{\tilde{x}}_1,{\tilde{y}}_1)=\sum _{s\in \mathcal{S}}{W}_{Y|Y_1,X_1,S}(y|{\tilde{y}}_1,{\tilde{x}}_1,s)J(s|x_1,y_1),\hfill \\ \hfill \forall {\tilde{x}}_1,x_1\in {\mathcal{X}}_1,y\in \mathcal{Y},y_1,{\tilde{y}}_1\in {\mathcal{Y}}_1.\end{array}$$

(28)

Equivalently, the channel $W_{Y|{\overline{Y}}_1,S}$ is symmetrizable, where ${\overline{Y}}_1=(Y_1,X_1)$.

Lemma 4.

If the AVRC $\mathcal{L}$ is strongly degraded and symmetrizable-${\mathcal{X}}_1\times {\mathcal{Y}}_1$, then it has zero capacity, i.e., $\mathbb{C}(\mathcal{L})=0$.

Lemma 4 is proved in Appendix H. An example is given below.

Example 1.

Consider a state-dependent relay channel $W_{Y,Y_1|X,X_1,S}$, specified by

$$\begin{array}{cc}\hfill Y_1=& X+Z\mathrm{mod}2,\hfill \\ \hfill Y=& X_1+S,\hfill \end{array}$$

where $\mathcal{X}={\mathcal{X}}_1=\mathcal{Z}=\mathcal{S}={\mathcal{Y}}_1=\{0,1\}$ and $\mathcal{Y}=\{0,1,2\}$, and the additive noise is distributed according to $Z\sim \mathrm{Bernoulli}(\theta )$, $0\le \theta \le 1$. It is readily seen that $W_{Y,Y_1|X,X_1,S}$ is strongly degraded and symmetrizable-${\mathcal{X}}_1\times {\mathcal{Y}}_1$, by (2) and (28). In particular, (28) is satisfied with $J(s|x_1,y_1)=1$ for $s=x_1$, and $J(s|x_1,y_1)=0$ otherwise. Hence, by Lemma 4, the capacity is $\mathbb{C}(\mathcal{L})=0$. On the other hand, we show that the random code capacity is given by ${\mathbb{C}}^{\star }(\mathcal{L})=\min \left\{\frac{1}{2},1-h(\theta )\right\}$, using Corollary 3. The derivation of the random code capacity is given in Appendix I.

3.3. AVRC with Orthogonal Sender Components

Consider the special case of a relay channel $W_{Y,Y_1|X,X_1,S}$ with orthogonal sender components [5]; [3] (Section 16.6.2), where $X=(X^{\prime },X^{″})$ and

$$\begin{array}{c}\hfill W_{Y,Y_1|X^{\prime },X^{″},X_1,S}(y,y_1|x^{\prime },x^{″},x_1,s)=W_{Y|X^{\prime },X_1,S}(y|x^{\prime },x_1,s)·W_{Y_1|X^{″},X_1,S}(y_1|x^{″},x_1,s).\end{array}$$

(29)

Here, we address the case where the channel output depends on the state only through the relay, i.e., $W_{Y|X^{\prime },X_1,S}(y|x^{\prime },x_1,s)=W_{Y|X^{\prime },X_1}(y|x^{\prime },x_1)$.

Lemma 5.

Let $\mathcal{L}$ = $\{W_{Y|X^{\prime },X_1}$ $W_{Y_1|X^{″},X_1,S}\}$ be an AVRC with orthogonal sender components. The random code capacity of $\mathcal{L}$ is given by

$$\begin{array}{c}\hfill {\mathbb{C}}^{\star }(\mathcal{L})={\mathsf{R}}_{PDF}^{\star }(\mathcal{L})={\mathsf{R}}_{CS}^{\star }(\mathcal{L})=\underset{p(x_1)p(x^{\prime }|x_1)p(x^{″}|x_1)}{\max }\min \left\{I(X^{\prime },X_1;Y),\underset{q(s)}{\min }{I}_q(X^{″};Y_1|X_1)+I(X^{\prime };Y|X_1)\right\}.\end{array}$$

(30)

If $W_{Y_1|X^{″},X_1,S}$ is non-symmetrizable-${\mathcal{X}}^{″}|{\mathcal{X}}_1$, and $W_{Y|X^{\prime },X_1}(y|x^{\prime },x_1)\ne W_{Y|X^{\prime },X_1}(y|{\tilde{x}}^{\prime },x_1)$ for some $x_1\in {\mathcal{X}}_1$, $x^{\prime },{\tilde{x}}^{\prime }\in {\mathcal{X}}^{\prime }$, $y\in \mathcal{Y}$, then the deterministic code capacity is given by $\mathbb{C}(\mathcal{L})={\mathsf{R}}_{PDF}^{\star }(\mathcal{L})={\mathsf{R}}_{CS}^{\star }(\mathcal{L})$.

The proof of Lemma 5 is given in Appendix J. To prove Lemma 5, we apply the methods of [5] to our results. Specifically, we use the partial decode-forward lower bound in Theorem 1, taking $U=X^{″}$ (see (9) and (19)).

4. Gaussian AVRC with Sender Frequency Division

We give extended results for the Gaussian AVRC with sender frequency division (SFD), which is a special case of the AVRC with orthogonal sender components [5]. We determine the random code capacity of the Gaussian AVRC with SFD, and give lower and upper bounds on the deterministic code capacity. The derivation of the deterministic code bounds is mostly independent of our previous results, and it is based on the technique by [87]. The Gaussian relay channel $W_{Y,Y_1|X,X_1,S}$ with SFD is a special case of a relay channel with orthogonal sender components [5], specified by

$$\begin{array}{cc}\hfill Y_1=& X^{″}+Z,\hfill \\ \hfill Y=& X^{\prime }+X_1+S,\hfill \end{array}$$

(31)

where the Gaussian additive noise $Z\sim \mathcal{N}(0,{\sigma }^2)$ is independent of the channel state. As opposed to Lemma 5, the main channel here depends on the state, while the channel to the relay does not. In the case of a Gaussian channel, power limitations need to be accounted for, and thus, we consider the Gaussian relay channel under input and state constraints. Specifically, the user and the relay’s transmission are subject to input constraints $\mathsf{\Omega }>0$ and ${\mathsf{\Omega }}_1>0$, respectively, and the jammer is under a state constraint $\mathsf{\Lambda }$, i.e.,

$$\begin{array}{c}\frac{1}{n}\sum _{i=1}^n(X_i^{\prime 2}+X_i^{″2})\le \mathsf{\Omega },\frac{1}{n}\sum _{i=1}^n{X}_{1,i}^2\le {\mathsf{\Omega }}_1\mathrm{w}.\mathrm{p}.1,\hfill \\ \frac{1}{n}\sum _{i=1}^n{S}_i^2\le \mathsf{\Lambda }\mathrm{w}.\mathrm{p}.1.\hfill \end{array}$$

(32)

We note that Ahlswede’s Elimination Technique cannot be used under a state constraint (see [57]). Indeed, if the jammer concentrates a lot of power on the shared randomness transmission, then this transmission needs to be robust against a state constraint that is higher than $\mathsf{\Lambda }$. Thereby, the results given in Section 3.2.2 do not apply to the Gaussian AVRC under input and state constraints.

For the compound relay channel, the state constraint is in the average sense. That is, we say that the Gaussian compound relay channel ${\mathcal{L}}^{\mathcal{Q}}$ with SFD is under input constraints $\mathsf{\Omega }$ and ${\mathsf{\Omega }}_1$ and state constraint $\mathsf{\Lambda }$ if

$$\begin{array}{c}\frac{1}{n}\sum _{i=1}^n(X_i^{\prime 2}+X_i^{″2})\le \mathsf{\Omega },\frac{1}{n}\sum _{i=1}^n{X}_{1,i}^2\le {\mathsf{\Omega }}_1,\mathrm{w}.\mathrm{p}.1,\hfill \\ \mathcal{Q}=\{q(s):\mathbb{E}{S}^2\le \mathsf{\Lambda }\}.\hfill \end{array}$$

(33)

Coding definitions and notation are as follows. The definition of a code is similar to that of Section 2.3. The encoding function is denoted by $\mathbf{f}=({\mathbf{f}}^{\prime },{\mathbf{f}}^{″})$, with ${\mathbf{f}}^{\prime }:[1:2^{nR}]\to {\mathbb{R}}^n$ and ${\mathbf{f}}^{″}:[1:2^{nR}]\to {\mathbb{R}}^n$, and the relay encoding function is denoted by ${\mathbf{f}}_1:{\mathbb{R}}^n\to {\mathbb{R}}^n$, where ${\mathrm{f}}_{1,i}:{\mathbb{R}}^{i-1}\to \mathbb{R}$, for $i\in [1:n]$. The boldface notation indicates that the encoding functions produce sequences. Here, the encoder and the relay satisfy the input constraints ${∥{\mathbf{f}}^{\prime }(m)∥}^2+{∥{\mathbf{f}}^{″}(m)∥}^2\le n\mathsf{\Omega }$ and ${∥{\mathbf{f}}_1({\mathbf{y}}_1)∥}^2\le n{\mathsf{\Omega }}_1$ for all $m\in [1:2^{nR}]$ and ${\mathbf{y}}_1\in {\mathbb{R}}^n$. At time $i\in [1:n]$, given a message $m\in [1:2^{nR}]$, the encoder transmits $(x_i^{\prime },x_i^{″})=({\mathrm{f}}_i^{\prime }(m),{\mathrm{f}}_i^{″}(m))$, and the relay transmits $x_{1,i}={\mathrm{f}}_{1,i}(y_{1,1},\dots ,y_{1,i-1})$. The decoder receives the output sequence $\mathbf{y}$, and finds an estimate $\widehat{m}=g(\mathbf{y})$. A $(2^{nR},n,\epsilon )$ code $\mathcal{C}$ for the Gaussian AVRC satisfies $P_{e|\mathbf{s}}^{(n)}(\mathcal{C})\le \epsilon$, for all $\mathbf{s}\in {\mathbb{R}}^n$ with ${∥\mathbf{s}∥}^2\le n\mathsf{\Lambda }$, where

$$\begin{array}{c}\hfill P_{e|\mathbf{s}}^{(n)}(\mathcal{C})=\frac{1}{2^{nR}}\sum _{m=1}^{2^{nR}}{\int }_{\mathcal{D}{(m,\mathbf{s})}^c}\frac{1}{{(2\pi {\sigma }^2)}^{n/2}}{e}^{-{∥\mathbf{z}∥}^2/2{\sigma }^2}d\mathbf{z},\end{array}$$

(34)

with

$$\begin{array}{c}\hfill \mathcal{D}(m,\mathbf{s})=\left\{\mathbf{z}\in {\mathbb{R}}^n:g\left({\mathbf{f}}^{\prime }(m)+{\mathbf{f}}_1\left({\mathbf{f}}^{″}(m)+\mathbf{z}\right)+\mathbf{s}\right)=m\right\}.\end{array}$$

(35)

Achivable rates, deterministic code capacity and random code capacity are defined as before. Next, we give our results on the Gaussian compound relay channel and the Gaussian AVRC with SFD.

5. Main Results—Gaussian AVRC with SFD

We give our results on the Gaussian compound and AVRC with SFD. The results on this compound relay channel and on the random code capacity of this AVRC are obtained through a straightforward extension of our previous results and derivations. However, the derivation of the deterministic code bounds is mostly independent of our previous results, and it is based on modifying the technique by Csiszär and Narayan in their paper on the Gaussian AVC [87].

5.1. Gaussian Compound Relay Channel

We determine the capacity of the Gaussian compound relay channel with SFD under input and state constraints. Let

$$\begin{array}{c}{\mathsf{F}}_G(\alpha ,\rho )\triangleq \min \{\frac{1}{2}\log \left(1+\frac{{\mathsf{\Omega }}_1+\alpha \mathsf{\Omega }+2\rho \sqrt{\alpha \mathsf{\Omega }}\sqrt{{\mathsf{\Omega }}_1}}{\mathsf{\Lambda }}\right),\hfill \\ \hfill \frac{1}{2}\log \left(1+\frac{(1-\alpha )\mathsf{\Omega }}{{\sigma }^2}\right)+\frac{1}{2}\log \left(1+\frac{(1-{\rho }^2)\alpha \mathsf{\Omega }}{\mathsf{\Lambda }}\right)\}.\end{array}$$

(36)

Lemma 6.

The capacity of the Gaussian compound relay channel with SFD, under input constraints Ω and ${\mathsf{\Omega }}_1$ and state constraint Λ, is given by

$$\begin{array}{c}\hfill \mathbb{C}({\mathcal{L}}^{\mathcal{Q}})=\underset{0\le \alpha ,\rho \le 1}{\max }{\mathsf{F}}_G(\alpha ,\rho ),\end{array}$$

(37)

and it is identical to the random code capacity, i.e., $\mathbb{C}({\mathcal{L}}^{\mathcal{Q}})={\mathbb{C}}^{\star }({\mathcal{L}}^{\mathcal{Q}})$.

The proof of Lemma 6 is given in Appendix K, based on our results in the previous sections. The parameter $0\le \alpha \le 1$ represents the fraction of input power invested in the transmission of the message component which is decoded by the relay, in the partial decode-forward coding scheme. Specifically, in the achievability proof in [5], $\alpha \mathsf{\Omega }$ and $(1-\alpha )\mathsf{\Omega }$ are the variances of $X^{\prime }$ and $X^{″}$, respectively. The parameter $\rho$ stands for the correlation coefficient between the decode-forward transmission $X^{\prime }$ and the relay transmission $X_1$.

5.2. Gaussian AVRC

We determine the random code capacity of the Gaussian AVRC with SFD under constraints.

Theorem 2.

The random code capacity of the Gaussian AVRC with SFD, under input constraints Ω and ${\mathsf{\Omega }}_1$ and state constraint Λ, is given by

$$\begin{array}{c}\hfill {\mathbb{C}}^{\star }(\mathcal{L})=\mathbb{C}({\mathcal{L}}^{\mathcal{Q}})=\underset{0\le \alpha ,\rho \le 1}{\max }{\mathsf{F}}_G(\alpha ,\rho ).\end{array}$$

(38)

The proof of Theorem 2 is given in Appendix L. The proof follows the same considerations as in our previous results.

Next, we give lower and upper bounds on the deterministic code capacity of the Gaussian AVRC with SFD under constraints, obtained by generalizing the non-standard techniques by Csiszár and Narayan in their 1991 paper on the Gaussian AVC [87]. Define

$$\begin{array}{c}\begin{array}{ccc}{\mathsf{R}}_{G,low}(\mathcal{L})\triangleq \hfill & \max \hfill & {\mathsf{F}}_G(\alpha ,\rho )\hfill \\ & \mathrm{subject}\mathrm{to}\hfill & 0\le \alpha ,\rho \le 1,\hfill \\ & & (1-{\rho }^2)\alpha \mathsf{\Omega }>\mathsf{\Lambda },\hfill \\ & & \frac{{\mathsf{\Omega }}_1}{\mathsf{\Omega }}{(\sqrt{{\mathsf{\Omega }}_1}+\rho \sqrt{\alpha \mathsf{\Omega }})}^2>\mathsf{\Lambda }+(1-{\rho }^2)\alpha \mathsf{\Omega }.\hfill \end{array}\hfill \end{array}$$

(39)

and

$$\begin{array}{cc}\hfill & \begin{array}{ccc}{\mathsf{R}}_{G,up}(\mathcal{L})\triangleq \hfill & \max \hfill & {\mathsf{F}}_G(\alpha ,\rho )\hfill \\ & \mathrm{subject}\mathrm{to}\hfill & 0\le \alpha ,\rho \le 1,\hfill \\ & & {\mathsf{\Omega }}_1+\alpha \mathsf{\Omega }+2\rho \sqrt{\alpha \mathsf{\Omega }·{\mathsf{\Omega }}_1}\ge \mathsf{\Lambda }.\hfill \end{array}\hfill \end{array}$$

(40)

It can be seen that ${\mathsf{R}}_{G,low}\le {\mathsf{R}}_{G,up}$, since

$$\begin{array}{c}\hfill {\mathsf{\Omega }}_1+\alpha \mathsf{\Omega }+2\rho \sqrt{\alpha \mathsf{\Omega }·{\mathsf{\Omega }}_1}=(1-{\rho }^2)\alpha \mathsf{\Omega }+{(\sqrt{{\mathsf{\Omega }}_1}+\rho \sqrt{\alpha \mathsf{\Omega }})}^2\ge (1-{\rho }^2)\alpha \mathsf{\Omega }.\end{array}$$

(41)

The analysis is based on the following lemma by [87].

Lemma 7

(see [87] (Lemma 1)). For every $\epsilon >0$, $8\sqrt{\epsilon }<\eta <1$, $K>2\epsilon$, and $\mathsf{M}=2^{nR}$, with $2\epsilon \le R\le K$, and $n\ge n_0(\epsilon ,\eta ,K)$, there exist $\mathsf{M}$ unit vectors $\mathit{a}(m)\in {\mathbb{R}}^n$, $m\in [1:\mathsf{M}]$, such that for every unit vector $\mathit{c}\in {\mathbb{R}}^n$ and $0\le \theta ,\zeta \le 1$,

$$\begin{array}{c}|\left\{\tilde{m}\in [1:\mathsf{M}]:\langle \mathbf{a}(\tilde{m}),\mathbf{c}\rangle \ge \theta \right\}|\le 2^{n\left({[R+\frac{1}{2}\log (1-{\theta }^2)]}_{+}+\epsilon \right)},\hfill \end{array}$$

(42)

and if $\theta \ge \eta$ and ${\theta }^2+{\zeta }^2>1+\eta -2^{-2R}$, then

$$\begin{array}{cc}\hfill & \frac{1}{\mathsf{M}}|\left\{m\in [1:\mathsf{M}]:|\langle \mathbf{a}(\tilde{m}),\mathbf{a}(m)\rangle |\ge \theta ,|\langle \mathbf{a}(\tilde{m}),\mathbf{c}\rangle |\ge \zeta ,\mathit{for}\mathit{some}\tilde{m}\ne m\right\}|\le 2^{-n\epsilon },\hfill \end{array}$$

(43)

where ${[t]}_{+}=\max \{0,t\}$ and $\langle ·,·\rangle$ denotes inner product.

Intuitively, the lemma states that under certain conditions, a codebook can be constructed with an exponentially small fraction of “bad” messages, for which the codewords are non-orthogonal to each other and the state sequence.

Theorem 3.

The deterministic code capacity of the Gaussian AVRC with SFD, under input constraints Ω and ${\mathsf{\Omega }}_1$ and state constraint Λ, is bounded by

$$\begin{array}{c}\hfill {\mathsf{R}}_{G,low}(\mathcal{L})\le \mathbb{C}(\mathcal{L})\le {\mathsf{R}}_{G,up}(\mathcal{L}).\end{array}$$

(44)

The proof of Theorem 3 is given in Appendix M.

Remark 6.

Csiszár and Narayan [87] have shown that for the classical Gaussian AVC, reliable decoding is guaranteed when the input constraint Ω is larger than the state constraint Λ. Here, we use a partial decode-forward coding scheme, where the message has two components, one which is decoded by the relay, and the other is transmitted directly. The respective optimization constraints $\frac{{\mathsf{\Omega }}_1}{\mathsf{\Omega }}{(\sqrt{{\mathsf{\Omega }}_1}+\rho \sqrt{\alpha \mathsf{\Omega }})}^2>\mathsf{\Lambda }+(1-{\rho }^2)\alpha \mathsf{\Omega }$ and $(1-{\rho }^2)\alpha \mathsf{\Omega }>\mathsf{\Lambda }$ in the RHS of (39), guarantee reliability for each decoding step.

Remark 7.

Csiszár and Narayan [87] have further shown that for the classical Gaussian AVC, if $\mathsf{\Omega }\le \mathsf{\Lambda }$, the capacity is zero. The converse proof in [87] follows by considering a jammer who chooses the state sequence to be a codeword. Due to the symmetry between $\mathbf{X}$ and $\mathbf{S}$, the decoder cannot distinguish between the transmitted codeword and the impostor sent by the jammer. Here, we consider a jammer who simulates ${\mathbf{X}}^{\prime }+{\mathbf{X}}_1$. Specifically, The jammer draws a codeword ${\mathbf{X}}^{\prime }={\mathbf{f}}^{\prime }(\tilde{m})$ uniformly at random, and then, generates a sequence ${\tilde{\mathbf{Y}}}_1$ distributed according to the conditional distribution $P_{{\mathbf{Y}}_1|M=\tilde{m}}$. If the sequence $\tilde{\mathbf{S}}={\mathbf{f}}^{\prime }(\tilde{m})+{\mathbf{f}}_1({\tilde{\mathbf{Y}}}_1)$ satisfies the state constraint Λ, then the jammer chooses $\tilde{\mathbf{S}}$ as the state sequence. Defining $\alpha \mathsf{\Omega }$, ${\mathsf{\Omega }}_1$, and ρ as the empirical decode-forward transmission power, relay transmission power, and their correlation coefficient, respectively, we have that the state constraint ${∥\tilde{\mathbf{S}}∥}^2\le n\mathsf{\Lambda }$ holds with high probability, if ${\mathsf{\Omega }}_1+\alpha \mathsf{\Omega }+2\rho \sqrt{\alpha \mathsf{\Omega }·{\mathsf{\Omega }}_1}<\mathsf{\Lambda }$. The details are in Appendix M.

Figure 4 depicts the bounds on the capacity of the Gaussian AVRC with SFD under input and state constraints, as a function of the input constraint $\mathsf{\Omega }={\mathsf{\Omega }}_1$, under state constraint $\mathsf{\Lambda }=1$ and ${\sigma }^2=0.5$. The top dashed line depicts the random code capacity of the Gaussian AVRC. The solid lines depict the deterministic code lower and upper bounds ${\mathsf{R}}_{G,low}(\mathcal{L})$ and ${\mathsf{R}}_{G,up}(\mathcal{L})$. For low values, $\mathsf{\Omega }<\frac{\mathsf{\Lambda }}{4}=0.25$, we have that ${\mathsf{R}}_{G,up}(\mathcal{L})=0$, hence the deterministic code capacity is zero, and it is strictly lower than the random code capacity. The dotted lower line depicts the direct transmission lower bound, which is ${\mathsf{F}}_G(1,0)$ for $\mathsf{\Omega }>\mathsf{\Lambda }$, and zero otherwise [57]. For intermediate values of $\mathsf{\Omega }$, direct transmission is better than the lower bound in Theorem 3. Whereas, for high values of $\mathsf{\Omega }$, the optimization constraints in (39) and (40) are inactive, hence, our bounds are tight, and the capacity coincides with the random code capacity, i.e., $\mathbb{C}(\mathcal{L})={\mathbb{C}}^{\star }(\mathcal{L})={\mathsf{R}}_{G,low}(\mathcal{L})={\mathsf{R}}_{G,up}(\mathcal{L})$.

6. The Primitive AVRC

In this section, we give our results on the primitive AVRC [2], and then consider the Gaussian case. Part of the motivation given in [2] to consider the primitive relay channel was that the overall behavior and properties are the same as the non primitive (“regular”) relay channel. We show that this is not true in the arbitrarily varying scenario. In particular, the behavior of the primitive Gaussian AVRC with SFD is different compared to the non-primitive counterpart considered above.

6.1. Definitions and Notation

Consider a setup where the sender transmits information over state-dependent memoryless relay channel $W_{Y,Y_1|X,S}$, while there is a noiseless link of capacity $C_1>0$ between the relay and the receiver. Communication over a primitive relay channel is depicted in Figure 5. Given a message $M\in [1:2^{nR}]$, the encoder transmits $X^n=f(M)$ over the channel $W_{Y,Y_1|X,S}$, which is referred to as the primitive relay channel. The relay receives $Y_1^n$ and sends an index $L=f_1(Y_1^n)$ to the receiver, where $f_1:{\mathcal{Y}}_1^n\to [1:2^{n{C}_1}]$. The decoder receives both the channel output sequence $Y^n$ and the relay output L, and finds an estimate of the message $\widehat{M}=g(Y^n,L)$. In accordance with the previous definitions, the primitive AVRC ${\mathcal{L}}_{\mathrm{prim}}=\{W_{Y,Y_1|X,S}\}$ has a state sequence of unknown distribution, not necessarily independent nor stationary. The deterministic code capacity and the random code capacity are defined as before, and denoted by $\mathbb{C}({\mathcal{L}}_{\mathrm{prim}})$ and ${\mathbb{C}}^{\star }({\mathcal{L}}_{\mathrm{prim}})$, respectively.

6.2. Main Results—Primitive AVRC

We give our results on the primitive AVRC below. However, since the proofs are based on the same arguments as given for the non primitive AVRC, we omit the proofs of the results in this section. The details are given in [91].

Using similar arguments to those given for the non primitive relay channel, we obtain the following bounds on the random code capacity,

$$\begin{array}{cc}\hfill {\mathsf{R}}_{CS}^{\star }\triangleq & \underset{q(s)}{\min }\underset{p(x)}{\max }\min \left\{I_q(X;Y)+C_1,I_q(X;Y,Y_1)\right\},\hfill \end{array}$$

(45)

and

$$\begin{array}{cc}\hfill {\mathsf{R}}_{PDF}^{\star }\triangleq & \underset{p(u,x)}{\max }\min \left\{\underset{q(s)}{\min }{I}_q(U;Y)+\underset{q(s)}{\min }{I}_q(X;Y|U)+C_1,\underset{q(s)}{\min }{I}_q(U;Y_1)+\underset{q(s)}{\min }{I}_q(X;Y|U)\right\}.\hfill \end{array}$$

(46)

Theorem 4.

The random code capacity of a primitive AVRC ${\mathcal{L}}_{\mathrm{prim}}$ is bounded by

$$\begin{array}{c}\hfill {\mathsf{R}}_{PDF}^{\star }\le {\mathbb{C}}^{\star }({\mathcal{L}}_{\mathrm{prim}})\le {\mathsf{R}}_{CS}^{\star }.\end{array}$$

(47)

Those bounds have the same form as the cutset upper bound and the partical decode-forward lower bound in Section 3 (cf. (8), (9) and (45), (46)). As in Section 3, we can use the bounds above to determine the capacity in the strongly degraded and reversely degraded cases, based on the direct transmission lower bound (for $U=\varnothing$), and the full decode-forward lower bound (for $U=X$).

Corollary 5.

Let ${\mathcal{L}}_{\mathrm{prim}}$ be a primitive AVRC.

1. 

If $W_{Y,Y_1|X,S}$ is strongly reversely degraded, i.e., $W_{Y,Y_1|X,S}=W_{Y|X,S}{W}_{Y_1|Y}$, then

$$\begin{array}{c}\hfill {\mathbb{C}}^{\star }({\mathcal{L}}_{\mathrm{prim}})=\underset{q(s)}{\min }\underset{p(x)}{\max }{I}_q(X;Y).\end{array}$$

(48)

2. 

If $W_{Y,Y_1|X,X_1,S}$ is strongly degraded, i.e., $W_{Y,Y_1|X,X_1,S}=W_{Y_1|X}{W}_{Y|Y_1,S}$, then

$$\begin{array}{c}\hfill {\mathbb{C}}^{\star }({\mathcal{L}}_{\mathrm{prim}})=\underset{p(x)}{\max }\min \left\{\underset{q(s)}{\min }{I}_q(X;Y)+C_1,I(X;Y_1)\right\}.\end{array}$$

(49)

As for the deterministic code capacity, we give the following theorem.

Theorem 5.

Let ${\mathcal{L}}_{\mathrm{prim}}$ be a primitive AVRC.

1. 

If $W_{Y_1|X,S}$ is non-symmetrizable, then $\mathbb{C}({\mathcal{L}}_{\mathrm{prim}})={\mathbb{C}}^{\star }({\mathcal{L}}_{\mathrm{prim}})$. In this case,

$$\begin{array}{c}\hfill {\mathsf{R}}_{PDF}^{\star }\le \mathbb{C}({\mathcal{L}}_{\mathrm{prim}})\le {\mathsf{R}}_{CS}^{\star }.\end{array}$$

(50)

2. 

If $W_{Y,Y_1|X,S}$ is strongly reversely degraded, where $W_{Y_1|X,S}$ is non-symmetrizable, then

$$\begin{array}{c}\hfill \mathbb{C}({\mathcal{L}}_{\mathrm{prim}})=\underset{q(s)}{\min }\underset{p(x)}{\max }{I}_q(X;Y).\end{array}$$

(51)

3. 

If $W_{Y,Y_1|X,S}$ is strongly degraded, such that $W_{Y_1|X}(y_1|x)\ne W_{Y_1|X}(y_1|\tilde{x})$ for some $x,\tilde{x}\in \mathcal{X}$, $y_1\in {\mathcal{Y}}_1$, then

$$\begin{array}{c}\hfill \mathbb{C}({\mathcal{L}}_{\mathrm{prim}})=\underset{p(x)}{\max }\min \left\{\underset{q(s)}{\min }{I}_q(X;Y)+C_1,I(X;Y_1)\right\}.\end{array}$$

(52)

4. 

If $W_{\tilde{Y}|X,S}$ is symmetrizable, where $\tilde{Y}=(Y,Y_1)$, then $\mathbb{C}({\mathcal{L}}_{\mathrm{prim}})=0$.

The proof of Theorem 5 is available in [91]. To illustrate our results, we give the following example of a primitive AVRC.

Example 2.

Consider a state-dependent primitive relay channel $W_{Y,Y_1|X,S}$, specified by

$$\begin{array}{cc}\hfill Y_1=& X(1-S),\hfill \\ \hfill Y=& X+S,\hfill \end{array}$$

where $\mathcal{X}=\mathcal{S}={\mathcal{Y}}_1=\{0,1\}$, $\mathcal{Y}=\{0,1,2\}$, and $C_1=1$, i.e., the link between the relay and the receiver is a noiseless bit pipe. It can be seen that both the sender-relay and the sender-receiver marginals are symmetrizable. Indeed, $W_{Y|X,S}$ satisfies

$$\begin{array}{c}\hfill \sum _{s\in \mathcal{S}}{W}_{Y|X,S}(y_1|x,s)J(s|\tilde{x})=\sum _{s\in \mathcal{S}}{W}_{Y|X,S}(y_1|\tilde{x},s)J(s|x),x,\tilde{x}\in \mathcal{X},y\in \mathcal{Y},\end{array}$$

(53)

with $J(s|x)=1$ for $s=x$, and $J(s|x)=0$ otherwise, while $W_{Y_1|X,S}$ satisfies (53) with $J(s|x)=1$ for $s=1-x$, and $J(s|x)=0$ otherwise. Nevertheless, the capacity of the primitive AVRC ${\mathcal{L}}_{\mathrm{prim}}=\{W_{Y,Y_1|X,S}\}$ is $\mathbb{C}({\mathcal{L}}_{\mathrm{prim}})=1$, which can be achieved using a code of length $n=1$, with $f(m)=m$, $f_1(y_1)=y_1$,

$$\begin{array}{c}g(y,\ell )=g(y,y_1)=\left\{\begin{array}{cc}0\hfill & y=0\hfill \\ 1\hfill & y=2\hfill \\ y_1\hfill & y=1\hfill \end{array}\right.\hfill \end{array}$$

(54)

for $m,y_1\in \{0,1\}$ and $y\in \{0,1,2\}$. This example shows that even if the sender-relay and sender-receiver marginals are symmetrizable, the capacity may still be positive. We further note that the condition in part 4 of Theorem 5 implies that $W_{Y|X,S}$ and $W_{Y_1|X,S}$ are both symmetrizable, but not vice versa, as shown by this example. That is, as the capacity is positive, we have that $W_{\tilde{Y}|X,S}$ is non-symmetrizable, where $\tilde{Y}=(Y,Y_1)$, despite the fact that the marginals $W_{Y|X,S}$ and $W_{Y_1|X,S}$ are both symmetrizable.

6.3. Primitive Gaussian AVRC

Consider the primitive Gaussian relay channel with SFD,

$$\begin{array}{cc}\hfill Y_1=& X^{″}+Z,\hfill \\ \hfill Y=& X^{\prime }+S,\hfill \end{array}$$

(55)

Suppose that input and state constraints are imposed as before, i.e., $\frac{1}{n}{\sum }_{i=1}^n(X_i^{\prime 2}+X_i^{″2})\le \mathsf{\Omega }$ and $\frac{1}{n}{\sum }_{i=1}^n{S}_i^2\le \mathsf{\Lambda }$ with probability 1. The capacity of the primitive Gaussian AVRC with SFD, under input constraint $\mathsf{\Omega }$ and state constraint $\mathsf{\Lambda }$ is given by

$$\begin{array}{c}\hfill \mathbb{C}({\mathcal{L}}_{\mathrm{prim}})={\mathbb{C}}^{\star }({\mathcal{L}}_{\mathrm{prim}})=\underset{0\le \alpha \le 1}{\max }\left[\frac{1}{2}\log \left(1+\frac{\alpha \mathsf{\Omega }}{\mathsf{\Lambda }}\right)+\min \left\{C_1,\frac{1}{2}\log \left(1+\frac{(1-\alpha )\mathsf{\Omega }}{\mathsf{\Lambda }}\right)\right\}\right].\end{array}$$

(56)

This result is due to the following. Observe that one could treat this primitive AVRC as two independent channels, one from $X^{\prime }$ to Y and the other from $X^{″}$ to $Y_1$, dividing the input power to $\alpha \mathsf{\Omega }$ and $(1-\alpha )\mathsf{\Omega }$, respectively. Based on this observation, the random code direct part follows from [92]. Next, the deterministic code direct part follows from part 1 of Theorem 5, and the converse part follows straightforwardly from the cutset upper bound in Theorem 4.

7. Discussion

We have presented the model of the arbitrarily varying relay channel (AVRC), as a state dependent relay channel, where jamming attacks result in either a random or a deterministic state sequence, $S^n\sim q(s^n)$, where the joint distribution $q(s^n)$ is unknown and it is not necessarily of a product form. We have established the cutset upper bound and the partial decode-forward lower bound on the random code capacity of the AVRC. We have determined the random code capacity in special cases of the degraded AVRC, the reversely degraded AVRC, and the AVRC with orthogonal sender components. To do so, we used the direct transmission lower bound and the full decode-forward lower bound, along with quasi-convexity properties which are required in order to use the minimax theorem.

We have provided generalized symmetrizability conditions under which the deterministic code capacity coincides with the random code capacity. Specifically, we have shown that if the sender-relay and sender-receiver marginals are non-symmetrizable for a given relay transmission, then the capacity is positive. We further noted that this is a sufficient condition for positive capacity, which raises the question whether it is also a necessary condition. In other words, if those marginals are symmetrizable for every given relay transmission, does that necessarily imply that the capacity is zero? The answer is no, and we have refuted this assertion using a simple example, where the relay acts as a source of state information to the receiver. Then, we provided a stronger symmetrizability condition, which is necessary for the capacity to be positive. We have shown by example that the deterministic code capacity can be strictly lower than the random code capacity of the AVRC.

The Gaussian AVRC with sender frequency division (SFD) under input and state constraints is also addressed in this paper. The random code capacity is determined using the above results, whereas the deterministic code capacity is lower and upper bounded using an independent approach. Specifically, we extended the technique by Csiszár and Narayan in their 1991 paper on the Gaussian AVC [87]. We have shown that the deterministic code capacity can be strictly lower than the random code capacity, for low values on the input constraint.

Furthermore, we have considered the primitive AVRC, where there is a noiseless link between the relay and the receiver of limited capacity [2]. We tested Kim’s assertion that “the primitive relay channel captures most essential features and challenges of relaying, and thus serves as a good testbed for new relay coding techniques” [2]. We have shown that this assertion is not true in the arbitrarily varying scenario. Specifically, for the primitive Gaussian AVRC with SFD, the deterministic code capacity and the random code capacity are always the same, regardless of the value of the input constraint (see (56)), in contrast to our findings for the non primitive case, as demonstrated in Figure 4.