Improving MIMO detection performance in presence of phase noise using norm difference criterion Tanumay Datta and Sheng Yang Centrale Supélec, Gif-sur-Yvette, France Abstract-Practical MIMO communication systems suffer performance loss from oscillator phase noise. In particular, traditional maximum likelihood (ML) detection algorithm results in an error floor in symbol error probability, and thus becomes unable to harvest the spatial diversity to be obtained in MIMO systems without phase noise. In this paper, we propose a method to detect the correctness of the traditional ML solution in the presence of strong phase noise. A criteria based on the ML cost differences between the ML solution and the next best solutions is used to determine a set of possible candidate solutions. We also propose a novel algorithm for data detection using phase noise estimation techniques to obtain an modified ML cost for each of the candidate solutions. This approach results in symbol error rate performance improvement by reducing the error floor without incurring much additional complexity due to phase noise estimation. Theoretical arguments as well as simulation studies are presented to support the performance improvement achieved.

I. INTRODUCTION

¡¡Generic introductory material about MIMO, phase noise, literature to be added¿¿

The main motivation in this paper is to use the traditional ML detection solution which is obtained easily for small MIMO systems to get a better detection performance in presence of phase noise. Our main contribution here is two-fold. Firstly, we have studied the properties of ML cost function in MIMO systems in presence of phase noise. We formulate a criterion based on norm differences between the best and the second best vectors to decide upon the correctness of the ML solution. Next using this criterion we generate a set of candidate vectors for further processing to improve the solution. Theoretical arguments have been presented for the norm difference criterion. Secondly, we formulate a modified ML cost function which accounts for the transmit and receive phase noise values as well. Next for each of the candidate vectors this modified ML cost is computed by estimating phase noise values iteratively. The vector that minimizes the modified ML cost among the candidate set of vectors is declared as the final solution. This proposed detection algorithm is shown to have performance improvement in terms of SER without incurring much additional complexity due to phase noise estimation. SER simulation results for various antenna, modulation alphabet combinations are presented. For example, in a 4×4 MIMO system using 4-quadrature amplitude modulation (QAM) alphabet in high SNR regime, 85% SER improvement is obtained while incurring extra phase noise estimation complexity in only 7% of cases. Although simulation results are only shown for MIMO wireless channel models, the pro-posed techniques are applicable for other types of channels also which suffer from phase noise phenomenon.

The rest of the paper is organized as follows. In section II, we describe the MIMO channel model with phase noise. The study of properties of ML cost and the generation of candidate set of vectors based on norm difference criterion in presented in section III. In section IV, we present the proposed detection algorithm using phase noise estimation techniques. The simulation results and discussions are presented in section V. Finally the paper is concluded in section VI.

II. CHANNEL MODEL

We assume a MIMO wireless channel with N t transmit and N r receive antennas. The transmitted vector is denoted by

x = [x 1 , x 2 , • • • , x Nt ] T , where x k ∈ C, 1 ≤ k ≤ N t .
Let E s denote the average energy of the alphabet C. In this paper, we only consider constellations as symbol alphabet with uniform probability distribution over the points. Let H denote the channel matrix, where the (i, k)th element of H, denoted as h i,k , represents the channel gain between kth transmit antenna and ith receive antenna. We assume Rayleigh-fading wireless channel, hence h i,k ∼ CN (0, 1) ∀ i, k. The received vector in base-band y is defined as

y = Θ R HΘ T x + n, (1)
where Θ R and Θ T denotes the phase noise matrices on receive and transmit side respectively, and n is the additive white Gaussian noise (AWGN) vector whose ith entry n i ∼ CN (0, N 0 ), 1 ≤ i ≤ N r . The average received signal-tonoise ratio (SNR) is defined as γ = 10 log 10 NtEs N0 in dB. The transmit and receive phase noise matrices are defined as Θ T = [diag e jθt,1 , e jθt,2 , • • • , e jθt,N t ] and Θ R = [diag e jθr,1 , e jθr,2 , • • • , e jθr,N r ]. We also define the vector form representation of all the transmit and receive noise values as θ = [θ t,1 , θ t,2 , • • • , θ t,Nt , θ r,1 , θ r,2 , • • • , θ r,Nr ] T . All the oscillators are assumed to be independent and identical. We also assume that θ t,k ∼ N (0, σ 2 t ), 1 ≤ k ≤ N t and θ r,i ∼ N (0, σ 2 r ), 1 ≤ i ≤ N r . For simplicity we assume that σ 2 t = σ 2 r = σ 2 θ . In this paper, we consider the scenario when perfect channel state information in available in the receiver (CSIR), i.e., H is known at the receiver. Also, the statistics of AWGN and phase noise vectors (i.e., N 0 and σ 2 θ respectively) are known at the receiver. We also denote H θ = Θ R HΘ T and R = H H H.

III. PROPERTIES OF ML COST IN PRESENCE OF PHASE

NOISE

In this section we study the properties of ML cost function for MIMO detection in presence of phase noise and formulate techniques to approach the problem of data detection in such channels. The ML solution can be written as

x ML = arg max x∈C N t p( x|y) = arg max x∈C N t p(y| x) = arg max x∈C N t θ p(y| x, θ)p( θ)d θ (2)
It can be noted that the evaluation of the ML solution in presence of phase noise is not straightforward. But as an suboptimum technique the receiver can perform traditional ML detection using H instead of H θ ignoring phase noise, as H is perfectly known at the receiver but not H θ . We define f ( x) = ||y -H x|| 2 as the ML cost of a vector x obtained ignoring phase noise and will referred to as 'impure' ML cost function. Let us define

x

(1)

ML = arg min x∈C N t ||y -H x|| 2 , (3)
which is the impure ML solution. It can be observed that, x

(1)

ML = x ML when σ θ = 0. Also, if σ θ = N 0 = 0, then x (1)
ML = x ML = x, i.e. the true ML solution and 'impure' ML solution coincides with the actually transmitted vector.

But in general, they may or may not be same. Our main aim in this section is to find criterion for x

(1) ML = x, and if the criterion is not met, find a set of candidate vectors which contains x.

In absence of phase noise, i.e. σ θ = 0, the ML cost of the actual transmitted vector is nothing but the norm of the AWGN vector ||n|| 2 , which is chi-square distributed with mean N r N 0 , variance N r N 2 0 and 2N r degrees of freedom. Now in presence of phase noise,

||y -Hx|| 2 = ||H θ x -Hx + n|| 2 .
(4)

Now we compute the expected value of the 'impure' ML cost of the correct vector.

