第6章差錯控制

6.1產(chǎn)生差錯的原因6.2差錯控制方法6.3常用的檢錯與糾錯碼

6.4ARQ原理習(xí)題6.1產(chǎn)生差錯的原因

數(shù)字信號在傳輸過程中通常會受到干擾的影響，使得在接收端可能發(fā)生錯誤判決。 噪聲干擾造成的差錯有兩種，一種是在傳輸過程中每隔一段時間會出現(xiàn)一到兩個誤碼，我們稱之為隨機誤碼；另一種是在傳輸過程中一小段時間內(nèi)會出現(xiàn)大量錯碼，我們稱之為突發(fā)誤碼。6.2差錯控制方法

差錯控制方法，常用的有四種：

1)檢錯重發(fā)法(ARQ) 2)前向糾錯法(FEC) 3)混合糾錯法(HEC) 4)反饋檢驗法(IRQ)6.3常用的檢錯與糾錯碼

差錯控制能夠?qū)崿F(xiàn)的核心是采用了差錯控制編碼，在發(fā)送端對要傳輸?shù)臄?shù)據(jù)信號按照一定的規(guī)則加上一些監(jiān)督碼元，監(jiān)督碼元與信息碼元之間按一定規(guī)則結(jié)合在一起形成信道編碼，在接收端若發(fā)現(xiàn)監(jiān)督碼元與信息碼元之間的關(guān)系與規(guī)定的規(guī)則不符，就可以檢出錯誤和糾正錯誤。所謂信息碼元是指原始的信息數(shù)據(jù)；所謂監(jiān)督碼元是指為了檢錯和糾錯而在信息碼元后增加的“冗余”碼元。

差錯控制編碼是信息論中的一個重要的研究內(nèi)容，差錯控制編碼有很多種，常見的有以下幾種：

(1)根據(jù)信息碼元和監(jiān)督碼元之間的檢驗關(guān)系可分為線性碼和非線性碼。若信息碼元和監(jiān)督碼元之間的關(guān)系滿足二進制加法運算法則，則為線性，稱為線性碼；若信息碼元和監(jiān)督碼元之間的關(guān)系不滿足二進制加法運算法則，則為非線性，稱為非線性碼。

(2)根據(jù)信息碼元和監(jiān)督碼元之間的關(guān)系是否只局限在由當(dāng)前信息碼元和監(jiān)督碼元組成的一個碼字內(nèi)，可分為分組碼和卷積碼。

(3)根據(jù)接收端是只能檢測出錯誤還是既可以檢測出錯誤又可以糾正錯誤，可分為檢錯碼和糾錯碼。

(4)根據(jù)碼字中的信息碼元是否與原始數(shù)據(jù)信息位一致可分為系統(tǒng)碼和非系統(tǒng)碼。 6.3.1奇偶校驗碼 奇偶校驗碼是一種最簡單的檢錯碼，在計算機的數(shù)據(jù)傳輸中得到了廣泛的應(yīng)用。奇偶校驗碼分為兩種：奇校驗與偶校驗。其原理很簡單，在信息碼元后面加上一位監(jiān)督碼元，若信息碼元與監(jiān)督碼元的關(guān)系是使信息碼元與監(jiān)督碼元組成的碼字中“1”的個數(shù)為偶數(shù)個，則為偶校驗；若信息碼元與監(jiān)督碼元的關(guān)系是使信息碼元與監(jiān)督碼元組成的碼字中“1”的個數(shù)為奇數(shù)個，則為奇校驗。若數(shù)據(jù)傳輸過程中碼字中的任一位發(fā)生錯誤，勢必破壞這種奇偶監(jiān)督關(guān)系，從而可以發(fā)現(xiàn)錯誤。

設(shè)信息碼元為，若為偶校驗，則監(jiān)督碼元c為 若為奇校驗，則監(jiān)督碼元c為 6.3.2水平垂直校驗碼 水平垂直校驗碼又稱二維奇偶校驗碼。 發(fā)送時可以逐行傳輸，也可以逐列傳輸，接收端將接收到的數(shù)據(jù)仍排成發(fā)送時的矩陣形式，然后按照與發(fā)送端統(tǒng)一的校驗關(guān)系檢測是否有錯。例如，設(shè)有7個7位信息碼元組成的矩陣，其奇偶監(jiān)督碼元(以奇校驗為例)如下：

信1001110101001001

息0011001010011110

碼1110010101011000

元1101001100101111

11000111監(jiān)督碼元 6.3.3海明碼 差錯控制編碼中用得較多的有一種線性分組碼。所謂線性分組碼，它的信道編碼方式是在k位信息碼元后加上r位監(jiān)督碼元，監(jiān)督碼元與信息碼元之間構(gòu)成線性關(guān)系。信息碼元確定后，監(jiān)督碼元可以根據(jù)編碼規(guī)則，通過線性運算得到。線性分組碼構(gòu)成如圖6-1所示。圖6-1線性分組碼的構(gòu)成

