Introduction In this summary we discuss two types of multiuser channels: the mult-access channel and broadcast channel. In the former many senders wish to send messages to one receiver, and in the letter one sender wishes to send messages to many receivers. We are specifically interested in a survey of tools that are used.

Information-Theoretic Tools Here we list the tools that have been develeped over the years and used to prove various bounds

The Slepian-Wolf binning technique First introduced by Slepian and Wolf in their landmark paper (Slepian:76) to show the capacity of source coding with side information. Also used by Gel'fand-Pinsker (Gelfand:80) to show the capacity of channel coding with side information. The latter was extended to include the broadcast channel by Marton (Marton:79) and El Gamel (Gamel:81). Possibly also used earlier by Bergmans and Galleger in (Bergmans:73_Broadcast_Degraded, (Bergmans:74_Broadcast_AWGN) and (Gallager:74). Interestingly also used to show and achievable region for interference channels by Carleial in (Carleial:78Interference). Probably also by Han.

Equivocation in a time series First used by Shannon for a Fano-like lower bound on the error probability of a causal transmitter side information channel in (Shannon:58CCSI). This is similar to the technique used to bound the inner region of the two-way communication channel also by Shannon in (Shannon:61Twoway).

Images of a set via two channels Used by Körner and Marton first in (Korner:77Images) and in (Korner:77BC_deg_mess), and finally in (Marton:79) to give a converse for the general discrete memoryless broadcast with one deterministic component channel. In (Korner:77Images), the authors considered situation in the figure

Multi-source coding The problem in considering the encoder for Y is that it has to both satisfy the constraint of the decoder for Z and take advantage of the information from X as well as possible.

Moment bounding First used by Wyner and Ziv in (Wyner:76) to show the rate-distortion function for source coding with side information. Conversely it was used to show the capacity of channel coding with side information but with power constraint by Pradhan (Sandeep) and is included in (Kusuma:01Thesis) Also used by Bergmans to prove the converse theorem for the AWGN degraded broadcast channel (with power constraint) in (Bergmans:74_Broadcast_AWGN). Also used by Gel'fand and Pinsker in (Gelfand:80) to prove the capacity of channel coding with noncausal side information. Finally, this was used to give a simpler bound on the achievable region of the general nondegraded discrete memoryless broadcast channels by van der Meulen and El Gamal in (Gamal:81).

Method of types The textbook of Csiszár and Körner uses the method of types to examine several multilaser information theory scenarios. Note that the method of types is applicable only to discrete systems. It appears that this sheds new light on previously difficult to understand results of Körner, Marton, Csiszár, et.al in various papers.

Multiple Access In this section we review the basics behind the multiple access channel, including the definition, and the capacity region results, and some examples. This material is drawn directly from Cover and Thomas (Cover:91). Following the development there, we state and prove the results for the case of two senders to one receiver. The general case of d senders then follows easily. In addition, in order to begin suggesting some of the difficulties one encounters in the network information theory set-up, we give a simple example (again from Cover:91) that demonstrates that there is no general source--channel separation theorem in network information theory, as there is in the one--to--one communication channel.

