{'fraction_non_alphanumeric': 0.051225426517710226, 'fraction_numerical': 0.01654109292456915, 'mean_word_length': 4.253639672429482, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Approximate Feedback Capacity of the Gaussian Multicast Channel

We characterize the capacity region to within log{2(M-1)} bits/s/Hz for the M-transmitter K-receiver Gaussian multicast channel with feedback where each receiver wishes to decode every message from the M transmitters. Extending Cover-Leung's achievable scheme intended for (M,K)=(2,1), we show that this generalized scheme achieves the cutset-based outer bound within log{2(M-1)} bits per transmitter for all channel parameters. In contrast to the capacity in the non-feedback case, the feedback capacity improves upon the naive intersection of the feedback capacities of K individual multiple access channels. We find that feedback provides unbounded multiplicative gain at high signal-to-noise ratios as was shown in the Gaussian interference channel. To complement the results, we establish the exact feedback capacity of the Avestimehr-Diggavi-Tse (ADT) deterministic model, from which we make the observation that feedback can also be beneficial for function computation.


I. INTRODUCTION
While feedback plays a significant role in improving the reliability of communication systems [1], a traditional viewpoint on feedback capacity has been pessimistic over the past few decades. This is mainly due to Shannon's original result on feedback capacity which shows that feedback provides no increase in capacity for discrete memoryless point-to-point channels [2]. For multiple-access channels (MACs), feedback can increase the capacity [3]; however, the increase in capacity for Gaussian MACs is bounded by 1 bit for all channel parameters [4].
In contrast to these results, recent research shows that feedback provides more significant gain for communication over interference channels [5]- [7]. Interestingly, the feedback gain is shown to be unbounded for certain channel parameters; i.e., the gap between the feedback and non-feedback capacities can be arbitrarily large as the signal-to-noise ratio (SNR) of each link increases. One distinction of interference channels with respect to MACs is that each receiver decodes its desired message in the presence of undesired interfering signals. A natural question to ask is whether feedback gain depends crucially on the presence of interference. In this paper, we make progress towards addressing this question. To isolate the interference issue, we start with a Gaussian MAC with two transmitters and feedback. We then modify the channel by adding additional receivers with identical message demands and feedback links from those receivers to the two transmitters. We call the new channel the two-transmitter, K-receiver Gaussian multicast channel with feedback. 1 Note that this channel does not pose any interference while still maintaining the many-to-many structure of interference channels. We present a coding scheme for this channel which generalizes Cover-Leung's scheme (intended for MACs) [10], and achieves rates within 1 bit/s/Hz per transmitter of the cut-set outer bound for all channel parameters. We further extend our results for the case of M -transmitters and approximate the feedback capacity within log {2(M − 1)} bits/s/Hz per transmitter. We find that feedback can provide multiplicative gain in the high-SNR regime, and that feedback is useful not only for mitigating interference [6], but also for providing qualitatively-similar gains for channels with a manyto-many structure. In particular, we find that the feedback capacity region strictly enlarges the intersection of the feedback capacity regions of K individual MACs. This is in contrast to the non-feedback case where the capacity region is simply the intersection of K individual MAC capacity regions.
To complement our results on approximate feedback capacity, we establish the exact feedback capacity region of the Avestimehr-Diggavi-Tse (ADT) deterministic model. As a byproduct, we also find that feedback increases the achievable rates for function computation. Specifically using a twotransmitter two-receiver example where each receiver wants to reconstruct a modulo-2 sum of two independent Bernoulli sources generated at the two transmitters, we demonstrate that feedback can increase the non-feedback computing capacity.
Related Work: Feedback strategies for MACs were studied previously in [4], [5], [10]- [13]. For the two-user case, Cover and Leung [10] developed an achievable scheme that employs block Markov encoding and a decode-and-forward scheme. Willems [11] proved the optimality of this scheme for a class of deterministic channels. Ozarow [4] established the exact feedback capacity region using a different approach based on Schalkwijk-Kailath's scheme [1]. Kramer developed more generic techniques of the approach and extended the 1 In the non-feedback case, this channel is well known as the compound MAC [8], [9]. However, this name is not appropriate in the feedback case. The compound MAC has a single physical receiver which can feed back only one of the possible candidates of the received signals experiencing different channel states. In our model, on the other hand, all of the received signals can be fed back.
. . . result to include an arbitrary number of transmitters [5]. In the present paper, we generalize Cover-Leung's scheme to approximate the feedback capacity region of the M -transmitter K-receiver Gaussian multicast channel with an additional (K − 1) receivers as well as corresponding feedback links from those receivers to the M transmitters.
The two-user compound MAC with conference encoders [8] or decoders [9] is also partially related to our work in the sense that dependence between the transmitted signals (or received signals) can be created through conferencing encoders (or decoders). However, we find a significant distinction. In the conferencing encoder problem [8], [14], the capacity region is shown to be the intersection of the capacity regions of individual MACs. Similar behaviors follow for a class of conferencing decoder problems [9]. In contrast, we find that the feedback capacity region of our multicast channel enlarges the intersection of the feedback capacity regions of individual MACs.
Recently, Lim-Kim-El Gamal-Chung developed an achievable scheme for discrete memoryless networks [15], and demonstrated the approximate optimality of their scheme for multi-source Gaussian multicast networks. Our feedback channel with unfolding can be cast into a multi-source Gaussian multicast network. However, we exploit the structure of our feedback channel to induce correlation between transmitters which leads to a tighter result.

II. MODEL
We focus on the Gaussian multicast channel with M = 2 transmitters and K receivers first. Section IV-C includes our results for M > 2. As shown in Fig. 1, each receiver decodes all of the messages and is able to feed its received signal back to both transmitters. Without loss of generality, we normalize the transmit signal powers as P 1 = P 2 = 1 and channel noise powers as Z k ∼ CN (0, 1) for all k ∈ {1, 2, . . . K}. Hence, the signal-to-noise ratio (SNR) at each receiver captures the effect of the channel gains: SNR mk |g mk | 2 , where g mk ∈ C is the complex-valued channel gain from transmitter m to receiver k.
Each transmitter m ∈ {1, 2} encodes an independent and uniformly distributed message W m ∈ {1, 2, . . . , 2 N Rm }. The encoded signal X mi of transmitter m at time i is a function of its own message and past feedback signals: where Y ki is the received signal at receiver k at time i. A rate pair (R 1 , R 2 ) is said to be achievable if there exists a family of codebooks subject to power constraints and corresponding encoding/decoding functions such that the average decoding error probabilities go to zero as the code length N tends to infinity. The capacity region C is the closure of the set of the achievable rate pairs.

Theorem 1 (Inner Bound):
The capacity region includes the set R of (R 1 , R 2 ) such that for 0 ≤ ρ ≤ 1 and ∀k, (1) Proof: See Section IV-A. Remark 1: We compare this to the naive rate region which is the intersection of the feedback capacity regions of individual MACs: where C MAC k (ρ) denotes the feedback capacity region of the Gaussian MAC for receiver k, given ρ [4]. Note that the intersection constrains individual rate bounds, thus reducing the rate region. On the other hand, our rate region contains no such individual rate bounds, thus improving upon R naive . This is in contrast to the nonfeedback case and the compound MAC case with encoders [8] (or decoders [9]), where the capacity region is simply the intersection of individual MAC capacity regions.
Remark 2: Fig. 2 shows a numerical result of the innerand-upper bound gap for the symmetric capacity, denoted by C sym = sup {R : (R, R) ∈ C}. For illustrative purpose, we consider a two-receiver symmetric channel setting where SNR 1 := SNR 11 = SNR 22 and SNR 2 := SNR 12 = SNR 21 . While the worst-case gap is 1 bit due to the coarse analysis in Corollary 1, the actual gap is upper-bounded by approximately 0.08 over a wide range of channel parameters. This suggests that a refined analysis could lead to an even smaller gap. For instance, in the high-SNR regime, we obtain the asymptotic symmetric capacity as follows.
Corollary 2: For a two-receiver symmetric channel setting, the symmetric capacity at the high SNR regime is Proof: Due to the high-SNR assumption, it follows that the optimal correlation coefficients for the inner and upper respectively, resulting in the matching inner and upper bound as (7).
Feedback Gain: From Theorems 1 and 2, we can see that feedback can provide a significant capacity increase as was shown in the Gaussian interference channel [6]. To see this clearly, let us consider the two-receiver symmetric channel setting as above. Fig. 3 plots the high-SNR-regime symmetric capacity normalized by the MAC symmetric capacity for Rx Feedback gain for a two-receiver symmetric channel setting as in Fig. 2. Note that feedback provides unbounded multiplicative gain when SNR 1 is far apart from SNR 2 . use α := min{log SNR1,log SNR2} max{log SNR1,log SNR2} for x-axis to indicate a signal strength difference between SNR 1 and SNR 2 . Note that the symmetric nonfeedback capacity is simply the intersection of individual MAC capacities: Note that the gap between C NO sym and C MAC 1,sym can be arbitrarily large when SNR 1 and SNR 2 are far apart, i.e., α ≤ 1 2 . On the other hand, the symmetric feedback capacity is asymptotically the same as if there were only one receiver. As a result, feedback provides multiplicative gain for the regime of α ≤ 1 2 . In Section IV-A, we will provide an intuition behind this gain while describing an achievable scheme.

A. Achievability: Proof of Theorem 1
Motivating Example (Fig. 4): To develop an achievable scheme for the Gaussian channel, we utilize the ADT deterministic model [16]  We first explain an achievable scheme for a particular ADT model example, illustrated in Fig. 4. Specifically, we show how to achieve a (1.5, 1.5) rate-pair with feedback. As will be seen in Theorem 5, the feedback capacity region is given by R 1 + R 2 ≤ 3. Extrapolating from this example, we later make observations leading to a generic achievable scheme.
In the nonfeedback case, transmitter 1 can send only one bit a 1 through the top level, since the mincut between transmitter 1 and receiver 2 is limited by 1. Similarly transmitter 2 can send only one bit, say b 1 . However, feedback provides more options to route by creating additional paths, e.g.,  In time 2, transmitters 1 and 2 start with sending their own fresh information a 2 and b 2 on the top levels respectively. Now the idea is that transmitter 1 forwards the fed back B 1 using the second level. Note that this transmission allows receiver 1 to obtain B 1 without causing any harm to the transmission of (a 2 , b 2 ). Similarly transmitter 2 can deliver A 1 to receiver 2. Therefore, during the two time slots, transmitters 1 and 2 can deliver (a 1 , a 2 , A 1 ) and (b 1 , b 2 , B 1 ) respectively to both receivers, thus achieving (1.5, 1.5). Remark 3: The gain comes from the fact that feedback creates alternative paths to provide routing gain. In fact, this gain was already observed by [6] in the context of twouser strong interference channels where n 12 ≥ n 11 and n 21 ≥ n 22 in the ADT model. However in [6], this routing gain does not appear in the weak interference regime such as (n 12 = 1 < n 11 = 3, n 21 = 1 < n 22 = 3). On the other hand, in our multicast channel, we can see this routing gain even when cross links are weaker than direct links.
This example leads us to make two observations. First, feedback enables each transmitter to decode the other transmitter's information and then forwards this in the next time slot. Second, the transmitted signals in time 2 can be correlated with the previously-sent information. This motivates us to employ the decoding-and-forward and block Markov encoding schemes. In fact, an achievable scheme combining these two ideas was developed by Cover-Leung [10] in the context of the two-user discrete memoryless MAC with feedback. In this paper, we generalize this scheme to the multiple-receiver case, thereby obtaining an approximate capacity region within a provably small gap. As for a decoding operation, we employ backward decoding [17].
Here is the outline of achievability. We employ block Markov encoding with a total size B of blocks. In block 1, each transmitter sends its own information. In block 2, with feedback, each transmitter decodes the other user's information (sent in block 1). The two previously-sent messages are then available at each transmitter. Conditioning on these two messages, each transmitter generates its own fresh message and then sends a corresponding codeword. Each transmitter repeats this procedure until block B − 1. In the last block B, to facilitate backward decoding, each transmitter sends a predetermined message. Each receiver waits until a total of B blocks have been received and then performs backward decoding.
The achievable scheme outlined above is broadly applicable and not limited to the Gaussian channel. We characterize an achievable rate region for discrete mememoryless multicast channels in Lemma 1 and then choose an appropriate joint distribution to obtain the desired result. The generic coding scheme is also applicable to the ADT deterministic model and details will be presented in Section V.
Lemma 1: The feedback capacity region of the twotransmitter K-receiver discrete memoryless multicast channel includes the set of (R 1 , R 2 ) such that over all joint distributions p(u)p(x 1 |u)p(x 2 |u). Here U is a discrete random variable which takes on values in the set U where |U| ≤ min {|X 1 ||X 2 |, |Y 1 |, · · · , |Y K |} + 2.
Proof: See Appendix A. We now choose the following Gaussian input distribution to complete the proof: ∀m = 1, 2, where X m = U +X m and (U,X 1 ,X 2 ) are independent. Straightforward computation then gives (1)-(3). This completes the proof.

B. Outer Bound: Proof of Theorem 2
By symmetry, it suffices to prove the bounds of (4) and (6). These bounds are based on standard cut-set arguments.
Assume that the covariance between X 1 and X 2 is where (a) follows from the fact that W 1 is independent of W 2 , and X mi is a function of (W m , Y i−1
For the sum-rate outer bound, where (a) follows from the fact that conditioning reduces entropy; (b) follows from the memoryless property of channels; and (c) follows from the fact that |K Y1 | ≤ 1 + SNR 11 + SNR 21 + 2|ρ| √ SNR 11 · SNR 21 .
Proof: For M > 2, a multitude of auxiliary random variables can be incorporated to capture correlation between many transmitter pairs. For simplicity, however, we consider a natural extension of the two-transmitter case which includes only one auxiliary random variable. The only distinction is that with feedback, each transmitter decodes all of the messages of the other transmitters, and generates its new message and a corresponding codeword, conditioned on all of these decoded messages. This induces a multitude of constraints on the rate region. To avoid significant overlaps, we omit the detailed proof.  We now choose the following Gaussian input distribution to complete the proof: ∀m = 1, · · · , M , where X m = U +X m and (U,X 1 , · · · ,X M ) are independent. Straightforward computation then gives (12)- (13). This completes the proof.

Theorem 4 (Outer Bound):
The feedback capacity region of the M -transmitter K-receiver Gaussian multicast channel is included by the setC M of (R 1 , · · · , R M ) such that ∀K X := E[XX * ] 0, ∀S {1, · · · , M } and ∀k, where K S|S c denotes the conditional covariance matrix of X S given X S c and ρ mn := |[K X ] mn |.
Proof: As before, the proof of the outer bounds are based on the standard cutset argument. Hence, we omit the detailed proofs.

Corollary 3 (Constant Gap):
The gap between the inner bound and outer bound regions given in Theorems 3 and 4 is upper-bounded by ∆ := log {2(M − 1)} bits/s/Hz/transmitter: Proof: See Appendix B.

V. DETERMINISTIC CHANNEL
The ADT model was developed as a method of analysis to approximate the feedback capacity region of the Gaussian multicast channel. In this section, we find the exact feedback capacity region of the deterministic channel.
Theorem 5: The feedback capacity region of the Mtransmitter K-receiver ADT multicast channel is the set of (R 1 , · · · , R M ) such that ∀S {1, · · · , M } and ∀k, where Proof: The achievability proof is immediate due to Lemma 2. The achievable region is maximized when U = ∅ and (X 1 , · · · , X M ) are uniformly distributed and independent. Appendix C contains the converse proof.

VI. FUNCTION COMPUTATION
As a by-product of Theorem 5, we can find an interesting role of feedback for other communication scenarios such as computation in networks. To see this, consider an (M, K) = (2, 2) ADT multicast channel with feedback and parameters n 11 = n 22 = 3 and n 12 = n 21 = 1 (see Fig. 4). Suppose that both receivers wish to compute the same function of modulo-2 sums of two independent Bernoulli sources (S 1 , S 2 ) generated at the two transmitters. The computing rate for decoding S 1 ⊕ S 2 at all receivers is denoted R comp . Without feedback, the following cut-set based argument provides a bound on R comp : where the equality follows from the fact that S 1 ⊕ S 2 is independent of S 1 . For the particular ADT example, H(Y 1 |X 1 ) ≤ 1 and H(Y 2 |X 2 ) ≤ 1, from which R comp ≤ 1. On the other hand, the example in Fig. 4 shows the achievability of ( 3 2 , 3 2 ), thus yielding R FB comp ≥ 3 2 . Therefore, feedback can increase rates for computation. Our future work is to extend this example to larger classes of networks.

VII. CONCLUSION
We established the feedback capacity region of the Gaussian multicast channel with M transmitters and K receivers to within log {2(M − 1)} bits/s/Hz per transmitter of the cutset bound universally over all channel parameters. We characterized the exact feedback capacity region of the ADT model, and observed a feedback gain for function computation.
Our future work is along several new directions: (1) Improving our coding scheme based on Cover-Leung to incorporate ideas from [4], [12], [13], [18]; (2) Extending to more realistic scenarios where feedback is offered through rate-limited bitpiped links [19] or a corresponding backward channel [20]; (3) Exploring the role of feedback for function computation.

APPENDIX A PROOF OF LEMMA 1
Codebook Generation: Fix a joint distribution p(u)p(x 1 |u)p(x 2 |u). First generate 2 N (R1+R2) independent codewords u N (j, l), j ∈ {1, · · · , 2 N R1 }, l ∈ {1, · · · , 2 N R2 }, according to N i=1 p(u i ). For each codeword u N (j, l), encoder 1 generates 2 N R1 independent codewords x N 1 ((j, l), s), s ∈ {1, · · · , 2 N R1 }, according to N i=1 p(x 1i |u i ). Similarly, for each codeword u N (j, l), encoder 2 generates 2 N R2 independent codewords x N 2 ((j, l), q), q ∈ {1, · · · , 2 N R2 }, according to N i=1 p(x 2i |u i ). Encoding and Decoding: We employ block Markov encoding with a total size B of blocks. Focus on the bth block transmission. With feedback (y N,(b−1) 1 , · · · , y N,(b−1) K ), transmitter 1 tries to decode the messageŵ (b−1) 2 =q (sent from transmitter 2 in the (b − 1)th block). In other words, we find the uniqueq such that indicates the set of jointly typical sequences. Note that transmitter 1 already knows its own messages (w ). We assume thatŵ is correctly decoded from the previous block (b − 1). The decoding error occurs if one of two events happens: (1) there is no typical sequence; (2) there is anotherŵ such that it is a typical sequence. By AEP, the first error probability becomes negligible as N tends to infinity. By the packing lemma in [21], [22], the second error probability becomes arbitrarily small (as N tends to infinity) if Based on (w Each receiver waits until total B blocks have been received and then does backward decoding. Notice that a block index b starts from the last B and ends to 1. For block b, receiver k finds the unique pair (ĵ,l) such that where we assumed that a pair of messages (ŵ 2 ) was successively decoded from block (b + 1). Similarly other receivers follow the same decoding procedure.
Error Probability: By symmetry, we consider the probability of error only for block b at receiver k. We assume that (w ) = (1, 1) was sent through block (b − 1) and block b; and there was no backward decoding error from block B to (b + 1), i.e., (ŵ 2 ) are successfully decoded. Define an event: By AEP, the first type of error becomes negligible. Hence, we focus only on the second type of error. Using the union bound, we get Pr(E jl ) Pr(E j1 ) + j=1,l =1 Pr(E 1l ) Here note that (j = 1, l = 1) is the worst case, dominating the other two cases. The number 3 in the second inequality reflects all of these cases. Hence, the error probability can be made arbitrarily small if From (19) and (21), we complete the proof.

APPENDIX B PROOF OF COROLLARY 3
Let δ S = (15) − (12). Set ρ = min m,n ρ ij . We then get where (a) follows from Claim 1 (see below); and (b) follows from the determinant identity |I m + AB| = |I n + BA|. Therefore, the gap per transmitter is upper-bounded by This completes the proof.
APPENDIX C CONVERSE PROOF OF THEOREM 5 First, consider (18). Starting with Fano's inequality, we get ≤ N max{n 1k , · · · , n Mk } where (a) follows from the fact that conditioning reduces entropy; and H(Y ki ) is maximized when (X 1i , · · · , X Mi ) are uniformly distributed and independent. Next, consider (17). Let W S := {W m : m ∈ S}. Starting with Fano's inequality, we get where (a) follows from the fact that W S and W S c are independent; (b) follows from the fact that X i S c is a function of (W S c , Y i−1 1 , · · · , Y i−1 K ); (c) follows from the fact that conditioning reduce entropy; (d) follows from the fact that H(Y i |X S c ,i ) is maximized when (X 1i , · · · , X Mi ) are uniformly distributed and independent.