The Multicast Capacity of Finite Field Multiple-AccessNetworksBobak NazerMay 21, 2006AbstractWe study the problem of multicasting over a network of multiple-access channels(MACs). The separation-based solution to this problem is to reduce each MAC to a setof noiseless bit pipes via a channel code and then employ network coding. Sometimes,however, the physical-layer structure of the MAC can be exploited more advanta-geously. In many cases of interest, the MAC output is a (deterministic) function of itsinputs, corrupted by noise. We develop structured codes to exploit the natural functionof a MAC to reliably compute functions as part of a network code and show that inmany scenarios of interest our scheme outperforms the separation-based solution. Ifeach MAC can be written as a sum over some finite field plus noise, then our achievablerate coincides with the max-flow min-cut bound.1 IntroductionFinding the capacity region of an arbitrary collection of sources, channels, and sinks is anextremely difficult problem. For a graph of point-to-point channels, a single source, anda single receiver, the capacity is given by the max-flow min-cut bound and is achieved byrouting. However, if we consider a wireless network with multiple sources and sinks, thesituation becomes mu ch more complicated. The broadcast and multiple-access aspects ofthe medium already present significant difficulties. Increasing the number of transmittersand receivers makes the problem even worse. However, recently, some authors have m adesignificant progress on several aspects of this problem. The innovative work of Gupta andKumar determined scaling laws for the capacity of a wireless network with an increasingnumber of users under certain protocol constraints [1]. In this report, we are interested infinding the exact capacity region. As a result, we will have to turn to a more restrictivenetwork model. Specifically, we will focus on networks of multiple-access channels with asingle source and multiple receivers.The capacity for a single source, multiple sink n etwork is called the multicast capacityand has been the subject of much recent study following the discovery of network coding1in [2]. In this paper, Ahlswede et al. show that the multicast capacity of a network of point-to-point channels, which turns out to be the max-flow min-cut bound, cannot be achievedby routing alone: bits must be “mixed” at intermediate nodes. Some subsequent works,such as [3, 4], have shown that linear network codes are sufficient to achieve capacity. Fornetworks of point-to-p oint channels, network coding can be implemented separately fromchannel coding, i.e. there is a separation theorem [5]. In this paper, we show that if thenetwork includes a MAC, a separation-based scheme that converts the MAC into a set ofnoiseless bit pipes is not optimal in general. Specifically, we show that the natural operationperformed by a MAC can be exploited to mix bits for a network code. For example, theoutput of a Gaussian MAC is just the real sum of its inputs plus noise. With th e rightcoding scheme, we can use this summation to our advantage for reliably computing the sumof our inputs.A MAC is often a good model for a multi-user wireless uplink. By incorporating a MACinto a network of point-to-point channels, we are effectively modeling a hybrid wired/wirelessnetwork. The problem of multicasting information over a wireless network has been thetopic of much recent study, [6–8], but these works focus on the broadcast aspect of wirelesspacket networks and do not consider physical-layer MAC models. As shown in [9], certainfunctions can be reliably communicated over MACs at higher rates with a joint source-channel scheme than with a separation-based scheme. Since in network coding, we onlyneed to send functions of bits down certain paths, we should try to exploit this facet of theMAC in multicast networks of MACs.We begin with a motivating example centered around the butterfly network given in [2]to illustrate our coding scheme. We will t hen give the multicast capacity of finite field MACnetworks.2 Motivating ExampleConsider the channel network in Figure 1 (a). There is a discrete memoryless source S withentropy H(S). Each vertex on the graph represents a decoder/encoder pair. The labelededges represent noiseless bit pipes each with capacity C. At the center of the graph is a MACwith inputs X1(from the left) and X2(from the right) and output Y given by the conditionalpdf pY |X1X2(y|x1, x2).We allow ourselves n channel graph uses to losslessly communicate nsource symbols. We would like to characterize conditions on the noiseless bit pipes and theMAC to allow for lossless multicasting of S.To motivate our general scheme, we will compare a separation-based scheme to jointsource-channel coding for an ideally matched MAC, the mod-2 adder MAC. The mod-2adder MAC has two inputs X1and X2that take values in {0, 1}. The MAC output is givenby Y = X1⊕ X2⊕ Z where Z ∼ B(p).2(a)CˆS1CˆS2SC CMACCC C(b)CˆS1ˆS2CSC CCRMAC1RMAC2C C(c)CˆS1ˆS2CSC CCMACC∞ ∞C CFigure 1: (a) Simple MAC Network (b) Separation-Based Approach (c) Transformed MAC2.1 Separation-Based Network CodingGiven the network in Figure 1 (a), one might choose to use standard channel coding strategiescoupled with network coding. Using a multiple-access code, we can convert the network ofnoisy channels into a network of noiseless bit pipes (see Figure 1 (b)). Then, we can find anetwork code for our network of bit pipes.Using a standard MAC code, we can allocate a rate RMAC1for the left user and a rateRMAC2for the right user. The capacity region for the mod-2 adder MAC, RMAC, is the set ofall rate pairs, (R1, R2), satisfying:R1+ R2< 1 − hB(p) (1)where hB(p) = −p log p − (1 − p) log (1 − p), the binary entropy function.Lemma 1. For the channel network in Figure 1 (b), the following conditions are necessaryand sufficient for multicasting S to both receivers:C >H(S)2(2)1 − hB(p) > 2(H(S) − C) (3)Proof. (Necessity.) Recall that the maximum multicast rate for a graph of point-to-pointchannels is given by the cut-set bound. (For more detail, see [2].) From this we get that themulticast rate to each user satisfies:R < C + minC,1 − hB(p)2(4)3Clearly, if 2C < H(S), then reliable multicasting is impossible. From this we get the firstcondition:C >H(S)2(5)If the above condition is satisfied, then C is no longer a bottleneck. This leaves us with thesecond condition:1 − hB(p)2>
View Full Document
Unlocking...