网络编码.pptVIP

网络编码 概 要 1. 网络编码的提出及现状 2. 网络编码的基本原理 3. 基于网络编码的纠错码 4. 无线组播中的网络编码 5. 结束语 1. 网络编码的提出 网络编码的提出 网络编码的提出 （点对点的最小割最大流定理） 对于已知的网络流图，从发点 到收点 的流量 的最大值小于或等于任何一个割切的容量，即 记 。 网络编码的提出 网络编码的提出 网络编码的提出 网络编码带来的好处： 使组播传输速率达到最小割最大流决定的网络容量的上限 节省网络带宽资源消耗 均衡网络负载 提高网络鲁棒性 网络编码的发展过程 2000年，Ahlswede等提出了网络编码的概念。 2002年，Koetter等给出了网络编码的代数构造算法，是指数时间算法（集中式）。 2002年，Cai等提出了基于网络编码的网络纠错码概念。 2002年， Cai等提出了采用网络编码时的信息完安全性问题。 2003年，Sander等给出了网络编码的多项式时间算法（集中式）。 2003年，Chou等提出了分布式网络编码，通过仿真得到其性能。 2003年，Ho等也提出了随机网络编码（分布式）。 2004年，Wu等将网络编码应用于无线网络以节省能量。 网络编码的现状 线性网络编码和非线性网络编码； 分布式网络编码和集中式网络编码； 网络编码在组播和非组播网络中的应用 目前，组播集中式线性网络编码算法主要有两种：代数构造方式和多项式时间算法； 2. 网络编码的基本原理 信息传输网络可用图 表示 信源节点集： 信宿节点集： 边 的头节点用 表示 边 的尾节点用 表示 网络编码的基本原理 网络编码的数学描述 (适用于组播和非组播传输） 对边集 中的每条边 ，存在一种 映射： 这是对应于每条边的编码函数。 网络编码的基本原理 网络编码的数学描述(适用于组播和非组播传输） 目的节点 为了得到所需信息，存在映射： 映射 是对应于目的节点 的第 个信源符号的译码函数。 网络编码的基本原理 线性网络编码的代数构造 设所有信源 的总信息输出速率是 比特/单位时间。把它们的输出进行一个定序，如下： 其中 是节点 的信息输出速率。 网络编码的基本原理 线性网络编码的代数构造 设 是无延迟的通信网络。我们称这样的编码为线性网络编码，如果对于网络中的每一条边 的传输符号均满足： 其中 。 网络编码的基本原理 线性网络编码的代数构造 定义 矩阵 和 矩阵 如下： 则系统转移矩阵为： 网络编码的基本原理 组播线性网络编码成功的条件 组播通信网络中， 信源输出向量： 接收节点 接收向量: 其中, 是接收节点 的系统转移矩阵。 于是，为了由接收到的信息向量 解出信 源输入 ，则必须要求系统转移矩阵 可逆。 3. 基于网络编码的纠错码 基于网络编码的差错控制是针对网络、而非一条链路或一条路径进行操作的。通过合适的选择信源空间，可以纠正传输网络中几条链路上发生的传输错误，这是一个比较新的差错控制方式，称之为基于网络编码的差错控制 。 基于网络编码的纠错码 参与多播传输的链路数用 表示。 组播网络的网络容量 为 比特/单位时间。 基于网络编码的纠错码 如果从某条链路上输出的符号不等于输入的符号，那么称发生错误。 如果在传输网络中总共有 条链路发生错误，就称为网络发生了 个错误。 如果一个基于网络编码的纠错码能纠正所有错误个数小于等于 的情况，就称该码是 -差错控制码。 基于网络编码的纠错码 把发生在传输网络上的错误用一个 维行向量 表示，称为错误向量。如果其 中有 个分量不为零，则称错误向量重为 。 基于网络编码的纠错码 基于网络编码的纠错码 对于任意 , 和 可分,即能纠任意重量 小于等于 t 的错误，当且仅当 基于网络编码的纠错码 基于网络编码的纠错码 基于网络编码的纠错码 基于网络编码的纠错码 基于网络编码的纠错码 基于网络编码的纠错码 基于网络编码的纠错码 基于网络编码的纠错码 基于网络编码的纠错码 基于网络编码的纠错码 4. 无线组播中的网络编码 无线组播特