第6章差錯(cuò)控制技術(shù)6.1差錯(cuò)控制技術(shù)

6.2數(shù)據(jù)校驗(yàn)技術(shù)

6.3糾錯(cuò)碼

6.4數(shù)據(jù)壓縮原理

6.1差錯(cuò)控制技術(shù)

6.1.1基本概念數(shù)據(jù)通信系統(tǒng)的基本任務(wù)是高效而無差錯(cuò)地傳輸和處理數(shù)據(jù)信息。然而,數(shù)據(jù)通信系統(tǒng)的各個(gè)部分都可能產(chǎn)生差錯(cuò),如圖6.1所示。一般情況下,通信設(shè)備部分可以達(dá)到很高的可靠性和穩(wěn)定度,但由于傳輸信道較長,通過的區(qū)域比較復(fù)雜,因此數(shù)據(jù)通信系統(tǒng)中的差錯(cuò)主要來自于數(shù)據(jù)傳輸信道。

圖6.1數(shù)據(jù)通信系統(tǒng)中差錯(cuò)的產(chǎn)生

所謂差錯(cuò)控制,是指對傳輸?shù)臄?shù)據(jù)信號進(jìn)行檢錯(cuò)和糾錯(cuò),以及發(fā)現(xiàn)誤碼不能及時(shí)糾正時(shí),利用適當(dāng)?shù)牟铄e(cuò)控制方式進(jìn)行處理的技術(shù)。數(shù)據(jù)信號經(jīng)過遠(yuǎn)距離的傳輸會(huì)受到各種噪聲(如宇宙噪聲、工業(yè)干擾等各類噪聲)的干擾,使接收到的數(shù)據(jù)信號可能出現(xiàn)差錯(cuò),即誤碼。另外,由于數(shù)據(jù)傳輸信道本身特性不理想,也會(huì)使被傳輸?shù)臄?shù)據(jù)信號產(chǎn)生失真和時(shí)延,甚至可能導(dǎo)致接收信號產(chǎn)生差錯(cuò)。由上述原因引起的誤碼,可以歸納為兩種類型:

·隨機(jī)性錯(cuò)誤,其特點(diǎn)是數(shù)據(jù)信號序列中前后出錯(cuò)位之間沒有關(guān)系;

·突發(fā)性錯(cuò)誤,其特點(diǎn)是前后出錯(cuò)位之間有相關(guān)性。

我們常用傳輸誤碼率(參見第1章)來衡量數(shù)據(jù)傳輸信道的質(zhì)量。當(dāng)實(shí)際信道的誤碼率達(dá)不到用戶要求時(shí),就必須從以下兩個(gè)方面入手予以改進(jìn)。

·改善信道性能,包括選擇合適的傳輸信道、改善其傳輸特性、選用性能優(yōu)良的設(shè)備等,這種方法因受到技術(shù)和經(jīng)濟(jì)因素的制約,有時(shí)可能得不到理想的結(jié)果。

·在數(shù)據(jù)通信鏈路傳輸和處理過程中采用差錯(cuò)控制技術(shù)，即利用檢錯(cuò)糾錯(cuò)編碼技術(shù)來提高傳輸可靠性,降低系統(tǒng)誤碼率。這兩種方法在實(shí)際應(yīng)用中都是比較有效的。

6.1.2差錯(cuò)控制方法常用的差錯(cuò)控制方法很多,可以歸納為三類:時(shí)間冗余法、設(shè)備冗余法和數(shù)據(jù)冗余法,如圖6.2所示。這些方法都是通過冗余量來提高傳輸?shù)目煽啃?只是采用的措施不同而已。

(1)時(shí)間冗余法是用時(shí)間換取可靠性,即通過降低傳輸速率來達(dá)到提高系統(tǒng)可靠性之目的。

(2)設(shè)備冗余法是通過使用較多的信道和設(shè)備來提高傳輸可靠性,通常采用增加備用信道、備用設(shè)備來保證傳輸可靠性。

(3)數(shù)據(jù)冗余法則是通過對數(shù)據(jù)塊進(jìn)行某種抗干擾編碼,即利用增設(shè)冗余校驗(yàn)碼元來提高傳輸可靠性。時(shí)間冗余法只需選擇規(guī)約規(guī)定的速率,如有必要降低速率即可。設(shè)備冗余法又必須增加設(shè)備和信道投入,這樣會(huì)增加經(jīng)費(fèi)開支。因此,抗干擾編碼是經(jīng)濟(jì)實(shí)用的差錯(cuò)控制方法。下面我們只討論數(shù)據(jù)冗余法。

6.1.3數(shù)據(jù)冗余法

1.基本原理利用數(shù)據(jù)冗余法實(shí)現(xiàn)差錯(cuò)控制的基本思想是通過對碼元序列做某種變換,使得原來彼此獨(dú)立、無相關(guān)性的碼元之間產(chǎn)生某種關(guān)聯(lián)性,接收端再根據(jù)這種關(guān)聯(lián)規(guī)律來檢測或糾正傳輸序列中可能出現(xiàn)的誤碼。

2.傳輸控制方法

1)自動(dòng)檢錯(cuò)重發(fā)自動(dòng)檢錯(cuò)重發(fā)(ARQ,AutomaticRepeatreQust)又叫檢錯(cuò)反饋重發(fā)、自動(dòng)重發(fā)請求,采用自動(dòng)檢錯(cuò)重發(fā)方式,發(fā)送端按編碼規(guī)則對擬發(fā)送的信息碼元(簡稱信碼)附加冗余校驗(yàn)碼元,發(fā)送至信道,接收端對收到的碼元序列進(jìn)行檢錯(cuò),并通過反饋信道把檢測結(jié)果回送到發(fā)送端。發(fā)送端對其做如下處理:若接收端回送“接收正確”(ACK),則繼續(xù)發(fā)送下一幀數(shù)據(jù);如接收端回送“檢測到誤碼”(NAK),則重發(fā)原來的數(shù)據(jù)幀,直至接收端正確接收為止。

(1)發(fā)送-等待自動(dòng)檢錯(cuò)重發(fā)，如圖6.3所示。

發(fā)送端:編制檢錯(cuò)碼,發(fā)送。

接收端:接收碼元序列,檢錯(cuò)。若沒有誤碼,則回送接收

正確ACK;若檢測到有誤碼,則回送檢測到誤碼NAK,請求重新發(fā)送。

發(fā)送端:若接收到接收端回送的接收正確信息,則直接發(fā)送下一幀數(shù)據(jù);若接收到接收端回送檢測到誤碼信息,則重新發(fā)送本幀數(shù)據(jù)。