E ||y -Hx|| 2 = E ||H θ x -Hx + n|| 2 = E x H (H θ -H) H (H θ -H)x + E(||n|| 2 ) (5) = E s E tr (H θ -H) H (H θ -H) + N r N 0 (6) = 2E s E (tr(R)) (1 -e -σ 2 θ ) + N r N 0 (7) = 2E s N t N r (1 -e -σ 2 θ ) + N r N 0 . (8)
Equation ( 6) is obtained from (5) as

E(x i x k ) = 0, 1 ≤ i = k ≤ N t .
The proof is given in detail in Appendix A. From (8) it can be observed that due to presence of phase noise the expected value of the 'impure' ML cost of the true vector does not become zero even at infinite SNR. It can also be observed that for a given channel, E ||y -Hx|| 2 increases with σ 2 θ .

A. ML solution correctness criterion based on norm difference

Now we investigate whether it is possible to claim that the 'impure' ML solution is the actually transmitted vector or not. In order to do that we study the properties of the norm difference between x and the best vector among the rest. We define x

(2)

ML as the vector having the minimum 'impure' ML cost among all possible vectors excluding x, x

(2)

ML = arg min x∈C N t , x =x ||y -H x|| 2 . ( 9
)
Note that, when x

(1)

ML = x, x (2)
ML = x (1)
ML . We are interested in the metric κ defined as follows

κ △ = ||y -Hx (2) ML || 2 -||y -Hx|| 2 . ( 10
)
Hence, when x

(1) ML = x, κ > 0, and it is the difference between the two best vectors in terms of 'impure' ML cost. On the other hand, when x

(1) ML = x, κ < 0, and it is the norm difference between actually transmitted vector and the 'impure' ML solution. Now we intend to determine a threshold τ such that

p(|κ| < τ |x (1) ML = x) 1. ( 11
)
Hence τ is the approximate upper bound on the distance between the 'impure' ML vector and the actual vector when they are different. Using this threshold, we generate a candidate set S whose elements are the data vectors whose 'impure' ML costs are less than ||y -Hx ML inside the red circle with radius ρ τ . Hence it can be declared to be the correct vector x.

The case when Hx

(1) ML = x, but there are other points inside the circle is illustrated in Fig. 1 (b). This is the typical false alarm scenario, when Hx

(1) ML = x, but can not be declared to be so. In this case, |S| ≥ 2. Fig. 1 (c) shows the scenario when Hx

(1) ML = x. Also in this case, |S| ≥ 2. Equations ( 11) and ( 12) ensures that the candidate set mostly includes the actually transmitted vector, i.e., p(x ∈ S)

1. Note that, S is non-empty and contains atleast x

B. Properties of the norm difference κ

To study the properties of κ, we investigate the ML cost difference between x and its closest 1-symbol neighbours. We (1)

M L = x, |S| = 1, (b) x
(1) and(c) x

M L = x, |S| > 1,
(1)

M L = x, |S| > 1. compute the term δ i △ = ||y -H(x + λ i e i )|| 2 -||y -Hx|| 2
, where e i is the ith column of N t × N t identity matrix. Note that, for closest 1-symbol neighbours λ i = ±2, or ± 2j. Now in high SNR region, ignoring AWGN we obtain

δ i = ||(H θ -H)x -λ i h i || 2 -||(H θ -H)x|| 2 , = |λ i | 2 r i,i -2ℜ{λ i x H (H θ -H) H h i }, = |λ i | 2 r i,i -2ℜ{λ i x H H H θ h i } + 2ℜ{λ i x H r i }(13)
where r i,i is the (i, i)th element of R, and r i is the ith column vector of R.

Now we compute the expected value of δ i for a given channel matrix.

E(δ

i |H) = 2E ℜ{λ i x H i } r i,i + |λ i | 2 r i,i (14) -2E ℜ{λ i x H H H θ h i }
We observe that, for general square M -QAM alphabet with uniform probability distributions, E (ℜ{λ

i x i }) = -4 + 4 √ M .
Using this, we can simplify (15) as follows

E(δ i |H) = 4r i,i + 2r i,i -4 + 4 √ M (1 -e -σ 2 θ ) = 4r i,i 2 √ M -1 + 2 - 2 √ M e -σ 2 θ . (15)
The details of the derivation is given in Appendix B. We observe that, E(δ i ) is positive and decreases with σ 2 θ . Also, it decreases with increasing the constellation size M . It is to be noted that, κ ≤ min 1≤i≤N t δ i . Hence

E(κ) ≤ min 1≤i≤N t E(δ i ). (16)
In Fig. 2, we plot the simulated probability distribution functions (PDF) of κ, ||y -Hx|| 2 , and δ 4 for a fixed 4 × 4 MIMO channel using 4-QAM modulation alphabet and operating at 30 dB average received SNR and σ θ = 6 (1)

ML =
x, but incurs extra complexity of further processing when x

(1) ML = x by adding more vectors in S. Hence there is a performance complexity tradeoff in selection of τ .

In Fig. 3, we plot the variation in error in set generation probability i.e., p(x / ∈ S|x

(1)

ML = x) = p(|κ| > τ |x
(1) ML = x) and the extra complexity incurred in proportion of cases as p(κ ≤ τ |x

(1) ML = x) with respect to τ . For example, a choice of τ = 2.5, results in missing out nearly 5% error events but at the cost of incurring extra complexity only in close to 7% cases where ML detection ignoring phase noise itself gives correct solution.

The value of τ for the purpose of simulation is chosen by observing the histogram of κ over different channel realizations beforehand. Hence, it does not need to change for each channel. However, in case of MIMO channels when channel remains constant for a long time, for example LOS MIMO channels, a better value of τ can be predicted only for that channel.

IV. PROPOSED DATA DETECTION ALGORITHM USING PHASE NOISE ESTIMATION

The 'impure' ML detection process of evaluating x

(1)

ML is suboptimum and suffers from severe performance loss in higher SNR regime as its symbol error rate exhibits error floor. In this section we propose a detection algorithm using the candidate set S which improves the SER performance.

The true ML criteria for data detection in presence of phase noise can be rewritten as

x ML = arg max x∈C N t θ p(y| x, θ)p( θ)d θ (17)
≈ arg max

x∈C N t max θ p(y| x, θ)p( θ) (18)
= arg max

x∈C N t max θ e -||y-H θ x|| 2 N 0 e - N t +Nr k=1 θ 2 k 2σ 2 θ (19) = arg min x∈C N t min θ ||y -H θ x|| 2 + r Nt+Nr k=1 θ 2 k (20)
where in ( 19)

