Channels with Cooperation Links that May Be Absent

I Introduction

Communication This paper was presented in part at the 2014 and 2016 IEEE International Symposium on Information Theory. This work was supported by the ISRAEL SCIENCE FOUNDATION (ISF) (grant no. 684/11). techniques that employ cooperation between users in a network have been an extensive area of research in recent years. The interest in such schemes stems from the potential increase in the network performance. The employment of cooperative schemes require the use of system resources - bandwidth, time slots, energy, etc - that should be allocated for the cooperation to take place. Due to the dynamic nature of modern, wireless ad-hoc communication systems, the availability of these resources is not guaranteed a priori, as they depend on parameters that the system designer does not have any control on. For example, the cooperation can depend on the battery status of intermediate users (relays), on weather, or just on the willingness of peers in the network to help. A typical situation, therefore, is that the users are aware of the possibility that cooperation will take place, but it cannot be assured before transmission begins. Moreover, in many instances it is not possible to inform the transmitter whether or not a potential relay/helper decides to help. Thus, the traditional approach leaves the designer with two design options. Option 1 is the pessimistic one: assume that none of the unreliable relays exists, and design a system without cooperation. Option 2 takes the optimistic view: assume that the potential relays exist, and design a system with cooperation. The pros and cons of each of the designs are clear. Option 1 is “safe,” but results in relatively low rates. Option 2 aims to transmit at the maximal rates, but runs the risk that some of the relays/helpers are absent, in which case the coding scheme collapses.

In this work we suggest a third option: design a robust system, which takes advantage of the links if they are present, but can operate also if they are absent, although possibly at reduced rates. This design problem becomes simple if all the users in the system can be informed about the situation of the helpers before transmission begins. We study models in which, at least for part of the users, this information is not available before transmission. In general, this set of problems can be viewed as channel coding counterparts of well known problems in source coding, like multiple descriptions , successive refinement , and rate-distortion when side information may be absent . We focus on two channel models - the physically degraded broadcast channel (BC) with conferencing decoders, and the multiple access channel (MAC) with cribbing encoders. The BC with conferencing decoders was first studied by Dabora and Servetto , , and independently by Liang and Veeravalli , , who studied also the more general setting of relay-broadcast channels (RBC). In the model of Dabora and Servetto, a two-users BC is considered, where the decoders can exchange information via noiseless communication links of limited capacities $C_{1,2}$ and $C_{2,1}$. When the broadcast channel is physically degraded, information sent from the weaker (degraded) user to the stronger is redundant, and only the capacity of the link from the stronger user to the weaker (say $C_{1,2}$) increases the communication rates. For this case, Dabora and Servetto characterized the capacity region. Their result coincides with the results of Liang and Veeravalli when the relay link of is replaced with a constant rate bit pipe.

The MAC with cribbing encoders was introduced by Willems and Van Der Meulen in . Here there is no dedicated communication link that can be used explicitly for cooperation. Instead, one of the encoders can crib, or listen, to the channel input of the other user. This model describes a situation in which users in a cellular system are located physically close to each other, enabling part of them to listen to the transmission of the others with high reliability - i.e., the channel between the transmitters that are located in close vicinity is almost noiseless. Willems and Van Der Meulen considered in all consistent scenarios of cribbing (strictly causal, causal, non-causal, and symmetric or asymmetric), and characterized the capacity region of these models. Another relevant recent work is , where the MAC with partial cribbing encoders was considered, motivated by the additive noise Gaussian MAC model, where perfect cribbing means full cooperation between the encoders and requires an infinite entropy link. Finally, we mention , which considers the MAC channel with state and cribbing encoders. Accordingly, the state can be specialized to capture the availability of the cribbing links, which would lead to a setup similar to the one considered in our paper. Nonetheless, different from our paper, this state information is assumed to be causally known at the cribbed encoder and not to the cribbing encoder.

In the next sections, we propose and study extensions of the two models described above, when the cooperation links ($C_{1,2}$ of the physically degraded BC, and the cribbing link of the MAC) may or may not be present. For the MAC models, we first propose achievable rate regions which are based on the combination of superposition coding and block-Markov coding. Here, we consider the unreliable strictly causal, causal, and non-causal cribbing. Then, we propose a general outer bound, which is tight for some interesting special case where a constraint on the rates of the users is added. For the physically degraded BC, the results are conclusive. The results derived here were partially presented in .

It should be noted that multi-user communication systems with uncertainty in part of the network links have been studied in the literature - see, e.g., and , and references therein. The models suggested here, of the BC and MAC with uncertainty in the cooperation links, have not been studied before.

The outline of the rest of the paper is as follows. In Section II, we establish our notation. The physically degraded BC with unreliably cooperating decoders is presented and sutdied in Section III. In Section IV, we consider the MAC with cribbing encoders where the cribbing link may be absent. The proofs are provided in Section V.

II Notation Conventions

We use $H(\cdot)$ to denote the entropy of a discrete random variable (RV), and $I(\cdot;\cdot)$ to denote the mutual information between two discrete RVs. Calligraphic letters denote (discrete and finite) sets, e.g., ${\cal X}$, the complement of ${\cal X}$ is denoted by ${\cal X}^{c}$, while $\left|{\cal X}\right|$ stands for its cardinality. The $n$-fold Cartesian product of ${\cal X}$ is denoted by ${\cal X}^{n}$. An element of ${\cal X}^{n}$ is denoted by $x^{n}=(x_{1},x_{2},\ldots,x_{n})$; whenever the dimension $n$ is clear from the context, vectors (or sequences) are denoted by boldface letters, e.g., $x$. We denote RVs with capital letters-$X$, etc. We denote by $T_{\epsilon}^{n}(X)$ the weakly typical set for the (possibly vector) RV $X$, see for the definition of this set. Finally, we denote the probability distribution of the RV $X$ over ${\cal X}$ with $P_{X}$ and the conditional distribution of $Y$ given $X$ with $P_{Y|X}$.

III The Physically Degraded Broadcast Channel with Cooperating Decoders

Let ${\cal X}$, ${\cal Y}_{1}$, ${\cal Y}_{2}$ be finite sets. A broadcast channel (BC) $({\cal X},{\cal Y}_{1},{\cal Y}_{2},P_{Y_{1},Y_{2}|X})$ is a channel with input alphabet ${\cal X}$, two output alphabets ${\cal Y}_{1}$ and ${\cal Y}_{2}$, and a transition probability $P_{Y_{1},Y_{2}|X}$ from ${\cal X}$ to ${\cal Y}_{1}\times{\cal Y}_{2}$. The BC is said to be physically degraded if for any input distribution $P_{X}$, the Markov chain X\mbox{-\circ\hskip 2.84526pt}Y_{1}\mbox{-\circ\hskip 2.84526pt}Y_{2} holds, i.e.,

We will refer to $Y_{1}$ (resp. $Y_{2}$) as the stronger (resp. weaker, or degraded) user. We assume throughout that the channel is memoryless and that no feedback is present, implying that the transition probability of $n$-sequences is given by

