删除码ErasureCodes讲义.pptVIP

Erasure Codes 张大为 2002.9.24 背景介绍 最初，网络传输不可靠，产生了在协议栈各层实现的提供可靠性的技术。 Erasure codes用来解决链接层中不相关的错误，以及网络拥塞和buffer限制造成的丢包错误。 ARQ(Automatic Repeat reQuest)在单向传输的协议中能起到很好的作用，但是对于多播协议，使用ARQ就十分浪费资源了。 技术背景 EvenOdd Linear code EvenOdd 实现对m个m－1维的数组进行错误校验 包含两个校验列 校验列的计算 EvenOdd举例 EvenOdd举例（一） 填充第一个校验列 EvenOdd举例（二） EvenOdd举例（三） 假设后两列数据丢失 EvenOdd举例（三） 使用校验列来计算S S=0 + 1 + 1 + 0 + 1 + 0 + 0 + 0 EvenOdd Evenodd要求m为素数 m的选取 有n个数据 取m为大于n的最小素数 其余列补0 Linear Codes 对于域F=GF(q)上的一个(n,M,d)编码C为linear code,如果C在Fn的子空间为linear的，即对任意c1,c2? C,a1,a2? F,都有a1c1+a2c2? C 对于一个(n,k)线性码，定义k个n维的向量v1,v2,……vk,对k个消息m1,m2,……mk进行编码形成codeword x=m1v1+m2v2+……+mkvk 关键在于向量v的选取，能保证发现传输中产生的错误 Linear Codes举例 将向量v组成矩阵G v1=[100011],v2=[010110],v3=[001101] 消息编码过程 Linear Codes举例（一） 错误校验需要构造矩阵H,H满足HGT=0 H(mG)T=H(GTmT)=(HGT)mT=0 譬如G为 Linear Codes举例（二） 构造H为 对消息m(1100)进行编码得到 x=mG=1100010 如果传输过程中出现错误，接收方收到的x为1110010 HxT=sT=[011] Galois Field GF(q),q=pr,p为素数 能有效的控制一个在该域中运算的编码的数据膨胀 Prime field：r＝1 包含从0到p-1个整数 域中的加操作和乘操作就是简单的取和或乘积再对p取模 Extension field：r1 域中的元素用阶为r-1的多项式表达 加操作：两个多项式相加，系数模p 乘操作：多项式相乘，再对一个不可约的多项式取模，系数模P Extension Field 对于GF(28). 其中元素是byte. 元素(0100 1001)表示成x6+x3+1。 不可约的多项式： 1 0001 1101 = x8+x4+x3+x2+1. Extension Field乘法 Extension Field乘法 Erasure codes Erasure codes x=x0,x1,……,xk-1 生成矩阵G为n*k的矩阵 一个(n,k)的线性码可以表示为y=Gx Erasure codes G中任意k行必须线性无关，即G中任意k行的子矩阵可逆。 如果G中包含一个确定矩阵Ik，则线性码(n,k)称为系统码(systematic code)。 系统码在块丢失很少的情况下能较快的重构数据。 G中矩阵Ik外都必须是非零元素。 Erasure codes重构 y’=G’x - x=G’-1y’ y’为y的一个k个元素的子向量 G’为G中的一个k行的子矩阵 生成矩阵的构造 G=(Ik|Vk,n-k) Vk,n-k为一个Vandermonde矩阵，vij＝aij-1 Erasure codes实现问题 如何构造一个好的生成矩阵 如何快速的进行encoding，decoding操作 进一步的工作 谢谢！ * * 设m＝5 S = a3,1+a2,2+a1,3+a0,4 = 0+1+0+0 = 1 填充第二个校验列 *