差錯控制編碼糾錯碼

1、第八章 差錯控制編碼1 主要內(nèi)容8.1 引言8.2 糾錯編碼的基本原理8.3 線性分組碼8.4 循環(huán)碼8.5 小結(jié)28.1 引言 在數(shù)字信號傳輸中，由于噪聲的存在及信道特性不理想，都可使信號波形失真，從而在接收端就不可避免的產(chǎn)生錯誤判決。引起誤碼原因:(1)信道特性不理想(乘性干擾): 引起碼間串?dāng)_，通?？刹捎镁獾霓k法糾正。(2) 噪聲影響(加性干擾) : 需借助各種差錯控制編碼技術(shù)來克服。一、基本概念3差錯控制編碼又稱為信道編碼(糾錯編碼)，要求在滿足有效性前提下，盡可能提高數(shù)字通信的可靠性糾錯編碼：在要傳送的數(shù)字信息序列中按一定規(guī)則加上一些冗余碼元（監(jiān)督位),使序列按滿足一定數(shù)學(xué)規(guī)律的碼

2、字傳輸(編碼過程);譯碼:在接收端,利用這種規(guī)律性來鑒別傳輸過程是否發(fā)生錯誤或糾正錯誤，恢復(fù)原始信息序列。4二、糾錯編碼的分類 按功能分：檢錯碼和糾錯碼 按監(jiān)督碼元與信息碼元之間是否存在線性關(guān)系分：線性碼與非線性碼 按信息碼元與監(jiān)督碼元之間的約束關(guān)系不同分：分組碼與非分組碼如卷積碼按信息碼元在編碼后是否保持原來的信號形式分：系統(tǒng)碼與非系統(tǒng)碼按糾正差錯的類型分：糾正隨機(jī)錯誤的碼與糾正突發(fā)錯誤的碼 按碼元的取值分：二進(jìn)制碼與多進(jìn)制碼5三、誤碼的類型 隨機(jī)誤碼錯碼出現(xiàn)是隨機(jī)的、錯碼之間統(tǒng)計獨(dú)立。由隨機(jī)噪聲引起存在隨機(jī)誤碼的信道稱為隨機(jī)信道 突發(fā)誤碼錯碼成串集中出現(xiàn)，在很短的時間出現(xiàn)大量錯碼，而過后又

3、存在較大的無錯碼位，且差錯之間是相關(guān)的例如：脈沖噪聲，信道中衰落存在這種差錯的信道稱為突發(fā)信道6四、差錯控制方法（1）前向糾錯（FEC）7優(yōu)點(diǎn)：無需反向信道、譯碼總延遲恒定，具有恒定的信息 傳輸速率缺點(diǎn)：當(dāng)糾錯能力強(qiáng)時，要增加冗余位；接收可靠性對信道傳輸條件的惡化很敏感（2）自動要求重發(fā)（ARQ）8優(yōu)點(diǎn)：極低的不可檢測概率；編譯碼簡單；對任何信道都有效缺點(diǎn)：需要反向信道；譯碼延遲不固定；需要緩沖器（3）FEC/ARQ混合系統(tǒng)分為三類：停止等待ARQ、連續(xù)ARQ和選擇重發(fā)ARQ綜合利用FEC延遲小，糾錯能力強(qiáng)和ARQ傳輸可靠性高9發(fā)端發(fā)出同時具有檢錯和糾錯能力的碼，收端收到后，檢查錯誤情況：如果

4、錯誤在糾錯能力之內(nèi)，則自動糾正；若超出糾錯能力，但在檢錯能力之內(nèi)，則經(jīng)反向信道要求重發(fā)。注意：不同的糾錯編碼方法，有不同的檢錯或糾錯能力，一般說來，增加監(jiān)督碼元越多，檢錯或糾錯的能力就越強(qiáng)，提高傳輸可靠性是以降低傳輸有效性為代價的。108.2糾錯編碼的基本原理簡單例子：3位二進(jìn)制碼組（c1 c2 c3）,其中ci=0或1。此碼組有8種不同的組合：000 001 010 011 100 101 110 111可分別代表不同的信息含義。若將8種碼組都作為有用碼組來使用，比如代表8種天氣情況：000（晴），001（雷），010（雹），011（陰），100（風(fēng)），101（云），110（雨），111（雪

