1、3.3 常用差錯(cuò)控制編碼方法,教學(xué)目的 熟悉和掌握各種差錯(cuò)控制編碼方法 掌握各種差錯(cuò)控制編碼的應(yīng)用,3.3 常用差錯(cuò)控制編碼方法,3.3.1 奇偶校驗(yàn)編碼 3.3.2 方陣校驗(yàn)碼 3.3.3 恒比碼 3.3.4 正反碼 3.3.5 循環(huán)冗余校驗(yàn)編碼（CRC） 3.3.6 卷積碼,差錯(cuò)控制的核心就是抗干擾編碼，為了提高通信系統(tǒng)的檢錯(cuò)和糾錯(cuò)能力，人們創(chuàng)造出許多差錯(cuò)控制編碼，比較常用的有奇偶校驗(yàn)編碼、循環(huán)冗余校驗(yàn)編碼、卷積碼等。,3.3.1 奇偶校驗(yàn)編碼,又稱奇偶監(jiān)督編碼，或垂直冗余校驗(yàn)（VRC，Vertical Redundancy Check），在計(jì)算機(jī)數(shù)據(jù)傳輸中應(yīng)用廣泛。 編碼規(guī)則： 發(fā)送端，

2、將所要傳輸?shù)臄?shù)據(jù)碼元分組，在分組數(shù)據(jù)后面加一位監(jiān)督碼（校驗(yàn)位），使得該組碼連同監(jiān)督碼在內(nèi)的碼組中“1”的個(gè)數(shù)為奇數(shù)（奇校驗(yàn)）或偶數(shù)（偶校驗(yàn)）。 接收端，按照編碼規(guī)則檢查如果發(fā)現(xiàn)不符，就說(shuō)明產(chǎn)生差錯(cuò)，但不能明確差錯(cuò)的具體位置即不能糾錯(cuò)。,公式表示：設(shè)碼組長(zhǎng)度為n，表示為（an-1,an-2,a1,c0）其中前n-1位為信息位，第n位c0為監(jiān)督位 奇校驗(yàn)：an-1an-2a1c0=1即 c0= an-1an-2a11 偶校驗(yàn)：an-1an-2a1c0=0 即c0= an-1an-2a1,奇偶校驗(yàn)編碼,特點(diǎn)： 無(wú)論信息位為多少位，監(jiān)督位只有一位。 只能檢測(cè)信息碼組中奇數(shù)個(gè)錯(cuò)誤，對(duì)偶數(shù)個(gè)錯(cuò)誤無(wú)能為力；

3、 信息位越長(zhǎng),效率越高.,奇偶校驗(yàn)編碼,實(shí)例,寫(xiě)出下列二進(jìn)制序列的偶校驗(yàn)碼： 1001110 0101111 ,寫(xiě)出下列二進(jìn)制序列的奇校驗(yàn)碼： 1100101 0110010 ,10011100,01011111,11001011,01100100,3.3.2 方陣校驗(yàn)碼,又稱行列監(jiān)督碼，矩陣碼，縱向冗余校驗(yàn)碼（LRC，Lognitudinal Redundancy Check），它的碼元受到行和列兩個(gè)方向奇偶監(jiān)督，又稱二維奇偶校驗(yàn)碼。 編碼規(guī)則：每個(gè)碼元受到縱向（列）和橫向兩次監(jiān)督； 將欲發(fā)送的信息碼按行排成一個(gè)矩陣，矩陣中每一行為一碼組，每行的最后加上一個(gè)奇偶監(jiān)督碼元； 矩陣中的每一列是由