圖6.3發(fā)送-等待傳輸方式

圖6.4連續(xù)發(fā)送傳輸方式

(3)選擇重傳自動(dòng)檢錯(cuò)重發(fā),如圖6.5所示。

圖6.5選擇重傳傳輸方式

發(fā)送端:編制檢錯(cuò)碼,連續(xù)發(fā)送數(shù)據(jù)。接收端:連續(xù)接收碼元序列,檢錯(cuò)。若沒有誤碼,則繼續(xù)接收,回送確認(rèn)信息ACK;若檢測到有誤碼,則回送檢測到誤碼幀信息NAKn,請求重新發(fā)送誤碼幀,此時(shí)接收到的后續(xù)數(shù)據(jù)幀若正確則保留。發(fā)送端:若接收到接收端回送的確認(rèn)信息ACK,則繼續(xù)發(fā)送;若接收到接收端回送的檢測到誤碼信息NAK,則只重新發(fā)送誤碼幀,誤碼后面已發(fā)送的數(shù)據(jù)幀不再重新發(fā)送,而是接著發(fā)送后續(xù)數(shù)據(jù)幀。自動(dòng)檢錯(cuò)重發(fā)必須提供一條反饋信道及相應(yīng)的緩存和控制器,需要重發(fā)的次數(shù)與信道的狀況有關(guān)。但這種方式的檢錯(cuò)效果較好,所附加的冗余碼元約占總發(fā)送碼元的5％～20％,通常這種方式的傳輸效率比較高,因此適用于對數(shù)據(jù)通信實(shí)時(shí)性要求不很高的領(lǐng)域。

2)前向糾錯(cuò)發(fā)送端按照一定的編碼規(guī)則對擬發(fā)送的碼元附加冗余校驗(yàn)碼元,就構(gòu)成了糾錯(cuò)碼。前向糾錯(cuò)(FEC,ForwardErrorCorrection)指接收端將附加冗余碼元按一定的譯碼規(guī)則進(jìn)行變換,用來檢測所接收到的碼元中有無誤碼。若沒誤碼,則繼續(xù)接收;若有誤碼,則及時(shí)糾錯(cuò)。前向糾錯(cuò)方式實(shí)現(xiàn)比較簡單,無需反饋信道,適用于實(shí)時(shí)通信系統(tǒng)。但其差錯(cuò)控制碼與信道的差錯(cuò)統(tǒng)計(jì)特性有關(guān),因此對信道的差錯(cuò)統(tǒng)計(jì)特性必須有充分的了解。另外,糾錯(cuò)編碼方式冗余碼元要占總發(fā)送碼元的20％～50％,從而降低了傳輸效率。

3)混合糾錯(cuò)混合糾錯(cuò)(HEC,HybridErrorCorrection)是前兩種方式的結(jié)合。發(fā)送端發(fā)送具有檢錯(cuò)和糾錯(cuò)能力的碼元,接收端對所接收到的碼組進(jìn)行檢錯(cuò),若誤碼數(shù)較少,在糾錯(cuò)能力以內(nèi),能進(jìn)行糾錯(cuò),就直接糾錯(cuò),接著接收數(shù)據(jù);若誤碼數(shù)較多,超出了糾錯(cuò)范圍,則接收端反饋信息請求發(fā)送端重新發(fā)送該幀數(shù)據(jù),這種方法就是混合糾錯(cuò)?；旌霞m錯(cuò)雖綜合了ARQ和FEC的優(yōu)點(diǎn),但未能克服各自的缺點(diǎn),因而限制了它的實(shí)際應(yīng)用。

4)回程校驗(yàn)回程校驗(yàn)又稱“回聲法”。發(fā)送端發(fā)送數(shù)據(jù)幀,接收端接收到數(shù)據(jù)幀后,同時(shí)將該幀數(shù)據(jù)經(jīng)反饋信道回送到發(fā)送端。發(fā)送端將送回來的數(shù)據(jù)與原發(fā)數(shù)據(jù)進(jìn)行對照比較,如果完全一樣,則認(rèn)為傳輸接收無差錯(cuò),可繼續(xù)發(fā)送下一幀數(shù)據(jù);如果通過比較發(fā)現(xiàn)兩者不一致,則判斷為傳輸接收有差錯(cuò),發(fā)送端重發(fā)本幀數(shù)據(jù)。

根據(jù)回程校驗(yàn)的基本原理,這種方法也存在某些校驗(yàn)不穩(wěn)定因素。例如,接收端收到的數(shù)據(jù)信息本來沒有錯(cuò)誤,但在回送過程中出現(xiàn)了差錯(cuò),使得發(fā)送端做出接收有誤的判斷,繼而進(jìn)行重發(fā),這樣就在接收端造成了數(shù)據(jù)的重復(fù)并且降低了傳輸效率。還可能出現(xiàn)另一種情況,假設(shè)接收數(shù)據(jù)中某個(gè)碼元由“1”錯(cuò)成“0”,而在回送過程中,恰好又使該碼元由“0”錯(cuò)成“1”,此時(shí)發(fā)送端并不能做出接收出錯(cuò)的判斷,但實(shí)際上接收數(shù)據(jù)中確實(shí)存在著差錯(cuò)?；爻绦ｒ?yàn)具有設(shè)備簡單、實(shí)現(xiàn)容易的優(yōu)點(diǎn),但信道利用率下降了50％。根據(jù)應(yīng)用環(huán)境和條件,如通信速率較低,傳輸信道較好,且有反饋信道的場合,則要求控制簡單；而信道利用率要求不高的場合,則可采用回程校驗(yàn)法。

3.不用編碼的差錯(cuò)控制

不用編碼的差錯(cuò)控制是指無需對被傳輸?shù)男盘柎a元進(jìn)行差錯(cuò)編碼,而是利用傳輸方式中附加的冗余措施來減少傳輸中的差錯(cuò),即利用多種傳輸方式來提高傳輸可靠性。如采用重發(fā)多判,發(fā)送端將同一數(shù)據(jù)在一個(gè)信道上多次發(fā)送,或者在不同信道上同時(shí)發(fā)送,接收端根據(jù)所接收到的數(shù)據(jù)的一致性來檢測差錯(cuò)。通常接收端按表決方式來檢驗(yàn)收到的數(shù)據(jù)是否正確,取多數(shù)作為正確者,如三中取二。重發(fā)多判是利用設(shè)備冗余和時(shí)間冗余來換取可靠性的。6.2數(shù)據(jù)校驗(yàn)技術(shù)6.2.1基本概念