Fix the transmission length, $n$, and an integer $\nu_{1,2}$. Let ${\cal N}_{1,2}=\left\{1,2,\ldots,\nu_{1,2}\right\}$ be the index set of the conference message. Denote the sets of messages by ${\cal N}_{k}=\left\{1,2,\ldots,\nu_{k}\right\}$, $k=1,2$, and ${\cal N}^{\prime}_{2}=\left\{1,2,\ldots,\nu^{\prime}_{2}\right\}$ where $\nu_{1}$, $\nu_{2}$ and $\nu^{\prime}_{2}$ are integers. A code for the BC with unreliable conference link, that may or may not be present, operates as follows. Three messages $M_{1}$, $M_{2}$, and $M^{\prime}_{2}$ are drawn uniformly and independently from the sets ${\cal N}_{1}$, ${\cal N}_{2}$, and ${\cal N}^{\prime}_{2}$, respectively. The encoder maps this triplet to a channel input sequence, {\mbox{\boldmathx}}(M_{1},M_{2},M^{\prime}_{2}). At the channel output, Decoder $k$ has the output sequence $Y^{n}_{k}$, $k=1,2$, at hand. Decoder 1 (resp. Decoder 2) is required to decode the message $M_{1}$ (resp. $M_{2}$), whether or not the conference link is present. If the conference link is present, Decoder 1 sends a message $c\in{\cal N}_{1,2}$ to Decoder 2, based on the output sequence $Y_{1}^{n}$. I.e., $c=c(Y_{1}^{n})$. Finally, Decoder 2 decodes $M_{2}^{\prime}$ based on his output $Y_{2}^{n}$ and the conference message $c(Y_{1}^{n})$. The setting of the problem is depicted in Fig. 1.

Observe that only Decoder 2 benefits when the conference link is present. Indeed, since there is only a link from Decoder 1 to Decoder 2, whatever Decoder 1 can do with the link, he can also do without it. Therefore the rate to User 1 is independent of whether the link is present or not. Only User 2 can benefit from its existence, and thus there are two sets of messages intended to User 2 - ${\cal N}_{2}$ and ${\cal N}_{2}^{\prime}$.

In the following, we give a more formal description of the above described structure.

An $(n,\nu_{1},\nu_{2},\nu_{2}^{\prime},\nu_{1,2},\epsilon)$ code for the BC $P_{Y_{1},Y_{2}|X}$ with an unreliable conference link is an encoder mapping

such that the average probabilities of error $P_{e}$ and $P_{e}^{\prime}$ do not exceed $\epsilon$. Here,

where the sets $S_{e}$ and $S^{\prime}_{e}$ are defined as

and for notational convenience, the dependence of $S_{e}$ and $S^{\prime}_{e}$ on the messages is dropped in (4).

The conference rate $C_{1,2}$ and the communications rates $(R_{1},R_{2},R_{2}^{\prime})$ are defined as usual:

The interpretation of the rates is as follows: $C_{1,2}$ is the conference rate in case that it is present. The rate $R_{k}$ is intended to User $k$, $k=1,2$, to be decoded whether or not the conference is present. The rate $R_{2}^{\prime}$ is intended to User 2 and is the extra rate gained if the conference link is present.

A rate quadruple $(R_{1},R_{2},R^{\prime}_{2},C_{1,2})$ is said to be achievable with unreliable conference if for any $\epsilon>0$, $\gamma>0$, and sufficiently large $n$ there exists an $(n,e^{n(R_{1}-\gamma)},e^{n(R_{2}-\gamma)},e^{n(R_{2}^{\prime}-\gamma)},e^{n(C_{1,2}+\gamma)},\epsilon)$ code for the BC with unreliable conference link. The capacity region is the closure of the set of all achievable quadruples $(R_{1},R_{2},R^{\prime}_{2},C_{1,2})$ and is denoted by ${\cal C}$. For a given conference rate $C_{1,2}$, ${\cal C}(C_{1,2})$ stands for the section of ${\cal C}$ at $C_{1,2}$. Our interest is to characterize ${\cal C}(C_{1,2})$.

Let ${\cal R}(C_{1,2})$ be the convex hull of all rate triples $(R_{1},R_{2},R_{2}^{\prime})$ satisfying:

Our main result on the physical degraded BC with unreliable conference is the following

For any physically degraded BC with unreliable conference of rate $C_{1,2}$,

The proof is given in Section V. Given the last result, we make the following observations:

The direct part in the proof of Theorem 1 is based on a combination of superposition coding and binning. The intuitive explanation/interpretation of the various auxiliary random variables in (6) is as follows. First, the information of User 2 is encoded with $U$, which depends on the message $M_{2}$. This information is always decoded by both decoders, whether the conference link is present or not. The extra message of User 2, which is $M_{2}^{\prime}$ is encoded with $V$, which is superimposed on top of $U$. Finally, the message of User 1, namely $M_{1}$ is encoded with $X$, which is again superimposed on top of $U$ and $V$. The information encoded with $U$, $V$, and $X$, are always decoded by the first decoder, whether the conference link is present or not. The extra information encoded with $V$, however, is decoded (with the help of the conference link) by the second decoder only if the conference link is present. This is done by using the binning approach.

Let us examine the region ${\cal R}(C_{1,2})$ when $C_{1,2}=0$, that is, the case where even if the conference link is present, its rate is 0, and there is no benefit from the conference link. Due to (6d) the Markov condition (U,V)\mbox{-\circ\hskip 2.84526pt}Y_{1}\mbox{-\circ\hskip 2.84526pt}Y_{2} holds, implying, of course, also that V\mbox{-\circ\hskip 2.84526pt}(U,Y_{1})\mbox{-\circ\hskip 2.84526pt}Y_{2} holds. Therefore, when $C_{1,2}=0$, it is readily seen that the bounds in (6) reduce to

The total rate to User 2 is $R_{2}+R_{2}^{\prime}$. Now, it is easy to verify that after optimization over $(U,V)$, the rates guaranteed by (7) coincide with the capacity region of the degraded BC, as one should expect. Indeed, we have:

Another case of interest is when $R_{2}=0$. Here, User 2 will not get any rate if the conference link is absent. Choosing $U$ to be a null RV, the region of rates $(R_{1},R_{2}^{\prime})$ guaranteed by (6) reduces to

which coincides with the result in [3, Theorem 1].

It is interesting to check what happens in case that the rate to User 2 is smaller than the capacity of the cooperation link, namely, $R_{2}^{\prime}\leq C_{1,2}$. When the cooperation link is reliable (i.e., always available), which is the model considered in [3, Theorem 1], it can be shown that the capacity region is the convex hull of all rate pairs $(R_{1},R_{2}^{\prime})$ such that

for some joint distribution $P_{X,Y_{1}}=P_{X}P_{Y_{1}|X}$. This result is indeed reasonable due to the fact that in this case User 1 can transmit all the information through the cooperation link. To show (10), first note that the intersection between (9) and $R_{2}^{\prime}\leq C_{1,2}$ gives

