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

1、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ā)送端，將所要傳輸?shù)臄?shù)據(jù)碼元分組，在分組數(shù)據(jù)后面加一位監(jiān)督碼（校驗(yàn)位），使得該組碼連同監(jiān)督碼在內(nèi)的碼組中“1”的個(gè)數(shù)為

2、奇數(shù)（奇校驗(yàn)）或偶數(shù)（偶校驗(yàn)）。 接收端，按照編碼規(guī)則檢查如果發(fā)現(xiàn)不符，就說明產(chǎn)生差錯(cuò)，但不能明確差錯(cuò)的具體位置即不能糾錯(cuò),公式表示：設(shè)碼組長度為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)： 無論信息位為多少位，監(jiān)督位只有一位。 只能檢測信息碼組中奇數(shù)個(gè)錯(cuò)誤，對偶數(shù)個(gè)錯(cuò)誤無能為力,奇偶校驗(yàn)編碼,實(shí)例,寫出下列二進(jìn)制序列的偶校驗(yàn)碼： 1001110 0101111,寫出下列二進(jìn)制序列的奇校驗(yàn)碼：

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

4、誤及長度不大于方陣行數(shù)的突發(fā)錯(cuò)誤,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)督碼元；矩陣中的每一列是由不同碼組相同位置的碼元組成，在每列最后也加上一個(gè)監(jiān)督碼元，進(jìn)行奇偶校驗(yàn)；最后按行或列碼組的順序發(fā)送,XXXXXXXX X XXXXXXXXXXXX X X X XXXXXXXX X XXXXXXX,方陣校驗(yàn)碼結(jié)構(gòu),實(shí)

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

6、“3：2”或“5中取3”的恒比碼。 C52=10個(gè)許用碼組 英文電報(bào)采用“7中取3”或“4：3”恒比碼，共有C73=35個(gè)許用碼組,3.3.4 正反碼_能簡單糾錯(cuò)的編碼,多用于10單位電碼的前向自動(dòng)糾錯(cuò)設(shè)備中，能糾正一位差錯(cuò)，發(fā)現(xiàn)大部分兩位錯(cuò)，差錯(cuò)編碼和差錯(cuò)控制結(jié)合起來控制。以10單位電碼為例： n=k+r 且 k=r=5 1.編碼規(guī)則： (1)當(dāng)信息碼中“1”的個(gè)數(shù)為奇數(shù)時(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è)新

7、的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ò)控制方式，試問下列接收端收到的數(shù)據(jù)是否有錯(cuò)？能否糾正？ 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ù)個(gè)1，所以檢驗(yàn)碼取反，10111，信息碼中有一位出錯(cuò)，根據(jù)判決2，出錯(cuò)位置就是檢驗(yàn)碼組中0所對應(yīng)的位置，糾正后為11010,11010 + 01010 10000 由于接收信息碼中為奇數(shù)個(gè)1，所以檢驗(yàn)碼不變，根據(jù)判決3，監(jiān)督碼碼中有一位出錯(cuò)，出錯(cuò)位置就是檢驗(yàn)碼組中1所對應(yīng)的位置，糾正后為11010,10000 + 01010 01010 檢驗(yàn)碼中1的個(gè)數(shù)1，根據(jù)判決4，無法判斷和糾錯(cuò),3.3.5 循

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

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

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

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

13、（又叫信息多項(xiàng)式） 。 碼多項(xiàng)式與二進(jìn)制序列之間的一一對應(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ù) 對應(yīng)多項(xià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,碼多項(xiàng)式運(yùn)算法則: 二進(jìn)制碼多項(xiàng)式的加減運(yùn)算為模2加運(yùn)算，即兩個(gè)碼多項(xiàng)式相加時(shí)，對應(yīng)項(xiàng)系數(shù)進(jìn)行模2加減。 乘除運(yùn)算與普通多項(xiàng)式類似； 模2加減：即各位做不帶進(jìn)位、借

14、位的按位加減。這種加減運(yùn)算實(shí)際上就是邏輯上的異或運(yùn)算。即加法和減法等價(jià),碼多項(xiàng)式,生成多項(xiàng)式G(x): 求CRC碼時(shí)所用的“除數(shù)”所對應(yīng)的多項(xiàng)式叫生成多項(xiàng)式。 在串行通信中通常使用下列三種生成多項(xiàng)式G（X）來產(chǎn)生CRC碼。 CRC-16：G(x)=X16+X15+X2+1，美國二進(jìn)制同步系統(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,碼多項(xiàng)式,CRC碼性能,CRC碼是很有效的差錯(cuò)校驗(yàn)方法。除了正好數(shù)據(jù)塊的比特值是按除數(shù)值

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

16、息碼元。 如果每組的監(jiān)督碼元不但與本組碼的信息碼元有關(guān)，而且還與前面若干組信息碼元有關(guān)，即不是分組校驗(yàn)而是每個(gè)監(jiān)督碼元對它的前后碼元都實(shí)行監(jiān)督，前后相連，具有連環(huán)監(jiān)督的作用；因此我們稱為連環(huán)碼，即卷積碼。 卷積碼由 P.Elias于1955年最先提出，整個(gè)編解碼過程一環(huán)扣一環(huán)，連鎖地進(jì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è)信息碼與一個(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加法器

18、1構(gòu)成與發(fā)送端一樣的編碼器，用來計(jì)算監(jiān)督碼和解碼輸出。 用模2加法器2將計(jì)算出的監(jiān)督碼與接收到的監(jiān)督碼進(jìn)行比較，即先對ai編碼產(chǎn)生新的監(jiān)督碼bi，再與bi異或 if結(jié)果為0 then正確 else出錯(cuò)。 根據(jù)第2步的輸出進(jìn)行判決，由判決電路完成 由判決結(jié)果通過加法器3輸出結(jié)果,解碼器,設(shè)接收的碼序列b3a3b2a2b1a1b0a0其解碼過程為： （1） 第零拍， 前半拍電子開關(guān)倒向a, 移位寄存器R1移出a0,R2移出0，故加法器1結(jié)果生成一個(gè)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)在輸入端時(shí)，就可對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)在輸入端時(shí)，就可對a1做判斷。 （4）依次類推，當(dāng)b3出現(xiàn)在輸入端時(shí)，就可對a2做判斷規(guī)則如P69,解碼方程,模2加法器2的輸出對我們判決正確性至關(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中有一個(gè)出錯(cuò)，故判決ai無錯(cuò)