1.冗余人之所以要減肥,就是因?yàn)樯眢w內(nèi)有冗余的東西,而這些東西又不是我們正常生活所必需的,去掉這些多余的東西,可以使我們的身體更加健壯,但這些多余的東西又具有一定的作用,不能簡單地將其一刀割掉,將這種有一定作用而又不起主要作用的肌肉就稱為冗余肌肉。

數(shù)據(jù)冗余也是這樣,我們在信息碼后增加一些校驗(yàn)位,用來監(jiān)督信碼,以達(dá)到減錯(cuò)的目的,而這些校驗(yàn)位又不是信碼,所以將其稱為冗余碼。有一種可以滿足以上要求的檢錯(cuò)機(jī)制是對每個(gè)數(shù)據(jù)幀都發(fā)送兩次,因而接收設(shè)備可以在兩個(gè)版本的數(shù)據(jù)之間進(jìn)行逐位比較。任何一個(gè)不同都指示了一個(gè)差錯(cuò),并且相應(yīng)的糾錯(cuò)機(jī)制就可將差錯(cuò)定位。這個(gè)系統(tǒng)是十分精確的(在兩次傳輸?shù)臄?shù)據(jù)中具有完全相同的比特差錯(cuò)的幾率是非常小的),但是卻慢得讓人無法忍受——不僅傳輸時(shí)間加倍,而且還要加上對數(shù)據(jù)幀進(jìn)行逐位比較所需的時(shí)間。

在傳輸中加入只用于比較的附加信息的想法是不錯(cuò)的。但不是重復(fù)整個(gè)數(shù)據(jù)流,而是在每個(gè)數(shù)據(jù)幀的末尾加上一些更短的比特,附加比特對于所傳輸?shù)男畔碚f是多余的,一旦傳輸?shù)恼_性被確認(rèn),這些附加比特就被丟棄,這種技術(shù)稱做冗余。檢錯(cuò)采用了數(shù)據(jù)冗余技術(shù),就是在信息中加上附加比特以便于接收端進(jìn)行檢錯(cuò)。圖6.6即顯示了采用冗余比特來進(jìn)行數(shù)據(jù)幀正確性驗(yàn)證的過程。當(dāng)數(shù)據(jù)幀生成后,就通過一個(gè)設(shè)備來分析它并且加上相應(yīng)的冗余校驗(yàn)編碼?，F(xiàn)在增加了若干比特的數(shù)據(jù)冗余位(圖6.6中增加了4比特),通過鏈路傳輸?shù)浇邮辗?。接收方對整個(gè)傳輸流進(jìn)行校驗(yàn)判斷是否有誤碼。如果接收的比特流通過了校驗(yàn)標(biāo)準(zhǔn),數(shù)據(jù)幀的數(shù)據(jù)部分就被接收,而冗余位則被丟棄。

圖6.6數(shù)據(jù)冗余校驗(yàn)技術(shù)

2.檢錯(cuò)碼檢錯(cuò)碼是具有檢錯(cuò)功能的編碼,是指在發(fā)送每一組信息的同時(shí)發(fā)送一些冗余校驗(yàn)位,接收端通過這些冗余校驗(yàn)位對所接收的數(shù)據(jù)進(jìn)行判斷,確定其是否正確。檢錯(cuò)碼不能確定是哪一位存在誤碼,也就沒有糾錯(cuò)功能。如果檢測到存在誤碼,可以通過反饋信道傳送一個(gè)應(yīng)答幀把這個(gè)錯(cuò)誤的結(jié)果傳送到發(fā)送端,請求發(fā)送端重新發(fā)送該幀數(shù)據(jù),直至接收端收到正確的數(shù)據(jù)為止。

最簡單的檢錯(cuò)碼是奇偶校驗(yàn)。它是在一個(gè)二進(jìn)制數(shù)據(jù)后加上一位作為奇偶校驗(yàn)位。偶校驗(yàn)是在每一個(gè)字符后面增加一位,使該字符幀中“1”的個(gè)數(shù)為偶數(shù)。奇校驗(yàn)是在每一個(gè)字符后面增加一位,使該字符中“1”的個(gè)數(shù)為奇數(shù)。接收端通過檢測該幀數(shù)據(jù)中“1”的個(gè)數(shù)為奇數(shù)還是偶數(shù)來判斷接收數(shù)據(jù)是否有誤。奇偶校驗(yàn)并不是一種十分安全可行的檢錯(cuò)方法。如果有偶數(shù)個(gè)數(shù)據(jù)位在傳輸中同時(shí)出錯(cuò),接收端就無法檢測出差錯(cuò)的數(shù)據(jù),所以其檢錯(cuò)概率為50%。對于低速傳輸來說,奇偶校驗(yàn)是一種令人滿意的檢錯(cuò)法,也是數(shù)據(jù)通信中最常用的檢錯(cuò)方法之一。如計(jì)算機(jī)串行通信端口RS-232C采用的就是奇偶校驗(yàn)法。

3.糾錯(cuò)碼糾錯(cuò)碼是指在發(fā)送每一組信息時(shí)發(fā)送足夠的冗余校驗(yàn)位,接收端通過這些冗余校驗(yàn)位在接收譯碼器的控制下不僅可以發(fā)現(xiàn)錯(cuò)誤,而且還能自動(dòng)地糾正錯(cuò)誤。如果采用這種編碼,傳輸系統(tǒng)中不需反饋信道就可以實(shí)現(xiàn)一個(gè)對多個(gè)用戶的通信,但譯碼器比較復(fù)雜。為了糾正差錯(cuò),要求附加的冗余碼較多,這將會(huì)降低傳輸?shù)男省，F(xiàn)在比較常見的糾錯(cuò)編碼有漢明糾錯(cuò)碼、正反糾錯(cuò)碼等。在數(shù)據(jù)通信系統(tǒng)中,數(shù)據(jù)冗余校驗(yàn)通常采用四種類型:奇偶校驗(yàn)(也稱為垂直冗余校驗(yàn)VRC)、縱向冗余校驗(yàn)(LRC)、循環(huán)冗余校驗(yàn)(CRC)以及校驗(yàn)和法,如圖6.7所示。奇偶校驗(yàn)、縱向冗余校驗(yàn)及循環(huán)冗余校驗(yàn)在計(jì)算機(jī)網(wǎng)絡(luò)中應(yīng)用于物理層而被數(shù)據(jù)鏈路層使用。而校驗(yàn)和技術(shù)主要用于在數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層、傳輸層、會(huì)話層、表示層和應(yīng)用層之間傳輸數(shù)據(jù)。

圖6.7

校驗(yàn)方法

