II. THE DEPENDENCE BALANCE BOUND
- 格式：pdf
- 大小：55.83 KB
- 文档页数：7
Cut-Set Bound and Dependence Balance BoundLei Xiaolxiao@Date:4October,2006Reading:Elements of information theory by Cover and Thomas[1,Section14.10],and the paper by Hekstra and Willems[2].I.T HE C UT-S ET B OUNDThis section follows the discussion in[1,Section14.10].Consider m nodes in a memoryless network.Each node i transmit X(i)and receives Y(i).Communication from node i to node j is at rate R(ij).If we partition the network into a set of nodes S and its complement S c,the cut set bound gives us the following constraint on the possible achievable rates,in the sense that the probability of decoding errors goes to zeros as the codeword length approaches infinity. Theorem1:If the information rates{R(ji)}are achievable,then there exists some joint probability distribution p(x(1),x(2),···,x(m)),such thatR(ij)≤I(X(S);Y(S c)|X(S c))(1)i∈Sj∈S cfor all S⊂{1,2,···,m}.Thus the total rate offlow of information across a cut is bounded by the conditional mutual information.It is worth noting that cut-set bound are usually not achievable even for simple channels.For instance,the cut-set bound for multiple access channel takes the same form as the capacity,but fails to provide a restriction on the independence of the input distribution[1,Section14.10].II.T HE D EPENDENCE B ALANCE B OUNDWe start with the concept of K-information(also known as multiple information)–i.e.the mutual information among K random variables–and some of its properties.The dependence balance bound is then derived utilizing the results on K-information.A.The K-InformationDefinition1:The K-information I K,is defined byH(S),(2)I K V1;V2;···;V K =K k=1 −1 k−1S∈ V1,V2,···,V K|S|=kwhere•V1,V2,···,V K are K random variables(hence then name K-information);•H(S)denotes the joint entropy of the random variables in the set S.•|S|is the cardinality of the set S.The conditional K-information can be defined likewiseI K V1;V2;···;V K V0 =K k=1 −1 k−1H(S|V0)(3)S∈ V1,V2,···,V K|S|=kFor the purpose of illustration,a few examples for small K’s are given as follows:I1(A)=H(A)(4a) I2(A;B)=H(A)+H(B)−H(A,B)=I(A;B)(4b) I3(A;B;C)=H(A)+H(B)+H(C)−H(A,B)−H(A,C)−H(B,C)+H(A,B,C)(4c)=I(A;B)+I(C;B)−I(A,C;B)(4d) Some properties of the K-information:•K-information is symmetric in the variables.This is explained by the symmetry of the variables in the entropy function.•In contrast to the mutual information for two random variables,K-information can in generalbe negative.•Chaining propertyI K (V1,V2);V3;V4;···;V K+1|V0 =I K(V1;V3;V4;···;V K+1|V0)+I K(V2;V3;V4;···;V K+1|V0,V1)(5)•Recursive relationI K V1;V2;···;V K|V0 =I K−1(V1;V2;···;V K−1|V0)+I K−1(V1;V2;···;V K−1|V0,V K)(6)For the case of K=3,the above recursive relation givesI3(A;B;C|D)=I2(A;B|D)−I2(A;B|C,D)(7)More discussion(and references)on the subject of K-information can be found in Sunil Srini-vasa’s tutorial for EE80653at /˜jnl/ee80653/tutorials/sunil.pdf (University of Notre Dame NetID and password required).B.The Dependence Balance BoundWe consider the constraint on the input distribution on the two-input channel with noiseless feedback to the encoder,as depicted in Fig.1.More specifically,the following are assumed:•The two messages W1and W2at the input of the encoders are statistically independent,uniformly distributed,and of alphabet sizes M1and M2,respectively.•The messages are to be transmitted over the channel via N transmissions.•Each encoder is completely described by N encoding functions,mapping the message,W1or W2,and the previous channel outputs,Y n−1,into the next channel input,i.e.X1n=f1n(W1,Y n−1)(8a)X2n=f2n(W1,Y n−1)n=1,2,···,N(8b)--6bound indicates that each code has to produce at least the amount of dependence it consumes.Hence the name dependence balance bound.The dependence balance bound also gives K -information a physical interpretation for K =3as the dependence reduction [2].III.A PPLICATION :T WO W AY C HANNELThe dependence balance bound was derived in [2]to provide a tight outer bound for the common-output two way channel,as presented in Fig.2.The error probabilities are defined as-6-?--Note that the two input channel with feedback should satisfy the dependence balance constraint in(10).Let S be a uniform random variable taking value from1to N,defineT=(S,Y S−1)(15)X1=X1S(16)X2=X2S(17)Y=Y S(18) and the converse with the dependence balance bound can be stated as follows.Theorem2:For each single output two way channel,the capacity region is upper bounded by0≤R1≤I(X1;Y|X2,T)(19)0≤R2≤I(X2;Y|X1,T)(20) for some p(t,x1,x2,y)=p(t,x1,x2)p(y|x1,x2)satisfying I(X1;X2|T)≤I(X1;X2|Y,T).The support lemma can bound the alphabet size of T to three.IV.C OMPARISON OF THE T WO B OUNDSThe cut-set bound and the dependence balance bound are different in a number of aspects. The following is a comparison between the two bounds.•The cut-set bound is applicable to discrete memoryless network of any form(for example, with or without feedback,scalar output channels,or vector output channels).The dependence balance bound derived in[2]is only applicable to two input,single output channels with noiseless feedback to the two individual encoders.Kramer generalized the dependence balance bound to more than just two inputs in[3].However,single output at the channel, and feedback of this single output to the encoders are necessary to apply the dependence balance bound.•The cut set bound directly gives a upper bound on the rate,while the dependence balance bound only provides an additional constraint to the possible input distribution–which helptighten the outer bound due to a smaller region to maximize over.In this sense,the cut-set bound and dependence balance bound represent constraints on different quantities.•For the multiple access channel with feedback,the cut-set bound coincide with the capacity region in form[1],but does not restrict the input distribution to be a product ing the dependence balance bound and a parallel channel,it is shown in[2]that the dependence balance bound can provide the product form constraint originally derived in[4]with a different approach.V.R ECENT D EVELOPMENTSThe“refined and generalized”dependence balance bounds are developed and applied to K-user Gaussian multiple access channel with feedback in[5].Kramer and Savari studied two way channel networks with network coding in[6]and provides a new cut-set bound for such networks.R EFERENCES[1]T.M.Cover and J.A.Thomas,Elements of Information Theory.New York:Wiley-Interscience,1991.[2] A.P.Hekstra and F.M.J.Willems,“Dependence balance bounds for single-output two-way channels,”IEEE rm.Theory,vol.35,pp.44–53,Jan.1989.[3]G.Kramer,“Capacity results for the discrete memoryless network,”IEEE rm.Theory,vol.49,pp.4–21,Jan.2003.[4] F.M.J.Willems,“The feedback capacity region of a class of discrete memoryless multiple access channels,”IEEE Trans.Inform.Theory,vol.28,pp.93–95,Jan.1982.[5]G.Kramer and M.Gastpar,“Dependence balance and the gaussian multiaccess channel with feedback,”in Proc.IEEEInformation Theory Workshop,Punta del Este,Uruguay,Mar.2006.[6]G.Kramer and S.A.Savari,“Cut sets and informationflow in networks of two-way channels,”in Proc.IEEE InternationalSymposium on Information Theory,Chicago,IL,June2004.。