H θ = Θ R H Θ T .
The diagonal matrices Θ R and Θ T are formed using the entries of the test phase noise

vector θ = [ θ t,1 , θ t,2 , • • • , θ t,Nt , θ r,1 , θ r,2 , • • • , θ r,Nr ] T .
The validity of the approximation in ( 18) is discussed in detail in Appendix D. The parameter r = N0 2σ 2 goes to zero as SNR increases. We define the term in (20) as modified ML cost of the test vector x as

C ML ( x) = min θ ||y -H θ x|| 2 + r Nt k=1 θ 2 t,k + r Nr i=1 θ 2 r,i .
Now we propose a approximate method of finding C ML ( x) by computing the optimum Θ R and Θ T iteratively, rather than jointly which is computationally infeasible. Let us denote w = H Θ T x. The term ||y -H θ x|| 2 can be simplified as follows: 21)

||y -H θ x|| 2 = ||y -Θ R w|| 2 = ||y|| 2 + ||w|| 2 -2ℜ(y H Θ R w).(
From ( 21) it can be observed that the optimum value of entries of Θ R for minimizing ||y -H θ x|| 2 is given by θ 2 r,i , referred to as approximate modified ML cost for vector x. This process is repeated from all entries of candidate set S and the final detector output can be written as

θ opt r,i = ∠y i -∠w i , ∀1 ≤ i ≤ N r . ( 22
x det = arg min x∈S C * ML ( x). (24)
It can be observed that, this method of computing C * ML ( x) is approximate as we do not perform joint optimization over Θ R and Θ T and also do not take into account r Nr i=1 θ 2 r,i while computing θ opt r,i to keep the computations tractable. Neglecting r Nr i=1 θ 2 r,i is a valid approximation when r << 1, i.e. N o << 2σ 2 θ which occurs at high SNR. Hence this method of finding x det is expected to have performance loss in low to medium SNR regime.

Next, we propose another heuristic technique which combines the approximate modified ML cost C * ML ( x) and 'impure' ML cost f ( x) to get a more robust metric which will give improved performance in all SNR regime. Let us define

g( x) = q * f ( x) + C * ML ( x), (25)
where q is the relative weight. Intuitively, we would prefer f ( x) in low SNR regime, hence q > 1, and prefer C * ML ( x) in high SNR, making q < 1. Using this logic and proper scaling we set

q = N 0 min x∈S C * ML ( x) 2σ 2 θ min x∈S f ( x) . ( 26
)
detector output can be written as

x det new = arg min x∈S g( x). (27)
The steps of the proposed detection algorithm are listed below:

1) Perform 'impure' ML detection, generate x

(1)

ML . 2) Generate set S. 3) If |S| = 1, declare x (1)
ML to be the correct solution. End. 4) Else, for each x ∈ S, compute Θ T and Θ R . Hence compute C * ML ( x) and then g( x). 5) Find x det new . End.

V. SIMULATION RESULTS AND DISCUSSIONS

In this section, we present simulation results for different MIMO systems with varying number of antennas and modulation alphabet. In Fig. 4, we present the SER results for 2 × 2 and 4 × 4 MIMO systems using 4-QAM modulation alphabet. It can be observed that the proposed algorithm is able to achieve better performance in high SNR regime than ML detection ignoring phase noise. The performance improvement in obtained error floor is about about 70% of the ML detection performance.

VI. CONCLUSION

In this paper, we have studied the properties of ML cost function in MIMO systems in presence of phase noise. Our main contribution is to use the traditional ML detection solution which is obtained ignoring phase noise for further processing by estimating phase noise matrices to improve the detection performance. First, we have found a criterion based on norm differences between the best and second best vectors to decide upon the correctness of the ML solution, and also to generate a set of candidate vectors for further processing to improve the solution. Secondly, we have proposed a detection algorithm which performs phase noise estimation for each candidate vector and using the estimated phase noise matrices a modified ML cost is computed. The vector that minimizes the modified ML cost is declared as the final solution. Theoretical arguments have been presented along with SER simulation results for various antenna, modulation alphabet combinations to show the performance improvement obtained by the proposed algorithm.

REFERENCES [1]

Average received SNR (dB)

=

  { x : ||y -H x|| 2 < ||y -Hx (1) ML || 2 + τ }. (12) So the elements of S are the vectors which when left-multiplied by H lie inside the N r dimensional hypersphere centred around y with a radius of ρ τ △ = ||y -Hx (1) ML || 2 + τ . The different possible scenarios of 'impure' ML costs of vectors and cardinality of S are shown in Fig. 1. Let us denote x * as any point other than x and x (2) ML . Fig. 1 (a) shows the scenario when there is only point Hx (1)

  Criterion for declaring ML solution correct: If S contains only one element, i.e., x ML solution obtained ignoring phase noise is mostly the actually transmitted vector.

Fig. 1 .

 1 Fig. 1. Diagram representing different scenarios of ML cost distribution: (a) x

Fig. 3 .

 3 Fig. 3. Error (green line) and complexity (blue line) variation with τ .

Fig. 4 .Fig. 5 .

 45 Fig. 4. Symbol error rate for 4 × 4 MIMO, 4-QAM, σ θ = 6 • .

Fig. 6 .Fig. 7 .

 67 Fig. 6. Symbol error rate for 2 × 2 and 4 × 4 MIMO, 16-QAM, σ θ = 4 • .

  • . The channel matrix used is given in Appendix C. It can be observed that if we set τ = 2.5, p(x ∈ S) 1. Also, if S has only one element, i.e., x

			(1) ML , p(x (1) ML = x)		1. If we increase the thresh-
		0.1
		0.09								κ
		0.08								||y-Hx||	2
		0.07								δ 4
		0.06
	PDF	0.05
		0.04
		0.03
		0.02
		0.01
		0	-2	0	2	4	6	8	10	12	14

Fig. 2. Probability distribution function of κ, ||y -Hx|| 2 , and δ 4 for 4 × 4 MIMO, 4-QAM, 30 dB SNR old τ , p(x ∈ S) increases. This is beneficial when detected x

)

  Using the optimum Θ R in ||y -H θ x|| 2 , we get ||y -H θ x|| 2 = ||y|| 2 + ||w|| 2 -2 T , and not Θ R . Now, we minimize modified ML cost only with respect to Θ T . This is done by optimizing each index at a time by keeping other indices fixed. We begin with Θ T = 0 Nt×Nt . At index k, we compute the term || H Θ T x|| 2 -2 , ranging from -3σ θ to 3σ θ in steps of ∆ θ . The optimum value is updated at kth index, and we move on to next index. This procedure is repeated for all indices for a certain number of iterations. The final solution of Θ T is then used to compute Θ R as described in (21). Now using Θ T and Θ R , we compute the term C * ML ( x)

				values for θ t,k △ = ||y -H θ x|| 2 + r Nt k=1 θ 2 Nr t,k + r i=1
			Nr
			i=1	|y i ||w i |, (23)
	which only depends upon Θ Nr i=1 |y i || H Θ T x	i	| + r θ 2 t,k for a set of