4.碼距與檢錯(cuò)糾錯(cuò)能力的關(guān)系碼重:在信道編碼中,我們將碼組中非0碼元的數(shù)目定義為碼重。碼距d:將兩個(gè)碼組中對應(yīng)碼位上具有不同二進(jìn)制碼元的位數(shù)定義為兩碼組的距離,簡稱為碼距,用d表示。最小碼距dmin:在一種編碼中,任意兩個(gè)碼組之間碼距的最小值稱為最小碼距,用dmin表示。最小碼距dmin與編碼的檢錯(cuò)糾錯(cuò)能力有如下關(guān)系。(1)在一碼組中,若要求能檢測e個(gè)誤碼,則最小碼距應(yīng)滿足:dmin≥e+1(6.1)(2)在一碼組中,若要求能糾正t個(gè)誤碼,則最小碼距應(yīng)滿足:

dmin≥2t+1(6.2)

(3)在一碼組中,若要求能糾正t個(gè)誤碼,同時(shí)能檢測到e(e＞t)個(gè)誤碼,則最小碼距應(yīng)滿足:dmin≥e+t+1(e＞t)(6.3)編碼效率R:將信碼數(shù)k與碼組中碼元個(gè)數(shù)n(稱為碼長)之比稱為信道的編碼效率，即

(6.4)而碼長n=k+r,r為校驗(yàn)碼(也叫監(jiān)督碼)的位數(shù)。一般來說,校驗(yàn)碼元越多,檢錯(cuò)糾錯(cuò)能力就越強(qiáng),但編碼效率就越低。

例6.1已知有兩碼組分別為(0000)和(1111)。請問:

(1)若用于檢錯(cuò),能檢測幾位誤碼？

(2)若用于糾錯(cuò),能糾正幾位誤碼？

(3)若同時(shí)用于檢錯(cuò)和糾錯(cuò),其性能如何？

解可知碼組的最小碼距dmin＝4。

(1)若用于檢錯(cuò),根據(jù)dmin≥e+1,可得e=3,所以能檢出3位誤碼。

(2)若用于糾錯(cuò),根據(jù)dmin≥2t+1,得t=1,所以能糾正1位誤碼。

(3)若同時(shí)用于檢錯(cuò)和糾錯(cuò),根據(jù)dmin≥e+t+1(e＞t),可得e=2,t=1,即能檢測2位誤碼并能糾正1位誤碼。6.2.2奇偶校驗(yàn)

1.原理在差錯(cuò)檢測中最常用和實(shí)惠的方法是奇偶校驗(yàn),又稱為垂直冗余校驗(yàn)(VRC)。在數(shù)據(jù)后面附加一位奇偶校驗(yàn)位,組成一個(gè)相對完整的數(shù)據(jù)幀。當(dāng)采用偶校驗(yàn)時(shí),使得整個(gè)數(shù)據(jù)幀中1的個(gè)數(shù)(包括校驗(yàn)位)是偶數(shù)。

假設(shè)我們想要利用偶校驗(yàn)傳送二進(jìn)制數(shù)據(jù)1000011(字母C的ASCII碼),1的個(gè)數(shù)是3,是奇數(shù)。傳輸前,將該數(shù)據(jù)幀輸入到校驗(yàn)碼生成器中,生成一個(gè)校驗(yàn)比特(此例中是1)附加到數(shù)據(jù)幀的尾部,這樣本幀數(shù)據(jù)1的數(shù)目就是4個(gè),是偶數(shù)。然后系統(tǒng)通過網(wǎng)絡(luò)鏈路將擴(kuò)展后的數(shù)據(jù)幀傳輸出去。當(dāng)接收端收到數(shù)據(jù)幀后,將所有8比特都輸入到偶校驗(yàn)器中。若接收到10000111,共有4個(gè)1,是偶數(shù),就認(rèn)為該幀數(shù)據(jù)正確,保存該數(shù)據(jù)幀。如果在數(shù)據(jù)傳輸過程中數(shù)據(jù)幀收到干擾造成誤碼,接收方接收的是10010111而不是10000111,那么,當(dāng)偶校驗(yàn)器對1計(jì)數(shù)時(shí),將得到一個(gè)奇數(shù)即5個(gè)1。接收方就知道在該數(shù)據(jù)幀的某處發(fā)生了差錯(cuò),從而丟棄整個(gè)數(shù)據(jù)幀。整個(gè)過程如圖6.8所示。

圖6.8偶校驗(yàn)過程

奇偶校驗(yàn)中,在每一個(gè)數(shù)據(jù)幀中都增加了一個(gè)校驗(yàn)位,從而使得1的總數(shù)(包括校驗(yàn)位)是偶數(shù)。在此我們只討論偶校驗(yàn),整個(gè)幀“1”的個(gè)數(shù)應(yīng)為偶數(shù)。奇校驗(yàn)只是整個(gè)幀“1”的個(gè)數(shù)為奇數(shù),原理相同。用數(shù)學(xué)式表達(dá)為:若有一組數(shù)據(jù)為a1,a2,…,an-1,附加校驗(yàn)位為an,則可用下式表示其關(guān)系:(mod

2)校驗(yàn)為:(奇校驗(yàn))(偶校驗(yàn))(mod

2)

例6.2

若發(fā)送端要采用偶校驗(yàn)方式發(fā)送“China”一詞。這五個(gè)字母的ASCII編碼(參見附錄A)為:

1000011

1101000

1101001

1101110

1100001C

h

i

n

a按照偶校驗(yàn)的規(guī)則,計(jì)算得到校驗(yàn)位并附加于各字符編碼之后,得到其傳輸數(shù)據(jù)為:10000111

110100011101001011011101

11000011

2.性能奇偶校驗(yàn)可以檢測所有奇數(shù)比特差錯(cuò),若發(fā)生差錯(cuò)的總比特?cái)?shù)是奇數(shù)(1,3,5等),則該技術(shù)均可以檢測出其差錯(cuò)。如有一個(gè)6個(gè)“1”的偶校驗(yàn)數(shù)據(jù)幀:1000111011。如果其中的3比特發(fā)生了差錯(cuò)接收數(shù)據(jù)為1111111011,校驗(yàn)結(jié)果“1”的數(shù)目是奇數(shù),就可檢測到有誤碼,應(yīng)丟棄該幀數(shù)據(jù)。如數(shù)據(jù)幀的兩個(gè)比特被改變,接收的數(shù)據(jù)幀為:1110111011,數(shù)據(jù)幀中“1”的數(shù)目是8,數(shù)據(jù)幀中1的個(gè)數(shù)仍然是偶數(shù),盡管數(shù)據(jù)幀包含有兩個(gè)差錯(cuò)位,接收端還會(huì)認(rèn)為是正確的。所以,奇偶校驗(yàn)不能檢測所有發(fā)生了偶數(shù)位改變的差錯(cuò)。如果在傳輸中發(fā)生任何兩比特差錯(cuò),這兩個(gè)變化就產(chǎn)生了對消效果。所以盡管數(shù)據(jù)幀已經(jīng)被破壞,但它仍能通過奇偶校驗(yàn)。因此,奇偶校驗(yàn)可以檢測出奇數(shù)比特差錯(cuò),不能檢測偶數(shù)比特差錯(cuò)。

