Coding Schemes for Discrete Memoryless Multicast Networks with Rate-limited Feedback

Coding schemes for discrete memoryless multicast networks with feedback from receivers and relays to the transmitter are proposed. These coding schemes are based on block Markov coding, {joint backward decoding} and hybrid relaying strategies. In each block, the receivers and relays compress their channel outputs and send the compression indices through the feedback link to the transmitter. In the next block, after obtaining compression indices, the transmitter sends them together with the source message. Each receiver uses backward decoding to jointly decode the source message and all compression indices. Our coding schemes generalize Gabbai\&Bross's results for the single relay channel with partial feedback, where they used the restricted decoding and deterministic partitioning. It is shown that for the single relay channel with relay-transmitter feedback, our coding schemes improve the noisy network coding scheme by Lim, Y-H Kim and El Gamal, the distributed decode-forward coding scheme by Lim, Kim and Y-H Kim and all known lower bounds on the achievable rate in the absence of feedback. Furthermore, we modified our schemes and propose a new coding scheme for discrete memoryless multicast networks without feedback, which can potentially improve the noisy network coding and distributed decode-forward coding schemes.


I. INTRODUCTION
The relay channel, first introduced by van de Meulen [1], describes a 3-node communication channel where the transmitter sends message to the receiver with the assistance of relay. In their seminal paper, Cover and El Gamal proposed two basic coding strategies: compress-forward and decode-forward, for the discrete memoryless relay channel. Both strategies are based on block Markov coding. In the compress-forward strategy, relay compresses its outputs and sends compression index to the receiver. In the decode-forward strategy, the relay first decodes the full or part of source message and then sends the decoded message to the receiver. Both strategies have been generalized to the discrete memoryless multiple-relay channel [2]. The compress-forward strategy was later extended to a more general network-discrete memoryless network [3], [4]. Recently, a distributed decode-forward coding scheme was proposed by Lim, Kim, Y-H Kim that generalizes the decode-forward strategy to the general multicast network [5] and broadcast relay network [6].
When introducing (perfect) feedback from the receiver to the relay, the relay channel was shown to be a physically degraded [7], and therefore decode-forward achieves the channel capacity. For the case with feedback from the receiver or relay to the transmitter, the capacity is general unknown. In [8] Gabbai and Bross studied this problem and proposed inner bounds by using the restricted decoding and deterministic partitioning, introduced by Willems and Van der Meulen in [9].
In this paper, we consider the general discrete memoryless multicast network with rate-limited feedback. This network consists of N ≥ 3 nodes where the transmitter sends a message to different receivers with the assistance of multiple relays and in presence of feedback from the receivers and relays to the transmitter. For this setup, we propose two coding schemes based on block Markov coding, joint backward decoding and hybrid relaying strategy. In our first scheme, relays and receivers use compress-forward strategy to create their compression indices and then send them both into the forward communication and feedback channels. The transmitter, after obtaining the compression indices through feedback, sends them together with the source message. Receivers jointly decode the source message and all compression indices. Our second scheme is similar to the first scheme, except that the relay not only uses compress-forward strategy as in the first scheme, but also use partial decodes-forward strategy [7] to decode the source message. It is shown that our coding schemes generalize Gabbai&Bross's results [8] for the relay channel with relay-transmitter feedback. For some channels, such as the general Gaussian relay channel and Z relay channel, our coding schemes improve over the noisy network coding scheme by Lim, Y-H Kim and El Gamal, the distributed decode-forward coding scheme by Lim, Kim and Y-H Kim and all known lower bounds on the achievable rate in the absence of feedback.
Motivated by our feedback scheme, we propose a new coding scheme for discrete memoryless multicast networks without feedback, which can still potentially improve the noisy network coding and distributed decode-forward coding.

II. SYSTEM MODEL
Consider N -node discrete memoryless (DM) multicast networks with feedback from the receivers and relays to the transmitter, see This setup is characterized by 2N finite alphabets X 1 , . . . , X N , Y 1 , . . . , Y N , a channel law P Y1···YN |X1,...,XN and nonnegative feedback rates R Fb,k , for k ∈ [2 : N ]. Specifically, at discrete-time i, node j ∈ [1 : N ] sends input x j,i ∈ X j and then observes output y k,i ∈ Y j . After observing Y k,i , for k ∈ [2 : N ], node k sends a feedback signal F k,i ∈ F k,i to the transmitter, where F k,i denotes the finite alphabet of F k,i and is a design parameter of a scheme. The feedback link between the transmitter and node k is assumed to be instantaneous and noiseless but rate-limited to R Fb,k bits on average. Thus, if the transmission takes place over a total blocklength n, then Fig. 1. N -node discrete memoryless multicast network with partial feedback In the transmission, the transmitter communicates a message M ∈ [1 : 2 nR ] to the set of receivers D with the assistance of the set of relays R. A (2 nR , n) code for this channel consists of • a set of relay and receiver encoders that maps • a set of feedback-encoder that is to produce feedback symbols F k,i (Y k,1 , . . . , Y k,i ), for each k ∈ [2 : N ] and i ∈ [1 : n], • a set of decoders that estimatesM (d) based on Y n d , for d ∈ D. Assume M is uniformly distributed over the message set. The average probability of error is defined as P