APPENDIX B APPENDIX C APPENDIX D


Asma Ghorbel
email: asma.ghorbel@centralesupelec.fr

Mari Kobayashi
email: mari.kobayashi@centralesupelec.fr

CentraleSupélec Sheng Yang Lss

Cache-Enabled Broadcast Packet Erasure Channels with State Feedback

We consider a cache-enabled K-user broadcast erasure packet channel in which a server with a library of N files wishes to deliver a requested file to each user who is equipped with a cache of a finite memory M . Assuming that the transmitter has state feedback and user caches can be filled during off-peak hours reliably by decentralized cache placement, we characterize the optimal rate region as a function of the memory size, the erasure probability. The proposed delivery scheme, based on the scheme proposed by Gatzianas et al., exploits the receiver side information established during the placement phase. Our results enable us to quantify the net benefits of decentralized coded caching in the presence of erasure. The role of state feedback is found useful especially when the erasure probability is large and/or the normalized memory size is small.

I. INTRODUCTION

The exponentially growing mobile data traffic is mainly due to video applications (e.g. content-based video streams). Such video traffic has interesting features characterized by its asynchronous and skew nature. Namely, the user demands are highly asynchronous (since they request when and where they wish) and a few very popular files are requested over and over. The skewness of the video traffic together with the ever-growing cheap on-board storage memory suggests that the quality of experience can be boosted by caching popular contents at (or close to) end users in wireless networks. A number of recent works have studied such concept under different models and assumptions (see [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF]- [START_REF] Ji | Fundamental Limits of Distributed Caching in D2D Wireless Networks[END_REF] and references therein). In most of these works, it is assumed that the caching is performed in two phases: placement phase to prefetch users' caches under their memory constraints (typically during offpeak hours) prior to the actual demands; delivery phase to transmit codewords such that each user, based on the received signal and the contents of its cache, is able to decode the requested file. In this work, we focus on a coded caching model where a content-providing server is connected to many users, each equipped with a cache of finite memory [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF]. By carefully choosing the sub-files to be distributed across users, coded caching exploits opportunistic multicasting such that a common signal is simultaneously useful for all users even with distinct file requests. A number of extensions of [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF] have been developed including the case of decentralized placement phase [START_REF] Maddah-Ali | Decentralized coded caching attains order-optimal memory-rate tradeoff[END_REF], the case of non-uniform demands [START_REF] Ji | Order-optimal rate of caching and coded multicasting with random demands[END_REF], [START_REF] Maddah-Ali | Coded caching with nonuniform demands[END_REF], [START_REF] Hachem | Effect of Number of Users in Multi-level Coded Caching[END_REF], the case of unequal file sizes [START_REF] Zhang | Coded Caching for Files with Distinct File Sizes[END_REF]. Although the potential merit of coded caching has been highlighted in these works, many of them have ignored the inherent features of wireless channels.

The main objective of this work is to quantify the benefit of coded caching by relaxing the unrealistic assumption of a perfect shared link. To this end, we model the bottleneck link as a broadcast packet erasure channel (BPEC) to capture random failure or disconnection of any server-user link that a packet transmission may experience especially during high-traffic hours (deliverly phase). The placement phase is performed either in a decentralized [START_REF] Maddah-Ali | Decentralized coded caching attains order-optimal memory-rate tradeoff[END_REF] or centralized manner [START_REF] Maddah-Ali | Fundamental limits of caching[END_REF] over the erasure-free shared link. We further assume that the broadcast packet erasure channel is memoryless and independent and identically distributed (i.i.d.) across users and that the server acquires the channel states causally via feedback sent by users. Under this setting, we study the achievable rate region of the cache-enabled BPEC as a function of the main system parameters. Our contributions are twohold: 1) a comprehensive analysis of the algorithm proposed by Gatzianas et al. [START_REF] Gatzianas | Multiuser Broadcast Erasure Channel With Feedback-Capacity and Algorithms[END_REF], hereafter called GGT algorithm, which enables to characterize the achievable rate of high-order packet transmission; 2) characterization of the achievable rate region of the BPEC with feedback under decentralized cache placement for the case of distinct file requests. We prove that a simple delivery scheme extending GGT algorithm to the case of receiver side information can achieve the rate region.

Finally, we remark that a few recent works [START_REF] Huang | The Performance Analysis of Coded Cache in Wireless Fading Channel[END_REF], [START_REF] Timo | Joint Cache-Channel Coding over Erasure Broadcast Channels[END_REF] have considered coded caching by relaxing the perfect shared link assumption during delivery phase along the line of this work. On the one hand, the work [START_REF] Huang | The Performance Analysis of Coded Cache in Wireless Fading Channel[END_REF] studies the resource allocation problem by modeling the bottleneck link as multicarrier fading channels. On the other hand, the authors in [START_REF] Timo | Joint Cache-Channel Coding over Erasure Broadcast Channels[END_REF] characterize the information theoretic tradeoff between the reliable communication rate and the cache sizes in the erasure broadcast channel with asymmetric erasure probability across users. In both works, it is found that the performance of coded caching is somehow limited by the worst case user. Contrary to this rather pessimistic conclusion, we find that state feedback is useful to improve the performance of coded caching especially in the regime of a small memory size (with respect to the number of files) and with a large erasure probability. This is because the packets not received by the intended users but overheard by unintended users can create multicast opportunity for later transmission at the price of a delay. The structure of the paper is as follows. Section II introduces first the system model and definitions, and then highlights the main results of this work. Sections III and IV prove the converse and the achievability of the rate region of the cache-enabled BPEC with feedback, respectively. Section V provides some numerical results to show the performance of our proposed delivery scheme and finally section VI concludes the paper. Throughout the paper, we use the following notational conventions. The superscript notation X n represents a sequence (X 1 , . . . , X n ) of variables. X I is used to denote the set of variables {X i } i∈I . Logarithm is to the base 2. The entropy of X is denoted by H(X). We define I k {1, . . . , k} for k = 1, . . . , K and let [K] = {1, . . . , K}.

