The -User DM Broadcast Channel With Two Groupcast Messages: Achievable Rate Regions and the Combination Network as a Case Study

A novel class of achievable rate regions is obtained for the general $K$ -receiver discrete memoryless broadcast channel over which two groupcast messages are to be transmitted, with each message required by an arbitrary group of receivers. The associated achievability schemes are parameterized by an expansion of the message set which then determines how random coding techniques are employed. These techniques include generalized versions of up-set message-splitting, the generation of possibly multiple auxiliary codebooks for certain compositions of split messages using superposition coding with subset inclusion order, partial interference decoding at all receivers in general, joint unique decoding at receivers that desire both messages, and non-unique or indirect decoding at receivers that desire only one of the two messages. The generality of the proposed class of schemes implies new achievable rate regions for problems previously not considered as well as those that were studied before, with specific members of that class having rate regions that coincide with previously found capacity regions for special classes of broadcast channels with two private or two nested groupcast messages, wherein the group of receivers desiring one message is contained in that desiring the other. Moreover, new capacity results are established for certain partially ordered classes of broadcast channels for a class of two non-nested groupcast messages. To further show the strength of the proposed achievable rate regions we consider the so-called combination network as a test case. When specialized to the combination network, some members of the class of inner bounds are shown, via converse results, to result in the capacity region when the two messages are (a) intended for two distinct sets of $K{-}1$ receivers each and (b) nested, in which one message is intended for one or two (common) receivers and both messages are intended for all other (private) receivers. In the latter two nested messages cases, we hence recover, in a top-down manner, previous results by Bidokhti, Prabhakaran, and Diggavi, obtained therein using lower complexity network coding schemes based on rate-splitting and linear superposition coding but tailored to the combination network, while in the first case we obtain a new capacity result for a non-nested message set, which was hitherto unknown. Furthermore, we show the achievability of rate pairs in two interesting examples of combination networks, with three and four common receivers each. These examples were proposed in the previous literature to show the sub-optimality of the aforementioned rate-splitting and linear superposition coding scheme, and hence to motivate the additional consideration of a pre-encoding technique and a block-Markov linear superposition coding for the combination network, with the latter then lifted to the general broadcast channel. Our results suggest that the proposed framework here for the general broadcast channel when specialized to the combination network is strong enough to incorporate the enhancements afforded by those two latter techniques, thereby implying that perhaps block-Markov superposition coding is not necessary in the general broadcast channel. Moreover, there is a trade-off between the complexity of the coding scheme within the class of schemes we propose when applied to the combination network and that of the determination of the distribution of the auxiliary random variables and the encoding function that achieve the capacity region. This may have interesting implications for the general broadcast channel as well.