III. MAIN RESULTS
In this section, we present our main results as the following theorems. The detailed proof are given in Section V and Section VI.
Theorem 1: For DM multicast networks with feedback from receivers and relays to the transmitter, the rate R is achievable if for all T ⊆ [2 : N ], d ∈ D, and for some pmf Proof: See Section V-A. Theorem 2: For DM multicast networks with feedback from receivers and relays to the transmitter, the rate R is achievable if for all T ⊆ [2 : N ], d ∈ D, and for some pmf such that Proof: See Section V-B Remark 1: By setting U k = const., the achievable rate in Theorem 2 specializes to the rate in Theorem 1. (Setting U k = const. means that all relay nodes only perform compress-forward strategy without partially decode-forwarding the source message.) Based on coding schemes for Theorem 1 and 2, we propose another coding scheme for DM multicast networks without feedback. The new achievable rate is shown as below.
Theorem 3: For DM multicast networks without feedback, the rate is achievable if R satisfies (8) for all T ⊆ [2 : N ], d ∈ D, and for some pmf such that IV. EXAMPLES

A. The classic relay channel with relay-transmitter feedback
Consider the classical relay channel with perfect feedback from the relay to the transmitter, see Figure 2.

Fig. 2. Discrete memoryless relay channel with relay-transmitter feedback
For this channel, the achievable rate in Theorem 1 specializes to for some pmf P X1X2 PŶ 2 |X2Y2 . The achievable rate in Theorem 2 specializes to for some pmf P X1X2U2 PŶ 2|X2 U2Y2 . In [8] Gabbai and Bross considered this channel and proposed coding schemes based on restricted decoding and deterministic partitioning. It's easy to check that the rates (11) and (12) recover Gabbai&Bross's rates of Theorem 2 and Theorem 3 in [8], respectively.
By using noisy network coding [3], we obtain the achievable rate for some pmf P X1 P X2 PŶ 2|X2 Y2 , which coincide with the compress-forward lower bound (Theorem 6 in [7]). By using distributed decode-forward coding scheme [5], [6], we obtain the achievable rate for some P X1X2U2 , which coincide with the partial decode-forward lower bound (Theorem 7 in [7]).
In [8] Gabbai and Bross showed that for the general Gaussian relay channel and Z relay channel, the rate (12) is larger than the known lower bounds on the achievable rate in the absence of feedback, including the compress-forward lower bound as in (13), and the partial decode-forward lower bound as in (14). In view of this fact, we have the following Corollary: Corollary 1: For the DM single-relay channel with relay-transmitter feedback, our coding schemes recover Gabbai&Bross's results, strictly improve over the noisy network coding [3], the distributed decode-forward coding in [5] and all known lower bounds on the achievable rate in the absence of feedback.

B. Enhanced relay channel
Consider an enhanced relay channel where the transmitter accesses its channel output Y 1 , see Figure 3.

Fig. 3. Discrete memoryless enhanced relay channel
For this channel, the achievable rate in Theorem 3 specializes to . When using noisy network coding [3] for this channel, we obtain the following achievable rate for some pmf P X1 P X2 PŶ 2|X2 Y2 PŶ 1|X1 Y1 . It's easy to find that the optimal choice of Y 1 isŶ 1 = const., resulting the same achievable rate as (13). When using distributed decode-forward coding [5] for this channel, the achievable rate is same as (14). Note that by setting V 2 = X 2 ,Ŷ 2 = const., (15) reduces to the rate (14), which means our coding scheme could potentially improve distributed decode-forward coding.
One interesting finding is that for this enhanced relay channel, both noisy network coding and distributed decode-forward coding fail to make use of Y 1 . While in our scheme for Theorem 3, instead of compressing or ignoring Y 1 , the transmitter decodes the compression messages sent by receivers and relays based on Y 1 , which could potentially increase the rate achieved by noisy network coding and distributed decode-forward coding.
For each l b−1 , randomly and independently generate 2 nR sequences Encoding and decoding are explained with the help of Table I. . To ensure that source node perfectly knows l b−1 , we havê 3) Relays and receivers encoding: Relays and receivers both perform compress-forward strategy. In each block b ∈ [1 : B], node k ∈ [2 : N ] compresses y n k,b by finding a unique index l k,b s.t.
Then, it sends l k,b through the feedback link at rateR k ≤ R Fb,k and in block b + 1 sends x n k,b+1 (l k,b ). By the covering lemma, this is successful with high probability if . By the independence of the codebooks, the Markov lemma, packing lemma and the induction on backward decoding, this step is successful with high probability if and Combine (17-20), and by using Fourier elimination to eliminateR 2 , . . . ,R N , we obtain Theorem 1.