6.2.3縱向冗余校驗(yàn)

1.原理縱向冗余校驗(yàn)就是將數(shù)據(jù)串分成若干個(gè)段(通常用字節(jié)或字)組合在一起,然后按位求和作為該列的校驗(yàn)位,將所有校驗(yàn)位組成一個(gè)段,附加于數(shù)據(jù)段后面發(fā)送,接收端利用附加的校驗(yàn)段進(jìn)行校驗(yàn)。發(fā)送端用表格式(行和列)組織數(shù)據(jù)塊,將一個(gè)數(shù)據(jù)塊劃分成幾行,并將校驗(yàn)位組成的冗余行添加到整個(gè)數(shù)據(jù)塊中,對應(yīng)位求和并組成校驗(yàn)字段。

例如,我們要發(fā)送24位數(shù)據(jù),不是直接發(fā)送24位而是組成3行8列的表,然后,對每列計(jì)算校驗(yàn)位并建立一個(gè)8位的新行,這8位是整個(gè)塊的校驗(yàn)位。將所有行的第一位累加求和(不計(jì)進(jìn)位)得到第四行(校驗(yàn)字段)的第一個(gè)校驗(yàn)位,第二個(gè)校驗(yàn)位是將所有的第二位累加求和,依此類推。然后,將八個(gè)校驗(yàn)位附加到原始數(shù)據(jù)塊后面,組成完整的數(shù)據(jù)幀發(fā)送,如圖6.9所示。

圖6.9縱向校驗(yàn)

例6.3

設(shè)要采用縱向校驗(yàn)發(fā)送數(shù)據(jù)塊:100110101010011001101011。按位模2求和(對應(yīng)位異或)得到縱向校驗(yàn)位為:01010111

發(fā)送數(shù)據(jù)為:10011010101001100110101101010111接收端對接收的數(shù)據(jù)按位異或：10011010101001100110101101010111

00000000←若結(jié)果為0,說明數(shù)據(jù)幀傳輸正確,保存數(shù)據(jù)若在傳輸過程中,由于干擾造成誤碼使得接收到的數(shù)據(jù)為:11011010

10101110

01101011

01010111

接收端對接收的數(shù)據(jù)按位異或：11011010101011100110101101010111

01001000

←若結(jié)果不為0,說明數(shù)據(jù)幀存在誤碼,丟棄

2.性能縱向校驗(yàn)具有檢錯(cuò)功能,可以提高系統(tǒng)檢測突發(fā)差錯(cuò)能力。如例6.3所示,n位的LRC會(huì)容易檢測一個(gè)n位突發(fā)差錯(cuò)。多于n位的突發(fā)差錯(cuò)也可用LRC以很高的概率檢測出來。但是,有一種類型的差錯(cuò)仍然會(huì)被遺漏,如果在某個(gè)數(shù)據(jù)幀中的兩個(gè)比特被破壞,同時(shí)另一個(gè)數(shù)據(jù)幀中正好在相同位置的兩個(gè)比特也被破壞,那么LRC校驗(yàn)器就檢測不出這種差錯(cuò)。如有兩個(gè)數(shù)據(jù)幀11110000和11000011，在每個(gè)數(shù)據(jù)幀的第一個(gè)和最后一個(gè)位置的比特被改變,將數(shù)據(jù)幀變成01110001和01000010,那么LRC將無法檢測出這些差錯(cuò)。6.2.4循環(huán)冗余校驗(yàn)

1.原理循環(huán)冗余校驗(yàn)是一種很有效的冗余校驗(yàn)技術(shù)。和基于加法的VRC及LRC不同,循環(huán)冗余校驗(yàn)基于二進(jìn)制除法。在循環(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ù)所整除。到達(dá)接收端后,再用同一個(gè)數(shù)去除整個(gè)數(shù)據(jù)幀。如果在此時(shí)不產(chǎn)生余數(shù)即能夠被整除,就認(rèn)為數(shù)據(jù)幀是完整正確的,從而保存該數(shù)據(jù)幀。若有余數(shù)則意味著數(shù)據(jù)幀在傳輸中被破壞,存在誤碼,應(yīng)丟棄該數(shù)據(jù)幀。在循環(huán)冗余校驗(yàn)中使用的冗余比特是將數(shù)據(jù)幀除以一個(gè)預(yù)定的除數(shù)后產(chǎn)生的,余數(shù)就是循環(huán)冗余校驗(yàn)碼(CRC碼)。

2.循環(huán)冗余校驗(yàn)碼的特性(1)比除數(shù)少一位。(2)附加到數(shù)據(jù)串末尾后能形成一個(gè)可以被除數(shù)整除數(shù)據(jù)串。

3.循環(huán)冗余校驗(yàn)碼的生成

循環(huán)冗余校驗(yàn)技術(shù)的理論和應(yīng)用簡單明了,比較復(fù)雜的就是CRC碼的生成。下面介紹采用模2除法生成CRC碼的方法。

(1)選擇除數(shù)。根據(jù)任務(wù)性質(zhì),在通信規(guī)約里選擇合適的除數(shù)。設(shè)所選除數(shù)位數(shù)為n。

(2)在數(shù)據(jù)幀的末尾加上(n-1)個(gè)0,得到一個(gè)加長了的數(shù)據(jù)幀。

(3)采用二進(jìn)制除法用加長的數(shù)據(jù)幀除以除數(shù),產(chǎn)生的(n-1)位余數(shù)就是CRC碼。

(4)用從第(3)步得到的(n-1)比特的CRC碼替換被除數(shù)數(shù)據(jù)幀末尾附加的(n-1)個(gè)0。注意,CRC碼也可為全0。將以上編碼通過信道發(fā)送出去,數(shù)據(jù)碼在前,校驗(yàn)碼在后。接收端將整個(gè)數(shù)據(jù)串作為一個(gè)數(shù)據(jù)幀,除以發(fā)送端產(chǎn)生校驗(yàn)碼的那個(gè)除數(shù)。如果數(shù)據(jù)串無差錯(cuò)地到達(dá)接收方,循環(huán)冗余校驗(yàn)器產(chǎn)生的余數(shù)為0,則數(shù)據(jù)幀將通過檢驗(yàn),接收端保存該數(shù)據(jù)。如果在傳輸中數(shù)據(jù)幀被改變,產(chǎn)生了誤碼,除法得到的余數(shù)就不為0,說明存在誤碼,數(shù)據(jù)幀不能通過檢驗(yàn),丟棄該幀數(shù)據(jù)。CRC校驗(yàn)原理如圖6.10所示。

