1,第15章 网络信息论Network Information Theory,主讲人：郭迪 指导老师：王琳 2009-04-15,2,主要内容,概述 高斯多用户信道 联合典型序列 多接入信道 相关信源编码 一般多终端网络 最新发展,3,研究对象,在给定若干发送器、若干接收器以及描述网络中的相互干涉与噪声干扰效应的信道转移矩阵的条件下，确定该信道是否能够传输这些信源信号。 新要素：干扰、协作与反馈 分布式信源（数据压缩）和分布式通信（找出网络的容量区域），至今还未彻底解决 长远目标：分布式信源编码与网络信道编码结合在一起。,4,信息论的多用户推广,成功的例子,多接入信道：较为完善，具有 反馈的多址接入信道的容量域 的确定存在问题。,广播信道：一般广播信道容量 域尚未解决，只解决了一些特 殊问题。比如，退化广播信道。,5,信息论的多用户推广,依然未知的例子,干扰信道：尚未完全解决， 在某些情况下可给出上界。,中继信道：可给出信道容 量的上界。,双程信道：两对发送与接收器互相传递信息，与干扰信道类似。尚未完全解决，得到了可达码率区域的上下界。,6,网络与信息论的联姻,经典信息论不适用于网络的原因： 未考虑信源的突发特性（Bursty） 未考虑延时在“容量误码率”渐近分析中的影响 其他因素 Anthony Ephremides, Bruce Hajek, “Information Theory and Communication Networks: an Unconsummated Union,” 1998.,7,【Joao Barros,06】 未界定延时和可靠性 时域空域多尺度分解未能对无线网络时空变化进行最优化建模 未能发挥系统开销和反馈的作用,无线网络容量域计算障碍,8,研究热点,multiuser systems multiple-input multiple-output channels data dissemination algorithms queuing and delay issues throughput limits in noisy networks network coding Joint source-channel coding scaling laws in networks (e.g., sensor network),9,主要内容,概述 高斯多用户信道 联合典型序列 多接入信道 相关信源编码 一般多终端网络 最新发展,10,高斯多接入信道,首先回顾一下香农公式,其中Zi是独立同分布的高斯随机变量，信号总功率为P，即,信道的容量C为跑遍所有满足上述约束的X的分布求得的I(X;Y)的最大值，为,离散时间的AWGN信道可以描述为,11,一个特殊的例子,例1：假定输入为X1=X2=0,1，输出为Y=X1+X2。当输出Y=0或Y=2时，没有歧义，但是当Y=1时，存在(0,1)和(1,0)两种可能性。,等效的二元擦除信道,信道容量域,12,高斯多接入信道,设所有信源独立，功率为P，,令,对于高斯多址接入信道，当m时，信道容量。,信道容量域是一个m维空间中的多边形,最优译码方法： 在m个码簿中各自找出一个码字使得这些向量之和在欧几里得距离下与Y最近。,其容量域为,13,退化广播信道,一般情况下广播信道的容量依然没有得到解决，但是已知它仅与p(y1|x),p(y2|x)有关 退化的广播信道下容量域已经得到解决。 称广播信道是退化的，当 高斯广播信道是退化的,14,高斯广播信道,高斯广播信道可以被看作是退化的广播信道 其容量域为 其中,最优译码方法： Y2先译码，Y1先译出Y2对应的码字，减去后再译出Y1对应的码字,15,高斯中继信道,容量域为：,最优译码方法： 分组传输。取得所有可能是第一组传输发送的码字清单后，检查清单与划分的特定单元（从第二组传输协助的中继传输中知道该单元编号）相交的情况,若,16,高斯干扰信道,没有一般解 若干扰a满足,结论：无论在高干扰还是在无干扰下，信道的 容量域都是相同的（信道净化了）,最优译码方法： Y2先译码，Y1先译出Y2对应的码字，减去后再译出Y1对应的码字,17,高斯双程信道,反馈：发送器1可由接收器2以前接收到的信号决定下一步该发送什么 香农获得了一般双程信道的容量域上下界 对高斯信道，这两个界重合 容量域为：R1C(P1/N1),R2C(P2/N2) 高斯双程信道可分解为两个独立信道,18,主要内容,概述 高斯多用户信道 联合典型序列 多接入信道 相关信源编码 一般多终端网络 最新发展,19,联合典型序列,联合AEP能计算各种编码方案的联合典型译码的误差概率,20,21,主要内容,概述 高斯多用户信道 联合典型序列 多接入信道 相关信源编码 一般多终端网络 最新发展,22,多接入信道的容量区域,23,两个用户的多接入信道,平均误差概率,24,容量域的可达性证明,证明：固定 码簿的生成 编码 译码： 误差概率分析：并不依赖于具体发送的下标对。假设 出错：正确码字与接收到的序列是非典型的，或者有一对不正确的码字与接收到的序列是典型的。定义,25,容量域的可达性证明,26,对多接入信道容量区域的评述,将其他信号考虑为噪声 的一部分，译码单个信 号并将其从接收到的信 号中“”减去“的思想,27,m个用户的多接入信道,M个用户的多接入信道的容量区域为满足如下条件的所有码率向量所成集合的凸闭包，即对乘积分布,容量区域为一个斜多面体！,28,高斯多接入信道与信道复用技术,实际使用的复用方式 CDMA FDMA TDMA,该点意味着分配给每个信道的带宽与该信道的功率成比例,29,主要内容,概述 高斯多用户信道 联合典型序列 多接入信道 相关信源编码 一般多终端网络 最新发展,30,相关信源编码,分布式数据压缩与多接入信道问题是对偶的 对单个信源X编码，码率 是充分的 对相关信源进行分开编码，总码率 也是充分的。【Selpian and Wolf,1973】,31,Selpian-Wolf定理的可达性,随机盒子基本思想：为每个信源序列随机地选取一个下标。若典型信源序列集足够小，则不同的信源序列有不同下标的概率很高，并且可以用对应的下标恢复出信源序列。,32,随机码生成。 编码。 译码。 误差概率：盒子中超过一个典型序列或信源序列是非典型的时候出错。,33,可达性证明,34,多信源的Selpian-Wolf定理,35,Slepian-Wolf编码与多接入信道的对偶性,多接入信道编码定理，误差概率满足,Slepian-Wolf编码定理，误差概率满足,36,主要内容,概述 高斯多用户信道 联合典型序列 多接入信道 相关信源编码 一般多终端网络 最新发展,37,一般多用户网络,基本假设 多个发送器，多个接收器 所有消息相互独立 所有消息服从各自取值空间的均匀分布 信道是无记忆的 将所有节点集分成集合S和其补集Sc. 现在估计从S中节点到Sc中节点的信息流码率,38,一般多用户网络,上述定理有一个简单的最大流最小割解释。 考虑网络中任何一个分界线的一侧与另一侧， 穿过该分界线的码率不超过在给定另一侧的 输入条件下，一侧的输入与另一侧的输出之 间的条件互信息。 如果定理中不等式的等号能够成立，那么网 络中的信息流问题就能得到解决。但遗憾的 是，即使对一些简单的信道，这些不等式中 的等号都不会成立。,39,单用户经典理论,数据压缩定理来源于AEP，表明全部信源序列存在一个拥有了绝大部分概率的“小型”的子集（大小为2nH），根据这个子集使用H比特/字符并以很小的误差概率来表示这个信源。 数据传输定理基于联合的AEP；它依据的事实是：对于大的分组长度，信道的输出序列非常有可能与输入码字是联合典型的，而任何其他码字是联合典型的概率约为2-nI。因而，我们可以使用大约2nI个码字而保持可忽略的误差概率。 反馈不能增加无记忆信道的容量，能增加有记忆信道的容量,40,信源信道分离定理（多用户）,信源信道分离定理说明，我们可以独立地设计信源码和信道码，然后结合两者的结果以达到最优的效果。它表明了可以无噪声地在信道中传输当且仅当熵率小于信道容量。 成立的条件：信源的Selpian-Wolf码率区域与多接入信道的容量区域有非空的交。 但此条件是否必要？NO. 不成立的原因：多接入信道的容量随着信道输入间的相关性增加而增加。因此要使容量最大化，需要保留信道输入间的相关性。然而Selpian-Wolf编码却剔除这个相关性。,41,带反馈的容量区域（多用户）,即使信道无记忆，反馈也确能增加用户信道的容量区域。 二元多擦除信道：接收器到两个发送器的反馈充当了两个发送器间的分离信道的角色。发送器先于接收器将相互间传输的信息译码。然后相互协作解决接收端的不确定性，比非协作具有更高的容量（协作容量）。,42,主要内容,概述 高斯多用户信道 联合典型序列 多接入信道 相关信源编码 一般多终端网络 最新发展,43,Network coding,2000,R. Ahlswede 网络不再是语义无关的信息传输介质 Butterfly网络是网络编码最著名的例子 两个红色节点分别要把比特A和B 传送给两个绿色节点 每条链路的容量一致，每秒可以 传输1个bit的信息 考虑编码与不考虑编码的状态不同,44,Network coding,s,t,u,y,z,w,b,1,b,1,b,1,b,2,b,2,b,2,x,Canonical example Ahslwede et al. 00 What choices can we make? No longer distinct flows, but information,45,Network coding,s,t,u,y,z,w,b,1,b,1,b,1,b,1,b,2,b,2,b,2,x,b,1,b,1,Picking a single bit does not work Time sharing does not work No longer distinct flows, but information,46,Network coding,s,t,u,y,z,w,b,1,b,1,b,1,b,1,+,b,2,b,2,b,2,b,2,x,b,1,+,b,2,b,1,+,b,2,Need to use algebraic nature of data No longer distinct flows, but information,47,Network coding app.,P2P File Distribution Wireless Networks Wireless Networks Ad-hoc Sensor Networks Network Tomography Network security,48,Joint source-channel coding,Michael Gastpar, 2003 For a Gaussian example considered in this paper, the distortion of the best coding scheme according to the separation paradigm decreases like 1/ logM, while for Joint source-channel coding paradigm, it decreases like 1/M, where M is the total number of sensors.,49,Capacity region of cognitive radio networks,2008,Natasha Devroye Inte