II. SYSTEM MODEL AND MAIN RESULTS

A. System model and definitions

We consider a cache-enabled network depicted in Fig. 1 where a server is connected to K users through a broadcast packet erasure channel (BPEC). The server has an access to N files W 1 , . . . , W N where file i, i.e. W i , consists of F i packets of L bits each (F i L bits). Each user k has a cache memory Z k of M F packets for M ∈ [0, N ], where F 1 N N i=1 F i is the average size of the files. Under such a setting, consider a discrete time communication system where a packet is sent in each slot over the K-user BPEC. The channel input X i ∈ F q belongs to the input alphabet of size L = log q bits 1 . The channel is assumed to be memoryless and i.i.d. across users so that in a given slot we have

Pr(Y 1 , Y 2 , . . . , Y K |X) = K k=1 Pr(Y k |X) (1)
Pr(Y k |X) = 1 -δ, Y k = X, δ, Y k = E (2)
where Y k denote the channel output of receiver k and E denotes erasure. We let S i ∈ S = 2 {1,...,K} denote the state of 1 Throughout the paper, we assume that L > log 2 K so that the achievability results of [START_REF] Gatzianas | Multiuser Broadcast Erasure Channel With Feedback-Capacity and Algorithms[END_REF] hold. the channel in slot i which indicates the users who received correctly the packet. We assume that the transmitter obtains the state feedback S i-1 at the end of slot i while all the receivers know S n at the end of the transmission.

The caching is performed in two phases: placement phase and delivery phase. In placement phase, the server fills the caches of all users Z 1 , . . . , Z K up to the memory constraint. As in most works in the literature, we assume that the placement phase is done without error and neglect the cost, since it takes place usually during off-peak traffic hours. Once each user k makes a request d k , the server sends codewords so that each user can decode its requested file as a function of its cache content and received signals during delivery phase. We provide a more formal definition below. A (M, F d1 , . . . , F d K , n) caching scheme consists of the following components.

• N message files W 1 , . . . , W N are independently and

uniformly distributed over W 1 ו • •×W N with W i = F Fi q
for all i.

• K caching functions are given by φ k :

F N i=1 Fi q → F F M q map the files W 1 , . . . , W N into the cache contents Z k φ k (W 1 , . . . , W N ) (3)
for each user k. • A sequence of encoding functions which transmit at slot i

a symbol X i = f i (W d1 , . . . , W d K , S i-1 ) ∈ F q , based
on the requested file set and the channel feedback up to slot i -

1 for i = 1, . . . , n, where W d k , d k ∈ {∅, 1, . . . , N },
denotes the message file requested by user k.

• A decoding function of user k is given by the mapping

g k : F n q × F F M q × S n → F F d k q so that the decoded file is Ŵd k = g k (Y n k , Z k , S n ) as a function of the received signals Y n
k , the cache content Z k , as well as the state information S n . A rate tuple (R 1 , . . . , R K ) is said to be achievable if, for every > 0, there exists a (M, F d1 , . . . , F d K , n) caching strategy that satisfies

• reliability condition max (d1,...,d K )∈{1,...,N } K max k Pr(g k (Y n k , Z k , S n ) = W d k ) < • rate condition R k < F d k n . (4)
Throughout the paper, we express the entropy and the rate in terms of packets in oder to avoid the constant factor L = log 2 q. In this work, we focus on the case of equal file size F i = F for simplicity.

B. Decentralized cache placement

We mainly focus on decentralized cache placement proposed in [START_REF] Maddah-Ali | Decentralized coded caching attains order-optimal memory-rate tradeoff[END_REF] and adapt it to the packet-based broadcast channel (with no error). Under the memory constraint of M F packets, each user k independently caches a subset of M F N packets of file i, chosen uniformly at random for i = 1, . . . , N . By letting W i|K denote the sub-file of W i stored in the cache memories (known) of the users in K, the cache memory Z k of user k after decentralized placement is given by

Z k = {W i | K ∀k ⊆ K ⊆ [K], ∀i = 1, . . . , N.} (5)
To illustrate the placement strategy, consider an example of K = 3 users and a file A of F packets. After the placement phase, a given file A will be partitioned into 8 subfiles:

A = {A 0 , A 1 , A 2 , A 3 , A 12 , A 13 , A 23 , A 123 } (6)
where, for K ⊂ {1, 2, 3}, A K denotes the packets of file A stored exclusively in the cache memories of users in K. By a law of large numbers as F → ∞, the size of |A K | measured in packets is given by

|A K | F = p |K| (1 -p) 3-|K| . (7)

C. Main results

In order to characterize the rate region of a cached-enabled BPEC with state feedback, we focus on the case of most interest with N ≥ K and assume further that users' demands are all distinct.

Theorem 1. The optimal rate region of the cached-enabled BPEC with state feedback under decentralized cache placement is given by

K k=1 1 -M N k 1 -δ k R π k ≤ 1 (8)
for any permutation π of {1, . . . , K}.

The proof of Theorem 1 is provided in upcoming sections. This region yields the following symmetrical rate

R k = R sym (K) for all k with R sym (K) = 1 K k=1 (1-M N ) k 1-δ k . ( 9
)
The following corollary holds.

Corollary 1. The minimum number of transmissions to deliver a distinct file to each user in the cached-enabled BPEC under decentralized cache placement is given by

T tot = Θ(F ) K k=1 1 -M N k 1 -δ k (10)
as F → ∞.

The following remarks are in order. The results cover some special cases of interest. For the case without cache memory M = 0, the region in Theorem 1 simply boils down to the BPEC with state feedback [START_REF] Wang | On the Capacity of 1-to-Broadcast Packet Erasure Channels with Channel Output feedback[END_REF], [START_REF] Gatzianas | Multiuser Broadcast Erasure Channel With Feedback-Capacity and Algorithms[END_REF]. For the case of no erasure, the number of transmission in Corollary 1 scaled by F is precisely the rate-memory tradeoff under decentralized cache placement for N ≥ K [START_REF] Maddah-Ali | Decentralized coded caching attains order-optimal memory-rate tradeoff[END_REF]. In fact, after some simple algebra, the number of transmissions normalized by the file size can be rewritten as

T tot F = N M 1 - M N 1 -1 - M N K . ( 11
)
This coincides with the "rate" measured as the number of files to be sent over the shared perfect link as defined by Maddah-Ali and Niesen [START_REF] Maddah-Ali | Decentralized coded caching attains order-optimal memory-rate tradeoff[END_REF]. In the following sections we provide the proof of the converse and achievability.