for some joint distribution $P_{V,X,Y_{1}}=P_{V}P_{X|V}P_{Y_{1}|X}$. Let $\mathscr{A}$ and $\mathscr{B}$ denote the regions in (10) and (11), respectively. Then, it is evident that $\mathscr{B}\subseteq\mathscr{A}$ due to the Markov chain V\mbox{-\circ\hskip 2.84526pt}X\mbox{-\circ\hskip 2.84526pt}Y_{1}. We now proceed to show the reverse inclusion, i.e., $\mathscr{A}\subseteq\mathscr{B}$. To this end, let $(R_{1},R_{2}^{\prime})\in\mathscr{A}$, achieved by some $X$. We consider two cases: if $R_{1}=I(X;Y_{1})$, then by using (10a), we get $R_{2}^{\prime}=0$. However, from (11a) we see that $R_{1}=I(X;Y_{1})$ if and only if $V=\emptyset$, from which we also get that $R_{2}^{\prime}=0$. Thus, $(R_{1},R_{2}^{\prime})\in\mathscr{B}$. If, however, $R_{1}<I(X;Y_{1})$, then let $R_{1}=I(X;Y_{1})-\alpha$, for $\alpha>0$. We define

for some $\beta\in\left[0,1\right)$. Obviously, we have the Markov chain V\mbox{-\circ\hskip 2.84526pt}X\mbox{-\circ\hskip 2.84526pt}Y_{1}, and it is easy to see that

Now, since $\beta$ is arbitrary, we can choose as

Combining (10b), (15), and (16), we have that $(R_{1},R_{2})$ satisfy

for V\mbox{-\circ\hskip 2.84526pt}X\mbox{-\circ\hskip 2.84526pt}Y_{1}, which implies that $(R_{1},R_{2}^{\prime})\in\mathscr{B}$.

When the cooperation link is unreliable, however, using the same arguments as above, it can be shown that the capacity region when $R_{2}^{\prime}\leq C_{1,2}$ is the convex hull of all rate triples $(R_{1},R_{2},R_{2}^{\prime})$ that satisfy

for some distribution $P_{U,X,Y_{1},Y_{2}}=P_{U}P_{X|U}P_{Y_{1},Y_{2}|X}$. This result makes sense because of the fact that when the cooperation link is absent, we still would like to transmit some information to the User 2, which is captured by $U$.

To illustrate the general result in Theorem 1, we consider the following simple example.

Consider the example where the channel output $Y_{1}$ is clean, namely, $Y_{1}=X\in\left\{0,1\right\}$, and $Y_{2}$ is the output of a binary symmetric channel, i.e., $Y_{2}=X\oplus Z$, where $Z$ is Bernoulli with $\Pr\left\{Z=0\right\}=p$ and statistically independent of $X$. In this case, we obtain from Theorem 1 that the capacity region is:

Fig. 2 depicts the capacity region in (19), assuming that $C_{1,2}=0.5$, for several values of $R_{2}$. We present four curves corresponding to the capacity region of the standard BC without cooperation (black curve), the rates $(R_{1},R_{2})$ which refer to the case where (unreliable) conferencing/cooperation is absent (blue dashed curve), the rates $(R_{1},R_{2}+R_{2}^{\prime})$ which refer to the case where (unreliable) conferencing/cooperation is present (red doted curve), and the capacity region in case of reliable/perfect cooperation (green dashed-doted curve), i.e., regular cooperation with reliable link. It can be seen that (total) higher rates can be achieved in case of unreliable cooperation compared to the case where there is no cooperation at all, as expected. Also, comparing the $(R_{1},R_{2}+R_{2}^{\prime})$ curve and the reliable cooperation curve, it can be noticed that there is some degradation due to the fact that the cooperation link is unreliable. Finally, from the $(R_{1},R_{2})$ and the standard BC curves it can be seen that the there is some price in terms of the rate $R_{2}$ (namely, when there is no cooperation) due to the universality of the coding scheme in case of unreliable cribbing.

IV The Multiple Access Channel with Cribbing Encoders

A multiple access channel (MAC) is a quadruple $({\cal X}_{1},{\cal X}_{2},{\cal Y},P_{Y|X_{1},X_{2}})$, where ${\cal X}_{k}$ is the input alphabet of User $k$, $k=1,2$, ${\cal Y}$ is the output alphabet, and $P_{Y|X_{1},X_{2}}$ is the transition probability matrix from ${\cal X}_{1}\times{\cal X}_{2}$ to ${\cal Y}$. The channel is memoryless without feedback.

In this section we present achievable rates for the MAC with an unreliable cribbing - that may or may not be present - from Encoder 1 to Encoder 2. The basic assumptions are as follows. Since Encoder 2 listens to Encoder 1, he knows whether the cribbing link is present. Similarly, the decoder knows it since Encoder 2 can convey to him this message, as it is only one bit of information to transmit. Encoder 1, on the other hand, does not know whether the cribbing link is present, since he cannot be informed about it. He is only aware that cribbing could occur. Let ${\cal N}_{1}^{\prime}=\left\{1,2,\ldots,\nu_{1}^{\prime}\right\}$ and ${\cal N}_{2}^{\prime\prime}=\left\{1,2,\ldots,\nu_{2}^{\prime\prime}\right\}$ be two message sets. A coding scheme operates as follows. Four messages $M_{1}$, $M_{1}^{\prime}$, $M_{2}$, and $M_{2}^{\prime\prime}$ are drawn uniformly and independently from the sets ${\cal N}_{1}$, ${\cal N}_{1}^{\prime}$, ${\cal N}_{2}$, ${\cal N}_{2}^{\prime\prime}$, respectively. Encoder 1 maps the pair $(M_{1},M_{1}^{\prime})$ to an input sequence \mbox{\boldmathx}_{1}=\mbox{\boldmathx}_{1}(M_{1},M_{1}^{\prime}). If the cribbing link is absent, Encoder 2 maps the message $M_{2}$ to to an input sequence \mbox{\boldmathx}_{2}=\mbox{\boldmathx}_{2}(M_{2}). If the cribbing link is present, Encoder 2 knows \mbox{\boldmathx}_{1} strictly causally, thus maps the pair (M_{2}^{\prime\prime},\mbox{\boldmathx}_{1}) to an input sequence \mbox{\boldmathx_{2}}^{\prime\prime}, in a strictly causal manner:

At the output, the decoder decodes $(M_{1},M_{2})$ if cribbing is absent, and $(M_{1},M_{1}^{\prime},M_{2}^{\prime\prime})$ if cribbing is present.

Note that there is a slight difference in the interpretation of the message sets, compared to the message sets of the BC model studied in Section III. The pair $(M_{1},M_{1}^{\prime})$ is encoded by User 1, where $M_{1}$ is always decoded, and $M_{1}^{\prime}$ is decoded only if cribbing is present. For User 2, if cribbing is absent, $M_{2}$ is encoded, whereas if cribbing is present, $M_{2}^{\prime\prime}$ is encoded. Therefore User 2 can reduce his rate in case of cribbing, in favor of increasing the rate of User 1. Due to this structure, the joint distribution of $M_{2}$ and $M_{2}^{\prime\prime}$ is immaterial, as they never appear together in the coding scheme. The setting of the problem is depicted in Fig. 3.

