Capacity Results for the K-User Broadcast Channel with Two Nested Multicast Messages
Mohamed Salman Mahesh K. Varanasi




Adversarial Attack and Defense on Graph Data: A Survey
    Lichao Sun, 
        Yingtong Dou, 
        Carl Yang, 
        Kai Zhang,
        Ji Wang, 
        Yixin Liu,
        Philip S. Yu, Fellow, IEEE,
        Lifang He, 
        and Bo Li, 
        Lichao Sun, Kai Zhang, Yixin Liu, Lifang He are with the Department of Computer Science and Engineering, Lehigh University, Bethlehem, PA, 18015 USA. E-mail: {lis221, kaz321, yila22, lih319}@lehigh.edu.
        Yingtong Dou, and Philip S. Yu are with the University of Illinois Chicago, Chicago, IL, 60607 USA. E-mail: {ydou5, psyu}@uic.edu
        Carl Yang is with the Emory University Atlanta, GA 30322 USA. E-mail: j.carlyang@emory.edu
	    Ji Wang is with the College of Systems Engineering, National University of Defense Technology, Changsha, Hunan, 410073 P. R. China. E-mail: wangji@nudt.edu.cn.
	    Bo Li is with the University of Illinois Urbana-Champaign at Champaign, IL 61820 USA. E-mail: lbo@illinois.edu
	    

    December 30, 2023
===============================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================

empty
empty




The K-user discrete memoryless (DM) broadcast channel (BC) with two nested multicast messages is studied in which one common message is to be multicast to all receivers and the second private message to a subset of receivers. The receivers that must decode both messages are referred to as private receivers and the others that must decode only the common message as common receivers. For two nested multicast messages, we establish the capacity region for several classes of DM BCs characterized by the respective associated sets of pair-wise relationships between and among the common and private receivers, each described by the well-known more capable or less noisy conditions.

For three classes of DM BCs, the capacity region is simply achieved by superposition coding and the proofs of the converses rely on a recently found information inequality. 

The achievable rate region is then enhanced through the addition of a splitting of the private message into as many parts as there are common receivers and indirect decoding. A closed-form two-dimensional polyhedral description is obtained for it for a given coding distribution. Through a converse result that relies on the well-known Csiszar sum lemma and the information inequality, a specialization of this region that involves splitting the private message into just two sub-messages is proved to be the capacity region for several classes of DM BCs, beyond those for which superposition coding alone is capacity optimal, thereby underscoring the benefit of rate-splitting. 

All previously known capacity results for DM BCs with two nested multicast messages for the two and three-receiver DM BCs as well as DM BCs with one private or one common receiver are included in the general framework presented in this work.

















§ INTRODUCTION



The discrete-memoryless (DM) broadcast channel (BC) is an archetypal communication setting in network information theory where a transmitter is to send messages to K receivers. 
In this work, our focus is on the DM BC with two nested multicast messages, also known as degraded messages, wherein the transmitter must multicast a common message to all receivers, and a private message to a subset of receivers. 
This scenario is relevant in applications such as video and music broadcasting to many receivers which require two different levels of quality. The common message represents the standard quality multicast information that must be decodable by all receivers, while the private multicast message is a refinement to be decoded by a subset of receivers that, aggregated with the common message, represents the high quality message.

In spite of a great deal of attention starting in the 1970's, the capacity region of the BC with two nested multicast messages is known to date only for certain combination of numbers of users and classes of channels. We recall the definition of the well-known orderings between pairs of channels taken from the set of K point-to-point channels associated with the transmitter and each of the K receivers (which in turn can be used to define classes of BCs). Denote the transmitted symbol by the random variable X, an auxiliary random variable by U, and the received symbols at the K receivers by Y_1, Y_2 , ⋯ , Y_K, which are also used to refer to the respective receivers. The (conditional) probability mass functions of these random variables are denoted as is standard in the literature.
  Receiver Y_c is said to be physically degraded from Y_s if p(y_s,y_c|x)=p(y_s|x)p(y_c|y_s), i.e., X  Y_s  Y_c forms a Markov chain. 
 
   <cit.>
Receiver Y_s is less noisy than Y_c if I(U;Y_s)≥ I(U;Y_c) for all p(u,x). Henceforth, we denote this condition as Y_s ≻ Y_c.

 <cit.> 
Receiver Y_s is more capable than Y_c if I(X;Y_s)≥ I(X;Y_c) for all p(x). Henceforth, we denote this condition as Y_s ≽ Y_c. 
 

The less noisy condition is strictly less restrictive than the degraded relation (cf. <cit.>) and the more capable condition is in turn strictly less restrictive than the less noisy condition. 


When convenient, we refer to the less noisy condition Y_s ≻ Y_c as Y_c being more noisy than Y_s or denote it equivalently as Y_c  ≺  Y_s. Similarly, we may refer to the more capable condition Y_s ≽ Y_c as Y_c being less capable than Y_s or denote it equivalently as Y_c ≼ Y_s.

The two-receiver DM BC with degraded messages was first studied by Korner and Marton in 1977 <cit.>. Indeed, they found the capacity region for the general case without any restrictions on the channel to be the set of rate pairs (R_0 and R_1, denoting the rates of the common and private messages, respectively) satisfying

    R_0   ≤ I(U;Y_2)
    
    R_1   ≤ I(X;Y_1|U)
    
    R_0+R_1   ≤ I(X;Y_1)
 
for some p(u,x).
The achievability scheme uses superposition coding and joint decoding. The common message, denoted henceforth as M_0, is represented by the auxiliary random variable U with associated cloud center codewords, and the private message, denoted henceforth  as M_1, is superposed on U to generate the satellite codewords (according to p(x|u)) to be transmitted, denoted by X. Receiver Y_2 finds M_0 by decoding U and Y_1 finds (M_0,M_1) by decoding X. This scheme was shown earlier to achieve the capacity of the degraded DM BC XY_1Y_2 with private messages by Gallager <cit.>. The main contribution in <cit.> was thus to provide the converse proof using the images-of-a-set technique <cit.>. 

More recently, Diggavi and Tse addressed the DM BC with arbitrary K <cit.> with two general nested multicast messages, M_0 and M_1, in which M_0 is to be decoded by all receivers and M_1 by a subset 𝒮⊆{1,2,...,K} of private receivers, which is also the setting studied in this paper. Henceforth, we will let 𝒮 = {1,2,...,L} without loss of generality, so that the first L receivers are private receivers and the last K-L receivers are common receivers.  Using the same encoding scheme as in the 2-user case, and with each private receiver successively decoding the two messages (with common message first), a natural extension of the Korner-Marton region to this more general setting is the set of rate pairs 


    R_0   ≤ I(U;Y_i)  i∈{1,2,...,K}
    
    R_1   ≤ I(X;Y_s|U)  s∈𝒮

for some p(u,x). The authors of <cit.> proved that the above region is optimal for certain classes of DM BCs respectively in two cases, namely, the single private receiver case of 𝒮={1} and the single common receiver setting of  𝒮={1,  ⋯, K-1 }. The class of DM BCs for which (<ref>) was shown to be the capacity region when 𝒮={1} is defined by the K-1 Markov conditions X  Y_1  Y_i for each i∈{2,3,..,K}  and when 𝒮={1,  ⋯, K-1 } by the K-1 Markov conditions X Y_i  Y_K for each i ∈{ 1,2,..,K-1}. In both cases, the capacity regions are thus known for the respective classes of DM BCs defined by degradedness conditions, with each common receiver being a degraded version of each private receiver. 


The problem of characterizing capacity for the DM BC with two nested multicast messages for a larger class of DM BCs but for the three-receiver case was addressed by Nair and El Gamal <cit.> for the above two cases. When 𝒮={1}, they showed that the region (<ref>) is not in general optimal <cit.> and proposed an achievability scheme that involves rate splitting with superposition coding and indirect decoding. M_0 is represented by U (the cloud centers), a part of M_1 is superposed on U to obtain V, and the rest of M_1 is superposed on V to yield X. Receiver Y_3 finds M_0 by decoding U and Y_1 finds M_0  and M_1 by decoding X using joint typicality decoding, while Y_2 finds M_0 indirectly by decoding V. Using this scheme, the authors of <cit.> established the capacity region for the class of channels constrained by a single less noisy condition Y_3 ≺  Y_1, thereby significantly enlarging the class of BCs for which capacity was known for K=3 earlier due to <cit.>.

 
The K=3 and 𝒮={1,2} case was also addressed in <cit.> for which the authors showed therein that the natural extension of the Korner-Marton region given by (<ref>) is the capacity region for the class of channels defined by two restrictions, Y_3 ≺ Y_1 and Y_3 ≺ Y_2 <cit.>[There is a typo in the statement of Proposition 11 of <cit.>. The conditions stated therein Y_2 ≺  Y_1 and Y_2 ≺  Y_3 should be Y_3 ≺  Y_2 and Y_3 ≺   Y_1 (and these are stated correctly in the proof of Proposition 11 <cit.>).] in thereby strictly expanding the class of DM BCs for which capacity was known from <cit.>.

The converse proofs of <cit.> for the single private and single common receiver cases use mainly the Csiszar sum lemma <cit.>.