圖6.10CRC校驗(yàn)原理

4.模2除法生成CRC碼采用模2除法可以生成CRC碼,下面舉例說明CRC碼的生成方法。設(shè)要傳輸?shù)臄?shù)據(jù)為A=1011011,選擇的除數(shù)為B=1101,采用模2除法生成CRC碼。

(1)在被除數(shù)(要傳輸?shù)臄?shù))A=1011011后面加上3(因?yàn)槌龜?shù)是4位)個(gè)0,變?yōu)?C=1011011000

(2)用C=1011011000除以除數(shù)B。若被除數(shù)4位的第一位為“1”,就商“1”,將被除數(shù)的4位與除數(shù)的對應(yīng)位相異或,求得余數(shù)。本例中第1個(gè)4位為1011,與除數(shù)1101相異或,得到余數(shù)為110,余數(shù)最高位的0可省略不寫,但若第2位也為0,就不能省略了。若被除數(shù)4位的第一位為“0”,就商“0”,將被除數(shù)的4位與0000的對應(yīng)位相異或,求得余數(shù)。將被除數(shù)中下一位抄錄下來,使其位數(shù)與除數(shù)位數(shù)相同,繼續(xù)相除,直到被除數(shù)各位均已使用,所得到的余數(shù)比除數(shù)少一位,該余數(shù)就是CRC碼。具體相除過程如圖6.11所示。

圖6.11求CRC碼

5.循環(huán)碼校驗(yàn)發(fā)送端將附加了CRC碼的數(shù)據(jù)發(fā)送到信道,接收端接收到該數(shù)據(jù)串后,采用與發(fā)送端相同的除數(shù)對接收的數(shù)據(jù)幀進(jìn)行模2除。如果余數(shù)為0,說明沒有誤碼,去掉CRC碼,保存前面的數(shù)據(jù);如果余數(shù)不為0,說明傳輸過程中產(chǎn)生了誤碼,丟棄該幀數(shù)據(jù)。這樣就達(dá)到了校驗(yàn)的目的,校驗(yàn)過程如圖6.12所示。

圖6.12循環(huán)碼校驗(yàn)

圖6.13有誤碼的情況

6.除數(shù)的選擇原則前面我們采用二進(jìn)制數(shù)表示被除數(shù)和除數(shù),通常為了便于數(shù)學(xué)證明,也采用多項(xiàng)式來表示,其實(shí)質(zhì)是一樣的。一般情況下,多項(xiàng)式只寫出系數(shù)為1的項(xiàng),所以多項(xiàng)式描述比較短。循環(huán)冗余校驗(yàn)碼是基于將位串看成是系數(shù)為0或1的多項(xiàng)式,一個(gè)k位幀可以看成是從xk-1到x0的k次多項(xiàng)式的系數(shù)序列,這個(gè)多項(xiàng)式的階數(shù)為k-1。高位(最左邊)是xk-1項(xiàng)系數(shù),下一位是xk-2的系數(shù),以此類推。例如,1011010101有10位,表示成多項(xiàng)式為(x9+x7+x6+x4+x2+1)。多項(xiàng)式和二進(jìn)制數(shù)之間的對應(yīng)關(guān)系如圖6.14所示。圖6.14二進(jìn)制數(shù)與多項(xiàng)式的對應(yīng)關(guān)系

作為除數(shù)的多項(xiàng)式應(yīng)滿足以下兩個(gè)條件:

(1)不能被x除盡。這是為了保證檢測所有長度等于多項(xiàng)式階數(shù)(二進(jìn)制除數(shù)位數(shù))的差錯(cuò)。

(2)必須被(x＋1)整除。這是為了保證檢測出所有奇數(shù)位的差錯(cuò)。當(dāng)然,我們在選擇除數(shù)時(shí),要按照規(guī)約提供的除數(shù),選擇合適的位數(shù)和相應(yīng)的除數(shù)。常用的多項(xiàng)式如下:CRC-12:x12+x11+x3+x+1對應(yīng)的二進(jìn)制數(shù):1100000001011CRC-16:x16+x15+x2+1對應(yīng)的二進(jìn)制數(shù):11000000000000101CRC-ITU-T:x16+x12+x5+1對應(yīng)的二進(jìn)制數(shù):10001000000100001CRC-32:x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1對應(yīng)的二進(jìn)制數(shù)為100000100110000010001110110110111數(shù)字12、16和32是指CRC余數(shù)的長度。相應(yīng)地,CRC除數(shù)位數(shù)分別是13、17和33位。

7.性能由于每一位都多次參與了校驗(yàn)位的求取過程,因此CRC能檢測多種類型的誤碼,是一種很有效的檢錯(cuò)方法。如果除數(shù)按照前面提到的規(guī)則選取,則

(1)CRC能檢測所有影響奇數(shù)位的突發(fā)差錯(cuò);

(2)CRC能檢測所有長度小于或等于多項(xiàng)式階數(shù)的突發(fā)差錯(cuò);

(3)CRC能以非常高的概率檢測出長度大于多項(xiàng)式階數(shù)的突發(fā)差錯(cuò)。如CRC-12(x12+x11+x3+x+1),為12階多項(xiàng)式,能夠檢測所有奇數(shù)位的誤碼,也可檢測出所有長度小于或等于12的突發(fā)差錯(cuò)，并能以99.97％的概率檢測出長度大于12的突發(fā)差錯(cuò)。所以CRC是一種十分有效的檢錯(cuò)方法。

6.2.5校驗(yàn)和法

1.原理將要傳輸?shù)臄?shù)據(jù)按字節(jié)或字分成若干數(shù)據(jù)單元,每個(gè)單元為n位(通常是8bit或16bit)，然后將各單元數(shù)據(jù)累加求和,各位都能參與校驗(yàn)過程,保留和的位數(shù)與數(shù)據(jù)單元位數(shù)相同,求和過程中不計(jì)溢出位(模256或模65536)。一種方法是直接將校驗(yàn)和附加到數(shù)據(jù)后面,作為校驗(yàn)和與數(shù)據(jù)組成發(fā)送數(shù)據(jù)幀;另一種方法是將所求校驗(yàn)和取反,附加到數(shù)據(jù)串的后面,組成發(fā)送數(shù)據(jù)幀。接收端再依據(jù)同樣的求和法進(jìn)行校驗(yàn)。前一種方法是對所有數(shù)據(jù)串求和,與接收到的校驗(yàn)和進(jìn)行比較,若相等說明沒有誤碼,若不相等,說明傳輸過程中產(chǎn)生了誤碼;后一種方法因?yàn)閭鬏數(shù)浇邮斩说母郊游皇切ｒ?yàn)和的反碼,接收端要對接收到的數(shù)據(jù)和校驗(yàn)和統(tǒng)一累加求和,再取反,若為0,說明無誤碼,數(shù)據(jù)正確,若不為0,說明傳輸過程中產(chǎn)生了誤碼,這樣就達(dá)到了檢錯(cuò)的目的，如圖6.15所示。圖6.15校驗(yàn)和法