4、不同碼組相同位置的碼元組成，在每列最后也加上一個(gè)監(jiān)督碼元，進(jìn)行奇偶校驗(yàn)； 最后按行或列碼組的順序發(fā)送。,XXXXXXXX X XXXXXXXXXXXX X X X XXXXXXXX X XXXXXXX,方陣校驗(yàn)碼結(jié)構(gòu),實(shí)例,發(fā)送端在發(fā)送時(shí)則按列(或行）的順序傳輸：111010 110011 100001 010100 001111 接收端仍將碼元排成發(fā)送時(shí)方陣形式，然后按行、列進(jìn)行奇偶校驗(yàn),特點(diǎn)： 可以檢測(cè)出某行某列上的奇數(shù)個(gè)錯(cuò)誤和長(zhǎng)度不大于行（列）數(shù)的突發(fā)錯(cuò)誤。 可以檢測(cè)出某行或某列上偶數(shù)個(gè)錯(cuò)誤 不能糾正差錯(cuò)數(shù)正好是4的倍數(shù)且位置在行列矩陣/子矩陣的4個(gè)頂點(diǎn)上的差錯(cuò),方陣校驗(yàn)碼,失效！,3.

5、3.3 恒比碼(定比碼),編碼規(guī)則 ：恒比碼中每碼組中“1”和“0”個(gè)數(shù)保持恒定比例，接收端在檢測(cè)接收到的碼組中“1”的數(shù)目是否對(duì)就知道是否出錯(cuò)。 實(shí)例： 我國(guó)電傳機(jī)傳輸漢字時(shí)使用數(shù)字代表漢字，采用的所謂“保護(hù)電碼”就是一種“3：2”或“5中取3”的恒比碼。 C52=10個(gè)許用碼組 英文電報(bào)采用“7中取3”或“4：3”恒比碼，共有C73=35個(gè)許用碼組,3.3.4 正反碼_能簡(jiǎn)單糾錯(cuò)的編碼,多用于10單位電碼的前向自動(dòng)糾錯(cuò)設(shè)備中，能糾正一位差錯(cuò)，發(fā)現(xiàn)大部分兩位錯(cuò)，差錯(cuò)編碼和差錯(cuò)控制結(jié)合起來(lái)控制。以10單位電碼為例： n=k+r 且 k=r=5 1.編碼規(guī)則： (1)當(dāng)信息碼中“1”的個(gè)數(shù)為奇數(shù)

6、時(shí)，監(jiān)督碼與信息碼相同（正碼）10101 10101 (2)當(dāng)信息碼中“1”的個(gè)數(shù)為偶數(shù)時(shí)，監(jiān)督碼與信息碼相反（反碼）10100 01011,2.解碼方法： (1)將接收到信息碼與監(jiān)督碼按相應(yīng)的碼位模2加（異或），得到一個(gè)新的5位碼組。 (2)根據(jù)接收到的信息碼中“1”的個(gè)數(shù)： if“1”的個(gè)數(shù)為奇數(shù)，則取新5位碼組為校驗(yàn)碼組 if“1”的個(gè)數(shù)為偶數(shù)，則取新5位碼組的反碼為校驗(yàn)碼組,正反碼,正反碼判決表,（3），最后可按下表，根據(jù)檢驗(yàn)碼組中“1”的個(gè)數(shù)進(jìn)行判斷及糾正可能發(fā)現(xiàn)的錯(cuò)碼,實(shí)例：,已知信息碼11010使用正反碼差錯(cuò)控制方式，試問(wèn)下列接收端收到的數(shù)據(jù)是否有錯(cuò)？能否糾正？ 11010 11

7、010 10010 11010 11010 01010 10000 11010,（1） 編碼：11010（信息碼）11010（監(jiān)督碼）11010 11010（正反碼） （2） 解碼： 接收端11010 11010 接收端10010 11010 接收端11010 01010 接收端10000 11010 判斷：,11010 + 11010 00000 結(jié)果為0，正確。,10010 + 11010 01000 由于接收信息碼中為偶數(shù)個(gè)1，所以檢驗(yàn)碼取反，10111，信息碼中有一位出錯(cuò)，根據(jù)判決2，出錯(cuò)位置就是檢驗(yàn)碼組中0所對(duì)應(yīng)的位置，糾正后為11010,11010 + 01010 10000 由于

8、接收信息碼中為奇數(shù)個(gè)1，所以檢驗(yàn)碼不變，根據(jù)判決3，監(jiān)督碼碼中有一位出錯(cuò)，出錯(cuò)位置就是檢驗(yàn)碼組中1所對(duì)應(yīng)的位置，糾正后為11010,10000 + 01010 01010 檢驗(yàn)碼中1的個(gè)數(shù)1，根據(jù)判決4，無(wú)法判斷和糾錯(cuò),作業(yè),已知信息碼10010使用正反碼差錯(cuò)控制方式，試問(wèn)下列接收端收到的數(shù)據(jù)是否有錯(cuò)？能否糾正？ 11010 01101 10010 10010 10010 01101 10000 01001,11010 + 01101 10111 由于接收信息碼中為奇數(shù)個(gè)1，所以檢驗(yàn)碼不變，根據(jù)判決2，信息碼中有一位出錯(cuò)，出錯(cuò)位置就是檢驗(yàn)碼組中0所對(duì)應(yīng)的位置，糾正后為10010。,10010

9、+ 10010 00000 由于接收信息碼中為偶數(shù)個(gè)1，所以檢驗(yàn)碼取反，11111，信息碼中無(wú)錯(cuò)，,10010 + 01101 11111 由于接收信息碼中為偶數(shù)個(gè)1，所以檢驗(yàn)碼取反，00000,信息碼中無(wú)錯(cuò),10000 + 01010 01010 檢驗(yàn)碼中1的個(gè)數(shù)1，根據(jù)判決4，無(wú)法判斷和糾錯(cuò),3.3.5 循環(huán)冗余校驗(yàn)編碼（CRC）,Cyclic Redundancy checking (CRC)循環(huán)冗余校驗(yàn)，又稱多項(xiàng)式碼。 在循環(huán)冗余校驗(yàn)中，不是通過(guò)將各比特位相加來(lái)得到期望的校驗(yàn)，而是通過(guò)在數(shù)據(jù)單元末尾加一串冗余比特，稱作循環(huán)冗余校驗(yàn)碼或循環(huán)冗余校驗(yàn)余數(shù)，使得整個(gè)數(shù)據(jù)單元可以被另一個(gè)預(yù)定的

10、二進(jìn)制數(shù)所整除。,1.CRC校驗(yàn)基本思想,CRC校驗(yàn)的基本思想是： (1)根據(jù)欲發(fā)的k位信息生成一個(gè)r比特的序列，稱為幀校驗(yàn)序列FCS（Frame checking Series）。 （2）求出實(shí)際發(fā)送的數(shù)據(jù)幀（k+r位），這個(gè)幀所對(duì)應(yīng)二進(jìn)制序列恰好能夠被某個(gè)預(yù)先確定的數(shù)（生成多項(xiàng)式）整除。 （3）接收器用相同的數(shù)（生成多項(xiàng)式）去除傳來(lái)的幀。如果無(wú)余數(shù)，則認(rèn)為無(wú)差錯(cuò)；如果余數(shù)不為0，剛認(rèn)為傳輸出錯(cuò)。,奇偶校驗(yàn)對(duì)一個(gè)字符校驗(yàn)一次，適合異步通訊；而CRC對(duì)一個(gè)數(shù)據(jù)塊（frame）校驗(yàn)一次，適合同步通訊。在串行同步通信中，幾乎都使用這種校驗(yàn)方法。如磁盤(pán)信息的讀/寫(xiě)等。,2.CRC校驗(yàn)常用場(chǎng)合,CRC

11、碼生成和校驗(yàn)基本分為三步： 第一步：在數(shù)據(jù)單元(k位）的末尾加上r個(gè)0。r是一個(gè)比預(yù)定除數(shù)的比特位數(shù)(r十1)少1的數(shù)。 第二步：采用二進(jìn)制除法將新的加長(zhǎng)的數(shù)據(jù)單元（k+r位)除以除數(shù)。由此除法產(chǎn)生的余數(shù)就是CRC校驗(yàn)碼。,3.CRC碼的生成,第三步：求CRC循環(huán)冗余校驗(yàn)碼 (K+r)被除數(shù)+r(余數(shù)) 如果余數(shù)位數(shù)小于r，左邊的缺省位數(shù)補(bǔ)0。 如果余數(shù)為0,則r=0。,CRC碼的生成,CRC碼校驗(yàn)： 到達(dá)接收方的數(shù)據(jù)單去除以用來(lái)產(chǎn)生循環(huán)冗余校驗(yàn)余數(shù)的G（X）。 如果余數(shù)0，將通過(guò)檢驗(yàn)。如果余數(shù)非零，將通不過(guò)檢驗(yàn)。,4.CRC碼的校驗(yàn),任何一個(gè)二進(jìn)制數(shù)序列可以和一個(gè)只含有0和1兩個(gè)系數(shù)的代數(shù)多

12、項(xiàng)式建立起一一對(duì)應(yīng)的關(guān)系。因此，用來(lái)求CRC碼的那個(gè)除數(shù)通常用多項(xiàng)式來(lái)表示。原因如下： 代數(shù)多項(xiàng)式很短 可以通過(guò)多項(xiàng)式來(lái)進(jìn)行概念的數(shù)學(xué)證明。,5.多項(xiàng)式,多項(xiàng)式,任何一個(gè)n位的二進(jìn)制數(shù)都可以用一個(gè)n-1 次的多項(xiàng)式來(lái)表示,這種多項(xiàng)式叫碼多項(xiàng)式（又叫信息多項(xiàng)式） 。 碼多項(xiàng)式與二進(jìn)制序列之間的一一對(duì)應(yīng)關(guān)系： （an-1 an-2a1a0）N A (x)= an-1Xn-1+an-2Xn-2 +a1X+a0X0,碼多項(xiàng)式,多項(xiàng)式 二進(jìn)制序列實(shí)例,以n=3位二進(jìn)制數(shù)為例 二進(jìn)制數(shù) 對(duì)應(yīng)多項(xiàng)式 000 001 010 011 100 101 111,0,1,x,x+1,x2,x2+1,x2+ x+1,

13、1011011 x6+x4+x3+x+1 x5+x4+x2+x 110110,碼多項(xiàng)式運(yùn)算法則: 二進(jìn)制碼多項(xiàng)式的加減運(yùn)算為模2加運(yùn)算，即兩個(gè)碼多項(xiàng)式相加時(shí)，對(duì)應(yīng)項(xiàng)系數(shù)進(jìn)行模2加減。 乘除運(yùn)算與普通多項(xiàng)式類(lèi)似； 模2加減：即各位做不帶進(jìn)位、借位的按位加減。這種加減運(yùn)算實(shí)際上就是邏輯上的異或運(yùn)算。即加法和減法等價(jià)。,碼多項(xiàng)式,生成多項(xiàng)式G(x): 求CRC碼時(shí)所用的“除數(shù)”所對(duì)應(yīng)的多項(xiàng)式叫生成多項(xiàng)式。 在串行通信中通常使用下列三種生成多項(xiàng)式G（X）來(lái)產(chǎn)生CRC碼。 CRC-16：G(x)=X16+X15+X2+1，美國(guó)二進(jìn)制同步系統(tǒng)中采用。 CRC-CCITT：G(x)=X16+X12+X5+1

14、，CCITT推薦。 CRC-32：G(x)=X32+X26+X23+X22+ X16+X12+ X11+X10+X8+1X7+ X5+X4+X2+X+ 1,碼多項(xiàng)式,循環(huán)冗余碼生成器采用模2除法。下圖顯示了這一過(guò)程。 CRC校驗(yàn)器的功能完全像發(fā)生器一樣，當(dāng)收到附加了CRC碼的數(shù)據(jù)后，做同樣的模2 除法。如果余數(shù)是全0，則將CRC碼丟棄，接受數(shù)據(jù)。否則，丟棄收到的數(shù)據(jù)。,6.CRC碼生成器和校驗(yàn)器,CRC校驗(yàn)碼的生成器和校驗(yàn)器,發(fā)送方,接收方,0,G(X),111010100011010 CRC校驗(yàn)碼 信息碼 CRC冗余校驗(yàn)碼,7.CRC碼性能,CRC碼是很有效的差錯(cuò)校驗(yàn)方法。除了正好數(shù)據(jù)塊的比

15、特值是按除數(shù)值變化的錯(cuò)誤外，循環(huán)冗余校驗(yàn)(CRC)將檢測(cè)出其他所有錯(cuò)誤。而且，常用的CRC除數(shù)通常有16，或是32個(gè)比特，使得不可檢測(cè)的錯(cuò)誤可能降低到幾乎近于零。 CRC接收電路再配上適當(dāng)?shù)挠布娐凡粌H可以檢錯(cuò)，而且可以糾錯(cuò)，糾錯(cuò)能力很強(qiáng)特別適合檢測(cè)突發(fā)性錯(cuò)誤，在數(shù)據(jù)通信中得到較廣泛的應(yīng)用。,檢錯(cuò)性能,能檢測(cè)出全部單個(gè)錯(cuò)誤 能檢測(cè)出全部隨機(jī)二位錯(cuò)誤 能檢測(cè)出全部奇數(shù)個(gè)錯(cuò)誤 能檢測(cè)出全部長(zhǎng)度小于k位的突發(fā)錯(cuò)誤 能以1-（1/2）k-1概率檢測(cè)出長(zhǎng)度為（k+1）位的突發(fā)性錯(cuò)誤,課堂練習(xí)題,設(shè)某一循環(huán)碼，其生成多項(xiàng)式為G（X）=X5 + X2+1，試求出信息序列1101010101011的循環(huán)校驗(yàn)碼