The problem of transmitting two nested multicast messages has also been addressed in the more restricted context of combination networks <cit.>. These networks lie at the intersection of the multi-hop wired networks and single-hop BCs and can be considered as an example of deterministic DM BCs. In <cit.>, Bidokhti et al showed that a form of linear superposition coding with rate-splitting is optimal for two common receivers and any number of private receivers, i.e, K=L+2. When the number of common receivers increases beyond 2 (K>L+2), the linear superposition coding with rate splitting is shown to be not optimal anymore. For more than two common receivers, a new achievable rate region, which depends on block Markov encoding scheme, is obtained. This new inner bound is shown to be the capacity region for networks with three (or fewer) common receivers and any number of private receivers. Finally, a new inner bound for the DM BC with two nested multicast messages is proposed by extending the block Markov coding scheme to this case. The work of <cit.> however does not preclude the possibility that rate-splitting and superposition coding for the DM BC with two nested multicast messages with three common receivers when specialized to the combination network may suffice to obtain the capacity region, obviating the need for the block Markov coding scheme proposed therein.

In <cit.> and <cit.>, Romero and Varanasi, using notions from order theory and lattices, provide a general framework applicable for the K-user DM BC with any subset of the set of exponentially many possible messages, one for each subset of receivers. Therein, the authors obtain general inner bounds for rate-splitting and superposition coding based schemes in split-rate space and show the presence of polymatroidal structure. 


The achievability schemes of this work on two nested multicast messages can be seen as being related to the framework in <cit.>. However, the emphasis here is on carefully choosing relatively simple rate-splitting strategies tailored to the two nested multicast messages problem, employing partial interference decoding via non-unique, rather than unique, decoding, and on obtaining explicit two-dimensional descriptions for the achievable rate regions in terms of the rates of the two messages.
Such descriptions are then shown to be amenable to proving converse theorems that establish the capacity region for various classes of DM BCs for general K and L. 









 §.§ An Overview of Results




In the first main result of this paper, 
we characterize three classes of DM BCs for which the natural extension of the Korner-Marton scheme with superposition coding 

is capacity achieving. The first class is one in which there is a private receiver that is less capable than each of the other private receivers and less noisy than each of the common receivers. The second class is one in which there is a common receiver that is more noisy than all other receivers. The technical contribution in both these cases is the proof of the converse. Since the Csiszar sum lemma has no generalization for more than two receivers, we use the information inequality <cit.> to bypass this problem. This inequality was originally developed in the context of the 3-receiver DM BC with private messages <cit.>, where it was used to obtain a tight outer bound for the class of 3-receiver less noisy DM BCs defined by Y_3  ≺  Y_2  ≺  Y_1. 
Finally, the third class for which the natural extension of the Korner-Marton scheme is shown to be capacity-optimal is one where there is a common receiver that is more noisy than each of the other common receivers and there is a private receiver that is less capable than each of the other private receivers. 

In the special cases of (a) a single private receiver with 𝒮={1 } and (b) single common receiver so that 𝒮={1,  ⋯, K-1 }, the first and second classes of DM BCs mentioned above reduce to ones in which (a) Y_j  ≺ Y_1 for each j∈{2,3,..,K} and (b) Y_K ≺  Y_j for each j∈{1,2,..,K-1}, thereby expanding —by replacing degradedness conditions with the less noisy conditions—the corresponding classes of DM BCs for which capacity was found in <cit.>. In another direction, Case (b) is an extension of the corresponding result obtained in <cit.> from K=3 to general K. The third class of DM BCs for which capacity is established can be seen as an extension of the capacity result due to Korner-Marton  <cit.> for K=2 and L=1 to general K and L. 










In the second main result of his paper, drawing inspiration from the achievable scheme for the K=3 and L=1 case in <cit.>, we propose an inner bound based on rate splitting, superposition coding, and indirect decoding for general K and L. In particular, we split the private message M_1 into K-L sub-messages, with one sub-message for every common receiver (except the last one) through which it indirectly decodes the common message and one sub-message to be decoded only by the private receivers. For this rate-splitting strategy of the private message, a closed-form description of polyhedral achievable rate region per coding distribution would require projecting away an indeterminate number of split-rate variables for general K. When K=3 this projection can be done by hand using Fourier-Motzkin Elimination (FME) <cit.> as in <cit.>. For general K, we identify a certain structure in the region's inequalities and use that structure to eliminate the split rates. Consequently, we present a closed-form expression for our inner bound in terms of the original message rates. 

The third main contribution of this work is to consider the specialization of rate-splitting and superposition coding to one that splits the private message into only two sub-messages. One (private) sub-message is to be decoded only by the private receivers and the other (semi-public) sub-message by a subset of the common receivers. Those common receivers decode the common message by indirectly decoding the satellite codeword for the semi-public sub-message, which is superimposed on the cloud codewords for the common message. The rest of the common receivers decode the common message directly from the cloud centers. For this specialization, we obtain a converse result that uses both the Csiszar sum lemma and the information inequality to establish the capacity region for several sub-classes of three or more receiver DM BCs for which it was hitherto unknown. Moreover,  this result includes 
the capacity region for the class of three-receiver DM BCs with the restriction Y_3 ≺ Y_1 of  <cit.>. 








The rest of this paper is organized as follows. In Section <ref>, we formally state the problem set-up and establish notation. Section <ref> is devoted for the three main results following which the paper is concluded in Section <ref>. Detailed proofs of the first two results are given in Appendices <ref>, <ref> and <ref>. 



§ PRELIMINARIES AND DEFINITIONS




We consider a DM BC consisting of one transmitter X∈𝒳, K receivers Y_i∈𝒴_i, and the channel transition probability W(y_1...y_K|x) where the conditional probability of n channel outputs (Y_1j...Y_Kj),  j ∈{1,...,n}, conditioned on n channel inputs (X_1...X_n) is given by 

    p(y_1^n...y_K^n|x^n)= ∏_j=1^nW(y_1j...y_Kj|x_j)


As previously stated, we study the problem of groupcasting two nested multicast messages M_0 and M_1 over a K-user DM BC with M_0 to be decoded by all the receivers while the private message M_1 by the subset of L private receivers indexed by 𝒮={1, 2 , ⋯  , L}. The set of indices of the common receivers that need to only decode M_0 is denoted as 𝒞={L+1, ⋯ , K}.



The messages M_0 and M_1 have rates R_0 and R_1, respectively. A (2^nR_0, 2^nR_1, n) code consists of an encoder that assigns a codeword x^n(m_0,m_1) for each message pair (m_0,m_1) ∈ [1:2^nR_0]×[1:2^nR_1], and  K decoders with the j^th private decoder mapping the received sequences Y_j,1^n for each j ∈𝒮 into an estimate (m̂_0^(j),m̂_1^(j)) and the i^th common receiver mapping Y_i,1^n into an estimate m̂_0^(i) for each i ∈𝒞. The probability of error P_e^(n) is the probability that not all receivers decode their messages correctly. The rate pair (R_0,R_1) is said to be achievable if there exists a sequence of (2^nR_0,2^nR_1,n) codes with P_e^(n)→ 0 as n →∞. The closure of the union of achievable rates is the capacity region.







§ MAIN RESULTS



This section is organized along the lines of the overview of results in Section <ref>. In Section <ref>, we provide three conditions for the optimality of the superposition coding/joint decoding for the general case of the K-user DM BC with L private receivers in Theorem <ref>. 
The second main result is a  general inner bound 

based on splitting the private message into K-L sub-messages and superposition coding, and is presented in Section <ref>. In
Section <ref> a simplification of the general inner bound based on splitting the private message into just two sub-messages is presented and shown via a converse result that it is the capacity region of K-L-1 classes of DM BCs. 
In Section <ref>, we discuss the technical difficulty of proving a converse for a larger class of channels than for those found in Section <ref> using more than two splits of the private message.









Since the converse proofs in this section use the information inequality of <cit.>, we state it here for easy reference.




Let X  (Y,Z) be a DM BC without feedback and Z ≺  Y. Consider M to be any random variable such that
M X^n  (Y^n,Z^n) forms a Markov chain. Then, we have 
    I(Y^i-1;Z_i|M)≥    I(Z^i-1;Z_i|M)  1≤ i≤ n 
    
    I(Y^i-1;Y_i|M)≥    I(Z^i-1;Y_i|M)  1≤ i≤ n


.



























 §.§ Superposition Coding



In the next theorem, we state the three classes of K-receiver DM BCs for which superposition coding alone is capacity-optimal for general two nested messages. 


For the K-receiver DM BC with two general nested multicast messages and L private receivers the set of rate pairs (R_0,R_1) satisfying 


    R_0   ≤ I(U;Y_c)   ∀ c∈𝒞
    
    R_1   ≤ I(X;Y_s|U)  ∀ s∈𝒮
    
    R_0+R_1   ≤ I(X;Y_s)  ∀ s∈𝒮
 for some p(u,x) is the capacity region for the following cases:


  (i) ∃ a r ∈𝒮 such that Y_r ≼ Y_s ∀ s∈𝒮\{r} and Y_c ≺  Y_r ∀ c∈𝒞.

  (ii) ∃ a j ∈𝒞 such that Y_j ≺  Y_c ∀ c ∈𝒞\{j} and Y_j ≺  Y_s  ∀ s ∈𝒮.

  (iii) ∃ a j ∈𝒞 such that Y_j ≺ Y_c ∀ c  ∈𝒞\{j} and ∃ r ∈𝒮 such that Y_r ≼ Y_s ∀ s  ∈𝒮\{r}



