1、遠(yuǎn)動信息的信道編譯碼,差錯控制或抗干擾編碼,遠(yuǎn)動信息的信道編譯碼,抗干擾編碼的基本原理 奇偶校驗(yàn)碼與校驗(yàn)和 循環(huán)碼： 編譯碼原理 檢錯與糾錯能力 編譯碼算法,抗干擾編碼的基本原理,定義： 采用可靠、有效的編碼以發(fā)現(xiàn)或糾正數(shù)字信號在傳輸過程中由于噪聲干擾而造成的錯碼，稱為抗干擾編碼，又稱信道編碼。 實(shí)現(xiàn)方法： 對信源編碼得到的信息序列，按照某種規(guī)律，添加一定的校驗(yàn)碼元，構(gòu)成一個具有抗干擾能力的碼字。添加校驗(yàn)碼元的規(guī)律或規(guī)則不同，形成不同的編碼方法。 常用的編碼方法 奇偶校驗(yàn)、校驗(yàn)和、循環(huán)冗余校驗(yàn)（CRC）。,信道編碼的實(shí)現(xiàn),對于長度為k的信息碼元序列，按一定規(guī)律加入r=n-k位監(jiān)督碼元，組成長度

2、為n的碼字，記作(n,k)碼。 若r位校驗(yàn)碼只與本碼字中的k位信息位相關(guān)，稱為分組碼 若r位校驗(yàn)碼不僅與本碼字中的k位信息位相關(guān)，還與前面若干個碼字的信息元相關(guān)，稱為卷積碼 (n,k)碼可能出現(xiàn)的碼字為 2k 種 長度為n的碼元可能出現(xiàn) 2n 種,信道譯碼,信道譯碼： 接收端收到一個碼字后，判斷它是否發(fā)端發(fā)來的碼字，是哪個碼字。 采用最大似然譯碼： 將接收到的碼字與信道編碼時可能輸出的2k 個碼字比較，將其中最相似的碼字作為正確的接收碼字。,碼距與最小碼距,兩個長度相同的碼字之間對應(yīng)碼位上不相同的碼元的數(shù)目，稱為這兩個碼字之間的距離，簡稱碼距。 在一種碼的所有碼字集合中，任意兩個碼字之間的最小

3、距離，稱為這個碼字集合的最小碼距，記為dmin。,最大似然譯碼的實(shí)現(xiàn),計(jì)算收到的碼字與發(fā)端可能發(fā)送碼字之間的碼距，與哪個碼字的碼距最小，則判斷接收碼字就是這個發(fā)送碼字。 最小碼距dmin與檢錯能力與糾錯能力的關(guān)系： t 能糾正的錯誤個數(shù) l 能檢出的錯誤個數(shù),對抗干擾編碼的要求,編碼效率：對于(n,k)碼，編碼效率為： 編碼性能（較好的檢錯與糾錯能力） 編碼易于實(shí)現(xiàn),奇偶校驗(yàn)碼,編碼規(guī)則： 在n-1位信息元后面，添加一位碼元，使碼字中“1”的個數(shù)恒為奇數(shù)或偶數(shù)。 當(dāng)“1”的個數(shù)恒為奇數(shù)時，稱為奇校驗(yàn)碼 當(dāng)“1”的個數(shù)恒為偶數(shù)時，稱為偶校驗(yàn)碼 編碼效率： 性能分析： 檢錯能力：可以檢出奇數(shù)個錯誤

4、 糾錯能力：不能糾正錯誤,水平垂直奇偶校驗(yàn)碼,水平和垂直兩個方向的奇偶校驗(yàn)碼，也稱縱橫奇偶校驗(yàn)碼 構(gòu)成如圖所示,具有較強(qiáng)的檢錯能力,校驗(yàn)和CS（Check Sum）,把m個長為l的信息組作為二進(jìn)制數(shù)相加，形成校驗(yàn)和，將校驗(yàn)和附在m個信息組之后一起傳送。 接收端將收到的前面m個信息組以同樣方式相加，得到的校驗(yàn)和，與收到的校驗(yàn)和相比，校驗(yàn)是否一致。,模2運(yùn)算,在由元素0和1組成的二元域上定義模2運(yùn)算： 模2加法運(yùn)算： 000 101 011 110 模2減法運(yùn)算規(guī)則與加法相同。 模2乘法運(yùn)算： 000 100 010 111,碼多項(xiàng)式及其運(yùn)算,定義二元域上的多項(xiàng)式： f(x) = an-1 xn-

