資源描述：
《刪除碼(Erasure Codes)講義.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、ErasureCodes張大為2002.9.24背景介紹最初，網(wǎng)絡(luò)傳輸不可靠，產(chǎn)生了在協(xié)議棧各層實現(xiàn)的提供可靠性的技術(shù)。Erasurecodes用來解決鏈接層中不相關(guān)的錯誤，以及網(wǎng)絡(luò)擁塞和buffer限制造成的丟包錯誤。ARQ(AutomaticRepeatreQuest)在單向傳輸?shù)膮f(xié)議中能起到很好的作用，但是對于多播協(xié)議，使用ARQ就十分浪費資源了。技術(shù)背景EvenOddLinearcodeEvenOdd實現(xiàn)對m個m－1維的數(shù)組進(jìn)行錯誤校驗包含兩個校驗列校驗列的計算EvenOdd舉例設(shè)m＝5EvenOdd舉例（一）填充第一個校驗列S=a3,1+a2,2+a1,3+a0,4=0+1+0
2、+0=1EvenOdd舉例（二）填充第二個校驗列EvenOdd舉例（三）假設(shè)后兩列數(shù)據(jù)丟失EvenOdd舉例（三）使用校驗列來計算SS=0+1+1+0+1+0+0+0EvenOddEvenodd要求m為素數(shù)m的選取有n個數(shù)據(jù)取m為大于n的最小素數(shù)其余列補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進(jìn)行編碼形成codewordx=m1v1+m
3、2v2+……+mkvk關(guān)鍵在于向量v的選取，能保證發(fā)現(xiàn)傳輸中產(chǎn)生的錯誤LinearCodes舉例將向量v組成矩陣Gv1=[100011],v2=[010110],v3=[001101]消息編碼過程LinearCodes舉例（一）錯誤校驗需要構(gòu)造矩陣H,H滿足HGT=0H(mG)T=H(GTmT)=(HGT)mT=0譬如G為LinearCodes舉例（二）構(gòu)造H為對消息m(1100)進(jìn)行編碼得到x=mG=1100010如果傳輸過程中出現(xiàn)錯誤，接收方收到的x為1110010HxT=sT=[011]GaloisFieldGF(q),q=pr,p為素數(shù)能有效的控制一個在該域中運算的編碼的數(shù)據(jù)膨脹
4、Primefield：r＝1包含從0到p-1個整數(shù)域中的加操作和乘操作就是簡單的取和或乘積再對p取模Extensionfield：r>1域中的元素用階為r-1的多項式表達(dá)加操作：兩個多項式相加，系數(shù)模p乘操作：多項式相乘，再對一個不可約的多項式取模，系數(shù)模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行必須線性無關(guān)，即G中任意k行的子矩陣可逆。如果G中包含一個確定矩陣Ik，則線性碼(n,k)稱為系統(tǒng)碼(systematiccode)。系統(tǒng)碼在塊丟失很少的情況下能較快的重構(gòu)數(shù)據(jù)。G中矩陣Ik外都必須是非零元素。Erasurecodes重構(gòu)y’=G’x->x=G’-1y’y’為y的一個k個元素的子向量G’為G中的一個k行的子矩陣生成矩陣的構(gòu)造G=(Ik
6、Vk,n-k)Vk,n-k為一個Vandermonde矩陣，vij＝aij-1Erasurecodes實現(xiàn)問題如何構(gòu)造一個好的生成矩陣如何快速的進(jìn)行encod
7、ing，decoding操作進(jìn)一步的工作謝謝！
