數(shù)字通信基礎(chǔ) ch3(2)

1、3.3 常用差錯控制編碼方法,3.3.1 奇偶校驗編碼 3.3.2 方陣校驗碼 3.3.3 恒比碼 3.3.4 3.3.5 循環(huán)冗余校驗編碼（CRC） 3.3.6 卷積碼,差錯控制的核心就是抗干擾編碼，為了提高通信系統(tǒng)的檢錯和糾錯能力，人們創(chuàng)造出許多差錯控制編碼，比較常用的有奇偶校驗編碼、循環(huán)冗余校驗編碼、卷積碼等,3.3.1 奇偶校驗編碼,又稱奇偶監(jiān)督編碼，或垂直冗余校驗（VRC，Vertical Redundancy Check），在計算機數(shù)據(jù)傳輸中應(yīng)用廣泛。 編碼規(guī)則： 發(fā)送端，將所要傳輸?shù)臄?shù)據(jù)碼元分組，在分組數(shù)據(jù)后面加一位監(jiān)督碼（校驗位），使得該組碼連同監(jiān)督碼在內(nèi)的碼組中“1”的個數(shù)為

2、奇數(shù)（奇校驗）或偶數(shù)（偶校驗）。 接收端，按照編碼規(guī)則檢查如果發(fā)現(xiàn)不符，就說明產(chǎn)生差錯，但不能明確差錯的具體位置即不能糾錯,公式表示：設(shè)碼組長度為n，表示為（an-1,an-2,a1,c0）其中前n-1位為信息位，第n位c0為監(jiān)督位 奇校驗：an-1an-2a1c0=1即c0= an-1an-2a11 偶校驗：an-1an-2a1c0=0 即c0= an-1an-2a1,奇偶校驗編碼,特點： 無論信息位為多少位，監(jiān)督位只有一位。 只能檢測信息碼組中奇數(shù)個錯誤，對偶數(shù)個錯誤無能為力,奇偶校驗編碼,實例,寫出下列二進制序列的偶校驗碼： 1001110 0101111,寫出下列二進制序列的奇校驗碼：

3、 1100101 0110010,10011100,01011111,11001011,01100100,水平奇偶校驗,避免簡單奇偶校驗不能檢測突發(fā)錯誤的缺點。 編碼規(guī)則：經(jīng)過奇偶監(jiān)督編碼的碼元序列按行排成方陣，每一行為一組奇偶監(jiān)督碼(見實例)。發(fā)送端在發(fā)送時則按列的順序傳輸：11101 11001 10000 01010 00111 而接受端仍將碼元排成發(fā)送時方陣形式，然后按行進行奇偶校驗水平奇偶監(jiān)督碼,實例,特點 ：發(fā)送端是按列發(fā)送碼元，而不是按碼組（行）發(fā)送碼元，因此可把本來可能集中發(fā)生在一碼組中的突發(fā)錯誤分散到方陣中的各個碼組，同時又作為整個方陣的行監(jiān)督； 可以發(fā)現(xiàn)某一行上所有奇數(shù)個錯

4、誤及長度不大于方陣行數(shù)的突發(fā)錯誤,3.3.2 方陣校驗碼,又稱行列監(jiān)督碼，矩陣碼，縱向冗余校驗碼（LRC，Lognitudinal Redundancy Check），它的碼元受到行和列兩個方向奇偶監(jiān)督，又稱二維奇偶校驗碼。 編碼規(guī)則：使的每個碼元受到縱向（列）和橫向兩次監(jiān)督；將欲發(fā)送的信息碼按行排成一個矩陣，矩陣中每一行為一碼組，每行的最后加上一個奇偶監(jiān)督碼元；矩陣中的每一列是由不同碼組相同位置的碼元組成，在每列最后也加上一個監(jiān)督碼元，進行奇偶校驗；最后按行或列碼組的順序發(fā)送,XXXXXXXX X XXXXXXXXXXXX X X X XXXXXXXX X XXXXXXX,方陣校驗碼結(jié)構(gòu),實

