第6章差錯(cuò)控制

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

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

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

差錯(cuò)控制方法，常用的有四種：

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

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

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

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

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

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

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

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

信1001110101001001

息0011001010011110

碼1110010101011000

元1101001100101111

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

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

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

–1)個(gè)出錯(cuò)位置，這就是海明碼的工作機(jī)理。

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

2r

-1≥n

即

2r≥r+k+1

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

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

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

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

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

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

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

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

例如(7,3)循環(huán)碼，設(shè)其信息位為111，生成多項(xiàng)式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)冗余校驗(yàn)碼的硬件實(shí)現(xiàn)可由移位寄存器和除法電路實(shí)現(xiàn)，隨著微處理器和數(shù)字信號處理器的應(yīng)用日益廣泛，其編解碼的實(shí)現(xiàn)已變得較為容易。6.4ARQ原理

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

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

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

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

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

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

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

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

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