5、）11任一碼組在傳輸中若發(fā)生一個或多個錯碼，則將變成另一信息碼組這種編碼方法就不具有任何抗干擾能力：但如果在8種碼組中，規(guī)定只準(zhǔn)使用其中4種來傳輸信息，比如，許用碼組為：000（晴）， 011（陰）， 101（云）， 110（雨）這種編碼接收端有可能檢測碼組中出現(xiàn)的一位或三位錯誤，但不能發(fā)現(xiàn)兩位錯碼的情況接收端收到禁用碼組時，就認(rèn)為發(fā)現(xiàn)了錯誤12這種方法只能檢測錯誤，但不能糾正錯誤比如：當(dāng)接收端收到禁用碼組100時，無法判決哪一位碼發(fā)生了錯誤000（晴）101（云）110（雨）錯一位100要想糾正錯誤，需要增加多余度，比如，只準(zhǔn)使用兩個碼組13000（晴） 111（陰）其他均為禁用碼組，則它可

6、檢測兩個錯碼或能糾正一個錯碼。如：接收端接收到禁用碼組100，若認(rèn)為只有一個錯碼，可糾正，若錯碼數(shù)不超過2個，只能檢測錯誤4種信息完全可以由2位二進(jìn)制數(shù)字來表示，即前兩位。可見，第三位完全是多余的，這第三位就作為附加的監(jiān)督碼14一、糾錯編碼的基本思想 發(fā)送端按照某種規(guī)則在信息序列上附加監(jiān)督碼元，接收端則按照同一規(guī)則檢查兩者間關(guān)系 碼的檢錯和糾錯能力是用信息量的冗余來換取的。添加的冗余越多，碼的檢錯、糾錯能力越強(qiáng)，但信道的傳輸效率下降也越多。以犧牲通信的有效性（信息傳輸速率）來提高可靠性15二、糾錯編碼的理論基礎(chǔ)理論依據(jù)：Shannon信道編碼定理定理指出： 對于一給定的有干擾信道，若其信道容量

7、為C，只要發(fā)送端以低于C的速率R發(fā)送信息，則一定存在一種編碼方法，使編碼錯誤概率P隨著碼長n的增加，按指數(shù)下降到任意小的值。E（R）稱為誤差指數(shù)，n編碼長度，R信息發(fā)送速率16三、編碼距離與糾錯檢測的關(guān)系碼重：二進(jìn)編碼序列V中，包含1的個數(shù)為該碼組的重量（權(quán)），W(v)碼距：兩個等長碼組V1,V2中對應(yīng)碼位上不同二進(jìn)制碼元的個數(shù)，也叫漢明距離，d(V1,V2)例：V111001100和V2=10010111 重量分別為W14，W25；它們的距離為d(V1,V2)=5。兩碼組間的漢明距離也等于兩碼組對應(yīng)位模二加后所得碼組的重量幾個基本概念17最小碼距：對于某種編碼，所含的全部碼組之間的最小距離，

8、成為該碼的最小碼距，用dmin表示最小碼距的大小直接關(guān)系著這種編碼的檢錯和糾錯能力，它是衡量各種碼抗干擾能力大小的標(biāo)準(zhǔn)。碼組的最小距離越大，說明碼字間的最小差別越大，抗干擾能力越強(qiáng)。 最小碼距與檢錯和糾錯能力的關(guān)系1) 如果 一個碼能檢錯不多于e個錯，則要求2) 如果 一個碼能糾正不多于t個錯，則要求18如果 一個碼能糾正不多于t個錯，同時可以檢e個錯誤 則要求四、編碼效率設(shè)編碼序列長度與所包含的信息位數(shù)分別為n,k，則編碼效率指一個碼組中信息位所占比重：19編碼效率是衡量碼性能的一個重要參量，編碼效率與抗干擾能力這兩個參數(shù)是相互矛盾的編碼的主要任務(wù)就是如何找到一種編碼，在滿足一定誤碼率要求的

