删除码(Erasure Codes)讲义.ppt

《删除码(Erasure Codes)讲义.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ErasureCodes张大为2002.9.24背景介绍最初，网络传输不可靠，产生了在协议栈各层实现的提供可靠性的技术。Erasurecodes用来解决链接层中不相关的错误，以及网络拥塞和buffer限制造成的丢包错误。ARQ(AutomaticRepeatreQuest)在单向传输的协议中能起到很好的作用，但是对于多播协议，使用ARQ就十分浪费资源了。技术背景EvenOddLinearcodeEvenOdd实现对m个m－1维的数组进行错误校验包含两个校验列校验列的计算EvenOdd举例设m＝5EvenOdd举例（一）填充第一个校验列S=a3,1+a2,2+a1,3+a0,4=0+1+0

2、+0=1EvenOdd举例（二）填充第二个校验列EvenOdd举例（三）假设后两列数据丢失EvenOdd举例（三）使用校验列来计算SS=0+1+1+0+1+0+0+0EvenOddEvenodd要求m为素数m的选取有n个数据取m为大于n的最小素数其余列补0LinearCodes对于域F=GF(q)上的一个(n,M,d)编码C为linearcode,如果C在Fn的子空间为linear的，即对任意c1,c2C,a1,a2F,都有a1c1+a2c2C对于一个(n,k)线性码，定义k个n维的向量v1,v2,……vk,对k个消息m1,m2,……mk进行编码形成codewordx=m1v1+m

3、2v2+……+mkvk关键在于向量v的选取，能保证发现传输中产生的错误LinearCodes举例将向量v组成矩阵Gv1=[100011],v2=[010110],v3=[001101]消息编码过程LinearCodes举例（一）错误校验需要构造矩阵H,H满足HGT=0H(mG)T=H(GTmT)=(HGT)mT=0譬如G为LinearCodes举例（二）构造H为对消息m(1100)进行编码得到x=mG=1100010如果传输过程中出现错误，接收方收到的x为1110010HxT=sT=[011]GaloisFieldGF(q),q=pr,p为素数能有效的控制一个在该域中运算的编码的数据膨胀

4、Primefield：r＝1包含从0到p-1个整数域中的加操作和乘操作就是简单的取和或乘积再对p取模Extensionfield：r>1域中的元素用阶为r-1的多项式表达加操作：两个多项式相加，系数模p乘操作：多项式相乘，再对一个不可约的多项式取模，系数模PExtensionField对于GF(28).其中元素是byte.元素(01001001)表示成x6+x3+1。不可约的多项式：100011101=x8+x4+x3+x2+1.ExtensionField乘法ExtensionField乘法ErasurecodesErasurecodesx=x0,x1,……,xk-1生成矩阵G为n*k

5、的矩阵一个(n,k)的线性码可以表示为y=GxErasurecodesG中任意k行必须线性无关，即G中任意k行的子矩阵可逆。如果G中包含一个确定矩阵Ik，则线性码(n,k)称为系统码(systematiccode)。系统码在块丢失很少的情况下能较快的重构数据。G中矩阵Ik外都必须是非零元素。Erasurecodes重构y’=G’x->x=G’-1y’y’为y的一个k个元素的子向量G’为G中的一个k行的子矩阵生成矩阵的构造G=(Ik

6、Vk,n-k)Vk,n-k为一个Vandermonde矩阵，vij＝aij-1Erasurecodes实现问题如何构造一个好的生成矩阵如何快速的进行encod

7、ing，decoding操作进一步的工作谢谢！