5、1 + an-2 xn-2 + a1 x + a0 其中，ai = 0或1 信道編碼中，通常用多項(xiàng)式表示一個信息序列或碼字，稱為碼多項(xiàng)式或信息多項(xiàng)式 信息多項(xiàng)式： m(x) = mk-1 xk-1 + mk-2 xk-2 + m1 x + m0 碼多項(xiàng)式： c(x) = cn-1 xn-1 + cn-2 xn-2 + c1 x + c0,碼多項(xiàng)式及其運(yùn)算（二）,信息序列1001011可以用碼多項(xiàng)式表示為： x6+x3+x+1 對于f(x)=x4+x3+x2+1，g(x)=x+1 f(x) g(x) = f(x) g(x) = x4+x3+x2+x f(x) g(x) = x5+x2+x+1 f

6、(x) g(x) = x3+x+1,f(x)=x4+x3+x2+1，g(x)=x+1 f(x) g(x) = f(x) g(x) = x4+x3+x2+x f(x) g(x) = x5+x2+x+1 f(x) g(x) = x3+x+1,線性分組碼,當(dāng)分組碼滿足每個碼字中的每一位校驗(yàn)碼元，都是本碼字中信息碼元的線性模2和時，稱為線性分組碼。 例如，對于(6，3)分組碼，若每個碼字的校驗(yàn)碼與信息碼有下列關(guān)系： r2 = m2 + m0 r1 = m2 + m1 r0 = m1 + m0,（6，3）線性分組碼,線性分組碼的生成矩陣,循環(huán)碼,如果線性分組碼中的任一個碼字經(jīng)過循環(huán)移位之后，仍可以得到該

7、線性分組碼中的碼字，該線性分組碼稱為循環(huán)碼。 設(shè)（n，k）循環(huán)碼的碼字為：c=cn-1cn-2c1c0 循環(huán)1次后得到的碼字為：c(1)=cn-2cn-3c0cn-1 循環(huán)i次后得到的碼字為：c(i)=cn-i-1cn-i-2cn-i+1cn-i,循環(huán)碼的性質(zhì),1. (n,k)循環(huán)碼有且只有一個n-k次的碼多項(xiàng)式g(x)： g(x) = xn-k + gn-k-1 xn-k-1 + g1 x + 1 g(x)稱為循環(huán)碼的生成多項(xiàng)式。 2. (n,k)循環(huán)碼中的任一個碼多項(xiàng)式都是g(x)的倍式。 3. (n,k)循環(huán)碼的生成多項(xiàng)式是xn+1的一個因式。,循環(huán)碼的性質(zhì),性質(zhì)3提供了一種確定生成多項(xiàng)

8、式的方法： 若g(x)是一個n-k次多項(xiàng)式，且是xn+1的一個因式，則g(x)可以生成一個(n，k)循環(huán)碼。 例如： X7+1=(x+1)(x3+x2+1)(x3+x+1) 對于(7,4)循環(huán)碼，一個生成多項(xiàng)式為： g(x)x3+x+1,非系統(tǒng)循環(huán)碼的計(jì)算,若已知循環(huán)碼的生成多項(xiàng)式，根據(jù)性質(zhì)2，可以將生成多項(xiàng)式與指定信息碼相乘，計(jì)算出對應(yīng)的碼字。 非系統(tǒng)循環(huán)碼的計(jì)算： 根據(jù)循環(huán)碼的碼長n和信息位k選定生成多項(xiàng)式g(x)，完成m(x)g(x)的乘法運(yùn)算，得到信息多項(xiàng)式m(x)對應(yīng)的碼多項(xiàng)式c(x)。,由g(x) = x3+x+1生成的(7,4)非系統(tǒng)循環(huán)碼,系統(tǒng)循環(huán)碼的計(jì)算,(n，k)系統(tǒng)碼的編