Following is a formal definition of the scheme described above.

An $(n,\nu_{1},\nu_{1}^{\prime},\nu_{2},\nu_{2}^{\prime\prime},\epsilon)$ code for the MAC $P_{Y|X_{1},X_{2}}$ with unreliable strictly causal cribbing link consist of $n+2$ encoding maps

such that the average probabilities of error $P_{e}$ and $P_{e}^{\prime}$ do not exceed $\epsilon$. Here

where \mbox{\boldmathf}_{2}^{\prime\prime}(m_{2}^{\prime\prime},f_{1}(m_{1},m_{1}^{\prime})) is the sequence of maps $f_{2,i}^{\prime\prime}$ in (21c), the sets ${\cal Q}_{e}$ and ${\cal Q}_{e}^{\prime}$ are defined as

and the dependence of the sets ${\cal Q}_{e}$, ${\cal Q}_{e}^{\prime}$ on the messages is dropped in (23), for notational convenience.

The rates $(R_{1},R_{1}^{\prime},R_{2},R_{2}^{\prime\prime})$, and achievability of a given quadruple, are defined as usual. The capacity region of the MAC with unreliable strictly causal cribbing is the closure of the collection of all achievable quadruples $(R_{1},R_{1}^{\prime},R_{2},R_{2}^{\prime\prime})$, and is denoted by ${\cal C}_{\text{mac}}^{\text{strict}}$. Our interest is in characterizing ${\cal C}_{\text{mac}}^{\text{strict}}$.

Let ${\cal U}$ and ${\cal V}$, be finite sets, and let ${\cal P}^{\text{strict}}$ be the collection of all joint distributions $P_{U,V,X_{1},X_{2},X_{2}^{\prime\prime},Y,Y^{\prime\prime}}$ of the form

where $P_{Y^{\prime\prime}|X_{1},X_{2}^{\prime\prime}}$ is our MAC with $X_{2}^{\prime\prime}$ at the input of Encoder 2. Let ${\cal I}^{\text{strict}}_{\text{mac}}$ be the convex hull of all rate quadruples $(R_{1},R_{1}^{\prime},R_{2},R_{2}^{\prime\prime})$ satisfying

for some $P_{U,V,X_{1},X_{2},X_{2}^{\prime\prime},Y,Y^{\prime\prime}}\in{\cal P}^{\text{strict}}$ where

We start with the following result, which is proved in Subsection V-B.

For any MAC with unreliable strictly causal cribbing

Next, consider the case where causal cribbing, for the second user, is allowed, that is,

The capacity ${\cal C}_{\text{mac}}$ of the MAC with unreliable causal cribbing is defined similarly to the strictly causal case, but with (29) and (30), replacing (20) and (21c), respectively.

Let ${\cal P}$ be the collection of all joint distributions $P_{V,X_{1},X_{2},X_{2}^{\prime\prime},Y,Y^{\prime\prime}}$ of the form

The interpretation of the coding random variables and their joint distribution is as follows. The pair $(V,X_{1})$ are the coding RVs of User 1. These are fixed, regardless of whether cribbing is present or not. The input $X_{2}$ is the coding variable of User 2 if cribbing is absent, therefore it is independent of $(V,X_{1})$, and $Y$ is the MAC output due to inputs $X_{1},X_{2}$. When cribbing is present, User 2 encodes with $X_{2}^{\prime\prime}$ which can depend on $X_{1}$. The output of the channel due to inputs $X_{1}$ and $X_{2}^{\prime\prime}$ is denoted by $Y^{\prime\prime}$.

Let ${\cal I}_{\text{mac}}$ be the convex hull of all rate quadruples $(R_{1},R_{1}^{\prime},R_{2},R_{2}^{\prime\prime})$ satisfying

for some $P_{V,X_{1},X_{2},X_{2}^{\prime\prime},Y,Y^{\prime\prime}}\in{\cal P}$ where

We have the following result, proved in Subsection V-C.

For any MAC with unreliable causal cribbing

We shall make several remarks on the above results.

The bounds on the cardinalities of $U$, and $V$, are derived in a similar manner as in [14, Appendix B], and is based on Fenchel-Eggleston-Carathéodry Theorem.

The proof of Theorem 2 is based on the combination of superposition coding and block-Markov coding. The transmission is always performed in $B$ sub-blocks, of length $n$ each. In each sub-block, the messages of User 1 are encoded in two layers. First, the “resolution” information of User 1 is encoded with $U$, which depend on both messages $M_{1}$ and $M_{1}^{\prime}$. Then, the fresh information of message $M_{1}$ is encoded with $V$, and finally, the fresh information of $M_{1}^{\prime}$ is encoded with $X_{1}$, using superposition coding around the cloud centers $V$ and $U$. If the cribbing link is absent, Encoder 2 encodes his messages independently of Encoder 1. The decoder can then decode only the messages of $V$, that is, $M_{1}$, and $X_{2}$. If the cribbing link is present, block Markov coding is employed, similarly to the scheme used in for one sided causal cribbing. In this case, the decoder decodes the messages of $V$, $U$, $X_{1}$, and $X_{2}^{\prime\prime}$. Finally, to prove Theorem 3 we employ Shannon strategies.

Note that the main important observation in the achievability, is that User 1 must employ a universal encoding scheme, in the sense of being independent of the cribbing. User 2 and the decoder, however, can employ different encoding and decoding schemes, in accordance to existence or absence of the cribbing.

When cribbing is absent, the rates $R_{1}^{\prime}$ and $R^{\prime\prime}_{2}$ are not decoded. Thus, setting $V=X_{1}$ in the region ${\cal I}_{\text{mac}}$ yields the capacity region of the MAC without cribbing, as expected.

The r.h.s. of (26e) is smaller than that of (32e). Indeed,

where the inequality follows from the fact that conditioning reduce entropy, and the Markov chain (U,V)\mbox{-\circ\hskip 2.84526pt}(X_{1},X_{2}^{\prime\prime})\mbox{-\circ\hskip 2.84526pt}Y^{\prime\prime}.

Unfortunately, we were not able to show the converse part in general, but only for some special case, described in the sequel. In the following, we provide first an outer bound to the capacity region, assuming unreliable causal cribbing. Let ${\cal I}_{\text{mac}}^{O}$ be the convex hull of all rate quadruples $(R_{1},R_{1}^{\prime},R_{2},R_{2}^{\prime\prime})$ satisfying

for some $P_{V,X_{1},X_{2},X_{2}^{\prime\prime},Y,Y^{\prime\prime}}\in{\cal P}^{O}$ of the form

The forthcoming result is true also for the non-causal cribbing case, namely,

The following is proved in Subsection V-D.

For any MAC with unreliable causal (non-causal) cribbing

Next, we consider a case in which we were able to derive the capacity region.