2.校驗(yàn)和的生成

(1)發(fā)送端將數(shù)據(jù)分成若干個(gè)數(shù)據(jù)單元,通常是按字節(jié)或字為單位劃分的。

(2)將所有單元累加求和,不計(jì)溢出位,并將累加和取反,得到校驗(yàn)和。

(3)將校驗(yàn)和附加在數(shù)據(jù)段后面,組成發(fā)送數(shù)據(jù)幀發(fā)送。

3.接收端校驗(yàn)

(1)按照通信規(guī)約,將數(shù)據(jù)分成若干段,每段為nbit。

(2)將包括校驗(yàn)和在內(nèi)的所有數(shù)據(jù)段累加求和,取反。

(3)所得值若為0,說明接收數(shù)據(jù)正確,去掉校驗(yàn)和字段,保存數(shù)據(jù);若取反值不為0,證明傳輸過程中產(chǎn)生了誤碼,丟棄所有數(shù)據(jù)。

例6.4

設(shè)要發(fā)送24bit數(shù)據(jù),采用校驗(yàn)和法校驗(yàn)。欲傳輸?shù)臄?shù)據(jù)為:101001011001101111100111發(fā)送端:按8bit一組分段:10100101,10011011,11100111求和:

10100101

10011011+11100111累加和00100111取反↓校驗(yàn)和

11011000發(fā)送數(shù)據(jù)串為:同步碼10100101100110111110011111011000接收端:分段10100101,10011011,11100111,11011000求和,判斷

101001011001101111100111+1101100011111111取反↓

00000000結(jié)果為0,說明傳輸數(shù)據(jù)正確,去掉校驗(yàn)和,保存數(shù)據(jù)。

假若在傳輸過程中,有一段數(shù)據(jù)受到干擾,造成誤碼,結(jié)果如下:如第1段的第4位由0→1,接收端判斷如下:101101011001101111100111+1101100000001111取反↓

11110000結(jié)果不為0,說明傳輸數(shù)據(jù)有誤碼,丟棄該幀數(shù)據(jù)。

4.性能校驗(yàn)和法能檢測所有奇數(shù)比特的差錯(cuò),以及大多數(shù)偶數(shù)比特的差錯(cuò)。但是,如果在某一分段中的一個(gè)或多個(gè)比特被破壞,并且在下一個(gè)分段中具有相反值的對應(yīng)位也被破壞,其和不變,接收端將檢測不出誤碼?？v向冗余校驗(yàn)因?yàn)椴挥?jì)加法進(jìn)位,若相同列兩位同時(shí)發(fā)生誤碼時(shí),該列校驗(yàn)位就不變,接收端將無法檢測出誤碼。而校驗(yàn)和法保留了所有的進(jìn)位,因此,盡管兩個(gè)0變?yōu)?不會(huì)改變它們自身列的值,卻會(huì)改變高位列的數(shù)值。在實(shí)際應(yīng)用中,也可采用發(fā)送端將各段數(shù)據(jù)累加求和,所得到的累加和就作為校驗(yàn)和,附加在數(shù)據(jù)段后面發(fā)送,接收端將接收到的數(shù)據(jù)段(不包括校驗(yàn)和)累加求和,再與校驗(yàn)和相異或。若為0,說明數(shù)據(jù)正確,若不為0,證明有誤碼存在。

6.2.6恒比碼恒比碼又稱為等重碼,其碼字中1和0的位數(shù)保持恒定,因此稱為恒比碼,它也正是利用這一特性進(jìn)行檢錯(cuò)的。接收端只需判斷碼組中1和0的個(gè)數(shù),就可方便地檢測出碼組中任何一位發(fā)生的誤碼。例如我國電報(bào)通信中,電傳機(jī)采用的是(3∶2)恒比碼,就是在每一個(gè)碼組中1和0的比例為3∶2,每個(gè)碼組都由3個(gè)1和2個(gè)0組成,也叫五中取三碼,即在5位二進(jìn)制數(shù)碼(25＝32)中取1的數(shù)目恒為3的碼組,代表10個(gè)字符(0～9),如表6.1所示。

表6.1

3∶2恒比碼

接收端檢測恒比碼時(shí),通過計(jì)算接收碼組中1的個(gè)數(shù),判斷傳輸過程中有無誤碼。除了在一個(gè)碼組中同時(shí)出現(xiàn)“1”錯(cuò)成“0”,“0”錯(cuò)成“1”以外,能夠檢測其他多種誤碼形式,因此,恒比碼是一種檢錯(cuò)能力很強(qiáng)的編碼方式。在實(shí)際應(yīng)用中,采用恒比碼可使得國際電報(bào)的誤碼率保持在10-6以下。

6.3糾錯(cuò)碼

1.漢明碼漢明碼是1949年由美國貝爾實(shí)驗(yàn)室漢明(R.W.Hamming)提出來的,是糾正單個(gè)隨機(jī)錯(cuò)誤的線性碼。目前漢明碼及其變型已被廣泛應(yīng)用于數(shù)據(jù)通信和數(shù)字存儲(chǔ)系統(tǒng),是一種十分有用的差錯(cuò)控制編碼。漢明碼的碼型結(jié)構(gòu)與循環(huán)碼相同,也是碼組結(jié)構(gòu),由信息碼元和校驗(yàn)碼元組成。發(fā)送端根據(jù)編碼規(guī)則產(chǎn)生校驗(yàn)碼元,接收端則按照譯碼規(guī)則找出差錯(cuò)的具體位置后自動(dòng)進(jìn)行糾正。漢明碼參數(shù)如表6.2所示。

表6.2漢明碼參數(shù)

漢明碼的最小碼距dmin＝3(r是不小于3的任意正整數(shù))。通常用總長n和信碼長度k,即(n,k)來表示漢明碼的類型。