9、前提下，盡量提高編碼效率。五、編碼增益描述編碼系統(tǒng)對非編碼系統(tǒng)性能的改善程度，定義為在給定誤碼率要求下，非編碼系統(tǒng)與編碼系統(tǒng)之間所需信噪比的差。編碼增益越大越好208.3線性分組碼一、基本概念分組碼將信息碼首先分成若干組，然后為每組信碼附加若干位監(jiān)督碼元，這種編碼稱之為“分組碼”分組碼一般用（n,k）表示， k是信息碼的位數(shù)，n是碼組長度，監(jiān)督碼元位數(shù)r=n-k ，分組碼結(jié)構(gòu)碼長n=k+rk個信息位r個監(jiān)督位21注意：在分組碼中，監(jiān)督碼僅監(jiān)督本碼組中的信息碼元。在非分組碼中如卷積碼，監(jiān)督碼元除了與本組信息碼元有關(guān)，還與其它組的信息碼元有關(guān)線性碼碼組中監(jiān)督碼元和信息碼元之間滿足線性變換關(guān)系，由一

10、組線性方程（監(jiān)督方程）構(gòu)成。線性碼是一種代數(shù)碼。奇偶監(jiān)督碼是最簡單的線性碼。22二、幾種簡單的線性分組碼1、重復(fù)碼(n,1)的線性分組碼，最小碼距為n，當(dāng)n很大時，編碼效率低，糾錯能力強(qiáng)，2、奇偶校驗碼只有一個監(jiān)督碼（校驗位）的（n,n-1）的分組碼。分為兩種：奇數(shù)校驗碼和偶數(shù)校驗碼23奇數(shù)校驗碼：附加一位監(jiān)督碼，使碼組中“1”的個數(shù)為奇數(shù)設(shè)碼字（vn-1, vn-2, , v1, v0），v0為監(jiān)督元，則有： vn-1 vn-2 v1 v01 （8-1）在接收端，按上式計算各碼元，若結(jié)果為0認(rèn)為有錯；否則，無錯。如：11010 0模2加偶數(shù)校驗碼：附加一位監(jiān)督碼，使碼組中“1”的個數(shù)為偶數(shù)，

11、 vn-1 vn-2 v1 v00即滿足：（8-2）（8-1）與(8-2)叫做監(jiān)督方程或監(jiān)督關(guān)系式24在接收端，按上式計算各碼元，若結(jié)果為1認(rèn)為有錯；否則，無錯。如： 11010 1注意：只能檢測奇數(shù)個錯誤，當(dāng)錯碼為奇數(shù)個時，由于打亂了碼字中”1”個數(shù)的奇偶性，故能發(fā)現(xiàn)差錯。但當(dāng)錯碼為偶數(shù)個時，因碼字中1個數(shù)奇偶性保持不變，則無法發(fā)現(xiàn)錯碼。特點(diǎn)：結(jié)構(gòu)簡單，易于實現(xiàn)，編碼效率高，雖然不理想，但干擾不嚴(yán)重時，且碼長不長的情況下仍很有用。253、方陣碼也叫二維奇偶校驗碼（矩陣碼、行列監(jiān)督碼），其基本原理與簡單的奇偶校驗碼相似。不同的是每個碼元都要受到行和列的兩項監(jiān)督編碼方法：將所要傳送的碼序列編成一