9、碼過程： 信息多項(xiàng)式m(x)乘以xn-k，得到xn-k m(x) 以生成多項(xiàng)式除xn-k m(x)，若余式為r(x)， 即xn-k m(x)g(x)q(x)+r(x) 對應(yīng)的系統(tǒng)循環(huán)碼字為：c(x)= xn-k m(x) +r(x),由g(x) = x3+x+1生成的(7,4)系統(tǒng)循環(huán)碼,伴隨式,發(fā)送端發(fā)送的碼字為 C(x) = cn-1 xn-1 + cn-2 xn-2 + + c1 x + c0 接收端收到的碼字為： R(x) = rn-1 xn-1 + rn-2 xn-2 + + r1 x + r0 R(x)除以g(x)，可得余式s(x)，則 R(x)p(x)g(x)s(x) 多項(xiàng)式s(

10、x)稱為接收碼字R(x)的伴隨式。 若S(x)0，則認(rèn)為無錯碼； 若S(x)0，則認(rèn)為有錯碼,伴隨式與錯誤圖樣,接收端由于干擾而出現(xiàn)的錯誤圖樣為： E(x) = en-1 xn-1 + en-2 xn-2 + + e1 x + e0 則 R(x) = C(x) E(x) R(x)/g(x)C(x)/g(x)E(x)/g(x) 由于 C(x) = g(x)*p(x) 則 E(x) = g(x)*p(x)s(x) 結(jié)論：伴隨式中包含有E(x)的信息。,伴隨式與錯誤圖樣,接收碼字R(x)的錯誤碼元個數(shù)為t位， 當(dāng)t(dmin1)/2時， 任何一個重量為t的錯誤圖樣對應(yīng)一個伴隨式可以進(jìn)行糾錯(見下頁表

11、) 當(dāng)(dmin1)/2tdmin1時， 多個錯誤圖樣對應(yīng)一個伴隨式不能進(jìn)行糾錯，但可以檢出錯誤 當(dāng)tdmin時， 伴隨式等于零 不能檢出錯誤 伴隨式不等于零可以檢出錯誤,伴隨式與錯誤圖樣,循環(huán)碼的檢錯能力,錯誤圖樣多項(xiàng)式E(x)，有2n種排列，能夠被g(x)除盡的屬于不可檢出的錯誤。 干擾為單個錯位時，E(x)xi，能夠檢查出來。 當(dāng)g(x)滿足，g(x)=(x+1)g1(x)時，可以檢查出奇數(shù)個錯誤。,突發(fā)錯誤,突發(fā)錯誤：誤碼序列中的誤碼成串集中出現(xiàn) 突發(fā)長度：第一個錯誤碼元與最后一個錯誤碼元之間的長度 突發(fā)干擾的錯誤圖樣： E(x) = xiB(x) 其中，B(x) = xb-1+Bb-

12、2xb-2+B1x+1,循環(huán)碼的檢錯能力,由n-k次多項(xiàng)式g(x)生成的循環(huán)碼，具有以下特性： （1）可檢出突發(fā)長度b不大于n-k的突發(fā)錯誤 （2）當(dāng)突發(fā)長度b大于n-k時，不能檢錯出的錯誤占同樣長度的可能的突發(fā)錯誤總數(shù)的百分比為： 當(dāng)b-1n-k時，2-(n-k) 當(dāng)b-1=n-k 時，2-(n-k-1),系統(tǒng)循環(huán)碼的編譯碼電路,系統(tǒng)循環(huán)碼的編譯碼電路,串口接口電路：Z80-SIO、Intel8274、 Intel8253 生成多項(xiàng)式：g(x)x16+x12+x5+1,系統(tǒng)循環(huán)碼的編譯碼算法,m(x)=m39x39m38x38m1xm0 =m(x)x32+m(x)x24+m(x)x16+ m

13、(x)x8+ m(x) =(m(x)x8+m(x)x8+m(x)x8+m(x)x8+m(x) x8m(x)=(m(x)x8+m(x)x8+m(x)x8 +m(x)x8+m(x)x8,系統(tǒng)循環(huán)碼的編譯碼算法,設(shè)k位信息序列為：m=mk-1mk-2m1m0 (1) 把信息序列分成長度為n-k位的p個信息段，記為m=M1M2Mp (2) 第一個信息段M1后面添加n-k個零，并除以生成多項(xiàng)式g(x)得余式r1，與第二個信息段M2模2加得M2 (3) M2后面添加n-k個零，除以生成多項(xiàng)式g(x)得余式r2，與第三個信息段M3模2加得M3 (4) 對M2按上述步驟進(jìn)行得M4 ，直到對Mp ，計(jì)算得到rp，即為信息序列m編碼的余數(shù)。 信息序列對應(yīng)的碼字是c=M1M2Mprp,軟件表法,對于長度為n-k的二進(jìn)制序列，最多有2n-k種不同的取值，即被除數(shù)最多有2n-k種不同取值。 事先對2n-k個被除數(shù)進(jìn)行對生成多項(xiàng)式的除法運(yùn)算，將余數(shù)存放在內(nèi)存中，建立中間余數(shù)表。 進(jìn)行長度為n-k的進(jìn)行編碼除法運(yùn)算時，只需查表即可得到對應(yīng)的余式。,軟件表法,當(dāng)n-k較大時，軟件表占用內(nèi)存較多。 例如對于信息序列 m(x)=m15x15+