《信息论与编码》 课件 第7章网络信息论初步

1第7章网络信息论初步网络信息论简介网络通信的分类分布式无损压缩网络编码2网络信息论简介网络信息论简介3网络信息论简介网络信息论与普通信息论的对照本章主要内容概述4网络信息论与普通信息论的对照普通信息论的研究模型：特点：一个信源；

一个信宿；

一个通道。信源信宿噪声源信息信息干扰信道5网络信息论与普通信息论的对照网络信息论的研究模型：特点：多个信源；

多个信宿；

传输通道是网络式。6网络信息论与普通信息论的对照基本问题：网络信息论的基本问题仍然是有效性和可靠性。7网络信息论与普通信息论的对照有效性：普通信息论：有效性的极限是信源熵H(X)；网络信息论：当考虑多个信源之间有合作时，

有效性的极限是联合熵

H(X,Y)=H(X)+H(Y/X)

—分布式压缩；8网络信息论与普通信息论的对照可靠性：普通信息论：可靠传输的极限是信道容量；网络信息论：当传输通道是网络式的情形，通

信容量问题更复杂（如最大流-最

小割定理等），也需要考虑特殊

的编码（网络编码）。9网络信息论与普通信息论的对照网络信息论与传统信息论的内容对照分布式无损压缩（对照普通信息论的信源与信源熵：第2章、第5章）网络编码（对照普通信息论的信道编码：第3章、第6章）10本章主要内容概述由上面的分析，本章主要包括：网络信息论的基本概念、分类；分布式压缩；网络编码。11网络通信的分类网络通信的分类12网络通信的分类按信源信宿的数目分：多播通信：一个信源，多个信宿。广播：一个信源，任意多个信宿。信源发送的信息不针对特定信宿。网络通信：多个信源，多个信宿。13网络通信的分类按信源到信宿是否有中继分：单跳通信：信源通过信道直接和信宿通信，不需要中间节点接力。多跳通信：也叫做中继通信。信源通过中间节点接力，实现与信宿通信。每一次中间节点接力，叫做一跳。实现接力的中间节点，叫做中继节点。14网络通信的分类中继通信又可以细分为两类：放大转发：中继节点直接将接收到的来自信源的有噪信号进行放大，并将其发送给后续目的节点。解码转发：中继节点收到前序节点发来的信号后，先对接收到的信号进行解调和解码，然后将数据重新进行编码调制后发给后续节点。15分布式压缩分布式压缩16分布式压缩分布式压缩如上图所示的网络通信情形，存在两个及以上未经压缩的信源。如果要求接收端能够无损地恢复两个信源，最小的总传输速率是多少？这就是分布式压缩问题。17分布式压缩二元离散无记忆信源的分布式压缩定义：若有一个速率对（R1，R2），R1是X1的传输速率，

R2是X2的传输速率：可使接收端无损地恢复两个信源（X1，X2），则称速率对（R1，R2）对分布式无损信源编码是可达的。则可达速率对（R1，R2）满足下图所示的界：18分布式压缩19分布式压缩简单解释如下：当R1>H(X1)时，只要R2=H(X2/X1)，就有可能实现无损解压缩；当R2>H(X2)时，只要R1=H(X1/X2)，就有可能实现无损解压缩；当R1<H(X1)时，则需要R2=H(X1，X2)-R1

，即R1+R2=H(X1，X2），才有可能实现无损解压缩。这三段线段组成了所谓的外界（OuterBound）20分布式压缩另一方面：只要R1>H(X1)并且R2>H(X2)，则一定可以实现无损解压缩。这两段线段组成了所谓的内界（InnerBound）21分布式压缩内界可以理解为两个信源不需要合作，实现无损解压缩所需的条件；而外界则是当两个信源有合作时的情形。22分布式压缩有协助的无损压缩问题：如果图中接收者只需要无损恢复其中一个信源（例如X），而另一个信源（协助者，Y）的编码器向解码器提供经编码的边信息来帮助降低第一个编码器的码率。那么，

X所需要传输的信息率是多少？23分布式压缩24分布式压缩此时，内界和外界如上图所示。简单解释如下：如果没有协助者，即R2=0，则R1>=H(X)对无损解压缩X是充分必要的；如果协助者无损地将Y发送给解码器，即R2>=H(Y)时，则R1>=H(X/Y)对无损解压缩X是充分必要的。当R2<H(Y)时，接收端不能无损解压缩Y，只能得到一个关于Y的有损估计，设为Z；则需要R1>=H(X/Z)对无损解压缩X是充分必要的。25网络编码网络编码26网络编码蝶形网络问题：27网络编码图中，节点1希望各发送一个2bit的消息给目标节点6和7；假设所有链路的容量都是1bit。因为两个消息都必须通过链路（4，5）发送，因此，在传统点对点通信模式下（每个节点只进行接收-转发操作，称为路由），需要两个单位时间才能完成。28网络编码如果我们允许节点除了进行路由操作，还可以完成简单的运算，对图7-10的网络，我们假定可以进行“模2和”运算，那么该2bit的消息就可以在一个单位时间内送达两个接收者。29网络编码方式如下：中继节点2、3和5只进行路由操作（接收-转发），而中继节点4发送从节点2和节点3收到的信息的模2和；节点6（接收者1）在接收到从节点2传送过来信息和从节点5转发的（从节点4传送过来）信息后，就可以通过两者的模2和得到所需要的信息；节点7（接收者2）也可以通过类似的操作，得到所需要的信息。30网络编码网络上节点进行的这种运算称为“网络编码”。31网络编码于是，和传统信息论相似，有以下两个问题：（1）多信源多信宿网络通信的容量（最大通信能力）是多少？（2）为达到网络通信容量，需要采用什么样的方法？32网络编码--网络通信容量单播图网络的通信容量单播网络的通信容量，等于最小割集的容量，或者称为最小割集的最大流量（最小割-最大流），即式中，S是有向图的一个割集。33网络编码--网络通信容量多播图网络的通信容量图中，信源节点1希望向信宿节点集传送不同消息（多播）。34网络编码--网络通信容量信宿节点集为D的多播图网络容量存在上界：式中，C(S)是从信源节点1到信宿节点j的一个割集S的容量。式的右端，可以理解为集合D中的所有目的节点容量（最大流-最小割）中的最小值。35网络编码网络编码分为线性网络编码和非线性网络编码，仅介绍线性网络编码。所谓线性网络编码，是指中继节点所使用的网络编码函数和译码函数都是线性函数，一般仅为简单的加法和乘法运算。36网络编码线性网络编码示意图如图所示：