III. OPTIMALITY OF DELIVERY PHASE

In this section, we provide the converse part of Theorem 1 under the assumption that decentralized cache placement is performed. We let p = M N denote the probability of storing a file in a given user's cache memory. First we provide two useful lemmas.

Lemma 1. [11, Lemma 5] For the broadcast erasure channel with independent erasure events (with probability

{δ k }) for different users, if U is such that X i ↔ U Y i-1 I S i-1 ↔ (S i+1 , . . . , S n ), ∀ I, 1 1 -i∈I δ i H(Y n I | U, S n ) ≤ 1 1 -i∈J δ i H(Y n J | U, S n ), (12)
for any sets I, J such that J ⊆ I ⊆ {1, . . . , K}.

Proof: Appendix A.

Lemma 2. Under decentralized cache placement [START_REF] Maddah-Ali | Decentralized coded caching attains order-optimal memory-rate tradeoff[END_REF], the following equality holds for any i and

K ⊆ [K] H(W i | {Z k } k∈K ) = (1 -p) |K| H(W i ).
Proof:

H(W i | {Z k } k∈K ) = H(W i | {W l|J } J:J∩K =∅, l=1,...,N ) (13) = H(W i | {W i|J } J:J∩K =∅ ) (14) = H({W i|J } J:J∩K=∅ ) (15)
= J:J∩K=∅ H(W i|J ) (16) = J:J∩K=∅ p |J| (1 -p) K-|J| H(W i ) (17) = H(W i ) K-|K| l=0 K -|K| l p l (1 -p) K-l (18) = (1 -p) |K| H(W i ) (19)
where the first equality follows from (5), the second equality follows due to the independence between message files, the third equality follows by identifying the unknown parts of W i given the cache memories of K and using the independence of all sub-files; (16) is again from the independence of the sub-files; (17) is from the law of large number similarly as in [START_REF] Huang | The Performance Analysis of Coded Cache in Wireless Fading Channel[END_REF]; finally the last equality follows by applying the binomial theorem.

We apply genie aided bounds to create a degraded erasure broadcast channel by providing the messages, the channel outputs, as well as the receiver side information (contents of cache memories) to enhanced receivers. We focus on the case without permutation and the demand (d 1 , . . . , d K ) = (1, . . . , K) due to the symmetry. We have for user k, k = 1, . . . , K,

n(1 -p) k R k = (1 -p) k H(W k ) (20) = H(W k |Z k S n ) (21) ≤ I(W k ; Y n I k | Z k S n ) + n n,k (22)
≤ I(W k ; Y n I k , W k-1 | Z k S n ) + n n,k (23) = I(W k ; Y n I k | W k-1 Z k S n ) + n n,k (24)
where the second equality is by applying Lemma 2 and noting that S n is independent of others, ( 22) is from the Fano's inequality; the last equality is from

I(W k ; W k-1 | Z k S n ) = 0.
Putting all the rate constraints together, and letting n,k

n,k /(1 -p) k , n(1 -p)(R 1 -n,1 ) ≤ H(Y n 1 | Z 1 S n ) -H(Y n 1 | W 1 Z 1 S n ) . . . n(1 -p) K (R K -n,K ) ≤ H(Y n I K | W K-1 Z K S n ) -H(Y n I K | W K Z K S n ) (25)
We now sum up the above inequalities with different weights, and applying Lemma 1 for K -1 times, namely, for k = 1, . . . , K -1,

H(Y n I k+1 | W k Z k+1 S n ) 1 -δ k+1 ≤ H(Y n I k+1 | W k Z k S n ) 1 -δ k+1 (26) ≤ H(Y n I k | W k Z k S n ) 1 -δ k (27)
where the first inequality follows because removing conditioning increases the entropy. Finally, we have

K k=1 (1 -p) k 1 -δ k (R k -n ) ≤ H(Y n 1 | Z 1 S n ) n(1 -δ) - H(Y n I K | W K Z K S n ) n(1 -δ K ) (28) ≤ H(Y n 1 ) n(1 -δ) ≤ 1 (29)
which establishes the converse proof.

IV. ACHIEVABILITY

Exploiting the polyhedron structure, the vertices of the rate region (8) can be proven to be

R k = R sym (|K|), k ∈ K 0, k / ∈ K (30) for K ⊆ [K].
The proof follows the same footsteps as [13, Section V] and shall be omitted. This means that when only |K| users are active in the system, each active user achieves the same symmetrical rate as the reduced system of dimension |K|.

Then, it suffices to prove the achievability of the symmetrical rate for a given dimension K. To this end, we first revisit the algorithm proposed by Gatzianas et al. [START_REF] Gatzianas | Multiuser Broadcast Erasure Channel With Feedback-Capacity and Algorithms[END_REF], hereafter called GGT algorithm, and characterize the high-order transmission rates. Then, we extend GGT algorithm to the context of the cached-enabled broadcast erasure packet channel.

A. GGT algorithm revisited

The algorithm proposed by Gatzianas et al. [START_REF] Gatzianas | Multiuser Broadcast Erasure Channel With Feedback-Capacity and Algorithms[END_REF] consists of K phases. In each phase k, the transmitter sends order-k packets simultaneously useful to a subset of k users. A phase k is further partitioned into K k subphases in each of which the transmitter sends packets intended to a unique subset of k users. We wish to provide an informal but intuitive description of GGT algorithm along the line of [START_REF] Maddah-Ali | Completely Stale Transmitter Channel State Information is Still Very Useful[END_REF] by assuming the number of private packets N 0 per user is arbitrarily large so that the length of each phase becomes deterministic. First we introduce the basic notions together with key parameters. To simplify the description of the algorithm, we let i, j denote the cardinality of I, J.

• t j denotes the duration of a given subphase intended to j users in slots. The duration of phase j is given by T j = K j t j . • A packet of order-i becomes order-j for a given user for i < j ≤ K if erased by this user and all users in [K] \ J but received by J \ I. The probability of this event is denoted by α i→j = δ K-j+1 (1 -δ) j-i . We let

N i→j = t i α i→j (31)
denote the number of such packets. • An order-j packet is consumed for a given user if this user or at least one user in [K] \ J receives it. The probability of this event is denoted by β j = 1 -δ K-j+1 . Due to the symmetry across users, we can focus on any arbitrary user to define the parameters N i→j and β j . Under this setting, the length of order-j subphase is given recursively by