Assume that $R_{1}^{\prime}=0$, which means that there is no extra rate sent by User 1 to be decoded when cribbing is present. In this case, the first user is fully decoded no matter whether cribbing is present or not. Then, according to Theorem 3, it is easy to verify that an achievable region is given by:

for some $P_{V,X_{1},X_{2},X_{2}^{\prime\prime},Y,Y^{\prime\prime}}\in{\cal P}$ of the form

Let ${\hat{\cal I}}_{\text{mac}}^{I}$ be the convex hull of all rate triples $(R_{1},R_{2},R_{2}^{\prime\prime})$ satisfying (39) and (40). Next, let ${\hat{\cal I}}_{\text{mac}}^{O}$ be the convex hull of all rate triples $(R_{1},R_{2},R_{2}^{\prime\prime})$ satisfying:

for some $P_{V,X_{1},X_{2},X_{2}^{\prime\prime},Y,Y^{\prime\prime}}\in{\cal P}^{O}$ in (36). It is easy to see that ${\hat{\cal I}}_{\text{mac}}^{O}$ is obtained upon substitution of $R_{1}^{\prime}=0$ in (35), and thus according to Theorem 4, it is an outer bound on (39). In this stage, one may realize that for $R_{1}^{\prime}=0$, the auxiliary RV $V$ should be superfluous, and we can actually substitute $X_{1}$ instead. This is indeed reasonable due to the fact that $V$ is used to convey the message $M_{1}$, and the extra messages from the first user, that is $M_{1}^{\prime}$, is encoded by $X_{1}$. Accordingly, let ${{\hat{{\cal I}}}}_{\text{mac}}$ be the convex hull of all rate triples $(R_{1},R_{2},R_{2}^{\prime\prime})$ satisfying:

for some $P_{X_{1},X_{2},X_{2}^{\prime\prime},Y,Y^{\prime\prime}}$ of the form

The subsequent lemma is proved in Appendix B.

Let ${\hat{\cal I}}_{\text{mac}}^{I}$, ${\hat{\cal I}}_{\text{mac}}^{O}$, and ${{\hat{{\cal I}}}}_{\text{mac}}$, be defined in (39), (41), and (42), respectively. Then,

Hence, using Lemma 1, we obtain the following result.

For any MAC with unreliable causal (non-causal) cribbing, if $R_{1}^{\prime}=0$, then ${{\hat{{\cal I}}}}_{\text{mac}}$ is the capacity region.

According to (42), if the first user is fully decoded no matter whether cribbing is present or not, then there is no bound on the individual rate of the first user when cribbing is present (we have only bounds on the rate of the second user (42d) and on the sum rate (42e)). Instead, as can be seen from (42d)-(42e), it is assumed that $X_{1}$ is already known to the receiver when cribbing is present. The reason is that since cribbing can only help in recovering $X_{1}$, the bound on the individual rate of the first user when cribbing is absent dominates (or, more strict).

An interesting conclusion arises from the region in (42)-(43). Note that (42a)-(42c), when evaluated over all product distributions $P_{X_{1}}P_{X_{2}}$ (as in (43)), coincides with the capacity region of the standard MAC, without cribbing. Therefore, for the case of $R_{1}^{\prime}=0$, there is no loss of performance when using a robust coding scheme, relative to the case of no cribbing at all. To illustrate the results in Theorems 3 and 5, and the above conclusion, we consider the following examples.

Consider the channel model depicted in Fig. 4, where the channel output is $Y=(Y_{1},Y_{2})$, $\rho_{0}\triangleq\Pr\left\{Y_{2}=1|X_{2}=0\right\}=\Pr\left\{Y_{2}=0|X_{2}=1\right\}$ and $\rho_{1}\triangleq\Pr\left\{Y_{2}=1|X_{2}=2\right\}=\Pr\left\{Y_{2}=0|X_{2}=3\right\}$. The crossover probabilities $\rho_{0}$ and $\rho_{1}$ depend on $X_{1}$ in the following way: if $X_{1}=0$, then $(\rho_{0},\rho_{1})=(0,1/2)$, and if $X_{1}=1$, then $(\rho_{0},\rho_{1})=(1/2,0)$. Accordingly, if cribbing is present, then User 2 can transmit his information via a noiseless channel. In this case, the total rate that User 2 can transmit is 1, which is the maximal possible rate for him since the output $Y_{2}$ is binary. When cribbing is absent, User 2 cannot know which of the channels is clean, and thus cannot transmit at the maximal rate 1. Let $P_{X_{1}}\triangleq\Pr\left\{X_{1}=0\right\}$, and $p_{i}\triangleq\Pr\left\{X_{2}=i\right\}$, for $i=0,1,2,3$. Using (42), it is a simple exercise to check that

where ${\cal H}_{2}\left(\cdot\right)$ is the binary entropy, and note that in this example the sum-rate constraints in (42c) and (42e), are redundant because they are given by the sum of the individual rate constraints. Also, note that the optimal distribution $P_{X_{2}^{\prime\prime}|X_{1}}$ in this case, is given by

Fig. 5 presents three curves corresponding to the capacity region of the standard MAC without cribbing (green “$+$” curve), the rates $(R_{1},R_{2})$ which refer to the case where cribbing is absent (blue doted curve), and the rates $(R_{1},R_{2}^{\prime\prime})$ which refer to the case where cribbing is present (red curve). Each value of $R_{1}$ is associated with two rates $R_{2}$ and $R_{2}^{\prime\prime}$. For example, if $R_{1}=0.7$ then $R_{2}\approx 0.8$, $R_{2}^{\prime\prime}=1$. It is evident that higher rates can be achieved for the second user due to the cribbing, as expected. Also, it can be seen that the $(R_{1},R_{2})$ curve coincide with the capacity region of the standard MAC without cribbing, as expected from (42). This means that the coding scheme for the case of unreliable cribbing is robust for the case of $R_{1}^{\prime}=0$. That is, when $R_{1}^{\prime}=0$, the uncertainty about the cribbing link does not have negative influence on the performance compared to the case of no cribbing at all. Finally, we mention that in this example, the capacity region in case of reliable cribbing coincides with the $(R_{1},R_{2}^{\prime\prime})$ curve.

Consider the model in the previous example, but now $Y_{1}=X_{1}\oplus Z$, where $Z$ is a Bernoulli RV, independent of $X_{1}$, and $\Pr\left\{Z=0\right\}=q$. The capacity region in this case is given in Appendix C (see (C.13)). Fig. 6 presents four curves corresponding to the capacity region of the standard MAC without cribbing (green “$+$” curve), the rates $(R_{1},R_{2})$ (blue doted curve), the rates $(R_{1},R_{2}^{\prime\prime})$ (red curve), and the capacity region in case of reliable cribbing (black dashed curve). In the simulations we choose $q=0.1$. As before, higher rates can be achieved for the second user due to the cribbing, as expected, and it can be seen that the $(R_{1},R_{2})$ curve coincide with the capacity region of the standard MAC. Finally, contrary to the previous example, here, there is some degradation compared to the reliable cribbing case.