12、個方陣，方陣中每一行為一個碼組。每行的最后加上一個監(jiān)督碼元，進(jìn)行奇偶監(jiān)督。在每列的最后也加上一個監(jiān)督碼，進(jìn)行奇偶監(jiān)督26例：若發(fā)送碼序列為（1100100111 0100011100 0010011110 010101101 11）,求其奇偶監(jiān)督方陣 1 1 0 0 1 0 0 1 1 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0 經(jīng)編碼后的校驗位和信息位一起傳輸:（ 1100100111001000111000001

13、0011110101010110000011000000111001111100 ）27特點(diǎn)：（1）有可能檢測偶數(shù)個錯誤，但是不能檢測在方陣中構(gòu)成 矩形四個角的錯誤，因為在行列兩個方向均有偶數(shù)個錯誤。（2）適于檢測突發(fā)錯碼，能糾正突發(fā)錯誤，如當(dāng)碼組中僅在一行有奇數(shù)個錯誤時，能夠確定錯誤位置，并糾正它。（3）284、恒比碼（等比碼或等重碼）每個碼組中含“1”和“0”的個數(shù)的比例恒定在檢測時，計算接收碼組中“1”的數(shù)目是否正確，能檢測 出所有奇數(shù)個錯誤，并能部分檢測出偶數(shù)個錯誤（成對交 換錯誤檢測不出） 簡單，適用于電傳機(jī)或其它鍵盤設(shè)備產(chǎn)生的字母和符號例：我國電傳機(jī)用“5中取3”恒比碼表示10個數(shù)

14、字29表 我國五單位保護(hù)電碼表在國際無線電報通信中，廣泛采用“7中取3”恒比碼。（是一種五中取三碼）30四、線性分組碼編碼原理1、漢明碼：能糾正單個隨機(jī)錯誤且編碼效率較高的線性分組碼，其參數(shù)：監(jiān)督位：碼長：信息位：最小距離：編碼效率：當(dāng)m很大時，312、以（7，4）漢明碼為例來說明編碼原理設(shè)碼字為a6 a5 a4a3 a2 a1 a0，信息碼元a6 、a5 、a4、a3來源于待編碼的信息序列；監(jiān)督碼元 a2 、a1、 a0的取值應(yīng)根據(jù)信息碼元按監(jiān)督 關(guān)系式來決定a6+a5+a4+a2=0a6+a5+a3+a1=0a6+a4+a3+a0=0a2 = a4+a5+a6a1 = a3+a5+a6a0

15、 = a3+a4+a6（8-3）每個方程分別為某一個監(jiān)督碼元的奇偶校驗方程。通常稱這幾個線性方程為對應(yīng)碼的一致監(jiān)督關(guān)系式或一致校驗方程32給定信息位后，根據(jù)上式算出各監(jiān)督位，該編碼的所有碼組如下表33（1）監(jiān)督矩陣（奇偶校驗矩陣）1 a6+ 1 a5+ 1 a4 +0 a3+ 1 a2 + 0 a1+ 0 a0=01 a6+ 1 a5+ 0 a4 +1 a3+ 0 a2 + 1 a1+ 0 a0=01 a6+ 0 a5+ 1 a4 +1 a3+ 0 a2 + 0 a1+ 1 a0=0a6+a5+a4+a2=0a6+a5+a3+a1=0a6+a4+a3+a0=0上式監(jiān)督關(guān)系式(8-3)可寫成34

16、寫成矩陣形式可記為： HVT=0T 或VHT=035H稱為線性碼監(jiān)督矩陣 rn階矩陣 監(jiān)督矩陣H確定了編碼時監(jiān)督碼元與信息碼元的關(guān)系， 可由H和信息碼元求出全部碼組 把具有PIr形式的H矩陣稱為典型形式的監(jiān)督矩陣，其中P為r k階矩陣, Ir為r r階單位方陣 H矩陣的各行應(yīng)線性無關(guān)。矩陣若能寫成典型形式，則其各行一定線性無關(guān)監(jiān)督矩陣特點(diǎn):36(2)生成矩陣對（7,4）線性碼，由其一致監(jiān)督方程式，再附加4個等式a6 = a6a5 = a5a4 = a4a3= a3a2 = a4+a5+a6a1 = a3+a5+a6a0 = a3+a4+a63738k n階矩陣，編碼方法完全由生成矩陣G確定把具