16、CRC（要求寫(xiě)出計(jì)算步驟）。,設(shè)某一循環(huán)碼，其生成多項(xiàng)式為G（X）= X5+X4+ X2+1，試求出信息序列1010001100的CRC循環(huán)校驗(yàn)碼（要求寫(xiě)出計(jì)算步驟）。,3.3.6 卷積碼,1.概述 2.編碼器 3.解碼器,1.概述,前面介紹的編碼方法都是線性分組碼，即監(jiān)督碼只負(fù)責(zé)監(jiān)督檢驗(yàn)本碼組中的信息碼元。 如果每組的監(jiān)督碼元不但與本組碼的信息碼元有關(guān)，而且還與前面若干組信息碼元有關(guān)，即不是分組校驗(yàn)而是每個(gè)監(jiān)督碼元對(duì)它的前后碼元都實(shí)行監(jiān)督，前后相連，具有連環(huán)監(jiān)督的作用；因此我們稱為連環(huán)碼，即卷積碼。 卷積碼由 P.Elias于1955年最先提出，整個(gè)編解碼過(guò)程一環(huán)扣一環(huán)，連鎖地進(jìn)行下去。,2

17、.編碼器,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ò)程 第一次， 前半拍開(kāi)關(guān)接到a輸出a0 ，后半拍開(kāi)關(guān)倒向b輸出b0=a00=a0 第二次， 前半拍開(kāi)關(guān)接到a輸出a1，后半拍開(kāi)關(guān)倒向b輸出 b1=a1a0 第i次，前半拍開(kāi)關(guān)接到a輸出ai，后半拍開(kāi)關(guān)倒向b輸出bi=aiai-1,2.編碼器,（2） 連環(huán)碼結(jié)構(gòu)： 信息碼: an-1an-2aia1a0 監(jiān)督碼 bn-1bn-2bib1b0 連環(huán)碼輸出序列 bn-1an-1biaib2a2b1a1b0a0 即“信