The region in (<ref>) is the extension of the two-receiver Korner-Marton region in (<ref>) to the K-receiver DM BC when all private users use joint decoding.


In Case (i), when Y_r ≼ Y_s for s ∈𝒮\{r}, the last two sets of inequalities of (<ref>) become R_1≤ I(X;Y_r|U) and  R_0+R_1≤ I(X;Y_r). Moreover, since Y_c ≺  Y_r, the latter inequality is redundant. Hence, the region defined by (<ref>) becomes the set of rate pairs (R_0,R_1) satisfying 

    R_0   ≤ I(U;Y_c)   ∀ c∈𝒞
    
    R_1   ≤ I(X;Y_r|U)

for some p(u,x). The converse proof for the above two inequalities is given in Appendix <ref>. It is inspired from the converse proofs in <cit.> where the information inequality plays a crucial role. To the reader familiar with that inequality it is clear that the optimal choice of the auxiliary random variable would be U_i=M_0,Y_r,1^i-1. It does not involve Y_c^n, and hence, the proof holds for each c∈𝒞.

In Case (ii), when Y_j ≺  Y_c for all c ∈𝒞\{j}, the first set of inequalities in (<ref>) become R_0≤ I(U;Y_j). Moreover, since Y_j ≺  Y_s for all s ∈𝒮, the last set of inequalities in (<ref>) becomes redundant.

Hence, the rate region in (<ref>) can be written as the set of rate pairs (R_0,R_1) satisfying 

    R_0   ≤ I(U;Y_j)   
    
    R_1   ≤ I(X;Y_s|U)  ∀ s∈𝒮

for some p(u,x). The converse for these two inequalities are also presented in Appendix <ref>, where the optimal choice of the auxiliary random variable is U_i=M_0,Y_j,1^i-1, which is not a function of Y_s^n. Note that the information inequality is used in this converse proof as well.

Lastly, for the class of channels in Case (iii), the achievable region defined by (<ref>) becomes the set of rate pairs (R_0,R_1) satisfying[For Case (iii) joint decoding is needed at the private receivers whereas for Cases (i) and (ii) successive decoding suffices.]

    R_0   ≤ I(U;Y_j)   
    
    R_1   ≤ I(X;Y_r|U)  
    
    R_0+R_1   ≤ I(X;Y_r)
 for some p(u,x), which is equivalent to the two-receiver Korner-Marton region in (<ref>). In particular, it is the capacity region for DM BC when only receivers Y_j and Y_r are present. 
Next, we note that the capacity region of the two-receiver DM BC with receivers Y_j and Y_r is an outer bound for the K-receiver DM BC under consideration since the addition of the other receivers cannot enlarge the capacity region. Hence, since the region (<ref>) is also achievable (with superposition coding), it is the capacity region for the K-receiver DM BC. Note that the converse proof for the two-receiver case in <cit.> uses the Csiszar sum lemma, i.e., the optimal choice of the auxiliary random variable is U_i=M_0,Y_j,1^i-1Y_r,i+1^n. 











In Figs. <ref> and <ref>, we illustrate the classes of channels considered in Theorem <ref> with a Hasse diagram each, that allows for a quick visualization of each class. In Fig. <ref>, the conditions of Case (i) are depicted: among the private receivers, there is one which is pair-wise less capable (shown with dashed lines) than all other private receivers and less noisy (shown with solid lines) than all the common receivers. In Fig. <ref> the conditions of Case (ii) are shown: there is one common receiver that is pair-wise more noisy than all the other common receivers and all private receivers. Fig. <ref> shows the class of channels in Case (iii): there is one common receiver that is pair-wise more noisy than all the other common receivers and there is one private receiver which is pair-wise less capable than all other private receivers.


Although we are considering the K-receiver DM BC, the obtained capacity regions for the three cases of Theorem <ref> depend only on the channels of a subset of the receivers. For instance, in Case (i), the region depends on only K-L+1 receivers, while in Case (ii) it depends on L+1 receivers, and in Case (iii) it depends on only two receivers. In particular, the addition of any number of less noisy common receivers Y_c (with Y_j ≺ Y_c) in Cases (ii) and (iii) and/or any number of more capable private receivers Y_s (with Y_r ≼ Y_s) in Cases (i) and (iii) does not change the capacity region from what it was before adding these receivers. Note that in Case (iii) of channels there is no order restriction across the common and private receivers, unlike in Cases (i) and (ii), i.e., restrictions are only needed among the common receivers and among the private receivers.






Theorem <ref> includes several results known in the literature. These are listed below.


  * Consider Case (iii) of Theorem <ref> for K=2 and L=1. In this case, there is no restriction on the channel and the capacity region is given as (<ref>) (with r=1 and j=2) which is the Korner-Marton capacity region for the two-receiver case.

  * Consider general K but L=1. This case was addressed in <cit.> where optimality was shown for the class of DM BCs under the degraded order restrictions X Y_1  Y_c, ∀ c ∈𝒞. Case (i) of Theorem <ref> gives the capacity region for the larger class of channels, Y_c≺ Y_1 ∀ c∈𝒞. This class if depicted in Fig <ref>.

  * Consider general K but L=K-1. This case was addressed in <cit.> where optimality was shown for the class of DM BCs under the degraded order restrictions X Y_s  Y_K, ∀ s ∈𝒮. Case (ii) of Theorem <ref> expands this result to the class of channels Y_K≺ Y_s, ∀ s ∈𝒮, shown in Fig <ref>. 


  * Case (ii) of Theorem <ref> is a generalization to general K and L of the result in <cit.> for K=3 and L=2 which obtained capacity for DM BCs defined by the two restrictions Y_3 ≺ Y_1 and Y_3 ≺ Y_2.

Note also that the converse proof of Case (ii) of Theorem <ref> mainly depends on the information inequality, while that in <cit.> mainly depends on the Csiszar sum lemma.















 
In <cit.>, the capacity region was established for K=3 and L=1 for the class of channels Y_2 ≺  Y_1 
(or Y_3 ≺  Y_1). 
However, Case (i) of Theorem <ref> gives the capacity for a strictly more restrictive class of DM BCs defined by Y_2 ≺  Y_1 and Y_3 ≺  Y_1. The reason for this is that the achievable scheme in <cit.> is more complex in that it involves rate-splitting and indirect decoding, which brings us to the next section. In particular, we will generalize the scheme of <cit.> to general K and L next.





































 §.§ Rate-Splitting and Superposition Coding: A New Inner Bound


We expand our study of the capacity regions of classes of K-user DM BCs with two nested multicast messages for general L by incorporating rate splitting before superposition coding.





An inner bound of K-user DM BC for two nested multicast messages (M_0,M_1) with M_0 to be decoded by all receivers and M_1 to be decoded by the first L private receivers is the set of rate pairs (R_0,R_1) satisfying

    R_0≤    I(U_c;Y_c)  ∀ c∈𝒞
    
    R_1≤    I(X;Y_s|U_K)  ∀ s∈𝒮
    
    R_0+R_1≤    I(X;Y_s|U_c)+I(U_c;Y_c)  ∀ s∈𝒮∀ c∈𝒞\{K}
    
    R_0+R_1≤    I(X;Y_s) ∀ s∈𝒮

for some (U_K,U_K-1,...,U_L+1,X) such that U_K U_K-1 U_K-2 ... U_L+1 X forms a Markov chain. This inner bound is the capacity region for the DM BCs of Cases (i)-(iii) of Theorem <ref>.

 We give an outline of the proof here and provide the detailed version in Appendix <ref>. Split the private message M_1 into K-L parts. There is a part for every common receiver except Y_K, with M_1i for each i∈{L+1,L+2,..,K-1} and one part, denoted M_11, to be decoded only by the private receivers. M_0 is represented by U_K, then M_1K-1 is superposed on U_K to obtain U_K-1, and then M_1K-2 is superposed on U_K-1 to yield U_K-2, and so on. Finally, (M_0,M_1) is represented by X. The receiver Y_K finds M_0 by decoding U_K, the common receiver Y_c finds M_0 by indirectly decoding U_c for each c ∈{L+1,..,K-1}, and the private receivers find (M_0,M_1) by decoding X. 


From the proof in Appendix <ref>, it is clear that the superposition coding only 
region of (<ref>) is contained in (<ref>) because we can just set all the split rates to zero in (<ref>) and (<ref>). Hence, for the classes of channels for which region (<ref>) is optimal as given by the three cases of Theorem <ref>, the rate region of Theorem <ref> reduces to region (<ref>) and is the capacity region. 



