信息论-网络编码 ppt课件.ppt

文档介绍：网络编码组员:代亮亮徐杰郭鑫李文杰胡怡刘慧芳张晓宇*PPT课件概念12应用3总结4目录原理*PPT课件1、概念网络编码:通信网络中信息处理和传输理论研究上的重大突破。网络编码:融合了编码和路由转发的信息交换技术,在传统存储转发的路由方法基础上,通过允许对接收的多个数据包进行编码(如模二加、有限域上的运算等)信息融合,增加单次传输的信息量,以提高网络信息传输效率和整体性能核心:允许网络节点对传输信息进行编码处理经典信息论中的信息传输:单纯共享网络和链路资源,彼此独立。*PPT课件网络编码的起源与发展概念诞生:workInformationFlowTheory”1999Yeung和Zhang发表的关于卫星通信的论文正式发表:2000网络编码理论的奠基之作:workInformationFlow”里程碑(2003):香港中文大学讯息工程系的李硕彦教授、杨伟豪教授、蔡宁教授发表了论文“workCoding”指出线性网络编码可以达到多播方式下的网络容量。Koetter和Medard提出网络编码的代数学(Algebra)框架,即用抽象代数来解决线性网络编码的问题,为研究网络编码提供了一个用力的数学工具Sanders等提出具有多项式复杂度的线性信息流算法,该算法属于集中式的码构造算法。Ho等提出随机网络编码(workCoding,RNC),属于分布式的码构造方法。*PPT课件基础知识:最大流最小割定理1/5割:网络中定点的一个划分,把网络中所有的顶点划分为两个顶点的集合S和T,其中源点s属于S,汇点t属于T,记为CUT(S,T)顶点集:S={1,2,3},T={4,5}构成一个割框外是容量,框内是流量注:源点和汇点不能属于同一个顶点集合:如下就不能构成一个割*PPT课件基础知识:最大流最小割定理2/5s-t图:a一个源点和一个汇点b有向边,<i,j>是从i到jc每条边都有一个非负的权值d容量cap(i,j)等于0,说明不存在边*PPT课件基础知识:最大流最小割定理3/5割边:如果一条弧的两个顶点分别属于顶点集S和T(一个在S,另一个在T),这条弧成为CUT(S,T)的一条割边。割的容量:割CUT(S,T)中所有正向割边的容量和,称为CUT(S,T)的容量,不同割的容量不同。最小割:所有割中权重和最小的一个割。:割的容量为4+4=8正向流量:4+2=6逆向流量:1*PPT课件定理一:如果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)是一个最小割。基础知识:最大流最小割定理4/5*PPT课件最大流最小割定理:任何网络中,最大流等于最小割的容量形象的比喻:水流管道的最大流量由最细的管子容量决定。网络的最大流量由最小割决定。基础知识:最大流最小割定理5/5*PPT课件