18、息碼 監(jiān)督碼 信息碼”，一個(gè)信息碼與一個(gè)校驗(yàn)碼構(gòu)成一組但每個(gè)校驗(yàn)碼bi=aiai-1除了與本組碼有關(guān)還與前一組信息碼有關(guān)，故稱為卷積碼。,3.解碼器,a b,接收到的監(jiān)督碼,計(jì)算出的監(jiān)督碼,判決電路,1,2,3,解碼輸出,解碼輸入,Si,Si-1,連環(huán)碼入口,解碼器,解碼思路： 移位寄存器R1、R2及模2加法器1構(gòu)成與發(fā)送端一樣的編碼器，用來(lái)計(jì)算監(jiān)督碼和解碼輸出。 用模2加法器2將計(jì)算出的監(jiān)督碼與接收到的監(jiān)督碼進(jìn)行比較，即先對(duì)ai編碼產(chǎn)生新的監(jiān)督碼bi，再與bi異或, if結(jié)果為0 then正確 else出錯(cuò)。 根據(jù)第2步的輸出進(jìn)行判決，由判決電路完成 由判決結(jié)果通過(guò)加法器3輸出結(jié)果,解碼器,

19、設(shè)接收的碼序列b3a3b2a2b1a1b0a0其解碼過(guò)程為： （1） 第零拍， 前半拍電子開(kāi)關(guān)倒向a, 移位寄存器R1移出a0,R2移出0，故加法器1結(jié)果生成一個(gè)a00= a0。 后半拍電子開(kāi)關(guān)倒向b結(jié)果,接收到b0，生成S0 =b0（= a0）a0 ，R3為0故與門(mén)輸出0 又R2輸出為0，所以加法器3輸出為0,解碼器,（2）第一拍 前半拍電子開(kāi)關(guān)倒向a ，R1移出工a1,R2移出a0加法器1輸出a1 a0 后半拍電子開(kāi)關(guān)倒向b，加法器2輸入b1 ,加法器2輸出 S1 = b1 （ a1 a0） 在第一拍后半期當(dāng)b1 出現(xiàn)在輸入端時(shí)，就可對(duì)a0做判斷。,解碼器,（3）第二拍 前半拍電子開(kāi)關(guān)倒向a ，R1移出工a2,R2移出a1，加法器1輸出a2 a1 后半拍電子開(kāi)關(guān)倒向b，加法器2輸入b2加法器2輸出 S2 = b2 （ a2 a1） 在第二拍后半期當(dāng)b2 出現(xiàn)在輸入端時(shí)，就可對(duì)a1做判斷。 （4）依次類(lèi)推，當(dāng)b3出現(xiàn)在輸入端時(shí)，就可對(duì)a2做判斷規(guī)則如P69。,解碼方程,模2加法器2的輸出對(duì)我們判決正確性至關(guān)重要。,解碼器,判決規(guī)則： 當(dāng)Si及Si+1都為“0”時(shí)， ai正確 當(dāng)Si及Si+1都為“1”時(shí)，必定是ai出錯(cuò) 當(dāng)Si為“1”而 Si1為“0”時(shí)，必定是ai-1 、bi中