信息论-网络编码(课堂PPT)课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《信息论-网络编码(课堂PPT)课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息论 网络 编码 课堂 PPT 课件
- 资源描述:
-
1、网络编码网络编码组员:代亮亮 徐杰 郭鑫 李文杰 胡怡 刘慧芳 张晓宇概念概念12应用应用3总结总结4原理原理概念概念12应用应用3总结总结4原理原理网络编码:通信网络中信息处理和传输理论研究上的重大突破。网络编码:融合了编码和路由转发的信息交换技术, 在传统存储转发的路由方法基础上, 通过允许对接收的多个数据包进行编码(如模二加、有限域 上的运算等)信息融合,增加单次传输的信息量, 以提高网络信息传输效率和整体性能核心核心:允许网络节点对传输信息进行编码处理经典信息论中的信息传输:单纯共享网络和链路资源,彼此独立。1998论文“ Network Information Flow Theory
2、”1999 Yeung和Zhang发表的关于卫星通信的论文2000网络编码理论的奠基之作:先锋论文“ NetworkInformationFlow” 香港中文大学讯息工程系的李硕彦教授、 杨伟豪教授、 蔡宁教授发表了论文“LinearNetworkCoding” 指出线性网络编码可以达到多播方式下的网络容量。 Koetter和Medard提出网络编码的代数学(Algebra)框架, 即用抽象代数来解决线性网络编码的问题, 为研究网络编码提供了一个用力的数学工具 Sanders等提出具有多项式复杂度的线性信息流算法, 该算法属于集中式的码构造算法。 Ho等提出随机网络编码(RandomNetwo
3、rkCoding,RNC), 属于分布式的码构造方法。割:网络中定点的一个划分,把网络中所有的顶点划分为两个顶点的集合S和T,其中源点s属于S,汇点t属于T,记为CUT(S,T)顶点集: S=1,2,3, T=4,5构成一个割框外是容量,框内是流量注:源点和汇点不能属于同一个顶点集合:如下就不能构成一个割s-t图:a 一个源点和一个汇点b 有向边,是从i到jc 每条边都有一个非负的权值d 容量cap(i,j)等于0,说明不存在边割边:如果一条弧的两个顶点分别属于顶点集S和T(一个在S,另一个在T),这条弧成为CUT(S,T)的一条割边。割的容量:割CUT(S,T)中所有正向割边正向割边的容量和
4、,称为CUT(S,T)的容量,不同割的容量不同。最小割:所有割中权重和最小的一个割。eg. 左图中:割的容量为4+4=8 正向流量:4+2=6 逆向流量:1定理一定理一: 如果f是网络中的一个流,CUT(S,T)是任意一个割,那么f的值等于正向割边的流量与负向割边的流量之差。推论一推论一:如果f是网络中的一个流,CUT(S,T)是一个割,那么f的值不超过割CUT(S,T)的容量推论二:推论二:网络中的最大流不超过任何割的容量。定理二定理二:在网络中,如果f是一个流,CUT(S,T)是一个割,且f的值等于割CUT(S,T)的容量,那么f是一个最大流,CUT(S,T)是一个最小割。最大流最小割定理
5、:最大流最小割定理:任何网络中,最大流等于最小割的容量形象的比喻:水流管道的最大流量由最细的管子容量决定。网络的最大流量由最小割决定。概念概念12应用应用3总结总结4原理原理蝴蝶网络”(Butterfly Network)左图为“单信源二信宿”蝴蝶网络设各链路容量为1S:信源节点。 Y,Z:信宿节点。 其余为中间节点。由最大流最小割定理,该多播的最大理论传输容量为2。即理论上信宿Y和Z能够同时收到信源S发出的2个单位的信息,,也就是说能同时收到b1和b2。图(a)图(b) 具备编码条件的网络节点A对接收到的信息进行一定方式的处理(编码) ,然后传输给下一级的网络节点B B再编码,然后传输给C。
6、如此反复,直到所有经过处理后的信息都汇聚到信宿节点为止。 在信宿节点,通过逆过程的操作(译码) ,即可译出信源发送的原始信息。目的: A和 B 希望分别向对方发送数据块 x 和 y BS BS SSA R BXY 简单网络编码示例基站中继站用户站BRYRBXARXRAY传统方法:需要 4 个时隙1) 2)3) 4) 网络编码方法:需要的时隙数减为 3 个1)2)3) R对X,Y执行异或操作并向A,B 广播,A,B各自有X,Y的信息,可以通过译码得到X,和YARXBRY概念12应用3总结4原理 协作通信通过网络节点协作的方式接收转发其他伙伴的信息到目的端,以获得系统的分集增益,从而对抗无线信道的
7、各种衰落。 网络编码借助于融合了编码和路由的新思想,通过允许中间节点对来自不同链路的信息进行解码组合,利用数据包之间的相关性来解码,从而提升整个网络的性能。网络编码在无线协作通信中的应用网络编码在无线协作通信中的应用背景与意义背景与意义协作通信系统模型 结合网路编码思想与协作通信技术,以能更好的充分发挥网络编码技术在无线协作通信系统中的应用优势,进一步提高基于网络编码的无线协作系统性能.协作通信的分类协作通信的分类放大转发(放大转发(AF, Amplify and Forward) 在信道质量较差的情况下,AF会将噪声放大。解码转发解码转发 (DF,Decode and Forward) 在信
8、道质量较差的情况下,DF中继无法正确解码。 两者都是信息的重复传输,信道利用率不高,造成资源浪费。编码协作(编码协作(CC,Cooperation Coded) 提供比重复编码更高效的编码方式,从而带来更多的编码增益。但是中继点复杂度高,中继点信号处理时延增大,降低了时效性。编码协作(编码协作(CCCC) CC协议是解码转发协作(DF)的进一步延伸,它改变DF策略的重复编码方式,通过两条不同的,相互独立的衰落信道来发送每个用户的信息码字的不同部分,从而提供更多的编码增益。无线网络编码分类无线网络编码分类1.网络层网络编码2.物理层网络编码 针对网络层编码技术,目前的一个研究重点是在实际的网络条
9、件下,采样网络编码后的网络容量以及可以达到的网络容量的传输策略 物理层网络编码提高了无线频谱的利用率,物理层网络编码技术目前的研究重点是怎样有效的从混合信号中分离出需要的信号。S1RS2D1x1x2x2x21xx 传输时隙传输时隙信息传输方向信息传输方向传输信息传输信息简要说明简要说明时隙1(直传)S1(R,D)X1S1传送信息X1到R和D时隙2(直传)S2(R,D)X2S2传送信息X2到R和D时隙3(协作)R(D)X1 X2R将收到的信息进行编码后转发给D时隙1时隙2时隙3网络编码在分布式存储中的应用 传统的存储模型中,大多为直连式存储系统,其存储设备直接与服务器 相连。此类存储模型可扩展性
10、极差,数据共享能力弱。 1986年,著名学者李凯针对大数据存储困难的现状提出了分布式存储 的概念,该思想源于虚拟存储系统。 分布式存储就是将源文件分散的存储到网络中的相互独立的空闲节点中。 优越性 (1)高可靠性高可靠性 (2)修复功能修复功能 (3)可扩展性可扩展性 (4)高性能高性能 (5)透明性透明性网络纠错码 网络编码的初衷在于提高网络的吞吐量,但是随着进一步研究发现它也是一种安全网络传输的好方式。然而在抗击拜占庭攻击时,我们不仅要能够检测出敌手对信息的恶意攻击,还要尽量能够做到对这些信息的恢复,这就是网络纠错码.传统的密码学方法存在一定的局限性 计算复杂度较大、 数据传输速率较低、
11、消息冗余较大 最常用冗余数据的维护技术是复制和纠删码。 当我们在利用纠删码纠删码对失效节点进行修复的时候,首先要将原始数据重建,然后将其用网络编码的方法进行编码,但是这样修复时数据的下载量远远多于节点的存储,即修复带宽远大于存储量。两种常用的冗余数据维护技术在对数据节点进行修复时,需要消耗很大的下载带宽,于是产生了一种新型的技术再生码。实现了存储量与修复下载带宽的良好折中,部分还巧妙地结合了复制与纠删码的各自优点,保证了具有极高的节点成功修复的可能性。他们把节点修复的问题刻画为网络系统中普遍的单源多播问题,然后把对分布式存储系统的分析化成对信息流图的分析ddknG),(对于任意 , 分布式存储
展开阅读全文