糾突發(fā)錯(cuò)誤編碼PPT課件

1、State Key Laboratory of Integrated Services Networks 糾突發(fā)錯(cuò)誤編碼糾突發(fā)錯(cuò)誤編碼突發(fā)信道突發(fā)信道短波、散射、有線(xiàn)信道；磁記錄信道等，突發(fā)錯(cuò)短波、散射、有線(xiàn)信道；磁記錄信道等，突發(fā)錯(cuò)誤或突發(fā)錯(cuò)誤與隨機(jī)錯(cuò)誤并存誤或突發(fā)錯(cuò)誤與隨機(jī)錯(cuò)誤并存突發(fā)信道的最好的差錯(cuò)控制方法是突發(fā)信道的最好的差錯(cuò)控制方法是ARQ以多項(xiàng)式表示錯(cuò)誤圖樣：在長(zhǎng)為以多項(xiàng)式表示錯(cuò)誤圖樣：在長(zhǎng)為n的碼字內(nèi)，的碼字內(nèi)，長(zhǎng)度不大于長(zhǎng)度不大于b的突發(fā)錯(cuò)誤圖樣是：的突發(fā)錯(cuò)誤圖樣是：E(x)=xib(x) i=0,1,n-b, deg(b(x) b-1循環(huán)（首尾相接）突發(fā)錯(cuò)誤圖樣：循環(huán)（首尾相

2、接）突發(fā)錯(cuò)誤圖樣：E(x)=xib(x)i=0,1,n-1 (mod xn-1)任何一個(gè)任何一個(gè)n,k分組碼，若能糾正碼組中長(zhǎng)分組碼，若能糾正碼組中長(zhǎng)度不大于度不大于b的所有突發(fā)錯(cuò)誤圖樣，則稱(chēng)的所有突發(fā)錯(cuò)誤圖樣，則稱(chēng)b為為該碼的該碼的糾突發(fā)能力糾突發(fā)能力。糾突發(fā)能力和糾突發(fā)能力和n，k關(guān)系關(guān)系一個(gè)一個(gè)q進(jìn)制進(jìn)制n, k線(xiàn)性分組碼，若要發(fā)現(xiàn)（或檢測(cè)）線(xiàn)性分組碼，若要發(fā)現(xiàn)（或檢測(cè)）所有長(zhǎng)度所有長(zhǎng)度b的突發(fā)錯(cuò)誤，其充要條件是需要的突發(fā)錯(cuò)誤，其充要條件是需要b個(gè)個(gè)校驗(yàn)元。校驗(yàn)元。任何任何n,k線(xiàn)性碼，能發(fā)現(xiàn)所有長(zhǎng)度線(xiàn)性碼，能發(fā)現(xiàn)所有長(zhǎng)度n-k的突發(fā)錯(cuò)的突發(fā)錯(cuò)誤。誤。糾突發(fā)能力和糾突發(fā)能力和n，k關(guān)系關(guān)

3、系一個(gè)一個(gè)q進(jìn)制進(jìn)制n, k線(xiàn)性碼，若線(xiàn)性碼，若(1)要糾正所有長(zhǎng)度要糾正所有長(zhǎng)度b的突發(fā)，則至少需要的突發(fā)，則至少需要2b個(gè)校個(gè)校驗(yàn)元，即驗(yàn)元，即n-k 2b； (Rieger限，必要條件限，必要條件) (2)要糾正所有長(zhǎng)度要糾正所有長(zhǎng)度b，且同時(shí)發(fā)現(xiàn)所有長(zhǎng)度，且同時(shí)發(fā)現(xiàn)所有長(zhǎng)度d, (db)的突發(fā)，至少需要的突發(fā)，至少需要b+d個(gè)校驗(yàn)元，即個(gè)校驗(yàn)元，即n-k b+d若若n, k線(xiàn)性碼要具有能糾正任何長(zhǎng)度線(xiàn)性碼要具有能糾正任何長(zhǎng)度b的突發(fā)錯(cuò)的突發(fā)錯(cuò)誤能力，其充要條件是任何兩個(gè)長(zhǎng)度誤能力，其充要條件是任何兩個(gè)長(zhǎng)度b的突發(fā)的的突發(fā)的任意組合不能作為一個(gè)碼字。任意組合不能作為一個(gè)碼字。糾突發(fā)能力和

4、糾突發(fā)能力和n，k關(guān)系關(guān)系具有糾突發(fā)能力為具有糾突發(fā)能力為b的的n,k線(xiàn)性碼，能檢測(cè)任何線(xiàn)性碼，能檢測(cè)任何兩個(gè)長(zhǎng)度兩個(gè)長(zhǎng)度b的突發(fā)錯(cuò)誤的所有組合，反之亦然。的突發(fā)錯(cuò)誤的所有組合，反之亦然。具有糾突發(fā)能力為具有糾突發(fā)能力為b的的n,k線(xiàn)性碼，能糾正任何線(xiàn)性碼，能糾正任何兩個(gè)長(zhǎng)度兩個(gè)長(zhǎng)度b的突發(fā)刪除錯(cuò)誤的突發(fā)刪除錯(cuò)誤若碼的糾錯(cuò)能力達(dá)到若碼的糾錯(cuò)能力達(dá)到R限，則該碼為限，則該碼為R意義下的最意義下的最佳就突發(fā)錯(cuò)誤碼，簡(jiǎn)稱(chēng)佳就突發(fā)錯(cuò)誤碼，簡(jiǎn)稱(chēng)R最佳碼。最佳碼。Z=2b/(n-k)s s=n-k-2b糾突發(fā)能力和糾突發(fā)能力和n，k關(guān)系關(guān)系1Td1324max,12TiidTbd12dp13441max,

5、42piidpdb 有最小距離為有最小距離為d的的n,k循環(huán)碼，能檢測(cè)每個(gè)長(zhǎng)度循環(huán)碼，能檢測(cè)每個(gè)長(zhǎng)度bi(i=1,2,T)的所有的所有T個(gè)突發(fā)，其中個(gè)突發(fā)，其中有最小距離為有最小距離為d的的n,k循環(huán)碼，能同時(shí)糾正循環(huán)碼，能同時(shí)糾正p個(gè)突發(fā)個(gè)突發(fā)錯(cuò)誤，且每個(gè)突發(fā)長(zhǎng)度為錯(cuò)誤，且每個(gè)突發(fā)長(zhǎng)度為bi，i=1,2,T，其中，其中糾突發(fā)能力和糾突發(fā)能力和n，k關(guān)系關(guān)系212nkb對(duì)任何一個(gè)對(duì)任何一個(gè)n, k, d3二進(jìn)制循環(huán)碼，糾突發(fā)能力二進(jìn)制循環(huán)碼，糾突發(fā)能力對(duì)大部分二進(jìn)制對(duì)大部分二進(jìn)制n, k, d3BCH碼，糾突發(fā)能力碼，糾突發(fā)能力b滿(mǎn)足滿(mǎn)足22nkdbFire碼碼設(shè)設(shè)g1(x)生成一個(gè)糾突發(fā)能力

6、為生成一個(gè)糾突發(fā)能力為b的的n1,k1循環(huán)碼，循環(huán)碼，p(x)的周期為的周期為a，且，且deg(p(x) b,(p(x),g1(x)=1，則，則由由g(x)=g1(x)p(x)生成的循環(huán)碼，碼長(zhǎng)生成的循環(huán)碼，碼長(zhǎng)n=n1a,能糾正能糾正長(zhǎng)度長(zhǎng)度b的所有突發(fā)錯(cuò)誤。的所有突發(fā)錯(cuò)誤。由由g(x)=(x2b-1+1)p(x)生成的生成的n,n-2b-m+1的循環(huán)碼稱(chēng)的循環(huán)碼稱(chēng)為為fire碼。能糾正碼字內(nèi)長(zhǎng)度碼。能糾正碼字內(nèi)長(zhǎng)度b的所有單個(gè)突發(fā)錯(cuò)的所有單個(gè)突發(fā)錯(cuò)誤。碼長(zhǎng)誤。碼長(zhǎng)n=LCM(e,2b-1)，e是是p(x)的周期，且的周期，且deg(p(x)=mb,(p(x),x2b-1+1)=1Z=2b/

7、(3b+1)RS碼碼GF(qm)上的能糾正上的能糾正t個(gè)錯(cuò)誤的個(gè)錯(cuò)誤的qm-1,qm-1-2tRS碼，碼，能糾正能糾正GF(qm)上的長(zhǎng)度上的長(zhǎng)度t的突發(fā)錯(cuò)誤，的突發(fā)錯(cuò)誤，Z=1n,k碼，碼，n=s sm，定義，定義m個(gè)連續(xù)碼元為一段，一個(gè)個(gè)連續(xù)碼元為一段，一個(gè)長(zhǎng)度長(zhǎng)度l lm并且局限于連續(xù)并且局限于連續(xù)l l段的突發(fā)，定義為一個(gè)段的突發(fā)，定義為一個(gè)定段突發(fā)錯(cuò)誤。定段突發(fā)錯(cuò)誤。若采用若采用GF(q)表示每個(gè)碼元，可糾正長(zhǎng)度表示每個(gè)碼元，可糾正長(zhǎng)度m的的t個(gè)個(gè)定段突發(fā)錯(cuò)誤，亦可糾正長(zhǎng)度定段突發(fā)錯(cuò)誤，亦可糾正長(zhǎng)度mt的單個(gè)定段突的單個(gè)定段突發(fā)錯(cuò)誤發(fā)錯(cuò)誤交錯(cuò)碼與乘積碼交錯(cuò)碼與乘積碼思路：將突發(fā)錯(cuò)誤離

8、散成隨機(jī)錯(cuò)誤思路：將突發(fā)錯(cuò)誤離散成隨機(jī)錯(cuò)誤交錯(cuò)碼：交錯(cuò)碼：n,k ni,ki，i：交錯(cuò)次數(shù)或交錯(cuò)度：交錯(cuò)次數(shù)或交錯(cuò)度 若行碼能糾正若行碼能糾正t個(gè)隨機(jī)錯(cuò)誤或個(gè)隨機(jī)錯(cuò)誤或b長(zhǎng)突發(fā)錯(cuò)誤，則長(zhǎng)突發(fā)錯(cuò)誤，則ni,ki交錯(cuò)交錯(cuò)碼能糾正所有長(zhǎng)度碼能糾正所有長(zhǎng)度it或或ib的突發(fā)的突發(fā) 若行碼能糾正若行碼能糾正t個(gè)隨機(jī)錯(cuò)誤，則個(gè)隨機(jī)錯(cuò)誤，則ni,ki交錯(cuò)碼能糾正交錯(cuò)碼能糾正t個(gè)長(zhǎng)度個(gè)長(zhǎng)度i的突發(fā)錯(cuò)誤或糾正長(zhǎng)度的突發(fā)錯(cuò)誤或糾正長(zhǎng)度it的單個(gè)突發(fā)的單個(gè)突發(fā)a1,n-1 a1,n-2 . a1,n-k a1,n-k-1 a1,1 a1,0a2,n-1 a2,n-2 . a2,n-k a2,n-k-1 a2,1 a2,0ai,n-1 ai,n-2 . ai,n-k ai,n-k-1 ai,1 ai,0交錯(cuò)碼與乘積碼交錯(cuò)碼與乘積碼乘積碼乘積碼(二維碼二維碼)：n1,k1,n2,k2 n1n2,k1k211111111111121212112112212121121121,11,21,1,11,02,12,22,2,12,0,1,2,1,01,11,21,1,11,0.nnn kn knnn kn kk nk nk n kk n kkknknkn kkn kkaaaaaaaaaaaaaaaaaaaa 21212112112,1,2,1,0.n nn nn n kn n knaaaaa bma