Definition and Examples We give the definition and examples here. A Discrete Memoryless Multiple Access Channel DMMAC consists of input alphabets 𝒳 1 , 𝒳 2 , and an output alphabet 𝒴 2 , and a probability transition function of. Encoding independently from each other, the two senders wish to send as much information as possible to the reciever. They encode using a code. We have the following. Rate Code A rate R 1 R 2 code for the multiple access channel, is a map from the message sets, ℳ 1 1 2 … 2 n R 1 ℳ 2 1 2 … 2 n R 2 to 𝒳 1 n , 𝒳 2 n , respectively, given by encoding functions f 1 , f 2 , and a decoding function We call this a 2 n R 1 2 n R 2 n code. We will assume that both senders select messages to send at random from their respective message sets, where the selected message is distributed uniformly at random. Therefore the fidelity criterion which we focus on is the average probability of error: Given this performance measure, the usual definition follow. Rate Pair A rate pair R 1 R 2 is called achievable if there exists a sequence of 2 n R 1 2 n R 2 n codes with as x . The capacity region of the multiple access channel is the closure of all achievable rate pairs, R 1 R 2 . The Binary Addition Channel Suppose that the message alphabets are both 0 1 , and that the receiver sees . By sending all 1's, say, from sender one, sender two can obtain a rate of 1, and similarily for sender one if sender two is restricted to only one digit. The convex hull of these extreme points defines a triangular region, which we will see is in fact the capacity region. The Binary Multiplication Channel Now consider the simple modification of the above channel where instead of binary addition we have binary multiplication. Again the region is the same as above. The Binary Addition Channel Now suppose that in example 1 above, the recieved sees the actual sum, rather than the mod two sum of the two messages sent. If the receiver sees 0 or 2, the decoding is unambiguous. A recieved 1, however, could be the result of a 1 0 , or a 0 1 from the senders. Suppose user 1 sends at full rate. Then, in fact, sender two can still send across some information. Indeed, in this case, from the second sender's perspective, the channel looks like and erasure channel with probability one half, and therefore sender two can transmit at rate R 2 1 1 2 . This follows because we assumed the sent messages are uniformly distributed. Therefore, the second sender's message will be ambiguously received exactly when sender one sends a 1, and sender two a zero, and vice versa. This happens with probability one half. Graphically, this is given in the figure . We now state the theorem that gives the capacity region of the multiple access region. We give the proof in the next section.

Binary Erasure MAC

Some Comments on Channel Source Separartion Here we give and example that shows that it is no longer obvious what we mean by source and channel separation, in the network information theory case. In the single sender and single receiver case, this theorem tells us that we may encode the source as we wish, meaning we may compress it in any optimal way we can, and then channel code optimally, with possibly no knowledge of the source coding used. In particular then, this implies we can transmit a source reliably across a channel with capacity C, if and only if we can compress it to a source with rate RC. Analogously, we would expect that a source may be transmitted across a network, if the compression region and capacity region overlap. Consider the example of the binary multiple access channel given above: The first two senders send from the binary alphabet X 0 1 , and the receiver receives y x 1 x 2 taking values from the ternary alphabet 0 1 2 . Recall that this has a capacity region given in the figure. Now consider the source that puts equal weight on the three points 0 0 0 1 0 1 . Using Slepian-Wolf encoding, we can encode this source with rate . This is 3 1.58 . Notice then, that this point is not in the capacity region of the multiple access channel, as there is no point R 1 R 2 for which R 1 R 2 1.5 . However, it is clear that this channel can be transmitted without error (and in fact without coding) through the given multiple access channel.

The Broadcast Channel The broadcast channel was first introduced by Cover in his famous work (Cover:72). Our expostion is based on Cover's review paper of the broadcast channel (Cover:98). A Discrete Memoryless Broadcast Channel DMBC consist of an input alphabet 𝒳 and two alphabets 𝒴 and 𝒵 and a probability transition function . The broadcast channel is said to be memoryless if: The encoder wishes to find a codeword X to be sent through the channel such that the two recievers can receive their messages reliably. The figure shows the block diagram.

The broadcast channel An interpretation of the encoding process is that there are two encoders for the two sets of messages that must collaborate to jointly encode their messages in the best way possible. Here we make a note of the special case where only one part of the encoder is allowed to adapt to the other part, instead of both parts of the encoder jointly adapting their encoding. As will be formalized in the next section, this is the same as if the codebook of the encoder which is not allowed to adapt is partitioned into bins with exactly one codeword each. This is a corner point of the achievable region that we will derive next, and is exactly channel coding with side information introduced by Gel'fand and Pinsker (Gelfand:80), illustrated in thefigure.

Channel coding with side information