Consider the example where the channel output, $Y$, is given by:

where $X_{1},X_{2},Z_{1}$, and $Z_{2}$, are binary RVs, where $Z_{1}$ is Bernoulli with $\Pr\left\{Z_{1}=0\right\}=p_{1}$, $Z_{2}=0$ if $X_{1}=0$, and it is Bernoulli with $\Pr\left\{Z_{2}=0\right\}=p_{2}$, otherwise (i.e., if $X_{1}=1$). Here, $X_{1},X_{2},Z_{1}$ and $Z_{2}$, are independent. When cribbing is present, the channel output, $Y^{\prime\prime}$, is given by:

where now $X_{2}^{\prime\prime}$ may depend on $X_{1}$. Let $\Pr\left\{X_{i}=0\right\}\triangleq P_{X_{i}}$, for $i=1,2$, $\Pr\left\{X_{2}^{\prime\prime}=0|X_{1}=0\right\}=\mu_{1}$, and $\Pr\left\{X_{2}^{\prime\prime}=0|X_{1}=1\right\}=\mu_{2}$. Also, for two real numbers $0\leq a,b\leq 1$, define $a\ast b\triangleq a\cdot\bar{b}+\bar{a}\cdot b$, and $a\star b\triangleq a\cdot b+\bar{a}\cdot\bar{b}$, where $\bar{a}\triangleq 1-a$. Finally, let:

We wish to evaluate the region in (32) where $R_{1}^{\prime}$ may be positive. To this end, we choose the auxiliary RV $V$ to be:

which may be sub-optimal. We define the following quantities:

Then, using the above definitions, it is a simple exercise to check that (32) boils down to:

Fig. 7 depicts the achievable region in (54) for the case where $p_{1}=0.01$ and $p_{2}=0.4$. Since (54) is parametrized by four rates, it is convenient to fix the rate $R_{1}^{\prime}$ on some value, which was chosen in our calculations to be $R_{1}^{\prime}=0.3$. We present five curves corresponding to the capacity region of the standard MAC without cribbing (blue “$+$” curve), the rates $(R_{1},R_{2})$ (green curve), the rates $(R_{1},R_{2}^{\prime\prime})$ (red dashed-doted curve), the rates $(R_{1}+R_{1}^{\prime},R_{2}^{\prime\prime})$ which refer to the total rate of User 1 versus the rate of User 2 when cribbing is present (brown doted curve), and the capacity region in case of reliable cribbing (black dashed curve). Each value of $R_{1}$ is associated with two rates $R_{2}$ and $R_{2}^{\prime\prime}$. For example, if $R_{1}=0.1$ then $R_{2}\approx 0.75$, $R_{2}^{\prime\prime}\approx 0.56$, and $R_{1}^{\prime}=0.3$. This means that when cribbing is present User 2 reduces his rate $R_{2}^{\prime\prime}$ in favor of increasing the rate of User $1$. This conclusion is noticeable from the fact that the the $(R_{1},R_{2})$ curve is on top of the $(R_{1},R_{2}^{\prime\prime})$ curve for any $R_{1}$. Finally, the best results are obtained in the case of reliable cribbing, as expected, and accordingly there is some degradation due to the fact that the cribbing is unreliable.

V Proofs

In this subsection, we prove Theorem 1. The direct part uses random selection and strong typicality arguments.

Direct Part. We start with the code construction.

Codebook construction: Fix a joint distribution $P_{U,V,X}$.

Generate $e^{nR_{2}}$ codewords \mbox{\boldmathu}(j), $j=1,2,\ldots e^{nR_{2}}$, i.i.d., according to $P_{U}$.

For every \mbox{\boldmathu}(j), generate $e^{nR_{2}^{\prime}}$ codewords \mbox{\boldmathv}(k|j), $k=1,2,\ldots e^{nR_{2}^{\prime}}$, independently according to $\prod_{i=1}^{n}P_{V|U}(v_{i}|u_{i}(j))$.

For every $j$, distribute the $e^{nR_{2}^{\prime}}$ codewords \mbox{\boldmathv}(k|j), $k=1,2,\ldots,e^{nR_{2}^{\prime}}$, into $e^{nC_{1,2}}$ bins, evenly and independently of each other. Thus, in every bin there are $e^{n(R_{2}^{\prime}-C_{1,2})}$ codewords \mbox{\boldmathv}(k|j) with a fixed index $j$. Denote by $b(k|j)$ the bin number to which \mbox{\boldmathv}(k|j) belongs. Note that

For every pair (\mbox{\boldmathu}(j),\mbox{\boldmathv}(k|j)), $j=1,2,\ldots,e^{nR_{2}}$, $k=1,2,\ldots,e^{nR_{2}^{\prime}}$, generate $e^{nR_{1}}$ vectors \mbox{\boldmathx}(l|j,k), $l=1,2,\ldots,e^{nR_{1}}$, independently of each other, according to $\prod_{i=1}^{n}P_{X|U,V}(x_{i}|u_{i}(j),v_{i}(k|j))$.

These codewords form the codebook, which is revealed to the encoder and the decoders.

Encoding: Given a triple $(j,k,l)$, where $j=1,2,\ldots,e^{nR_{2}}$, $k=1,2,\ldots,e^{nR_{2}^{\prime}}$, $l=1,2,\ldots,e^{nR_{1}}$, the encoder sends via the channel the codeword \mbox{\boldmathx}(l|j,k).

Decoding: We assume first that the conference link is absent. Decoder 2 has \mbox{\boldmathy}_{2} at hand. He looks for the unique index $\hat{j}$ in $\left\{1,2,\ldots,\exp(nR_{2})\right\}$ such that

If such $\hat{j}$ does not exist, or there is more than one such index, an error is declared. By classical results, if

the index $j$ is decoded correctly with high probability.

Decoder 1 has \mbox{\boldmathy}_{1} at hand. He looks for the unique index $\hat{\hat{j}}$ in $\left\{1,2,\ldots,\exp(nR_{2})\right\}$ such that

If such $\hat{\hat{j}}$ does not exist, or there is more than one such index, an error is declared. By classical results, if

Decoder 1 succeeds to decode correctly the index $j$ with high probability. Since the channel is degraded, if (56) holds, it implies (57). Next, Decoder 1 looks for the unique index $\hat{\hat{k}}$ in $\left\{1,2,\ldots,\exp(nR_{2}^{\prime})\right\}$ such that

If such $\hat{\hat{k}}$ does not exist, or there is more than one such, an error is declared. By classical results, the index $k\in\left\{1,2,\ldots,\exp(nR_{2}^{\prime})\right\}$ is decoded correctly with high probability if

Having the pair $(\hat{\hat{j}},\hat{\hat{k}})$ at hand, Decoder 1 looks for the unique index $\hat{\hat{l}}\in\left\{1,2,\ldots,\exp(nR_{1})\right\}$ satisfying

By classical results, this step succeeds if the rate $R_{1}$ satisfies

This concludes the decoding process when the conference link is absent. By (56), (59) and (61), the conditions for correct decoding when there is no conferencing are