Theorem <ref> represents one generalization of the achievability scheme proposed for K=3 and L=1 in <cit.>. Other generalizations are possible. Most generally, one can split the private message into 2^K-L parts as was done by the authors in <cit.>. However, a key feature of the scheme in Theorem <ref> is that the reliability conditions in split-rate space have a structure that allows us to analytically project away the split rates using the FME method to get a closed-form expression for the polygonal achievable rate region. This then sets the stage for proving converse results for new classes of DM BCs as in Theorem <ref> to follow. Whereas, projecting away exponentially many split rates for the scheme in <cit.> doesn't appear to lend itself to an explicit description for general K and L. The “brute-force" FME procedure, though tedious, can however be done when K-L ≤ 2 <cit.>.  



The authors in <cit.> showed that indirect decoding is unnecessary in the K=3,L=1 case. This raises the question of whether the achievable rate region of Theorem <ref> remains unchanged if the common receivers employed unique decoding[This question is addressed by Proposition <ref> in Appendix <ref> in the more limited context of Corollary <ref> of Theorem <ref> to follow.]. Note however that the structure of the inequalities for non-unique decoding was used to project away the split rates to prove Theorem <ref>. Hence, even if non-unique decoding is unnecessary in Theorem <ref>, it is unclear if the (greater number of) inequalities for unique decoding would lend themselves to analytically eliminating split rates. Moreover, even if this were possible, the explicit description of the polygonal rate regions in that inner bound may have a description that could render proving the converse result of Theorem <ref> (to follow) intractable. 












Next, we provide three examples of achievable rate regions resulting from Theorem <ref>. 







Consider the smallest non-trivial case K=3, L=1 which was studied previously in <cit.>. If we specialize the region (<ref>) to it, we get the region of rate pairs

    R_0≤   min{I(U_3;Y_3),I(U_2,Y_2)}
    
    R_1≤    I(X;Y_1|U_3) 
    
    R_0+R_1   ≤ I(X;Y_1|U_2)+I(U_2;Y_2)
    
    R_0+R_1   ≤ I(X;Y_1)

for some U_3  U_2  X.

The above region, when further specialized to the class of DM BCs for which Y_3 ≺ Y_1, is equivalent to that in <cit.>. 




Consider a case where K=4 and L=1. For this case, we get from (<ref>) that the set of rates for which

    R_0   ≤min{I(U_4;Y_4),I(U_3,Y_3),I(U_2,Y_2)}
    
    R_1   ≤ I(X;Y_1|U_4) 
    
    R_0+R_1   ≤min{I(X;Y_1|U_2)+I(U_2;Y_2), I(X;Y_1|U_3)+I(U_3;Y_3)}
    
    R_0+R_1   ≤  I(X;Y_1)

for some U_4  U_3  U_2  X is achievable.





Consider next K=4 and L=2. For this case, we get from (<ref>) that the set of rates for which

    R_0   ≤min{I(U_4;Y_4),I(U_3,Y_3)}
    
    R_1   ≤min{I(X;Y_1|U_4),I(X;Y_2|U_4) }
    
    R_0+R_1   ≤min{I(X;Y_1|U_3),I(X;Y_2|U_3)}+I(U_3;Y_3)
    
    R_0+R_1   ≤min{ I(X;Y_1),I(X;Y_2)}

for some U_4  U_3  X is achievable.



The optimality of the regions in Examples <ref>-<ref> for classes of channels beyond those described by 

Theorem <ref> is addressed in Theorem <ref> in the next section. Example <ref> is further discussed in Section <ref>.



 §.§ Simple Rate-Splitting and A Converse



Next, Theorem <ref> is specialized by splitting the private message into two parts instead of K-L parts. Consequently, the resulting rate region is shown to be the capacity region for several classes of DM BCs using the information inequality and the Csiszar sum lemma in the proof of the converse. A discussion of the 
apparent insufficiency of these inequalities for proving a converse for more than two rate splits is given in Section <ref>.

With just two split rates, the most general scheme is one in which one group of common receivers decodes the common message indirectly while the rest of the common receivers decode it directly. 