2.漢明不等式要指明單個(gè)錯(cuò)誤的位置,碼長與檢驗(yàn)碼元之間應(yīng)滿足下列關(guān)系:2r≥n+1或

(6.7)(6.8)這就是漢明不等式。當(dāng)不等式取等號時(shí),表示碼長一定,用來糾正一位錯(cuò)碼的漢明碼所用的校驗(yàn)碼元個(gè)數(shù)最少。

3.漢明碼的編碼規(guī)則

(1)規(guī)定每個(gè)校驗(yàn)碼元只允許參加一個(gè)組的校驗(yàn)。若采用r(n-k)個(gè)校驗(yàn)碼元,則可組成r個(gè)校驗(yàn)組,分別用G1,G2,…,Gr表示。

(2)每一個(gè)信息碼元必須參加(2～r)個(gè)校驗(yàn)組,且校驗(yàn)組模式不能重復(fù)。根據(jù)上述編碼規(guī)則,如果某一信息碼元或校驗(yàn)碼元發(fā)生錯(cuò)誤,則必然會(huì)使其參加的校驗(yàn)組的奇偶校驗(yàn)出現(xiàn)錯(cuò)誤。能夠確定差錯(cuò)的位置,將其取反,便可達(dá)到糾錯(cuò)的目的。例6.5以簡單的(7,4)漢明碼為例,說明漢明碼的編碼和糾錯(cuò)原理。

解(7,4)漢明碼的碼長n＝7,信息碼元數(shù)k＝4,則校驗(yàn)碼元數(shù)r＝3,滿足漢明不等式

2r≥n+1用ai表示信息碼元,ri表示校驗(yàn)碼元,其編碼結(jié)構(gòu)的形式為:a3a

2a1a0r2r1r0(信碼＋校驗(yàn)碼)。當(dāng)然,其編碼形式還可以有多種,通信雙方一定要采用同一種編碼形式。根據(jù)編碼規(guī)則,表6.3給出了(7,4)漢明碼的一種編碼形式。因?yàn)橛?個(gè)校驗(yàn)碼元,所以可組成3個(gè)校驗(yàn)組,分別用G1、G2、G3表示。每個(gè)校驗(yàn)碼元只參加一個(gè)組的校驗(yàn),如r2參加G1。表中用符號“”表示該碼元參加這一組的校驗(yàn)。表6.3(7,4)漢明碼的一種編碼形式

校驗(yàn)碼生成方程組為:

(mod

2)（6.10）例6.6

請采用漢明碼發(fā)送數(shù)據(jù)0101。解信碼長k=4根據(jù)漢明不等式

取

得

r=3n=7即為(7,4)漢明碼。

表6.4漢明碼編碼形式

所以發(fā)送數(shù)據(jù)串為:0101

010

。

4.接收端檢錯(cuò)

為了達(dá)到檢錯(cuò)和糾錯(cuò)的目的,接收端只要對收到的碼組按照發(fā)送端編碼關(guān)系進(jìn)行計(jì)算即可,其譯碼方程組為:

(6.10)

顯然,當(dāng)未出現(xiàn)傳輸差錯(cuò)時(shí),Gi′應(yīng)等于0,即差錯(cuò)模式{G1′,G2′,G3′為000。而當(dāng)出現(xiàn)差錯(cuò)且差錯(cuò)的數(shù)目在允許范圍之內(nèi)時(shí),Gi′就不等于0。根據(jù)差錯(cuò)模式的不同可以準(zhǔn)確判斷碼組中出現(xiàn)一個(gè)差錯(cuò)時(shí)發(fā)生差錯(cuò)的具體位置,如表6.5所示。對于檢測到的差錯(cuò)碼元,只要令其取反,便實(shí)現(xiàn)了自動(dòng)糾錯(cuò)的功能。表6.5

漢明碼的糾錯(cuò)模式

例6.7

若例6.5中接收端接收到的數(shù)據(jù)為0101010,求接收端的校驗(yàn)過程。

解根據(jù)校驗(yàn)方程組:可知接收數(shù)據(jù)無差錯(cuò),接收數(shù)據(jù)正確,去掉校驗(yàn)位,保存數(shù)據(jù)0101。

例6.8若例6.5中接收端接收到的數(shù)據(jù)為0111010,求接收端的校驗(yàn)過程。解根據(jù)校驗(yàn)方程組:

校驗(yàn)碼組為110,從表6.5可知是a1產(chǎn)生了差錯(cuò),將其取反,糾錯(cuò),所得正確碼組為0101010,去掉校驗(yàn)位,保存正確數(shù)據(jù)0101。可知接收數(shù)據(jù)無差錯(cuò),接收數(shù)據(jù)正確,去掉校驗(yàn)位,保存數(shù)據(jù)0101。

6.4數(shù)據(jù)壓縮原理數(shù)據(jù)通信的目的是高效、準(zhǔn)確地傳輸數(shù)據(jù)信息,所謂高效就是單位時(shí)間內(nèi)傳送的信息量大。我們可以從兩個(gè)方面著手,一方面通過提高信道容量來提高傳輸速率,另一方面是通過提高單位數(shù)據(jù)包含的信息量,并將包含一定信息量的數(shù)據(jù)進(jìn)行壓縮,以使其平均信息量提高，這是一個(gè)行之有效的方法。相信隨著計(jì)算機(jī)速率的不斷提高,各種數(shù)據(jù)壓縮算法的不斷推出,數(shù)據(jù)壓縮技術(shù)將會(huì)在提高數(shù)據(jù)傳輸效率方面發(fā)揮更大的作用。本節(jié)將簡要介紹數(shù)據(jù)壓縮技術(shù)的原理及實(shí)現(xiàn)方法,使讀者對數(shù)據(jù)壓縮技術(shù)及其在數(shù)據(jù)通信中的應(yīng)用有一個(gè)概括的了解。

所謂數(shù)據(jù)壓縮是指在保證原有信息量的前提下,對要傳輸?shù)臄?shù)據(jù)進(jìn)行歸并、整理,使其總的數(shù)據(jù)量減少的一種方法。例如,在我們要傳送的一個(gè)文件中，所有的數(shù)據(jù)符號都是小寫英文字母a～z,那么其編碼需要多少位數(shù)據(jù)呢？如果我們采用8位ASCII碼,其總的數(shù)據(jù)就為8×n(n為符號數(shù))。由于文件中所有符號只有26個(gè)小寫英文字母,是否必須采用8位編碼？能否找到一種數(shù)據(jù)量更小的編碼方式呢？針對此文件,我們完全可以采用5位二進(jìn)制編碼來表示26個(gè)字母,即我們可以用5bit編碼來代替8bit編碼,這樣既保證了文件中符號信息的傳輸,又