Observe that, although the rate $R_{2}^{\prime}$ is decoded by Decoder 1 (if (62b) is satisfied), it does not arrive to User 2, since the conferencing link is absent. The bound (62b) is still needed in order to guarantee that Decoder 1 can proceed and decode the index $l$ (the message intended to him).

We turn now to the case where the conference link is present. Decoder 1 operates exactly as in the case of no conference, and decodes the indices $\hat{\hat{j}}$, $\hat{\hat{k}}$, and $\hat{\hat{l}}$. If (62) hold, these steps succeed with high probability. He then sends $b(\hat{\hat{k}}|\hat{\hat{j}})$, the index of the bin to which \mbox{\boldmathv}(\hat{\hat{k}}|\hat{\hat{j}}) belongs, via the conference link. Due to (55), the link capacity suffices, and Decoder 2 receives $b(\hat{\hat{k}}|\hat{\hat{j}})$ without an error.

Decoder 2 decodes the index $\hat{j}$ as in the case of no conference. After receiving from Decoder 1 the bin index $b(\hat{\hat{k}}|\hat{\hat{j}})$, he looks in this bin for the unique index $\hat{k}$ such that

If such an index does not exist, or there is more than one such, an error is declared. From the code construction, every bin contains approximately $e^{n(R_{2}^{\prime}-C_{1,2})}$ codewords $v$. Assuming that the previous decoding steps were successful (i.e., $\hat{\hat{j}}$, $\hat{\hat{k}}$, $\hat{j}$ are the correct indices for $j$, $k$, and $j$, respectively), by classical results $\hat{k}$ is correct with high probability if

The region defined by (62) and (64) coincides with ${\cal R}(C_{1,2})$. This concludes the proof of the achievability part.

Converse Part. We start with a sequence of codes $(n,e^{nR_{1}},e^{nR_{2}},e^{nR_{2}^{\prime}},e^{nC_{1,2}},\epsilon_{n})$ with increasing blocklength $n$, satisfying $\lim_{n\rightarrow\infty}\epsilon_{n}=0$. We denote by $M_{k}$ the random message from ${\cal N}_{k}$, $k=1,2$, and by $M_{2}^{\prime}$ the message from ${\cal N}_{2}^{\prime}$. The conference message is denoted by $M_{1,2}$. By Fano’s inequality we can bound the rate $R_{2}$ as

where $\lim_{n\rightarrow\infty}\delta_{n}=0$, due to $\lim_{n\rightarrow\infty}\epsilon_{n}=0$, and (a) follows from the chain rule. We now bound the rate $R_{2}^{\prime}$ as follows. If the conference link is present, then the messages $M_{2}^{\prime}$ can be decoded by Decoder 2 based on $Y_{2}^{n}$ and the message transmitted via the conference link, $M_{1,2}$. Therefore

Moreover, the message $M^{\prime}_{2}$ can be decoded by Decoder 1, regardless of the conference link. Hence:

where $(a)$ is true because the channel is physically degraded. The rate $R_{1}$ can be bounded by

where $(a)$ is true since the channel is physically degraded. Equality $(b)$ holds since $X_{i}$ is a deterministic function of the messages $M_{1}$, $M_{2}$, and $M_{2}^{\prime}$, and since $Y_{1,i}$ is independent of $(M_{2},M_{2}^{\prime},Y_{2}^{i-1},Y_{1}^{i-1},M_{1})$ when conditioned on $X_{i}$. Defining $U_{i}\triangleq(M_{2},Y_{2}^{i-1})$ and $V_{i}\triangleq(M_{2}^{\prime},Y_{1}^{i-1})$, which due to (2) satisfy the Markov chain (U_{i},V_{i})\mbox{-\circ\hskip 2.84526pt}X_{i}\mbox{-\circ\hskip 2.84526pt}(Y_{1,i},Y_{1,i}), and using the fact that

we obtain from (66), (V-A), (68), and (69) the bounds

Using the standard time-sharing argument as in [22, Ch. 14.3], one can rewrite (71) by introducing an appropriate time-sharing random variable. Therefore, if $\epsilon_{n}\to 0$ as $n\to\infty$, the convex hull of this region can be shown to be equivalent to the convex hull of the region in (6).

Finally, the bounds on the cardinalities of $U$ and $V$ follow from Fenchel-Eggleston-Carathéodry Theorem, similarly as used for the 3-receiver degraded BC [21, Appendix C]. ∎

V-B Proof of Theorem 2

The proof of Theorem 2 is based on the combination of superposition coding and block-Markov coding. The transmission is always performed in $B$ sub-blocks, of length $n$ each. In each sub-block, the messages of User 1 are encoded in two layers. First, the “resolution” information of User 1 are encoded with $U$, which depend on both messages $M_{1}$ and $M_{1}^{\prime}$. Then, the fresh information of message $M_{1}$ is encoded with $V$, and finally, the fresh information of $M_{1}^{\prime}$ is encoded with $X_{1}$, using superposition coding around the cloud centers $V$ and $U$. If the cribbing link is absent, Encoder 2 encodes his messages independently of Encoder 1. The decoder can then decode only the messages of $V$, that is, $M_{1}$, and $X_{2}$. If the cribbing link is present, block Markov coding is employed, similarly to the scheme used in for one sided causal cribbing.

It is important to emphasize that User 1 must employ a universal encoding scheme, in the sense of being independent of the cribbing. User 2 and the decoder, however, can employ different encoding and decoding schemes, in accordance to existence or absence of the cribbing. Accordingly, in the sequel, we describe the encoding scheme for the first user separately.

We use a random coding argument to demonstrate the achievability part. The messages $M_{1,b}\in\left\{1,2,\ldots,\exp(nR_{1})\right\}$ and $M^{\prime}_{1,b}\in\left\{1,2,\ldots,\exp(nR_{1}^{\prime})\right\}$, for $b=1,2,\ldots,B-1$, which are uniformly distributed and independent of each other, will be sent over the MAC in $B$ blocks, each of $n$ transmissions. Note that if $B\to\infty$, the overall rates are $R_{1}(B-1)/B\to R_{1}$ and $R_{1}^{\prime}(B-1)/B\to R_{1}^{\prime}$. In each of the $B$ blocks the same codebook is used, and is constructed, for the first user, as follows.

Codebook construction for User 1: Fix a joint distribution $P_{U}P_{V}P_{X_{1}|U,V}$, and a sufficiently small $\epsilon>0$.

Generate $e^{n(R_{1}+R_{1})}$ codewords $v$, i.i.d., according to $P_{V}$. Label them \mbox{\boldmathv}(m_{0},m_{1}), for $m_{0},m_{1}\in\left\{1,2,\ldots,\exp(nR_{1})\right\}$.

Generate $e^{n(R_{1}+R_{1}^{\prime})}$ codewords $u$, independently according to $P_{U}$. Label them \mbox{\boldmathu}(m_{0},m_{0}^{\prime}), for $m_{0}\in\left\{1,2,\ldots,\exp(nR_{1})\right\}$ and $m_{0}^{\prime}\in\left\{1,2,\ldots,\exp(nR_{1}^{\prime})\right\}$.

