{'fraction_non_alphanumeric': 0.055868167202572344, 'fraction_numerical': 0.016720257234726688, 'mean_word_length': 4.028698464025869, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Comparison of Superposition Coding Schemes

There are two variants of superposition coding schemes. Cover's original superposition coding scheme has code clouds of the identical shape, while Bergmans's superposition coding scheme has code clouds of independently generated shapes. These two schemes yield identical achievable rate regions in several scenarios, such as the capacity region for degraded broadcast channels. This paper shows that under the optimal maximum likelihood decoding, these two superposition coding schemes can result in different rate regions. In particular, it is shown that for the two-receiver broadcast channel, Cover's superposition coding scheme can achieve rates strictly larger than Bergmans's scheme.


I. INTRODUCTION
Superposition coding is one of the fundamental building blocks of coding schemes in network information theory. This idea was first introduced by Cover in 1970 at the IEEE International Symposium on Information Theory, Noordwijk, the Netherlands, in a talk titled "Simultaneous Communication," and appeared in his 1972 paper [6]. Subsequently, Bergmans [2] adapted Cover's superposition coding scheme to the general degraded broadcast channel (this scheme is actually applicable to any nondegraded broadcast channel), which establishes the capacity region along with the converse proof by Gallager [11]. Since then, superposition coding has been applied in numerous problems, including multiple access channels [12], interference channels [3], [5], [13], relay channels [7], channels with feedback [8], [15], and wiretap channels [4], [9].
In a nutshell, the objective of superposition coding is to communicate two message simultaneously by encoding them into a single signal in two layers. A "better" receiver of the signal can then recover the messages on both layers while a "worse" receiver can recover the message on the coarse layer of the signal and ignore the one on the fine layer.
On a closer look, there are two variants of the superposition coding idea in the literature, which differ in how the codebooks are generated. The first variant is described in Cover's original 1972 paper [6]. Both messages are first encoded independently via separate random codebooks of auxiliary sequences. To send a message pair, the auxiliary sequences associated with each message are then mapped through a symbol-by-symbol superposition function (such as addition) to generate the actual codeword. One can visualize the image of one of the codebooks centered around a fixed codeword from the other as a "cloud" (see the illustration in   Superposition codebooks for which (a) the structure within each cloud is identical and (b) the structure is nonidentical between clouds. Codewords (dots) are annotated by "m1, m2", where m1 is the coarse layer message and m2 is the fine layer message. Figure 1(a)). Since all clouds are images of the same random codebook (around different cloud centers), we refer to this variant as homogeneous superposition coding. Note that in this variant, both messages enter on an equal footing and the corresponding auxiliary sequences play the same role. Thus, there is no natural distinction between "coarse" and "fine" layers and there are two ways to group the resulting superposition codebook into clouds.
The second variant was introduced in Bergmans's 1973 paper [2]. Here, the coarse message is encoded in a random codebook of auxiliary sequences. For each auxiliary sequence, a random satellite codebook is generated conditionally independently to represent the fine layer message. This naturally results in clouds of codewords given each such satellite codebook. Since all clouds are generated independently, we refer to this variant as heterogeneous superposition coding. This is illustrated in Figure 1 A natural question is whether these two variants are fundamentally different, and if so, which of the two is preferable. Both variants achieve the capacity region of the degraded broadcast channel [2]. For the two-user-pair interference channel, the two variants again achieve the identical Han-Kobayashi inner bound (see [13] for homogeneous superposition coding and [5] for heterogeneous superposition coding). Since heterogeneous superposition coding usually yields a simpler characterization of the achievable rate region with fewer auxiliary random variables, it is tempting to prefer this variant.
In contrast, we show in this paper that homogeneous superposition coding always achieves a rate region at least as large as that of heterogeneous superposition coding for twouser broadcast channels, provided that the optimal maximum likelihood decoding rule is used. Furthermore, this dominance can be sometimes strict. Intuitively speaking, homogeneous superposition coding results in more structured interference from the undesired layer, the effect of which becomes tangible under optimal decoding. The rest of the paper is as follows. In Section II, we formally define the two variants of superposition coding schemes and present their respective rate regions. In Section III, we compare these rate regions. Additional remarks are provided in Section IV.
Throughout the paper, we closely follow the notation in [10]. In particular, for X ∼ p(x) and ǫ ∈ (0, 1), we define the set of ǫ-typical n-sequences x n (or the typical set in short) [14] as T

II. RATE REGIONS FOR THE TWO-RECEIVER BC
Consider a two-receiver discrete memoryless broadcast channel depicted in Figure 2. The sender wishes to communicate message M 1 to receiver 1 and message M 2 to receiver 2. We define a (2 nR1 , 2 nR2 , n) code by an encoder x n (m 1 , m 2 ) and two receiversm 1 (y n 1 ) andm 2 (y n 2 ). We assume the mes- and independent of each other. The average probability of error is defined as P is said to be achievable if there exists a sequence of (2 nR1 , 2 nR2 , n) code such that lim n→∞ P (n) e = 0. We now describe the two superposition coding techniques for this channel and compare their achievable rate regions under optimal decoding.

A. Homogeneous Superposition Coding (U V Scheme)
Codebook generation: Fix a pmf p(u) p(v) and a function x(u, v). Randomly and independently generate 2 nR1 sequences u n (m 1 ), m 1 ∈ [1 : 2 nR1 ], each according to Encoding: To send the message pair (m 1 , m 2 ), transmit Decoding: Both receivers use simultaneous nonunique decoding, which is rate-optimal in the sense that it achieves the same rate region as maximum likelihood decoding [1] under the codebook ensemble at hand. In particular, upon receiving y n 1 , receiver 1 declaresm 1 is sent if it is the unique message such that u n (m 1 ), v n (m 2 ), y n 1 ∈ T (n) ǫ for some m 2 . If there is no uniquem 1 , it declares an error. Similarly, upon receiving y n 2 , receiver 2 declaresm 2 is sent if it is the unique message such that u n (m 1 ), v n (m 2 ), y n 2 ∈ T (n) ǫ for some m 1 . If there is no uniquem 2 , it declares an error. Standard typicality arguments show that receiver 1 will succeed if or, equivalently, if Similarly, receiver 2 will succeed if or, equivalently, if The regions for both receivers are depicted in Table 1. Letting R UV (p) denote the set of rates (R 1 , R 2 ) satisfying (1) and (2), it follows that the rate region is achievable. Here, co(·) denotes convex hull, and P UV is the set of distributions of the form p = p(u) p(v) p(x|u, v) where p(x|u, v) represents a deterministic function.
Decoding: Both receivers use simultaneous nonunique decoding, which is rate-optimal as we show below. In particular, upon receiving y n 1 , receiver 1 declaresm 1 is sent if it is the unique message such that u n (m 1 ), x n (m 1 , m 2 ), y n 1 ∈ T (n) ǫ Receiver 1 Receiver 2 for some m 2 . If there is no uniquem 1 , it declares an error. Similarly, upon receiving y n 2 , receiver 2 declaresm 2 is sent if it is the unique message such that u n (m 1 ), x n (m 1 ,m 2 ), y n 2 ∈ T (n) ǫ for some m 1 . If there is no uniquem 2 , it declares an error. Standard arguments show that receiver 1 will succeed if or, equivalently, if Following an analogous argument to the one in [1], it can be shown that this region cannot be improved by applying maximum likelihood decoding. Receiver 2 will succeed if In the Appendix, we show that this region cannot be improved by applying maximum likelihood decoding. The regions for both receivers are depicted in Table 1. Let R UX (p) denote the set of all (R 1 , R 2 ) pairs satisfying both (3) and (4). Clearly, the rate region is achievable. Here, P UX is the set of distributions of the form p = p(u, x).
If the roles of m 1 and m 2 in code generation are reversed, one can also achieve the region R V X = co(∪ p R V X (p)) obtained by swapping Y 1 with Y 2 and R 1 with R 2 in the definition of R UX (p).
It is worth reiterating that the two schemes above differ only in the dependence/independence between clouds around different u n sequences, and not in the underlying distributions from which the clouds are generated. Indeed, it is well known that the classes of distributions P UX and P UV are equivalent in the sense that for every p(u, x) ∈ P UX , there exists a q(u) q(v) q(x|u, v) ∈ P UV such that v q(u) q(v) q(x|u, v) = p(u, x) (see for example [10, p. 626]).

III. MAIN RESULT
Theorem 1. The rate region achieved by homogeneous superposition coding includes the rate region achieved by heterogeneous superposition coding, i.e., Moreover, there are channels for which the inclusion is strict.
Proof: Due to the convexity of R UV and the symmetry between U X and V X coding, it suffices to show that R UX (p) ⊆ R UV for all p ∈ P UX . Fix any p ∈ P UX . Let q ′ ∈ P UV be such that U = X, V = ∅, and the marginal on X is preserved q ′ (x) = p(x). Let q ′′ ∈ P UV be such   that V = X, U = ∅, and the marginal on X is preserved q ′′ (x) = p(x). An inspection of (1)-(4) and Table 1 reveals that R UV (q ′ ) is the set of rates satisfying and R UV (q ′′ ) is the set of rates satisfying It then follows that co R UV (q ′ )∪R UV (q ′′ ) includes the rate region We will consider three cases and show the claim for each.
• If I(X; Y 1 ) ≥ I(X; Y 2 ) then R UX (p) reduces to the rate region which is included in the rate region in (5), and therefore in R UV .
• If I(X; Y 1 ) < I(X; Y 2 ) and I(X; Y 1 | U ) ≥ I(X; Y 2 | U ), then R UX (p) reduces to the rate region which is also included in the rate region in (5), and therefore in R UV .
• If I(X; Y 1 ) < I(X; Y 2 ) and I(X; Y 1 | U ) < I(X; Y 2 | U ), then R UX (p) reduces to the rate region (see Figure 3(a)) R 2 ≤ I(X; Y 2 | U ) Find a q ∈ P UV with q(u, x) = p(u, x), and note that R UV (q) is described by the bounds Comparing (6) with (7) (Figure 3(b)), one sees that R UX (p) ⊆ co R UV (q) ∪ R UV (q ′ ) . This proves the first claim of the theorem. Now consider the vector broadcast channel with binary inputs (X 1 , X 2 ) and outputs (Y 1 , Y 2 ) = (X 1 , X 2 ). For all p ∈ P UX , we have from (4) that R 1 + R 2 ≤ I(X 1 X 2 ; Y 2 ) ≤ 1, and similarly for all p ∈ P V X . Thus, R UX ∪ R V X is included in the rate region R 1 +R 2 ≤ 1. Note, however, that the rate pair (1, 1) is achievable using the U V scheme by setting U = X 1 and V = X 2 . This proves the second claim.

IV. DISCUSSION
In addition to the basic superposition coding schemes presented in Section II, one can consider coded time sharing [10], which could potentially enlarge the achievable rate regions. In the present setting, however, it can be easily checked that coded time sharing does not enlarge R UX . Thus, the conclusion of Theorem 1 continues to hold and homogeneous superposition coding with coded time sharing outperforms heterogeneous superposition coding with coded time sharing.

APPENDIX OPTIMALITY OF THE RATE REGION IN (4)
We show that no decoding rule for receiver 2 can achieve a larger rate region than the one in (4) given the codebook ensemble of heterogeneous superposition coding. To this end, denote the random codebook by C = (U n (1), U n (2), . . . , X n (1, 1), X n (1, 2), . . . ).
By the averaged version of Fano's inequality in [1], where ǫ n → 0 as n → ∞. Thus, where (a) follows by providing M 1 to receiver 2 as side information from a genie and (b) follows from the codebook ensemble and the memoryless property. To see the second inequality, first assume that After receiver 2 has recovered m 2 , the codebook given this message reduces to C ′ = (X n (1, m 2 ), X n (2, m 2 ), X n (3, m 2 ), . . . ).