17、有IkQ形式的G矩陣稱為典型形式的生成矩陣，其中，Ik為kk階單位方陣，Q為k r階矩陣V可看成是G矩陣的各行的線性組合，為保證不同的信息分組對應(yīng)不同的碼字，G矩陣各行應(yīng)線性無關(guān)生成矩陣特點(diǎn)：393、線性分組碼伴隨式（或校驗子）監(jiān)督關(guān)系式 HVT=0T 或VHT=0碼字是由H矩陣所確定的線性方程組的解，所以可以由H矩陣來檢驗接收的序列是否為碼字若接收到碼字R=V+E，E為錯誤矢量（或錯誤圖樣）計算SRHT=(V+E)HT =VHT+EHT=EHT當(dāng)S0表明沒錯，此時E0；否則，S不為0，表明有錯，E也不為0。S稱為校驗子（伴隨式）40任意兩個許用碼組模2和仍為一許用碼組，即具有封閉性。兩碼組之

18、間的距離是另一碼組的重量，最小碼距=非零碼的最小碼重(1的個數(shù)）4、線性分組碼最小碼距及性質(zhì)許用碼字41設(shè)（7,4）線性碼的生成矩陣G為：當(dāng)信息位為0001時，（1）試求其后的監(jiān)督位。（2）監(jiān)督矩陣H42解：（1）43（2）監(jiān)督矩陣H根據(jù)生成矩陣和監(jiān)督矩陣的關(guān)系：G= IkQ，H=PIr其中P=QT，可得監(jiān)督矩陣H為：448.4循環(huán)碼一、循環(huán)碼的編碼原理循環(huán)碼是一種重要的線性分組碼，是在代數(shù)學(xué)基礎(chǔ)上建立起來的，編碼和解碼設(shè)備都不太復(fù)雜，且有較強(qiáng)的檢（糾）錯能力。特點(diǎn)： 封閉性 循環(huán)性：即碼中任一碼組循環(huán)一位(將最右端的碼元移 到左端或反之）以后，仍為該碼中的一個碼組。4546若(vn-1,vn

19、-2,v1,v0)是一(n,k)循環(huán)碼的碼組，則(vn-2 ,vn-3 ,v1,v0 ,vn-1)(vn-3 ,vn-4 , , v0 , vn-1 ,vn-2) ( v0 ,vn-1 , vn-2 ,vn-3 ,v2 ,v1) 也都是該循環(huán)碼的碼組。1、碼多項式設(shè)一個(n,k) 線性分組碼，其中的每個碼字V= (vn-1,vn-2,v1,v0)可用一個n-1 次多項式表示，即V(x)= vn-1xn-1+ vn-2xn-2+ + v1x+ v04647如：對于（7，3）循環(huán)碼的任意碼組可表示為： V(x)= a6x6+ a5x5+ a4x4 + a3x3 + a2x2 + a1x+ a0如碼

20、組（）對應(yīng)的碼多項式可表示為 V(x)=1*x6+1*x5+ 0*x4 + 0*x3 + 1*x2 + 0*x+1 = x6 + x5 + x2 +1碼多項式與碼字的關(guān)系：本質(zhì)上是一回事，僅是表示方法的不同而已。x僅是碼元位置的標(biāo)志。并不關(guān)心x的取值。4748序號碼字序號碼字信息位a6 a5 a4監(jiān)督位a3 a2 a1 a0信息位a6 a5 a4監(jiān)督位a3 a2 a1 a01000000051001011200101116101110030101110711001014011100181110010一種（7，3）循環(huán)碼的全部碼字4849若一個整數(shù)m可以表示為:則有mp（模n），同樣對于多項式而

21、言：則可以寫為：F(x)R(x) （模N(x)）。即一任意多項式F(x)被一個n次多項式N(x)除，得到商式Q(x)和一個次數(shù)小于n的余式R(x)4950例如碼組（）對應(yīng)的碼多項式可為：V7(x)= x6 + x5 + x2 +1其被x2+1除得x6 + x5 + x2 +1 x+1 （模x2+1）重要結(jié)論在循環(huán)碼中，若V(x)是一個長為n的許用碼組，Vi(x)為V(x)碼組向左循環(huán)移位i次的結(jié)果，也是一許用碼組，則xi V(x)在按模xn+1運(yùn)算下，也是一許用碼組。即 xi V(x)Vi(x) （模xn+1）5051例如：其對應(yīng)的碼組為，它正是表5-10中第3碼字。結(jié)論：一個碼長為n的(n，

22、k)循環(huán)碼，它必為按模xn+1運(yùn)算的一個余式。51522、循環(huán)碼的生成多項式與生成矩陣 循環(huán)碼完全由其碼組長度n和生成多項式g(x)所決定 問題：尋找構(gòu)成生成矩陣的k個線性無關(guān)的許用碼組（n，k)循環(huán)碼中一定能找到這樣一個碼組：前面的k-1位都是0，而第k位及第n位為1，其它各位gi為0或1：（00001gn-k-1gn-k-2 g2 g11) 5253其對應(yīng)的碼多項式為g(x)，且 g(x)一定是碼中唯一的一個n-k次多項式，這唯一的n-k次多項式g(x)稱為碼的生成多項式可以證明生成多項式g(x)具有以下特性： （1） g(x)是一個常數(shù)項為1的 次多項式； （2） g(x)是 的一個因式