The Degraded Broadcast Channel The first popular special case of the broadcast channel is the degraded broadcast channel, introduced by Cover in (Cover:72). Degraded Broadcast Channel A broadcast channel is degraded if there exists a distribution such that: Cover gave two examples of such channels: a binary symmetric broadcast channel, and the Gaussian broadcast channel. By definition, it is always possible to construct a degraded version of these channels. He also gave a construction and provided an achievable rate region, along with a conjecture of the achievable region for the more general degraded broadcast channel. Note that due to the construction of the degraded broadcast channel, the stronger user always decodes the weaker user's message first before decoding its own message Bergmans(Bergmans:73_Broadcast_Degraded) gave the proof of the achievable region of a general degraded broadcast channel. The converse was given by Bergmans(Bergmans:74_Broadcast_AWGN) and Gallager(Gallager:74). The Bergmans proof applies to the Gaussian broadcast channel, i.e. one with power constraint. Gallager's proof on the other hand uses an auxiliary variable U in terms of the collection of all the outputs up to the current time. Gallager's proof does not apply to power-constrained cases, and Bergmans' proof does not apply to the general case. Note that the idea of using U and defining it in terms of the collection of all outputs up to the currnet time is also used in the converse proof of the nondegraded broadcast channel with one deterministic component by Körner and Marton in (Marton:79). We will see this in SectionThe Discrete Memoryless Broadcast Channel.

Binary Symmetric Broadcast Our first example is based on the first case explored in Cover's landmark paper(Cover:72). Suppose the channel to the first, stronger receiver is a noiseless Binary Symmetric Channel (BSC), and the channel to the second, weaker receiver is a BSC with crossover probability p . Let α be the fraction of the total power allocated to the stronger user, and α ̂ the fraction of the total power allocated to the weaker user. The variable p ̂ denotes 1 α . In the exposition, Cover constructed 2 n C α ̂ p α p ̂ ε cloud centers in the form of codes for a compound channel with a higher crossover probability α ̂ p . With each cloud codewords, he sets aside all codewords of Hamming distance α n away from the cloud centers. Note that there are n α n such satellite codewords for each cloud. Note that the limit of this expression as n approaches 2 n H α . The stronger noiseless receiver will receive information at rate: R 1 C α ̂ p α p ̂ H α ε Due to the embedding of the satellites, the weaker receiver perceives the cloud center as if if had been sent through an additional, cascaded BSC of parameter α . Because of our design choice, it can still reliably decode the clouds and receive information at rate: R 2 C α ̂ p α p ̂ ε What we would like to do is to be able to get the same capacity without requiring that the stronger user decode the message for the weaker user. We use a binning argument to show that this is possible. We retstrict ourselves to the same BSC scenario. Since the stronger user is not allowed to know the codebook of the second user, we can only assume that there are 2 α p ̂ α ̂ p codewords of the weaker user, taken randomly from the 2 n all possible binary n -tuples. The stronger user constructs its codebook as follows: it builds a main codebook from all possible 2 n binary n -tuples, and randomly partitions this into 2 n H α bins. Each bin contains 2 n C α codewords. At the transmitter, the message for the stronger user selects on of the bins. It then looks at the codeword selected by the weaker user and looks inside the selected bin of user 1 to find a codeword that is closest to the codeword of the user 2. It will almost surely find a codeword with Hamming distance of at most H α away. The transmitter than sends this codeword into the channel. The stronger user will be able to decode this from its noiseless channel, and receives information at rate: R 1 C α ̂ p α p ̂ H α ε while the second user perceives its codeword as if it had first been subjected to a BSC with parameter α , and then a BSC with parameter p . Thus it can reliably decode its message at rate: R 2 C α ̂ p α p ̂ ε We note however, that this example works only for the case where the channel for the first user is noiseless. In general Cover's capacity region is superior to that of Marton's for the degraded broadcast.