t j = 1 β j j-1 i=1 j -1 i -1 N i→j . ( 32
)
Here is a brief summary of the algorithm: 1) Phase 1 (order-1 transmission): send N 0 private uncoded packets to each user. This generates N 1→j order-j packets to be sent during phase j = 2, . . . , K. 2) Phase j (order-j transmission) for j = 2, . . . , K: in each subphase intended to a subset J of users, send random linear combinations2 of j-1 i=1 j i N i→j packets for all I ⊆ J. This subphase generates N j→j order-j packets to be sent in phase j > j. Proceed sequentially for all subsets J of cardinality j. Fig. 2 illustrates the phase (subphase) organization for K = 3 and the packet evolution viewed by user 1. The order-3 packet is created both from phases 1 and 2. More precisely, the order-1 packets for user 1 becomes order-3 (via linear combination) if erased by user 1 and received by others (ERR). The number of such packets is N 1→3 . Order-2 packets intended to {1, 2} becomes order-3 if erased by user 1 but received by user 3 (EXR) while packets intended to {1, 3} become order-3 if erased by user 1 and received by user 2 (event EXR). The total number of order-3 packets created from phase 2 is 2N 2→3 . Lemma 3. In the K-user erasure broadcast channel with feedback, the sum rate of order-i packets, denoted by R i (K) is upper bounded by

R i (K) ≤ K i K-i+1 k=1 ( K-k i-1 ) 1-δ k . ( 33
)
Algorithm GGT achieves the RHS of (33) with equality.

Proof: Appendix B. As a corollary of Lemma 3, the symmetrical rate (9) can be rewritten in a convenient form.

Corollary 2. The order-1 rate, R 1 (K) = KR sym of the K-user broadcast erasure channel with feedback can be expressed as a function of R 2 , . . . , R K as follows.

R 1 (K) = KN 0 KN0 β1 + K j=2 ( K j )N1→j R j (K) (34)
where KN0 β1 is the duration of phase 1, K j N 1→j corresponds to the total number of order-j packets generated in phase 1.

Proof: Appendix C.

B. Proposed delivery scheme

Now we are ready to describe the delivery phase by extending GGT algorithm to the context of the cached-enabled network. For simplicity, we first provide an example of K = 3 users and three files A, B, C of size F packets each. After decentralized placement phase, each file is partitioned into 8 subfiles as seen in [START_REF] Maddah-Ali | Coded caching with nonuniform demands[END_REF]. Obviously, the subfile A J for 1 ∈ J, i.e. A 1 , A 12 , A 13 , A 123 are received by the destination and shall not be transmitted in delivery phase. The same holds for B J for 2 ∈ J as well as C J for 3 ∈ J.

In the presence of users' caches, the packets to be sent in phases j are composed by order-j packets created by the algorithm and placement phase. By treating placement phase as phase 0, we let N 0→j denote the number of order-j packets generated in placement phase for a subset of j users for j ≥ 2. For j = 1, we use a short-hand notation N 0→1 = N 0 . By focusing on user 1, we have

N 0 = |A 0 | = F (1 -p) 3 , N 0→3 = |A 23 | = F p 2 (1 -p) N 0→2 = |A 2 | = |A 3 | = F p(1 -p) 2 .
(35)

a) Phase 1: The transmitter sends A 0 , B 0 , C 0 in TDMA. Each packet is repeated until at least one user receives it. After a subphase intended to user 1, the subfile A 0 is partitioned into: A 0 = {A 01 , A 02 , A 03 , A 012 , A 013 , A 023 , A 0123 } where A 0J denotes with some abuse of notation the part of A 0 received by receivers in J for J ⊆ {1, 2, 3}. In other words, a subphase creates order-j packets whose number is given by

N 1→j+1 = |A 0J | = N 0 1 -δ 3 (1 -δ) j δ 3-j (36)
for any J of cardinality j = 1, 2. b) Phase 2: The transmitter sends packets in three subphases for users {1, 2}, {1, 3}, {2, 3}, where each subphase is of size

t 2 = N 1→2 + N 0→2 1 -δ
T 3 = t 3 = N 0→3 + N 1→3 + 2N 2→3 1 -δ . ( 37
)
For the three-user example, it is possible to compute the length of each phase recursively to find the symmetrical rate. In fact, it suffices to consider additionally the packets generated in phase 0 by adding N 0→j in (32). However, this straightforward approach is no longer feasible for a large K. Therefore, we apply Corollary 2 to find the symmetrical rate. From Lemma 3, we have R 2 (3) = 1-δ 2 1+2(1+δ) and R 3 (3) = 1 -δ. Plugging (35), (36), we readily obtain

R 1 cache (3) = 3 1 -p 1 -δ + (1 -p) 2 1 -δ 2 + (1 -p) 3 1 -δ 3 -1 . (38)
which coincides with 3R sym [START_REF] Ji | Fundamental Limits of Distributed Caching in D2D Wireless Networks[END_REF].

A generalization to the K-user case is rather trivial since the placement phase only yields the high-order packets to be sent together with those generated by the algorithm. The achievable symmetrical rate is obtained by modifying (34) by including the packets generated from placement phase as

R 1 cache (K) = KF KN0 β1 + K j=2 ( K j )(N0→j+N1→j) R j (K) . (39)
By repeating the same steps as the proof of Corollary 2, it readily follows that the above expression coincides with KR sym (K).

V. NUMERICAL EXAMPLES

In this section we provide some numerical examples to show the performance of our proposed delivery scheme. Fig. 3 illustrates the tradeoff between the erasure probability and the memory size for the case of K = 3. Each curve corresponds to a different symmetrical rate R sym [START_REF] Ji | Fundamental Limits of Distributed Caching in D2D Wireless Networks[END_REF]. The arrow shows the increasing R sym from 1/3, corresponding to the broadcast channel without memory M = 0 and erasure δ = 0, to infinity. The cache memory increases the rate performance even in the presence of erasure and the benefit of memory cache is significant for smaller erasure probabilities as expected from the analytical expression. Fig. 4 compares the number of transmission T tot , normalized by the file size F , achieved by our delivery scheme with feedback and the scheme without feedback. We consider the system with N = 100, K = 10 and the erasure probabilities of δ = 0 (perfect link), 0.2, and 0.6. We observe that state feedback can be useful especially when the memory size is small and the erasure probability is large. In fact, it readily follows that the rate region of the cached-enabled broadcast channel with no feedback is given by

K k=1 1 -M N k 1 -δ R π k ≤ 1 (40)
yielding