Fix l ∈ [L+1 : K]. Partition the common  receivers into the two groups 𝒞_1 =  {L+1,..,l} and 𝒞_2 = {l+1,..,K}. 
Then, the set of rate pairs (R_0,R_1) satisfying  

    R_0   ≤min{ I(U_l ; Y_c_1), I(U_K;Y_c_2},  c_1∈𝒞_1   c_2 ∈𝒞_2 
    
    R_1   ≤ I(X;Y_s|U_K),  s∈𝒮
    
    R_0+R_1   ≤ I(X;Y_s|U_l)+I(U_l ; Y_c_1),  c_1 ∈𝒞_1   s∈𝒮
    
    R_0+R_1   ≤ I(X;Y_s),    s∈𝒮
 for some U_K U_l X is achievable.

 We specialize the proof of Theorem <ref> in Appendix <ref> by splitting the private message into just two parts so that R_1=R_11+R_1l (i.e., set R_1,j=0 ∀ j∈𝒞\{l,K}[Note that R_1K is always equal to zero (<ref>).]). The region described in (<ref>) hence follows by eliminating the single split rate variable using FME, a simpler task than the proof in Appendix <ref>. 

Hence, when l ∈ [L+1 : K-1], to achieve the region (<ref>) the common receivers 
in 𝒞_1 find the common message indirectly by decoding U_l while those in 𝒞_2 find M_0 directly by decoding U_K. Evidently, the variable l controls the numbers of common receivers that decode M_0 directly and indirectly. When l=K, there is no rate-splitting. Here, all common receivers decode the common message directly from U_K so that we just get the rate region of (<ref>) due to superposition coding alone. 









Let l ∈ [L+1 : K] and partition the common  receivers into 𝒞_1 =  {L+1,..,l} and 𝒞_2 = {l+1,..,K}.
Consider the class of channels, shown in Fig <ref>, for which there exists a j ∈𝒞_1 such that  Y_j ≺  Y_c_1 for all c_1 ∈𝒞_1 \{j} and a r ∈𝒮 such that Y_r ≼ Y_s ∀ s ∈𝒮\{r}, and Y_c_2≺  Y_r  ∀ c_2 ∈𝒞_2. For this class of channels,
 the union of rate pairs (R_0,R_1) satisfying 

    R_0   ≤min{ I(U_l ; Y_j), I(U_K;Y_c_2}  c_2 ∈𝒞_2 
    
    R_1   ≤ I(X;Y_r|U_K)  
    
    R_0+R_1   ≤ I(X;Y_r|U_l)+I(U_l ; Y_j) 
     
    R_0+R_1   ≤ I(X;Y_r)
 
for some U_K U_l X is the capacity region.





 The proof of achievability can be deduced from Corollary <ref> by removing the redundant inequalities in (<ref>) for the class of channels under consideration in this theorem. 


The proof of converse for the first two inequalities of (<ref>) follow the same technique (which depends on the information inequality) as that in Theorem <ref>. The last inequality is straightforward. The only non-trivial inequality is the third one. We show that the optimal identification of the auxiliary random variables is U_Ki=M_0Y_r,1^i-1 and U_li=M_0Y_r,1^i-1Y_j,i+1^n. To prove the third inequality, observe that for any sequence of (2^nR_0, 2^nR_1, n) codes with lim_n →∞ P_e^(n) = 0, we have

    n (R_0+R_1)   =H(M_0)+H(M_1) 
       ≤ I(M_0;Y_j^n)+ I(M_1;M_0,Y_r^n)+ n ϵ_n 
     
       =∑_i=1^n  I(M_0;Y_j,i|Y_j,i+1^n)  
        
    +  ∑_i=1^n I(M_1;Y_r,i|M_0,Y_r,1^i-1) +n ϵ_n
    
       ≤∑_i=1^n I(M_0,Y_j,i+1^n;Y_j,i) 
       +  ∑_i=1^n I(M_1;Y_r,i|M_0,Y_r,1^i-1) +n ϵ_n 
       ≤∑_i=1^n I(M_0,Y_r,1^i-1,Y_j,i+1^n;Y_j,i) 
       - ∑_i=1^n I(Y_r,1^i-1;Y_j,i|M_0,Y_j,i+1^n) 
       +∑_i=1^n I(M_1;Y_r,i|M_0,Y_r,1^i-1,Y_j,i+1^n) 
        + ∑_i=1^n I(Y_j,i+1^n;Y_r,i|M_0,Y_r,1^i-1) 
    +n ϵ_n 
       =∑_i=1^n I(M_1;Y_r,i|M_0,Y_r,1^i-1,Y_j,i+1^n) 
       + ∑_i=1^n I(M_0,Y_r,1^i-1,Y_j,i+1^n;Y_j,i)+n ϵ_n 
       ≤∑_i=1^n I(X_i;Y_r,i|U_l,i)+I(U_l,i;Y_j,i)+n ϵ_n


where (<ref>) follows from Fano's inequality, the chain rule and non-negativity of conditional mutual information, and (<ref>) from chain rule for mutual information and the independence between M_1 and M_0. Inequality (<ref>) also follows from the chain rule, and (<ref>) is due to the Csiszar sum lemma. Now letting Q∈{1,2,...,n} to be a uniformly distributed random variable independent of all other random variables and defining U_K=(U_K,Q,Q), U_l=(U_l,Q,Q), and X=X_Q, the converse proof can be completed in the standard way. Note that we have U_KU_lX since U_l= (U_K,Y_j,i+1^n).











For each l ∈ [L+1:K-1], Theorem <ref> provides a distinct achievability region and establishes its capacity optimality for an associated distinct class of channels. Consequently, the general inner bound of Theorem <ref> is tight for the K-L-1 classes of channels characterized by each l ∈ [L+1:K-1]. When l=K, Theorem <ref> recovers Case (iii) of Theorem <ref>.


The following examples illustrate the effect of varying l on the capacity region and the class of channels for which capacity is achieved. 



Consider K=4 and L=1 and each of the three choices of l∈{2,3,4}. 

Let l=K=4 first. Theorem <ref> should reduce to Case (iii) of Theorem <ref>. Indeed, we get the result that the set of rate pairs (R_0,R_1) satisfying

    R_0   ≤ I(U_4;Y_4)
    
    R_1    ≤ I(X;Y_1|U_4)
    
    R_0+R_1   ≤ I(X;Y_1)

for some p(u_4,x) is the capacity region when Y_2≻ Y_4 and Y_3≻ Y_4 (without loss of generality, we let j=4 in Theorem <ref>). Assuming that receiver Y_4 is more noisy than the other two common receivers essentially boils the problem down to the two-receiver problem in which only receivers Y_1 and Y_4 are present. Indeed, the region in (<ref>) is the Korner-Marton region for the two-receiver DM BC (with receivers (Y_1, Y_4)) with no restriction between their channels.

Consider next the case of l=3. Theorem <ref> asserts that the union of rate pairs (R_0,R_1) satisfying

    R_0   ≤min{I(U_3;Y_3),I(U_4;Y_4)}
    
    R_1    ≤ I(X;Y_1|U_4)
    
    R_0+R_1   ≤ I(X;Y_1|U_3)+I(U_3;Y_3)

for some U_4 U_3  X is the capacity region when Y_1≻ Y_4 and Y_2≻ Y_3, (without loss of generality, we take j=3 in Theorem <ref>). The above region is hence the same as that in <cit.> for the three-receiver problem with receivers (Y_1,Y_3,Y_4) with the single restriction Y_1≻ Y_4. The rationale behind this is that when l=3, receivers Y_2 and Y_3 decode M_0 indirectly from U_2. But since Y_2≻ Y_3, only the weaker receiver Y_3 matters since Y_2 can decode M_0 if Y_3 can, essentially reducing the problem to the three-receiver case with receivers Y_1,Y_3 and Y_4.


When l=2, we get from Theorem <ref> that the capacity region for the class of channels under the restrictions Y_1≻ Y_3,Y_1≻ Y_4 is the rate pairs (R_0,R_1) satisfying

    R_0   ≤min{I(U_2;Y_2),I(U_4;Y_3),I(U_4;Y_4)}
    
    R_1    ≤ I(X;Y_1|U_4)
    
    R_0+R_1   ≤ I(X;Y_1|U_2)+I(U_2;Y_2)

for some U_4 U_2 X. Note that the last inequality in (<ref>) is redundant. Hence, the above result can be seen as a generalization of <cit.> from K=3 to K=4. 
 




Consider next the case of K=6 and L=1. Here, consider l∈{2,3,4,5}. 

The classes of channels for these l for which Theorem <ref> gives the capacity region are depicted in Fig. <ref>. For l=2, Fig. <ref> represents the conditions Y_1 ≻ Y_i for i∈{3,4,5,6}. For l=3 and j=3 in Theorem <ref>, Fig. <ref> represents the conditions Y_1 ≻ Y_i for i∈{4,5,6} and Y_2≻ Y_3. For l=4 and j=4, Fig. <ref> represents the conditions Y_1 ≻ Y_i for i∈{5,6} and Y_k≻ Y_4 for k∈{2,3}. Finally, for l=5 and j=5, Fig. <ref> represents the conditions Y_1 ≻ Y_6 and Y_k≻ Y_5 for k∈{2,3,4}. 


The case l=L+1 of Theorem <ref> deserves explicit mention, which we state as a corollary.










For the class of DM BCs with two nested multicast messages 
defined by the restrictions that ∃ r ∈𝒮 
such that Y_r ≼ Y_s ∀ s  ∈𝒮\{r} and also Y_c ≺  Y_r ∀ c∈𝒞\{L+1 }, the union of rate pairs (R_0,R_1) satisfying 

    R_0≤min{I(U_K;Y_c),I(U_L+1 ; Y_L+1)} ∀ c∈𝒞\{L+1 }
       R_1≤ I(X;Y_r|U_K)  
       R_0+R_1≤ I(X;Y_r|U_L+1)+I(U_L+1 ; Y_L+1)
 for some U_K U_L+1 X is the capacity region.   


 The proof follows directly from Theorem <ref> by setting l=L+1. Note that the last inequality in (<ref>) becomes redundant since the sum of the first two inequalities in (<ref>) gives a more restrictive condition on the sum-rate.











The class of channels for which Corollary <ref> gives capacity is depicted in Fig. <ref>. Comparing it with Fig. <ref>, it is evident that it represents a strictly larger class of channels than that of Case (i) of Theorem <ref> since the restriction Y_L+1≺  Y_r is not needed. 


Examples <ref>, <ref> and the l=2 cases of Examples <ref> and <ref> are  evidently examples of Corollary <ref>. In particular, according to Corollary <ref> the achievable rate region of Example <ref> (with K=3 and L=1) when Y_3 ≺ Y_1 (the last inequality in (<ref>) becomes redundant under this condition) is the capacity region under that condition. This result was first obtained in <cit.>. Corollary <ref> can thus be seen as one extension of <cit.>. Note also that unlike the converse proof of <cit.> which uses the Csiszar sum lemma, the converse proof of Corollary <ref> uses the Csiszar sum lemma and the information inequality, which together allows us to prove the more general result of Corollary <ref>.



The authors in <cit.> showed that indirect decoding is unnecessary in the K=3,L=1 case of Example <ref>. This raises the question of whether or not the achievable rate region of Corollary <ref> remains unchanged if the common receiver Y_L+1 employed unique decoding. This question is answered in the affirmative by Proposition <ref> in Appendix <ref>. Note that in <cit.>, it was shown that the region obtained by non-unique decoding turned out to be equivalent to that of unique decoding in <cit.> in the context of the two-user interference channel. The result of Proposition <ref> amplifies somewhat the main message of <cit.>, which details other instances where indirect (or non-unique) decoding does not lead to a strict enlargement of the rate region over that with unique decoding. 


















We noted in the l=3 case of Example <ref> in which K=4 and L=1 that under the restrictions of Theorem <ref> that the capacity region reduces to that of a three-receiver DM BC with appropriately chosen receivers. The next corollary shows this aspect of Theorem <ref> for general K and L.



For the class of DM BCs with two nested multicast messages defined by the restrictions that ∃ j ∈{L+1,⋯, K-1} such that Y_j ≺ Y_c ∀ c  ∈{L+1,⋯, K-1}\{j} and ∃ r ∈𝒮 such that Y_r ≼ Y_s ∀ s  ∈𝒮\{r} and Y_K≺ Y_r, the union of rate pairs (R_0,R_1) satisfying 

    R_0≤min{I(U_K-1 ; Y_j), I(U_K;Y_K)}
       R_1≤ I(X;Y_r|U_K)  
       R_0+R_1≤ I(X;Y_r|U_K-1)+I(U_K-1;Y_j)
 for some U_K  U_K-1 X is the capacity region.   

 The proof follows from Theorem <ref> by setting l=K-1. A direct proof of this result is to consider the embedded three-receiver DM BC with the critical receivers Y_r, Y_j and Y_K (for which the conditions of the corollary on the channels implies a single condition Y_K≺ Y_r). Under this restriction the region of (<ref>) is the capacity region of this three-receiver DM BC. Since adding receivers can't enlarge the capacity region and since the region (<ref>) is also achievable in the K-receiver case, it must be the capacity region for the the K-receiver problem. 



Note that Corollary <ref> gives a region that is equivalent to that in <cit.> for the three critical receivers (Y_K,Y_j,Y_r). The rationale behind this is as follows: when l= K-1, only receiver Y_K decodes M_0 directly from U_K. The rest of common receivers Y_c where c  ∈{L+1,⋯, K-1} decode  M_0 indirectly from U_K-1. Now, the assumed restriction that receiver Y_j is more noisy than each of these other common receivers means that if receiver Y_j can decode the common message successfully, so can all those other common receivers. A similar argument can also applied to the private receivers since there is one private receiver that is less capable than all other private receivers.  


Theorem <ref> can thus be seen as unifying and generalizing (for general K and L) the important capacity results of Korner and Marton <cit.> for K=2 and L=1 and of Nair and El Gamal <cit.> for K=3 and L=1. As stated previously, the converse proof of Theorem <ref> uses both the Csiszar sum inequality and the information inequality. Can these inequalities be used to further expand the classes of channels for which capacity can be found by using the greater generality of Theorem <ref> which involves more than two rate splits for the private message?




 §.§ More Than Two Rate Splits: A Discussion



In this section, we consider the K=4 and L=1 example and the rate region achievable according to Theorem <ref> given in (<ref>). That rate region involves splitting the private message into three sub-messages. We highlight the technical difficulty of proving a converse result for this region next.


Given that the capacity region for K=3,L=1 is only known when Y_1≻ Y_3 in <cit.>, we expect that at least one less noisy condition is required to establish the converse proof for the region in (<ref>) for K=4,L=1. Thus, let us assume that Y_1≻ Y_4. The last inequality in (<ref>) is redundant in this case. By using the information inequality as in Case (i) of Theorem <ref>, we can prove the converse for the first part of the first inequality (i.e., R_0 ≤min{I(U_4;Y_4)) as well as the second inequality in (<ref>) by letting U_4i=M_0,Y_1,1^i-1. 
Next, since the Csiszar sum lemma does not require any restrictions on the channel, we can use it to prove the converse for the rest of the first inequality and the third inequality in (<ref>) where 
the “right" choice of the auxiliary random variables would be U_2i=M_0Y_1,1^i-1Y_2,i+1^n and U_3i=M_0Y_1,1^i-1Y_3,i+1^n. This choice does not however match the Markov structure of the auxiliary random variables since we do not assume that Y_3 is a degraded version of Y_2. Moreover, there is no useful generalization of Csiszar sum lemma for K>2 that could be used to choose U_2i=M_0Y_1,1^i-1Y_2,i+1^nY_3,i+1^n, for instance, that satisfies the Markov structure of the auxiliary random variables. Due to this limitation, we have to add one more less noisy condition (Y_1≻ Y_3) that then allows us to use the information inequality instead. Hence, having the conditions Y_1≻ Y_4 and Y_1≻ Y_3 in hand, we can prove the converse for K=4,L=1 using a combination of the information inequality and Csiszar sum lemma. More precisely, the Csiszar sum lemma is used to choose U_2i=M_0Y_1,1^i-1Y_2,i+1^n and the information inequality is used to choose U_3i=M_0Y_1,1^i-1 (given Y_3 ≺ Y_1) and U_4i=M_0Y_1,1^i-1 (given Y_4 ≺ Y_1). Note hence that U_3i=U_4i. This means that when we assume Y_1≻ Y_4 and Y_1≻ Y_3 we only need two auxiliary random variables instead of three, so that having only two split rates instead of three suffice to prove the converse which gets us back to Theorem <ref>. We finally note that the region in (<ref>) for K=4,L=1 may not be optimal for channels with just a single restriction Y_1≻ Y_4, especially given the limited form of rate-splitting considered in Theorem <ref>. A more general rate splitting strategy as in <cit.> may have to be considered to find capacity for a class of channels less restrictive than the ones that satisfy Y_1≻ Y_4 and Y_1≻ Y_3. Such problems are of future interest.











§ CONCLUSION



K-user DM BCs with two nested multicast messages were studied in which one message is to be sent to all receivers and another to a subset of L private receivers. The capacity region  was established for several classes of channels. We showed that a natural extension of Korner-Marton region for K-user DM BC, which is achievable by superposition coding with successive or joint decoding at the private receivers, is capacity optimal for a larger class of channels than previously found for K ≥ 3 in the two cases in which there is either one private receiver or one common receiver. For the general case of L private receivers, we obtain new classes of DM BCs for which the natural extension of Korner-Marton region with superposition coding is capacity optimal. Moreover, we obtain a new inner bound in explicit form that uses rate splitting, superposition coding and indirect decoding. The general form of rate-splitting we consider splits the private message into as many parts as there are common receivers. Particular specializations of it in which the private message is split into just two sub-messages and some subset of common receivers employ indirect decoding is shown to be optimal for several new classes of DM BCs. 














§ PROOF OF THE CONVERSE FOR THEOREM <REF>

   

For Case (i) and Case (ii), the converse proof is based on the information inequality and is given next. In particular, we show that for every sequence of (2^nR_0, 2^nR_1, n) codes with lim_n →∞ P_e^(n) = 0 the inequalities in (<ref>) or the inequalities in (<ref>) hold for some p(u,x) for which U  X  (Y_1,Y_2, ⋯ , Y_K).


Consider case (i), i.e., the class of channels for which ∃ a r ∈𝒮 such that Y_r ≼ Y_s ∀ s∈𝒮\{r} and Y_c ≺  Y_r ∀ c∈𝒞.
For the first inequality in (<ref>) in Case (i), for each c∈𝒞, we have

    nR_0   = H(M_0) 
       ≤ I(M_0;Y_c^n) + n ϵ_n  
        = ∑_i=1^n I(M_0;Y_c,i|Y_c,1^i-1) + n ϵ_n 
       ≤∑_i=1^n I(M_0,Y_c,1^i-1;Y_c,i) + n ϵ_n 
       ≤∑_i=1^n I(M_0,Y_r,1^i-1;Y_c,i) + n ϵ_n  
       =  ∑_i=1^n I(U_i;Y_c,i) + n ϵ_n

where (<ref>) follows from Fano's inequality (with  lim_n →∞ϵ_n = 0), (<ref>) and (<ref>) from chain rule and non-negativity of mutual information, (<ref>) follows from an information inequality of Lemma <ref> because Y_c ≺ Y_r, and (<ref>) by defining U_i=M_0,Y_r,1^i-1 which satisfies U_i  X_i  (Y_r,i,Y_c,i).

The rest of the proof proceeds along standard lines. Define a time-sharing uniform random variable Q over [1:n] that is independent of all other involved random variables. Identify U=(U_Q,Q) and Y_c=Y_cQ and take the limit as n →∞, so that ϵ_n → 0, to get the first inequality in (<ref>).

To prove the second inequality in (<ref>), we have 

    nR_1   = H(M_1) 
    
       ≤ I(M_1;M_0, Y_r^n)+ n ϵ_n  
        = ∑_i=1^n I(M_1;Y_r,i|M_0 Y_r,1^i-1) + n ϵ_n  
       ≤∑_i=1^n I(X_i;Y_r,i|U_i) + n ϵ_n 
        = n I(X_Q;Y_r,Q|U_Q, Q) + n ϵ_n

where 

(<ref>) follows from Fano's inequality, (<ref>) from the independence of M_0 and M_1 and the chain rule for mutual information, (<ref>) from the definition of U_i, and (<ref>) by introducing the time-sharing random variable. Identify X=X_Q,Y_r=Y_r,Q so that U X (Y_r,Y_c) and take the limit as n →∞, to obtain (<ref>).

Consider Case (ii), i.e., the class of channels for which ∃ a j ∈𝒞 such that Y_j ≺  Y_c ∀ c ∈𝒞\{j} and Y_j ≺  Y_s  ∀ s ∈𝒮. For the first inequality in (<ref>), follow the steps leading to (<ref>) to obtain

    nR_0   =H(M_0) 
    
    
             ≤∑_i=1^n I(M_0,Y_j,1^i-1;Y_j,i) + n ϵ_n  
        = ∑_i=1^n I(U_i;Y_j,i) + n ϵ_n

where 
(<ref>) follows by defining U_i=M_0,Y_j,1^i-1, which satisfies U_i X_i  (Y_s,i,Y_j,i). 

To obtain the second inequality in (<ref>), note that for any s∈𝒮, following the steps leading 
to (<ref>), we have the first inequality below:

    nR_1    ≤∑_i=1^n I(M_1;Y_s,i|M_0 Y_s,1^i-1) + n ϵ_n  
       =∑_i=1^n I(M_1,Y_s,1^i-1;Y_s,i|M_0)  -I(Y_s,1^i-1;Y_s,i|M_0) +  n ϵ_n 
       ≤∑_i=1^n I(X_i;Y_s,i|M_0 )  -I(Y_s,1^i-1;Y_s,i|M_0) + n ϵ_n 
       ≤∑_i=1^n I(X_i;Y_s,i|M_0 )-I(Y_j,1^i-1;Y_s,i|M_0) + n ϵ_n 
       ≤∑_i=1^n I(X_i;Y_s,i|M_0, Y_j,1^i-1) + n ϵ_n 
       =∑_i=1^n I(X_i;Y_s,i|U_i) + n ϵ_n

where (<ref>) follows from the chain rule for mutual information, (<ref>) and (<ref>) from data processing inequality and that (M_0,M_1,Y_s,1^i-1,Y_j,1^i-1)  X_i Y_s,i. The inequality (<ref>) follows from an information inequality of Lemma <ref>, since Y_j ≺ Y_s, and (<ref>) from the definition of U_i. To complete the proof, we adopt the steps from (<ref>) to (<ref>), i.e., define a time-sharing uniform random variable Q over [1:n] that is independent of all other random variables, and identify U=(U_Q,Q), X=X_Q, Y_s=Y_s,Q, and Y_j=Y_j,Q (so that U  X  Y_s) to obtain (<ref>).







§ PROOF OF THEOREM 
<REF>

   
The following lemmas are used later in the proof of Theorem <ref>. They may also be of independent interest.



Consider the following set of inequalities for  R_0, R_1, and any integers 1≤ k≤ K-1 and K≥ 2

    R_0+∑_j=c^KR_1j   ≤  I(U_c;Y_c)  c∈{k,...,K}
    
     R_1-∑_j=c^KR_1j   ≤  I(U;Y|U_c) c∈{k,...,K}
    
     -R_1+∑_j=k^K R_1j   ≤ 0 
    
     -R_1c   ≤ 0  c∈{k,...,K}
 
where U_K U_K-1⋯ U_k U (Y_K,Y_K-1...,Y_k,Y) forms a Markov chain. Let k≤ l ≤ K-1. By projecting away the l-k+1 “split rate" variables (R_1k,R_1k+1,...,R_1l), we get the following polytope

    R_0+R_1  ≤ I(U;Y|U_c)+I(U_c;Y_c)  c∈{k,k+1,..,l}
        R_0+∑_j=l+1^K R_1j≤ I(U_c;Y_c)  c∈{k,k+1,..,l}
       R_0+∑_j=c^KR_1j≤  I(U_c;Y_c)  c∈{l+1,l+2.,..,K}
       R_1-∑_j=c^KR_1j≤  I(U;Y|U_c) c∈{l+1,l+2,...,K}
       -R_1+∑_j=l+1^K R_1j≤ 0 
       -R_1c≤ 0  c∈{l+1,...,K}

 The proof uses mathematical induction and the FME method to sequentially eliminate R_1j, j∈{k,k+1,..,l} and is given in Appendix <ref>. 
 



In the above lemma, we start with a polytope that consists of K-k+1 split rate variables described in (<ref>)-(<ref>). By projecting out the first l-k+1 of them we get the polytope in smaller dimension described in (<ref>)-(<ref>). Note that the set of inequalities in (<ref>)-(<ref>) looks similar to that in (<ref>)-(<ref>) with the only difference being that the index c belonging to {l+1,...,K} instead of {k,....,K}. On the other hand, the inequalities in (<ref>) and (<ref>) emerge due to the projection.






Consider the polytope of admissible rate pair (R_0, R_1) described by (<ref>)-(<ref>) in Lemma <ref> but allowing k ≤ l ≤ K under the Markov chain relation stated therein.







Its projection onto the (R_0,R_1) plane is the polygon described by the following inequalities

    R_0+ R_1 ≤I(U;Y|U_c) + I(U_c;Y_c)
       R_0≤  I(U_c;Y_c)  c∈{k,..,K}

 The proof is divided into two steps. 

From Lemma <ref>, by setting l=K-1, we get 

    R_0+R_1  ≤ I(U;Y|U_c)+I(U_c;Y_c)  c∈{k,k+1,..,K-1}
        R_0+ R_1K≤ I(U_c;Y_c)  c∈{k,k+1,..,K-1}
       R_0+ R_1K≤  I(U_K;Y_K)  
       R_1-R_1K≤  I(U;Y|U_K) 
       -R_1+R_1K≤ 0 
       -R_1K≤ 0

Next, using FME, we project out the last split rate R_1K.  

Note that the first set of inequalities (<ref>) does not contain R_1K, so that it will still the same after projecting out R_1K. Using FME, from (<ref>) and (<ref>), we get

    R_0+R_1 ≤ I(U;Y|U_K)+I(U_c;Y_c) c∈{k,k+1,..,K-1}

Given (<ref>), these inequalities are redundant since I(U;Y|U_K) ≥ I(U;Y|U_c) ∀ c∈{k,..,K-1}, a consequence of U_K U_K-1⋯ U_k U (Y_K,Y_K-1,...,Y_k,Y).

Again, using FME, projecting out R_1K from (<ref>) and (<ref>), we get 

    R_0≤ I(U_c;Y_c)  c∈{k,k+1,..,K-1}.

Finally, by projecting R_1K from (<ref>) and (<ref>), we have

    R_0+R_1≤ I(U;Y|U_K)+I(U_K;Y_K).

and from (<ref>) and (<ref>) to get

    R_0 ≤ I(U_K;Y_K).

Now, (<ref>), (<ref>), (<ref>) and (<ref>) together constitute the region in (<ref>). 

 


We now return to the proof of Theorem <ref>. The achievability scheme depends on superposition coding with rate splitting and indirect decoding. In particular, we split the private message M_1 into K-L parts, with one part M_11 with rate R_11 to be decoded only by the private receivers and a part for every common receiver except Y_K, denoted M_1c, with rate R_1c (c ∈𝒞\{K}). Fix a distribution p(u_K)∏_i=L+1^K-1p(u_i|u_i+1)p(x|u_L+1). Generate 2^nR_0 codewords u_K^n(m_0) according to ∏_i=1^n p(u_Ki). For each u_0^n(m_0), generate 2^nR_1K-1 codewords  u_K-1^n(m_0, m_1K-1) according to ∏_i=1^n p(u_K-1i|u_Ki). Then, for every u_c^n(m_0,m_1  K-1,...,m_1  c) where c ∈𝒞\{K,L+1}, generate 2^nR_1 c-1 codewords u_c-1^n (m_0, m_1K-1,...,m_1  c-1) according to ∏_i=1^n p(u_c-1i|u_ci). Finally, for every u_L+1^n(m_0 , m_1  K-1 ,...,m_1  L+1), generate 2^nR_11 codewords  x^n (m_0, m_1) according to ∏_i=1^n p(x_i|u_L+1i). To send (M_0,M_1), the sender expresses M_1 as (M_1 K-1,..,M_1 L+1, M_1 1) and sends x^n (m_0 , m_1 K-1 ,...,m_1 L+1 ,m_1 1). 

Receiver Y_K finds M_0 if there is a unique index such that u_K(m_0) and y_K^n are jointly typical. This happens with probability of correct decoding approaching unity as long as 

    R_0≤ I(U_K;Y_K)
The rest of the common receivers Y_c (c∈{L+1,...,K-1}) find M_0 by indirectly decoding U_c. It is not difficult to show that this decoding succeeds with high probability as long as

    R_0+∑_j=c^K-1R_1j≤  I(U_c;Y_c)  c∈{L+1,...,K-1}
 Finally, all private receivers find M_0,M_1 by decoding X. It can be shown that his happens successfully with high probability as long as the following inequalities hold:  

    R_1≤   I(X;Y_s|U_K)   s∈𝒮
      R_1-∑_j=c^K-1R_1j≤    I(X;Y_s|U_c)   c∈{L+1,...,K-1},s∈𝒮
    R_0+ R_1≤    I(X;Y_s)  s∈𝒮
 At this point, we need to eliminate the split rates from the sets of inequalities in (<ref>) and (<ref>)
and the inequalities 

    -R_1+∑_j=L+1^K-1 R_1j≤ 0 
       -R_1c≤ 0  c∈{L+1,...,K-1}

that guarantee that all split rates are positive to obtain the achievable region of Theorem <ref>.


The polytope described by (<ref>), (<ref>), (<ref>) and (<ref>) can be seen as an intersection of L  constituent polytopes, each corresponding to s ∈𝒮. In order to obtain the projection onto the (R_0, R_1) plane of that intersection, we apply Lemma <ref> to each constituent polytope and then take the intersection of the L resulting polygons.

For each s ∈𝒮, we project the polytope described by (<ref>), (<ref>), (<ref>) and (<ref>) onto the two-dimensional plane (R_0,R_1), using Lemma <ref> (by setting U=X, Y=Y_s and k=L+1 therein) to obtain for each s∈𝒮,

    R_0+ R_1 ≤I(X;Y_s|U_c) + I(U_c;Y_c)
       R_0≤  I(U_c;Y_c)  c∈{L+1,L+2,...,K-1}







Thus, the above inequalities for all s∈𝒮 together with (<ref>), (<ref>), and (<ref>) describe the achievability region in (<ref>), completing the proof of Theorem <ref>.
     
   


§ PROOF OF LEMMA  <REF>

    

We prove Lemma <ref> by mathematical induction. 


We begin by showing the initial case of l=k using FME to project out R_1k from the set of inequalities in (<ref>)-(<ref>). We rewrite these inequalities to emphasize those that contain R_1k as follows 

    R_0+R_1k+∑_j=k+1^KR_1j≤  I(U_k;Y_k) 
       R_0+∑_j=c^KR_1j≤  I(U_c;Y_c)  c∈{k+1,...,K}
       R_1- R_1k-∑_j=k+1^KR_1j≤  I(U;Y|U_k)
       R_1-∑_j=c^KR_1j≤  I(U;Y|U_c) c∈{k+1,...,K}
       -R_1+R_1k+∑_j=k+1^K R_1j≤ 0 
        -R_1k≤ 0 
        -R_1c≤ 0  c∈{k+1,...,K}
 
In the the above inequalities, only (<ref>),(<ref>), (<ref>), and (<ref>) contain R_1k. 

By eliminating R_1k from (<ref>) and (<ref>), we have 

    R_0+R_1≤ I(U;Y|U_k)+I(U_k;Y_k)

and from (<ref>) and (<ref>) we get 

    R_0+∑_j=k+1^KR_1j≤  I(U_k;Y_k)

Finally, we project away R_1k from (<ref>) and (<ref>) to get

    -R_1+∑_j=k+1^K R_1j≤ 0

Now consider (<ref>)-(<ref>) together with (<ref>), (<ref>) and (<ref>). These inequalities together form the polytope defined by (<ref>)-(<ref>) with l=k. Thus the lemma is true for l=k.










Next, consider the induction hypothesis that the lemma is true for l=i for some  K=1 ≤ i ≤ K-2. 
In other words, by projecting ways the split rates R_1k,..,R_1i, we have

    R_0+R_1  ≤ I(U;Y|U_c)+I(U_c;Y_c)  c∈{k,k+1,..,i}
        R_0+∑_j=i+1^K R_1j≤ I(U_c;Y_c)  c∈{k,k+1,..,i}
       R_0+∑_j=c^KR_1j≤  I(U_c;Y_c)  c∈{i+1,i+2.,..,K}
       R_1-∑_j=c^KR_1j≤  I(U;Y|U_c) c∈{i+1,i+2,...,K}
       -R_1+∑_j=i+1^K R_1j≤ 0 
       -R_1c≤ 0  c∈{i+1,...,K}


Next, we show that eliminating R_1i+1 from the above polytope, we obtain a polytope that is given by Lemma <ref> with l=i+1, thus completing its proof. 

Let us rewrite the above sets of inequalities to illustrate the dependence on R_1i+1 as follows:


    R_0+R_1  ≤ I(U;Y|U_c)+I(U_c;Y_c)  c∈{k,k+1,..,i}
        R_0+R_1i+1+∑_j=i+2^K R_1j≤ I(U_c;Y_c)  c∈{k,k+1,..,i}
       R_0+∑_j=c^KR_1j≤  I(U_c;Y_c)  c∈{i+2.,..,K}
       R_0+ R_1i+1+∑_j=i+2^KR_1j≤  I(U_i+1;Y_i+1) 
       R_1-∑_j=c^KR_1j≤  I(U;Y|U_c) c∈{i+2,...,K}
       R_1- R_1i+1-∑_j=i+2^KR_1j≤  I(U;Y|U_i+1)
       -R_1+R_1i+1+∑_j=i+2^K R_1j≤ 0 
       -R_1c≤ 0  c∈{i+2,...,K}
       -R_1i+1≤ 0

The inequalities (<ref>), (<ref>) and (<ref>), give upper bounds on R_1i+1 while  (<ref>) and (<ref>) give lower bounds on R_1i+1. 

By eliminating R_1i+1 from (<ref>) and (<ref>), we have 

    R_0+R_1≤ I(U;Y|U_i+1)+I(U_c;Y_c)  c∈{k,k+1,..,i}
 
From (<ref>), all the inequalities in (<ref>) are redundant since I(U;Y|U_i+1) ≥ I(U;Y|U_c) ∀ c∈{k,k+1,...,i}. This follows form the Markov chain U_K U_K-1⋯ U_i+1 U_i⋯ U_k U (Y_K,Y_K-1,..,Y_i+1,Y_i,..,Y_k,Y).

Then, by projecting R_1i+1 from (<ref>) and (<ref>), we have 

    R_0+∑_j=i+2^K R_1j≤ I(U_c;Y_c)  c∈{k,k+1,..,i}

From (<ref>) and (<ref>), we also eliminate R_1i+1 to get

    R_0+R_1≤ I(U;Y|U_i+1)+I(U_i+1;Y_i+1)

and from (<ref>) and (<ref>), to get

    R_0+∑_j=i+2^KR_1j≤ I(U_i+1;Y_i+1)

Finally, we eliminate R_1i+1 from (<ref>) and (<ref>) to get the redundant inequality 0 ≤ I(U;Y|U_i+1) and from (<ref>) and (<ref>) to get

    -R_1+∑_j=i+2^K R_1j≤ 0


Hence, after projecting away the split rates R_1k,...,R_1i,R_i+1, we get the  polytope 

    R_0+R_1  ≤ I(U;Y|U_c)+I(U_c;Y_c)  c∈{k,..,i+1}
        R_0+∑_j=i+2^K R_1j≤ I(U_c;Y_c)  c∈{k,k+1,..,i+1}
       R_0+∑_j=c^KR_1j≤  I(U_c;Y_c)  c∈{i+2,i+3.,..,K}
       R_1-∑_j=c^KR_1j≤  I(U;Y|U_c) c∈{i+2,i+3,...,K}
       -R_1+∑_j=i+2^K R_1j≤ 0 
       -R_1c≤ 0  c∈{i+2,...,K}

which coincides with that described by ((<ref>)-(<ref>)) in Lemma <ref> for l=i+1, as was to be proved.  Hence, by the principle of mathematical induction, Lemma <ref> is true for any l∈{k,k+1,..,K-1}, thus concluding its proof.



§ IS NON-UNIQUE DECODING NECESSARY?


At this point, we consider the following question: is the improvement in Corollary <ref> over Case (i) in Theorem <ref> due to rate splitting, indirect decoding, or both? In the next proposition, we show that when indirect decoding is replaced with direct decoding there is no loss of achievable rate region. However, the role of rate splitting appears to be essential for Corollary <ref>. 




Indirect decoding is unnecessary in Corollary <ref>. In other words, the result of Corollary <ref> can also be obtained if the common receiver Y_L+1 uses joint (unique) decoding instead of indirect decoding. 



If Y_L+1 uses joint decoding instead of indirect decoding, we get the following achievable rate region 

    R_0≤min{I(U_K;Y_c),I(U_L+1;Y_L+1)}∀ c∈𝒞\{L+1 }
       R_1≤ I(X;Y_r|U_K)
       R_1≤ I(X;Y_r|U_L+1)+I(U_L+1;Y_L+1|U_K)
       R_0+R_1≤ I(X;Y_r|U_L+1)+I(U_L+1;Y_L+1)

for some U_K U_L+1 X. We refer to the above region as the joint decoding region. Recall there r is such that Y_r ≼ Y_s for all s∈𝒮\{r}. We show that the extra inequality (the third one) is redundant by optimizing the choice of U_L+1 given U_K. We have the following two cases.


  * I(U_K;Y_c)≥ I(U_K;Y_L+1) ∀ c∈{L+2,...,K}: In this case, for any U_L+1, R_1 at the corner point of the indirect region can be described as

    R_1^*   =min{I(X;Y_r|U_K),I(X;Y_r|U_L+1)+
       I(U_L+1;Y_L+1)-min{I(U_K;Y_c),I(U_L+1,Y_L+1)}}
       =I(X;Y_r|U_L+1)+min{I(U_L+1;Y_r|U_K), 
       I(U_L+1;Y_L+1)-min{I(U_K;Y_c),I(U_L+1;Y_L+1)}}
       =I(X;Y_r|U_L+1)+min{I(U_L+1;Y_r|U_K),
       I(U_L+1;Y_L+1|U_K)+I(U_K;Y_L+1)-
       min{I(U_K;Y_c),I(U_L+1;Y_L+1)}}
 where (<ref>) and (<ref>) follows from the Markov chain U_K U_L+1 X and the chain rule of the mutual information. 
In this case, 
    min{I(U_K;Y_c),I(U_L+1;Y_L+1)}≤ I(U_K;Y_L+1)

From the above inequality, it is clear that

    R_1^*≤I(X;Y_r|U_L+1)+I(U_L+1;Y_L+1|U_K)

Hence, the extra inequality in the joint decoding region is redundant for any U_L+1 given U_K.

  * I(U_K;Y_c)≤  I(U_K;Y_L+1)  for any c∈ C and C is any subset C ⊆{L+2,...,K}:  equivalently, we have at least one mutual information term I(U_K;Y_c) c∈{L+2,...,K} is less than I(U_K;Y_L+1). Without loss of generality, we can assume that

    min{I(U_K;Y_c)}=I(U_K;Y_t) ≤  I(U_K;Y_L+1) 
    where,
     c∈{L+2,...,K}

The index t exists, since we assumed that we have at least one mutual information term that is less than I(U_K;Y_L+1). For this case, R_1 at the corner point of the indirect region can be written as

    R_1^*   =min{I(X;Y_r|U_K),I(X;Y_r|U_L+1)+
       I(U_L+1;Y_L+1)-I(U_K;Y_t)

Hence, we need to choose U_L+1 given U_K such that 

    I(X;Y_r|U_K)≤I(X;Y_r|U_L+1)+   I(U_L+1;Y_L+1)-
       I(U_K;Y_t)


The optimal choice is to set U_L+1=U_K because I(U_L+1;Y_L+1)≥I(U_K;Y_t). For this choice, indirect decoding and joint decoding again yield the same region. 








The work in <cit.> provides a general achievable rate region for the K-user DM BC with a general message set (any subset of the set of the exponentially many possible messages, one for each subset of receivers). That inner bound is based on a general form of rate-splitting, superposition coding and partial interference (unique) decoding.
In particular, in <cit.>, it was shown that known inner bounds/capacity regions in 2-receiver and 3-receiver BC special cases based on rate-splitting and superposition coding are reproduced by the general inner bound therein. Corollary <ref> and Proposition <ref> imply that the general inner bound in <cit.> when specialized to the K-user DM BC with two nested multicast messages and the particular rate-splitting strategy of Corollary <ref> along with unique decoding as in Proposition <ref> coincides with the capacity region for the new class of DM BCs specified by Corollary <ref>.


















IEEEtran