前面討論奇偶校驗碼時，若為偶校驗，則監(jiān)督碼元c為 若為奇校驗，則監(jiān)督碼元c為 那么，在接收端譯碼時，只要計算

若為偶校驗，S=0，就認(rèn)為無錯；若S=1，就認(rèn)為有錯。若為奇校驗，S=1，就認(rèn)為無錯；若S=0，就認(rèn)為有錯。我們把S的計算式稱為監(jiān)督關(guān)系式，S稱為校正子。 在海明碼中，我們將監(jiān)督碼元增加一位，相應(yīng)地設(shè)計出兩個監(jiān)督關(guān)系式，得到兩個校正子的值，兩個校正子就有四種可能的取值組合：00、01、10、11，表示了四種不同的情況。其中一種表示無錯，另外三種則可能表示出現(xiàn)一個誤碼情況下的三個出錯位置。依此類推，若有r位監(jiān)督碼元，就能指出一個誤碼情況下的(2r

–1)個出錯位置，這就是海明碼的工作機理。

一般來講，若碼長為n，信息碼元的位數(shù)為k，則監(jiān)督碼元的位數(shù)為r=n–k，如果要求r個監(jiān)督碼元構(gòu)造出來的監(jiān)督關(guān)系式能夠指出一位誤碼的n種可能位置，則必須滿足關(guān)系式

2r

-1≥n

即

2r≥r+k+1

面以(7，4)碼為例來說明海明碼如何構(gòu)造以及如何實現(xiàn)。所謂(7，4)碼，是指碼長n=7，信息碼元的位數(shù)k=4的碼型，為了能糾正一位誤碼，根據(jù)2r–?1≥n的計算式，則要求監(jiān)督碼元的位數(shù)r

≥3。現(xiàn)取r=3，n=k+r=7。a6a5a4a3a2a1a0表示這7個碼元，S1、S2、S3為三個監(jiān)督關(guān)系式中的校正子，S1、S2、S3的值與誤碼位置的對應(yīng)關(guān)系可根據(jù)簡單、有規(guī)律、易識別原則進行設(shè)定，設(shè)S1、S2、S3的值與誤碼位置的對應(yīng)關(guān)系如表6-1所示(偶校驗)。表6-1校正子與誤碼位置設(shè)定真值表

由表可知，a6、a5、a4、a3、a2、a1、a0與S1、S2、S3之間的函數(shù)關(guān)系式為發(fā)送端編碼時，信息位a6、a5、a4、a3的值是隨機的輸入信息，監(jiān)督位a2、a1、a0則與信息位的取值和監(jiān)督關(guān)系有關(guān)，即監(jiān)督位應(yīng)使S1、S2、S3的值為0，表示無錯，即

已知信息位后，可直接根據(jù)上式計算出監(jiān)督位，計算結(jié)果如表6-2所示。表6-2發(fā)送碼元真值表

接收端收到一個碼組后，先根據(jù)S1、S2、S3的計算式得到S1、S2、S3的值，然后根據(jù)表6-1判斷誤碼情況。 例如，若接收碼組為1100100，則可知S1=1，S2=0，S3=1

由表6-1可知，a4出錯，正確碼組應(yīng)為1110100。 海明碼的編碼電路也很簡單，如圖6-2所示。圖6-2海明碼編碼電路 6.3.4循環(huán)冗余校驗碼 循環(huán)碼中所謂的循環(huán)，是指若C=(Cn?1

Cn?2…C0?)是編碼中的一個碼字，則C循環(huán)移位(左移或右移)后所形成的碼字都是該編碼中的碼字，即其所有碼字為

我們以一種(7，3)循環(huán)碼為例，可得到其所有碼字列表，如表6-3所示。對于表中的碼字，我們通常用碼多項式T(x)來表示。把碼字中的碼元當(dāng)作多項式的系數(shù)(取0或1)，則n長的碼字可表示為表6-3(7,3)循環(huán)碼字

例如(7,3)循環(huán)碼，設(shè)其信息位為111，生成多項式g(x)=x4+x3+x2+x1，則其編碼過程如下：

(1)將信息位左移n?k=4位，得xn?k

m(x)：1110000。

(2)求余數(shù)。 即1110000/11101=100+0100/11101。 故余數(shù)為：0100 (3)合并，T(x)=xn?km(x)+r(x)，即1110000+0100=1110100。 循環(huán)冗余校驗碼的硬件實現(xiàn)可由移位寄存器和除法電路實現(xiàn)，隨著微處理器和數(shù)字信號處理器的應(yīng)用日益廣泛，其編解碼的實現(xiàn)已變得較為容易。6.4ARQ原理

自動請求重發(fā)系統(tǒng)通常簡稱為ARQ系統(tǒng)，其基本組成方框圖如圖6-3所示。圖6-3ARQ系統(tǒng)組成方框圖 ARQ的具體實現(xiàn)可分為多種方式： 6.4.1等待式ARQ