B. Scheme 1B
Note that in Scheme 1A above, relays and receivers only perform compress-forward strategy. In this subsection we present a scheme where relays perform mixed compress-forward and partial decode-forward strategy. 1 Since each Receiver d ∈ D make its own estimation of m b and l b−1 , the exact notation should be (m b−1 ). For simplicity of notation, we omit the superscript (d).
, l r,B ) Yrŷ r,1 (l r,1 |1, 1)ŷ r,2 (l r,2 |m 1 , l r,1 ) . . .ŷ r,B (l r,B |m ′ B−1 , l r,B−1 )ŷ r,B+1 (1|m ′ B , l r,B ) For each l d,b−1 , randomly and independently generate 2 nR ′ sequences . Encoding and decoding are explained with the help of Table II. 2) Source encoding: In each block b ∈ [1 : B + 1], assume that the transmitter already knows l b−1 through the feedback links. It sends . To ensure that source node perfectly knows l b−1 , we havê 3) Relays encoding: Relay nodes perform hybrid compress-forward and decode-forward strategy. For each block b ∈ [1 : then it compresses y n r,b by finding a unique index l r,b s.t.
Then, it sends l r,b through the feedback link at rateR r ≤ R Fb,r and in block b + 1 sends x n r,b+1 (m ′ b , l r,b ). By the covering and packing lemma, this is successful with high probability if for r ∈ R.

4) Receivers encoding:
Receiver d ∈ D compresses y n d,b by finding a unique index l d,b s.t.
Then, it sends l d,b through the feedback link at rateR d ≤ R Fb,d and in block b + 1 sends x n d,b+1 (l d,b ). By the covering lemma, this is successful with high probability if 2 Since each Relay r ∈ R makes its own estimation of m ′ b , the exact notation should bem b . For simplicity of notation, we omit the superscript (r).

5) Decoding:
Receiver d ∈ D performs backward decoding. For each block b ∈ [B +1, . . . , 1], it looks for . By the independence of the codebooks, the Markov lemma, packing lemma and the induction on backward decoding, the decoding is successful with high probability if and a). if T ∩ R = ∅ R +R(T ) For convenience, we ignore the constraints (25) Combine (21-24) and (27), and by using Fourier elimination to eliminate R ′ , R ′′ ,R 2 , . . . ,R N , we obtain Theorem 2.
VI. DISCRETE MEMORYLESS MULTICAST NETWORK In Section V we proposed two block Markov coding schemes for DM multicast networks in the presence of instantaneous, rate-limited and noisy-free feedback. Recall the noisy network coding scheme [3], [4] for DM multicast networks without feedback, where each node (including the transmitter) compresses its observation and sends the new compression index in next block. Comparing our coding scheme with noisy network coding, we observe that both schemes involve block Markov coding, compressing channel outputs and sending compression messages. However, our schemes allow hybrid relaying strategies at relays nodes and in each block, instead of creating new compression index, the transmitter forwards all compression indices sent by receivers and relays from previous block. In our scheme, different nodes operate differently according to the features of the network, which leads to a larger achievable rate than noisy network coding, as shown in examples in Section IV.
Motivated by Scheme 1A and 1B, we propose another scheme for N -node DM multicast networks without feedback. The main idea is as following: in each block b, node k ∈ [2 : N ] creates compression index l k,b−1 and sends (l k,b−1 , l k,b−2 ). The transmitter, after observing Y n 1,b , first decodes compression indices l b−1 , which is in essence a coding problem on a multiple access channel P Y1|X2,...,XN with side information X 1 . Then in block b + 1, the transmitter sends compression messages l b−1 with source message m b+1 . In this section we extend Scheme 1B to DM multicast networks. Similar extension can be applied to Scheme 1A.

Relay r
Rx d Tx , randomly and independently generate 2 nR ′′ sequences x n  (28) since the transmitter knows the source messages it sent.