23、； （3）該循環(huán)碼中其它碼多項式都是g(x)的倍式。 g(x)， xg(x) ， xk-1g(x)5354g(x)， ， xk-1g(x)都是許用碼組，連同g(x)共k個許用碼組，構(gòu)成碼的生成矩陣G(x)注：該生成矩陣并不是典型形式的，但可通過線性變換變換成典型的生成矩陣。5455一旦生成多項式g(x)確定以后，該循環(huán)碼的生成矩陣G(x)就可以確定，進(jìn)而該循環(huán)碼的所有碼字就可以確定。生成矩陣G(x)的每一行都是一個碼組。例試求（7，3）循環(huán)碼的生成多項式和生成矩陣。生成多項式g(x)是xn+1的一個因式，且g(x)是一個n-k次因式。因此，就可以先對xn+1進(jìn)行因式分解，找到它的n-k次因式。

24、5556解2：對（7,3）循環(huán)碼，n=7，k=3, r=4第一步：對x7+1進(jìn)行因式分解得： x7+1=(x+1)(x3+x2+1)(x3+x+1) .(1)第二步：構(gòu)造r=n-k次生成多項式g(x)。要從式（1）中找到r=n-k=4次的因子,這樣的因子有兩個 ： (x+1)(x3+x2+1)=x4+x2+x+1(a) (x+1)(x3+x+1)=x4+x3+x2+1(b)第三步：若按(a)構(gòu)成生成多項式:生成多項式為：g(x)= x4+x2+x+15657生成矩陣為：將第1行與第3行模2加作為第1行，則有 為典型生成矩陣5758若按(b)構(gòu)成生成多項式:生成多項式為：g(x)= x4+x3+x2+1生成矩陣為：進(jìn)行線性變換，得典型生成矩陣為：58593、循環(huán)碼的監(jiān)督多項式與監(jiān)督矩陣其中 是 逆多項式1、方法1：5960方法2：根據(jù)生成矩陣