等待式ARQ是指發(fā)送端發(fā)出一幀數(shù)據(jù)后，就等待接收端的確認(rèn)。如果接收端確認(rèn)收到的是正確的數(shù)據(jù)幀，則向發(fā)送端發(fā)回一個確認(rèn)幀ACK，發(fā)送端收到ACK后，繼續(xù)發(fā)送下一個數(shù)據(jù)幀；如果接收端經(jīng)差錯檢測確認(rèn)收到的是錯誤的數(shù)據(jù)幀，則向發(fā)送端發(fā)回一個否認(rèn)幀NCK，發(fā)送端在收到NCK后，重發(fā)這個在傳送過程中出現(xiàn)差錯的數(shù)據(jù)幀。數(shù)據(jù)幀在鏈路上傳輸有以下幾種情況：正常情況、數(shù)據(jù)幀出錯、數(shù)據(jù)幀丟失、應(yīng)答幀丟失。如圖6-4所示。

圖6-4數(shù)據(jù)幀在鏈路上傳輸?shù)膸追N情況(a)正常情況；(b)數(shù)據(jù)幀出錯；(c)數(shù)據(jù)幀丟失；(d)應(yīng)答幀丟失 6.4.2回退N步ARQ

等待式ARQ，由于每發(fā)一次數(shù)據(jù)幀后都要等待應(yīng)答，信道的利用率很低?；赝薔步ARQ則是在發(fā)完每一個數(shù)據(jù)幀后，不是停下來等待應(yīng)答，而是繼續(xù)發(fā)送下一個數(shù)據(jù)幀，是一種連續(xù)式ARQ?；赝薔步ARQ原理如圖6-5所示，要求第一幀的應(yīng)答信號在第N幀尚未發(fā)送之前到達，若不能到達，應(yīng)增加幀的長度或增加N的值，圖中設(shè)N=6。 當(dāng)?shù)谝粠l(fā)出后，不等待應(yīng)答信號的到達便立刻發(fā)出第二幀、第三幀直至第N幀，若第N幀發(fā)送結(jié)束之前收到的第一幀的應(yīng)答信號為ACK，則繼續(xù)發(fā)送第N+1幀，若應(yīng)答信號為NAK，則從錯的那一幀開始重發(fā)，相當(dāng)于回退了N步，后面的已發(fā)的幀即使正確也要進行重發(fā)。圖6-5回退N步ARQ(N=6) 6.4.3選擇重傳ARQ

選擇重傳ARQ是指在傳輸過程中收到NAK信號后，不是回退到錯誤處，重新將后面所有幀全部重傳，而是將已經(jīng)收到的幀存儲起來，只將出錯的幀進行重傳。這就需要接收端和發(fā)送端都具備存放N幀的緩存。其原理如圖6-6所示(N=6)。圖6-6選擇重傳ARQ 6.4.4滑動窗口協(xié)議 我們知道，在連續(xù)式ARQ中，由于發(fā)送端發(fā)送的下一幀數(shù)據(jù)并不需要等到前一幀數(shù)據(jù)的ACK信號到來后再發(fā)送，為了防止重幀以及方便接收端的排序，我們通過給幀編號的方法來實現(xiàn)連續(xù)傳輸。但如果不加限制地依次編號，幀的編號會越來越大，以至于在數(shù)據(jù)和應(yīng)答幀中，編號會占去絕大部分的信道容量，這在實際應(yīng)用中是絕對不允許的。在這種情況下，我們引入滑動窗口協(xié)議，對收發(fā)兩端進行適當(dāng)?shù)目刂啤?/p>

如圖6-7所示，當(dāng)發(fā)送端發(fā)完了5個幀時(0號幀至4號幀)，發(fā)送窗口已滿，停止發(fā)送，進入等待。設(shè)不久0號幀的確認(rèn)ACK到達，則發(fā)送窗口邊界右移一格，這時發(fā)送端就可以發(fā)送5號幀，因為5號幀已經(jīng)在窗口中了。設(shè)1、2、3號幀的確認(rèn)幀ACK已到達，則發(fā)送窗口邊界右移三格，繼續(xù)可以發(fā)送的幀號是6、7和0號。此時的0號幀由于發(fā)送窗口的限制，是在收到了前面0號幀確認(rèn)信息的基礎(chǔ)上才允許發(fā)送的，故不會與之混淆。圖6-7發(fā)送窗口示意圖

滑動窗口協(xié)議中發(fā)送窗口的寬度WT和接收窗口的寬度WR的取值不一定要相等，不同的取值表示了不同的傳輸方式：

(1)WT＞1，WR=1時，滑動窗口協(xié)議即回退N步ARQ；

(2)WT＞1，WR?＞1時，滑動窗口協(xié)議即選擇重傳AR