For every \mbox{\boldmathv}(m_{0},m_{1}) and \mbox{\boldmathu}(m_{0},m_{0}^{\prime}), generate $e^{nR_{1}^{\prime}}$ codewords \mbox{\boldmathx}_{1}, independently according to $\prod_{i=1}^{n}P_{X_{1}|U,V}(x_{1,i}|u_{i}(m_{0},m_{0}^{\prime}),v_{i}(m_{0},m_{1}))$. Label them \mbox{\boldmathx}_{1}(m_{1}^{\prime},\mbox{\boldmathu}(m_{0},m_{0}^{\prime}),\mbox{\boldmathv}(m_{0},m_{1})), for $m_{1}^{\prime}\in\left\{1,2,\ldots,\exp(nR_{1}^{\prime})\right\}$.

We now present the achievability scheme for the case where cribbing is absent.

1) Cribbing is absent: The message $M_{2,b}\in\left\{1,2,\ldots,\exp(nR_{2})\right\}$, for $b=1,2,\ldots,B-1$, is uniformly distributed, independent of the messages of the first user, and will be sent over the MAC in $B$ blocks, each of $n$ transmissions. If $B\to\infty$, the overall rate is $R_{2}(B-1)/B\to R_{2}$. In each of the $B$ blocks the same codebook is used, and is constructed, for the second user, as follows.

Codebook construction for User 2: Fix a distribution $P_{X_{2}}$, and a sufficiently small $\epsilon>0$. Generate $e^{nR_{2}}$ codewords \mbox{\boldmathx}_{2}, i.i.d., according to $P_{X_{2}}$. Label them \mbox{\boldmathx}_{2}(m_{2}), for $m_{2}\in\left\{1,2,\ldots,\exp(nR_{2})\right\}$.

The codewords of Users 1 and 2 form the codebook, which is revealed to the encoders and the decoder. The messages $m_{1,b}\in\left\{1,\ldots,\exp(nR_{1})\right\}$, $m^{\prime}_{1,b}\in\left\{1,\ldots,\exp(nR_{1}^{\prime})\right\}$, and $m_{2,b}\in\left\{1,\ldots,\exp(nR_{2})\right\}$, $b=1,\ldots,B-1$, are encoded in the following way.

Then, in block $b,\;b=2,3,\ldots,B$, the encoders send (73), shown at the top of the page.

Decoding: We employ simultaneous joint typicality decoding. At the end of the first block, the decoder looks for $(\hat{m}_{1,1},\hat{m}_{2,1})$ such that:

Next, assume that the decoder has correctly found $\hat{m}_{1,1}$. Then, to find the transmitted information at the end of the second block, the decoder looks for $(\hat{m}_{1,2},\hat{m}_{2,2})$ such that:

With the knowledge of $\hat{m}_{1,2}$ the information at the end of the third block can be decoded in a similar manner. In general, at the end of block $b$ the decoder looks for $(\hat{m}_{1,b},\hat{m}_{2,b})$ such that:

where $\hat{m}_{1,b-1}$ was decoded in the previous block.

Error Analysis: By classical results (e.g., standard MAC), there exists a sequence of codes with a probability of error that goes to zero as the block length goes to infinity, if:

This concludes the decoding process when the conference link is absent.

2) Cribbing is present: We turn now to the case where the cribbing link is present. The message $M^{\prime\prime}_{2,b}\in\left\{1,2,\ldots,\exp(nR_{2}^{\prime\prime})\right\}$, for $b=1,2,\ldots,B-1$, is uniformly distributed, independent of the messages of the first user, and will be sent over the MAC in $B$ blocks, each of $n$ transmissions. In each of the $B$ blocks the same codebook is used, and is constructed, for the second user, as follows.

Codebook construction for User 2: Fix a distribution $P_{X_{2}^{\prime\prime}|U}$, and a sufficiently small $\epsilon>0$. For every \mbox{\boldmathu}(m_{0},m_{0}^{\prime}), generate $e^{nR_{2}^{\prime\prime}}$ codewords \mbox{\boldmathx}^{\prime\prime}_{2}, independently according to $\prod_{i=1}^{n}P_{X_{2}^{\prime\prime}|U}(x_{2,i}|u_{i}(m_{0},m_{0}^{\prime}))$. Label them \mbox{\boldmathx}_{2}^{\prime\prime}(m_{2}^{\prime\prime},\mbox{\boldmathu}(m_{0},m_{0}^{\prime})), for $m_{2}^{\prime\prime}\in\left\{1,2,\ldots,\exp(nR_{2}^{\prime\prime})\right\}$. The codewords of Users 1 and 2 form the codebook, which is revealed to the encoders and the decoder.

Encoding: The messages $m_{1,b}\in\left\{1,\ldots,\exp(nR_{1})\right\}$, $m^{\prime}_{1,b}\in\left\{1,\ldots,\exp(nR_{1}^{\prime})\right\}$, and $m^{\prime\prime}_{2,b}\in\left\{1,\ldots,\exp(nR_{2}^{\prime\prime})\right\}$, $b=1,\ldots,B-1$, are encoded in the following way: In block 1, the encoders sendRecall that User 1 must employ the same encoding scheme as in the case of absent cribbing.:

Assume that as a result of cribbing from encoder $1$, after block $b,\;b=1,2,\ldots,B-1$, encoder 2 has estimates $\hat{m}_{1,b}$ and $\hat{m}^{\prime}_{1,b}$, for $m_{1,b}$ and $m^{\prime}_{1,b}$, respectively. To this end, encoder 2 first chooses $\hat{m}_{1,b}$ such that:

where $\hat{m}_{1,b-1}$ was determined at the end of block $b-1$ (recall that ${m}_{1,0}=1$). Then, given $\hat{m}_{1,b}$, he chooses $\hat{m}^{\prime}_{1,b}$ according to (80), shown at the top of the page, where $\hat{m}^{\prime}_{1,b-1}$ was determined at the end of block $b-1$.

Finally, in block $b,\;b=2,3,\ldots,B$, the encoders send (81), shown at the top of the next page.

Decoding: Here, the principle of backward decoding is used to find the transmitted information. In the last block, block $B$, the decoder looks for $(\hat{m}_{1,B-1},\hat{m}^{\prime}_{1,B-1})$ such that

Next, in block $B-1$, the decoder has at hand an estimate of the fresh information sent in block $B-1$, namely, $(\hat{m}_{1,B-1},\hat{m}^{\prime}_{1,B-1})$, and to find the transmitted information in block $B-1$ the decoder looks forThe messages $({m}_{1,B-2},{m}^{\prime}_{1,B-2})$ are the resolution information of user 1 at block $B-1$, which are actually the fresh messages of $B-2$. $(\hat{m}_{1,B-2},\hat{m}^{\prime}_{1,B-2},\hat{m}^{\prime\prime}_{2,B-1})$ according to (83), shown at the top of the page.