T tot-noFB = F K k=1 1 -M N k 1 -δ . (41)
This corresponds to the total number of transmission over the perfect link expanded by a factor 1 1-δ > 1 because any packet must be received by all users whatever the order of the packet is. Recalling that the feedback is useless for multicasting, the merit of feedback becomes significant if packets of lower order dominate the order-K packets. The case of small p = M N and large erasure probability corresponds to such a situation.

VI. CONCLUSIONS

In this work, we studied decentralized coded caching in the broadcast erasure packet channels with state feedback. Our main contribution is the characterization of the achievable rate region of the channel at hand for the worst case demand such that users' requests are all different in the regime of a large number of files N ≥ K. Contrary to the pessimistic conclusion made by recent work [START_REF] Huang | The Performance Analysis of Coded Cache in Wireless Fading Channel[END_REF], [START_REF] Timo | Joint Cache-Channel Coding over Erasure Broadcast Channels[END_REF] , it is found that the performance of coded caching is no longer limited by the worst user in the presence of state feedback. In fact, state feedback is useful to improve the rate performance especially when the erasure probability is large and/or the normalized memory size is small.

While we restricted ourselves to some regime of interest and to decentralized cache placement for the sake of simplicity, our work can be easily extended to other regimes and the case of centralized coded caching. For example, let us consider the case where subsets of users request a common file and the transmitter must convey a mixture of different-order messages (typically in the regime of N < K), our proposed delivery scheme can be extended to such situation along the line of [START_REF] Piantanida | Analog index coding over block-fading MISO broadcast channels with feedback[END_REF]. It should be noticed that the converse proof on the different-order message rate in Lemma 3 is already general enough to cover all possible file requests. Interestingly, the proposed delivery algorithm can apply directly to centralized coded caching by starting phase-(b + 1) transmission where b = KM N is the ratio of the aggregate memory to the library size. Other interesting yet non-trivial generalization includes the case of non-uniform popularity distribution as well as the case of online coded caching.

Fig. 1 .

 1 Fig. 1. A cached enabled broadcast packet erasure channel for the case of K = 3 and F i = F for all i

Fig. 2 .

 2 Fig. 2. Phase organization for K = 3 and packet evolution viewed by user 1.

Fig. 3 .

 3 Fig. 3. The tradeoff between the memory and the erasure for K = 3.

Fig. 4 .

 4 Fig. 4. The number of transmission Ttot as a function of memory size M for N = 100, K = 10.

2

  • subphase {1, 2}: linear combinations F between A 2 , A 02 and B 1 , B 01 • subphase {1, 3}: linear combinations G between A 3 , A 03 and C 1 , C 01 • subphase {2, 3}: inear combinations H between B 3 , B 03 and C 2 , C 02 Phase 2 creates order-3 packets given as linear combinations of F 13 , F 23 , G 12 , G 23 , H 12 , H 13 . The size of any of these packets is given by N 2→3 = |F 13 | = t 2 δ(1 -δ) 2 . c) Phase 3: Send order-3 packets obtained by linear combinations of A 23 , B 13 , C 12 created in placement phase, A 023 , B 013 , C 012 created in phase 1, and F 13 , F 23 , G 12 , G 23 , H 12 , H 13 created in phase 2. The length of phase 3 is given by

The exact generation method to generate the linear combination is explained in[START_REF] Gatzianas | Multiuser Broadcast Erasure Channel With Feedback-Capacity and Algorithms[END_REF] and shall not be repeated here.

APPENDIX ELEMENTS OF PROOFS

A. Proof of Lemma 1

We have, for J ⊆ I,

where the first equality is from the chain rule; the second equality is due to the current input does not depend on future states conditional on the past outputs/states and U ; the third one holds since Y I,i is deterministic and has entropy 0 when all outputs in I are erased (S i ∩ I = ∅); the fourth equality is from the independence between X i and S i ; and we get the last inequality by removing the terms Y i-1 I\J in the condition of the entropy. Following the same steps, we have

from which and (47), we obtain [START_REF] Piantanida | Analog index coding over block-fading MISO broadcast channels with feedback[END_REF].

B. Proof of Lemma 3

We first provide the converse proof. Similarly to section III, we build on genie-aided bounds and the channel symmetry inequality. Lemma 1. Let us assume that the transmitter wishes to convey the message W K to a subset of users K ⊆ {1, . . . , K} and receiver j wishes to decode all messages Wj ∆ = {W K } j∈K for j = 1, . . . , K. The messages are all independent. We let R K denote the rate of the message W K . In order to characterize the upper bound on the |K|-th order message rate R K , we use genie-aided bounds by assuming that receiver k provides Y k to receivers k + 1 to K. Under this setting and using the Fano's inequality, we have for receiver 1 :

For receiver k = 2, . . . , K, we have:

Summing up the above inequalities with appropriate weights and applying Lemma 1 K -1 times, we readily obtain for this user ordering:

We further impose the symmetrical rate condition such that R K = R K for any subset K, K with equal cardinality and define the j-th order message rate as R j (K) = R K for any K of cardinality j. By focusing on J of the same cardinality j in (53), the upper bound on R j (K) is given by

In order to prove the achievability of the i-th order rate, we proceed GGT algorithm from phase i by sending N i packets to each subset I ⊆ [K] with |I| = i. The length of j-order subphase in (32) is now given by

where we added the index i and the dependency on N i to clarify the fact that the algorithm starts by sending N i packets in each subphase in phase i with N i l→j = t i l α l→j . The dependency on N i might be omitted if it clear. For j = i, we have

The sum rate of order-i messages achieved by GGT algorithm is given by

We notice that the number of transmission from phase j to K can be expressed by grouping subphases in the following different way:

where

By following similar steps as [15, Appendix C], we obtain the recursive equation given by

for j > i. Since we have

and the binomial theorem n k=0 n k x k y n-k = (x + y) n , it readily follows that we have

By plugging the last expression in (58), we have

which coincides the upper bound of (33). This establishes the achievability proof.

C. Proof of Corollary 2

We prove that the RHS of (34), denoted here by f , coincides with R 1 (K) by exploiting the result of Lemma 3. By replacing R i (K) with R i GGT (K) defined in (58) for N i = N 1→i for i ≥ 2 and N 1 = N 1→1 , we have

To prove that

where t j is defined in (32), it suffices to prove the following equality:

For j = 2, the above equality follows from (32) and (57).

Now suppose that (67) holds true for 2 ≤ l ≤ j -1 and we prove it for j. From (32) we have where the second equality follows by recalling N l→j = t l α l→j and plugging the recursive expression (67) in t l for l = 2, . . . , j -1, the last equality is due to (57). Therefore, we verify the desired equality also for j. This yields

= R 1 GGT (K).

(75)