5、例,發(fā)送端在發(fā)送時則按列(或行）的順序傳輸：111010 110011 100001 010100 001111 接收端仍將碼元排成發(fā)送時方陣形式，然后按行、列進行奇偶校驗,特點： 可以檢測出某行某列上的奇數(shù)個錯誤和長度不大于行（列）數(shù)的突發(fā)錯誤。 可以檢測出某行或某列上偶數(shù)個錯誤 不能糾正差錯數(shù)正好是4的倍數(shù)且位置在行列矩陣/子矩陣的4個頂點上的差錯,方陣校驗碼,失效,3.3.3 恒比碼(定比碼,編碼規(guī)則 ：恒比碼中每碼組中“1”和“0”個數(shù)保持恒定比例，接收端在檢測接收到的碼組中“1”的數(shù)目是否對就知道是否出錯。 實例： 我國電傳機傳輸漢字時使用數(shù)字代表漢字，采用的所謂“保護電碼”就是一種

6、“3：2”或“5中取3”的恒比碼。 C52=10個許用碼組 英文電報采用“7中取3”或“4：3”恒比碼，共有C73=35個許用碼組,3.3.4 正反碼_能簡單糾錯的編碼,多用于10單位電碼的前向自動糾錯設(shè)備中，能糾正一位差錯，發(fā)現(xiàn)大部分兩位錯，差錯編碼和差錯控制結(jié)合起來控制。以10單位電碼為例： n=k+r 且 k=r=5 1.編碼規(guī)則： (1)當(dāng)信息碼中“1”的個數(shù)為奇數(shù)時，監(jiān)督碼與信息碼相同（正碼）10101 10101 (2)當(dāng)信息碼中“1”的個數(shù)為偶數(shù)時，監(jiān)督碼與信息碼相反（反碼）10100 01011,2.解碼方法： (1)將接收到信息碼與監(jiān)督碼按相應(yīng)的碼位模2加（異或），得到一個新

7、的5位碼組。 (2)根據(jù)接收到的信息碼中“1”的個數(shù)： if“1”的個數(shù)為奇數(shù)，則取新5位碼組為校驗碼組 if“1”的個數(shù)為偶數(shù)，則取新5位碼組的反碼為校驗碼組,正反碼,正反碼判決表,3），最后可按下表，根據(jù)檢驗碼組中“1”的個數(shù)進行判斷及糾正可能發(fā)現(xiàn)的錯碼,實例,已知信息碼11010使用正反碼差錯控制方式，試問下列接收端收到的數(shù)據(jù)是否有錯？能否糾正？ 11010 11010 10010 11010 11010 01010 10000 11010,1） 編碼：11010（信息碼）11010（監(jiān)督碼）11010 11010（正反碼） （2） 解碼： 接收端11010 11010 接收端10010

8、 11010 接收端11010 01010 接收端10000 11010 判斷,11010 + 11010 00000 結(jié)果為0，正確,10010 + 11010 01000 由于接收信息碼中為偶數(shù)個1，所以檢驗碼取反，10111，信息碼中有一位出錯，根據(jù)判決2，出錯位置就是檢驗碼組中0所對應(yīng)的位置，糾正后為11010,11010 + 01010 10000 由于接收信息碼中為奇數(shù)個1，所以檢驗碼不變，根據(jù)判決3，監(jiān)督碼碼中有一位出錯，出錯位置就是檢驗碼組中1所對應(yīng)的位置，糾正后為11010,10000 + 01010 01010 檢驗碼中1的個數(shù)1，根據(jù)判決4，無法判斷和糾錯,3.3.5 循

9、環(huán)冗余校驗編碼（CRC,Cyclic Redundancy checking (CRC)循環(huán)冗余校驗，又稱多項式碼。 在循環(huán)冗余校驗中，不是通過將各比特位相加來得到期望的校驗，而是通過在數(shù)據(jù)單元末尾加一串冗余比特，稱作循環(huán)冗余校驗碼或循環(huán)冗余校驗余數(shù)，使得整個數(shù)據(jù)單元可以被另一個預(yù)定的二進制數(shù)所整除,CRC校驗基本思想,CRC校驗的基本思想是： 根據(jù)欲發(fā)送的k位信息位構(gòu)成的報文，發(fā)送器生成一個r比特的序列，稱為幀校驗序列FCS（Frame checking Series），將r位FCS（即CRC碼）附加到k位信息序列之后作為實際發(fā)送的數(shù)據(jù)幀（k+r位），這個幀所對應(yīng)二進制序列恰好能夠被某個預(yù)先

10、確定的數(shù)（生成多項式）整除。接收器用相同的數(shù)去除傳來的幀。如果無余數(shù)，則認為無差錯；如果余數(shù)不為0，剛認為傳輸出錯,奇偶校驗對一個字符校驗一次，適合異步通訊；而CRC對一個數(shù)據(jù)塊（frame）校驗一次，適合同步通訊。在串行同步通信中，幾乎都使用這種校驗方法。如磁盤信息的讀/寫等,CRC校驗常用場合,CRC碼生成和校驗基本分為三步： 第一步：在數(shù)據(jù)單元(k位）的末尾加上r個0。r是一個比預(yù)定除數(shù)的比特位數(shù)(r十1)少1的數(shù)。 第二步：采用二進制除法將新的加長的數(shù)據(jù)單元（k+r位)除以除數(shù)。由此除法產(chǎn)生的余數(shù)就是循環(huán)冗余碼校驗碼,CRC碼的生成,第三步：用從第二步得到的r個比特的CRC碼替換數(shù)據(jù)單

11、元末尾附加的r個0。如果余數(shù)位數(shù)小于r，最左的缺省位數(shù)為0。如果除法過程根本未產(chǎn)生余數(shù)（也就是說，原始的數(shù)據(jù)單元本身就可以被除數(shù)整除）那么以r個0作為CRC碼替換余數(shù)所在的位置。產(chǎn)生的比特模式正好能被除數(shù)整除,CRC碼的生成,CRC碼校驗： 到達接收方的數(shù)據(jù)單元首先到達的是數(shù)據(jù)，然后是CRC校驗碼。接收方將整個數(shù)據(jù)串當(dāng)作一個整體去除以用來產(chǎn)生循環(huán)冗余校驗余數(shù)的同一個除數(shù)。 如果數(shù)據(jù)串無差錯地到達接收方，循環(huán)冗余校驗器將產(chǎn)生余數(shù)0。因此數(shù)據(jù)單元將通過檢驗。如果在傳輸中數(shù)據(jù)單元被改變，除法將產(chǎn)生非零余數(shù)，因此數(shù)據(jù)單元將通不過檢驗,CRC碼的校驗,循環(huán)冗余碼生成器采用模2除法。下圖顯示了這一過程。

12、CRC校驗器的功能完全像發(fā)生器一樣，當(dāng)收到附加了CRC碼的數(shù)據(jù)后，做同樣的模2 除法。如果余數(shù)是全0，則將CRC碼丟棄，接受數(shù)據(jù)。否則，丟棄收到的數(shù)據(jù),CRC碼生成器和校驗器,0,G(X,111010100011010 CRC校驗碼 信息碼 CRC冗余校驗碼,CRC校驗碼的生成器和校驗器,發(fā)送方,接收方,任何一個二進制數(shù)序列可以和一個只含有0和1兩個系數(shù)的代數(shù)多項式建立起一一對應(yīng)的關(guān)系。因此，用來求CRC碼的那個除數(shù)通常用多項式來表示。原因如下： 代數(shù)多項式很短 可以通過多項式來進行概念的數(shù)學(xué)證明,多項式,多項式,任何一個n位的二進制數(shù)都可以用一個n-1 次的多項式來表示,這種多項式叫碼多項式

13、（又叫信息多項式） 。 碼多項式與二進制序列之間的一一對應(yīng)關(guān)系： （an-1 an-2a1a0）N A (x)= an-1Xn-1+an-2Xn-2 +a1X+a0X0,碼多項式,多項式 二進制序列實例,以n=3位二進制數(shù)為例 二進制數(shù) 對應(yīng)多項式 000 001 010 011 100 101 111,0,1,x,x+1,x2,x2+1,x2+ x+1,1011011 x6+x4+x3+x+1 x5+x4+x2+x 110110,碼多項式運算法則: 二進制碼多項式的加減運算為模2加運算，即兩個碼多項式相加時，對應(yīng)項系數(shù)進行模2加減。 乘除運算與普通多項式類似； 模2加減：即各位做不帶進位、借

14、位的按位加減。這種加減運算實際上就是邏輯上的異或運算。即加法和減法等價,碼多項式,生成多項式G(x): 求CRC碼時所用的“除數(shù)”所對應(yīng)的多項式叫生成多項式。 在串行通信中通常使用下列三種生成多項式G（X）來產(chǎn)生CRC碼。 CRC-16：G(x)=X16+X15+X2+1，美國二進制同步系統(tǒng)中采用。 CRC-CCITT：G(x)=X16+X12+X5+1，CCITT推薦。 CRC-32：G(x)=X32+X26+X23+X22+ X16+X12+ X11+X10+X8+1X7+ X5+X4+X2+X+ 1,碼多項式,CRC碼性能,CRC碼是很有效的差錯校驗方法。除了正好數(shù)據(jù)塊的比特值是按除數(shù)值

15、變化的錯誤外，循環(huán)冗余校驗(CRC)將檢測出其他所有錯誤。而且，常用的CRC除數(shù)通常有13、17，或是33個比特，使得不可檢測的錯誤可能降低到幾乎近于零。 CRC接收電路再配上適當(dāng)?shù)挠布娐凡粌H可以檢錯，而且可以糾錯，糾錯能力很強特別適合檢測突發(fā)性錯誤，在數(shù)據(jù)通信中得到較廣泛的應(yīng)用,檢錯性能,能檢測出全部單個錯誤 能檢測出全部隨機二位錯誤 能檢測出全部奇數(shù)個錯誤 能檢測出全部長度小于k位的突發(fā)錯誤 能以1-（1/2）k-1概率檢測出長度為（k+1）位的突發(fā)性錯誤,3.3.6 卷積碼,1.概述 2.編碼器 3.解碼器,1.概述,前面介紹的編碼方法都是線性分組碼，即監(jiān)督碼只負責(zé)監(jiān)督檢驗本碼組中的信

16、息碼元。 如果每組的監(jiān)督碼元不但與本組碼的信息碼元有關(guān)，而且還與前面若干組信息碼元有關(guān)，即不是分組校驗而是每個監(jiān)督碼元對它的前后碼元都實行監(jiān)督，前后相連，具有連環(huán)監(jiān)督的作用；因此我們稱為連環(huán)碼，即卷積碼。 卷積碼由 P.Elias于1955年最先提出，整個編解碼過程一環(huán)扣一環(huán)，連鎖地進行下去,2.編碼器,aiai-1a2a1a0,b 0= a 0 b 1= a 0a 1 b 2= a 1a 2 b 3= a 2a 3 b i= a i-1a i,2.編碼器,1） 編碼器輸出過程 第一次， 前半拍開關(guān)接到a輸出a0 ，后半拍開關(guān)倒向b輸出b0=a00=a0 第二次， 前半拍開關(guān)接到a輸出a1，后

17、半拍開關(guān)倒向b輸出 b1=a1a0 第i次，前半拍開關(guān)接到a輸出ai，后半拍開關(guān)倒向b輸出bi=aiai-1,2.編碼器,2） 連環(huán)碼結(jié)構(gòu)： 信息碼: an-1an-2aia1a0 連環(huán)碼輸出序列 bn-1an-1biaib2a2b1a1b0a0 監(jiān)督碼bn-1bn-2bib1b0 即“信息碼 監(jiān)督碼 信息碼”，一個信息碼與一個校驗碼構(gòu)成一組但每個校驗碼bi=aiai-1除了與本組碼有關(guān)還與前一組信息碼有關(guān)，故稱為卷積碼,3.解碼器,a b,接收到的監(jiān)督碼,計算出的監(jiān)督碼,判決電路,1,2,3,解碼輸出,解碼輸入,Si,Si-1,連環(huán)碼入口,解碼器,解碼思路： 移位寄存器R1、R2及模2加法器

18、1構(gòu)成與發(fā)送端一樣的編碼器，用來計算監(jiān)督碼和解碼輸出。 用模2加法器2將計算出的監(jiān)督碼與接收到的監(jiān)督碼進行比較，即先對ai編碼產(chǎn)生新的監(jiān)督碼bi，再與bi異或 if結(jié)果為0 then正確 else出錯。 根據(jù)第2步的輸出進行判決，由判決電路完成 由判決結(jié)果通過加法器3輸出結(jié)果,解碼器,設(shè)接收的碼序列b3a3b2a2b1a1b0a0其解碼過程為： （1） 第零拍， 前半拍電子開關(guān)倒向a, 移位寄存器R1移出a0,R2移出0，故加法器1結(jié)果生成一個a00= a0。 后半拍電子開關(guān)倒向b結(jié)果,接收到b0，生成S0 =b0（= a0）a0 ，R3為0故與門輸出0 又R2輸出為0，所以加法器3輸出為0,

19、解碼器,2）第一拍 前半拍電子開關(guān)倒向a ，R1移出工a1,R2移出a0加法器1輸出a1 a0 后半拍電子開關(guān)倒向b，加法器2輸入b1 ,加法器2輸出 S1 = b1 （ a1 a0） 在第一拍后半期當(dāng)b1 出現(xiàn)在輸入端時，就可對a0做判斷,解碼器,3）第二拍 前半拍電子開關(guān)倒向a ，R1移出工a2,R2移出a1，加法器1輸出a2 a1 后半拍電子開關(guān)倒向b，加法器2輸入b2加法器2輸出 S2 = b2 （ a2 a1） 在第二拍后半期當(dāng)b2 出現(xiàn)在輸入端時，就可對a1做判斷。 （4）依次類推，當(dāng)b3出現(xiàn)在輸入端時，就可對a2做判斷規(guī)則如P69,解碼方程,模2加法器2的輸出對我們判決正確性至關(guān)重要,解碼器,判決規(guī)則： 當(dāng)Si及Si+1都為“0”時， ai正確 當(dāng)Si及Si+1都為“1”時，必定是ai出錯 當(dāng)Si為“1”而 Si1為“0”時，必定是ai-1 、bi中有一個出錯，故判決ai無錯