Gaussian Broadcast Channel Let there be two users with noise N 1 and N 2 respectively, and let N 1 N 2 . The first user is the better user and the second user is the worse user. We let the worse user pick any codeword into the one selected by the worse user. The better user considers the codeword selected by the worse user as side information of the additional noise the channel. We now examine the achievable rates in a Guassian broadcast channel. From the Gel'fand and Pinsker framework, we know the following capacities. The capacity of one user is: C 1 1 2 1 P 1 N 1 and the other user is: C 2 1 2 1 P 2 P 1 N 2 where we impose a total power constraint P total P 1 P 2 . This is consistent with the formulation in Cover if we consider only the nonoverlapping part of the message set. Note that the ordering of the stronger and weaker user is critical. Fig ?? gives the achievable rate in case of using CCSI as an enabling component in the coding. Although the concavity of the achievable rate region when N 1 N 2 is the most interesting motivation in the study of broadcast channels, we will nevertheless examine the case when N 1 N 2 , where the time sharing region is exactly the same as the prescribed limit in the achievable rate. For equal quality channels, adding the two expressions gives: C total 1 2 1 P 1 P 2 N Because we are limiting the total power to P total P 1 P 1 , and assign P 1 α P total and P 2 1 α P total respetively, we can see that we have also achieve the best achievable allocation of rates for the case when the noise powers are equal.

Achievable region of the degraded broadcast channel This result is due to Bergmans (Bergmans:73_Broadcast_Degraded). The method that he used is to consider and artificial channel which we discussed in the above example as shown in the figure Using typical set arguments, he obtained the achievable region for the degraded broadcast channel.

Artificial channel for degraded broadcast

Converse theorem for the degraded broadcast channel This result is due to Bergmans(Bergmans:74_Broadcast_AWGN) for the AWGN channel, and Gallager(Gallager:74) for the more general case without power limitation.

The Deterministic Broadcast Channel The capacity is given by Gel'fand and Pinsker in (Gelfand:80BC_det). An important example is the Blackwell channel, where the transition matrix is defined by a multiplication rule.

The Discrete Memoryless Broadcast Channel Here we do not allow the channel decomposition as for the degraded broadcast channel in the section Degraded Broadcast Channel.

Achievable region of the general broadcast channel The first result is due to T.M.Cover (Cover:72BC_gen_ach) and E.C. van der Meulen (Meulen:75), who discovered it simultaneously and independently. It was later refined by Hajek and Pursley (Hajek:79), who together with Cover and van der Meulen started the efforts during the 1976 ISIT. Their contribution is the evaluation of the region. Up to this point the evaluated region is defined by R x R y R xy where the last term is the rate of the common message meant for both receivers. They show that in evaluating R x R y 0 then one will get a region that is strictly larger. However, in doing so one has to insist on the independence of U V W which denote the message for receiver 1, receiver 2, and the common message between the two.

A Brief History fo Broadcast In the process of reading the relevant papers, we have made an attempt to graphically describe the history behind the development of the broadcast channel as shown in the figure

Conclusions By now it should be clear that there have been several tools developed for the multiuser information theory problem. But the primary question remains of whether the formulation is the correct one. For the multiaccess channel, the problem has largely been solved. Coding frameworks for multiaccess have been developed by various researchers, and multiaccess on fading channels has been studied by many researchers here at MIT. Unfortunately it appears that nonsynchronicity between the signal transmissions across many senders are discouraging the implementation of the more sophisticated coding techniques. For the broadcast channel, Cover's formulation sparked a strong interest in the broadcast channel problem, with the degraded and deterministic cases having been solved. However, the nondegraded case is still an open problem. And the set of tools used has transitioned from the early works where it depends on casting the problem as a special case of the degraded broadcast, to using newer but less intuitive tools. Is the nondegraded broadcast channel an important problem to solve? It is worth noting that this is the dual of the symmetric Slepian-Wolf problem, which is also of great interest to information theorists. Also note that because the sender is a single entity, we do not have the problem with nonsynchronicity for the broadcast channel. Finally, we should remark that many researchers have left information theory due to frustrations arising from the broadcast problem.