差錯(cuò)檢驗(yàn)與校正

差錯(cuò)檢驗(yàn)與校正2.4差錯(cuò)檢驗(yàn)與校正第2章數(shù)據(jù)通信基礎(chǔ)

計(jì)算機(jī)網(wǎng)絡(luò)的基本要求是高速而且無差錯(cuò)的傳輸數(shù)據(jù)信息，而通信系統(tǒng)主要由一個(gè)個(gè)物理實(shí)體組成。一個(gè)物理實(shí)體從制造、裝配等都無法達(dá)到理想的理論值，而且通信系統(tǒng)在運(yùn)作中，也會受到周圍環(huán)境的影響。因此數(shù)據(jù)在傳輸數(shù)據(jù)過程中發(fā)生差錯(cuò)是不可避免的，解決這個(gè)問題的技術(shù)稱為差錯(cuò)控制技術(shù)，即把差錯(cuò)控制在允許的范圍內(nèi)。通常差錯(cuò)控制技術(shù)包括兩個(gè)主要內(nèi)容：差錯(cuò)的檢驗(yàn)差錯(cuò)的校正1、差錯(cuò)出現(xiàn)的可能原因

數(shù)據(jù)傳輸中出現(xiàn)差錯(cuò)有多種原因，一般分為內(nèi)部因素和外部因素。

內(nèi)部因素有噪聲脈沖、脈動噪聲、衰減、延遲、失真等。機(jī)器設(shè)備本身的不理想、技術(shù)不成熟

外部因素有電磁干擾、太陽噪聲、工業(yè)噪聲等。對信號影響較大。

噪聲脈沖：通信中出現(xiàn)的離散型噪聲的統(tǒng)稱。它由時(shí)間上無規(guī)則出現(xiàn)的突發(fā)性干擾組成。

一般來說，傳輸中的差錯(cuò)都是由噪聲引起的。噪聲有兩大類：隨機(jī)熱噪聲和沖擊噪聲。隨機(jī)差錯(cuò)：隨機(jī)熱噪聲信道所固有的，持續(xù)存在的，隨機(jī)錯(cuò)通常較少。突發(fā)差錯(cuò)：沖擊噪聲由于外界特定的短暫原因所造成的沖擊噪聲，沖擊噪聲的幅度可以相當(dāng)大，它是傳輸中產(chǎn)生差錯(cuò)的重要原因。2、兩種差錯(cuò)控制技術(shù)檢錯(cuò)法糾錯(cuò)法在發(fā)送方的數(shù)據(jù)中增加一些用于檢查差錯(cuò)的附加位。用于有反饋的傳輸機(jī)制中。實(shí)現(xiàn)方法簡單，速度快。在待發(fā)送數(shù)據(jù)中增加足夠多的附加位，從而使得接收方能夠準(zhǔn)確地檢測到差錯(cuò)，并且可以自動地糾正差錯(cuò)。用于無反饋信息的傳輸機(jī)制中，如漢明碼。

3、奇偶校驗(yàn)

奇偶校驗(yàn)(ParityCheck)是一種校驗(yàn)代碼傳輸正確性的方法，是一種最簡單的檢錯(cuò)方法。根據(jù)被傳輸?shù)囊唤M二進(jìn)制代碼的數(shù)位中“1”的個(gè)數(shù)是奇數(shù)或偶數(shù)來進(jìn)行校驗(yàn)。采用何種校驗(yàn)是事先規(guī)定好的。采用奇數(shù)的稱為奇校驗(yàn)，反之，稱為偶校驗(yàn)。通常專門設(shè)置一個(gè)奇偶校驗(yàn)位，用它使這組代碼中“1”的個(gè)數(shù)為奇數(shù)或偶數(shù)。若用奇校驗(yàn)，則當(dāng)接收端收到這組代碼時(shí)，校驗(yàn)“1”的個(gè)數(shù)是否為奇數(shù)，從而確定傳輸代碼的正確性。

例如，在傳輸ASCII字符時(shí)，每個(gè)ASCII字符用7為表示，最后加上一個(gè)奇偶校驗(yàn)位總共成為8位。對于奇校驗(yàn)來說，最后加上的奇偶位校驗(yàn)使整個(gè)8位中1個(gè)數(shù)為奇數(shù)。

如發(fā)送1110001，采用奇校驗(yàn)時(shí)，奇偶位校驗(yàn)為1，即傳輸11100011。接收器檢查接收到的數(shù)據(jù)的1的個(gè)數(shù)為奇數(shù)，就認(rèn)為無錯(cuò)誤發(fā)生。若采用偶校驗(yàn)時(shí)，發(fā)送的二進(jìn)制碼是？已知字符T的ASCII碼值的十進(jìn)制表示為84，如果將最高位設(shè)置為奇校驗(yàn)位，則字符M的ASCII碼值設(shè)置奇校驗(yàn)位后，它的二進(jìn)制表示為（）

A.01001101B.11001101

C.01101011

D.10111101

解答：M的ASCII碼77，二進(jìn)制表示為01001101，里面有4個(gè)1所以奇偶校驗(yàn)取值為1，設(shè)置于最高位后就是B了。采用奇偶校驗(yàn)時(shí)，若其中2位同時(shí)發(fā)生錯(cuò)誤，則會發(fā)生沒有檢測錯(cuò)誤的情況。所以奇偶檢驗(yàn)雖然簡單，但并不是一種安全的差錯(cuò)控制方法。一般，在低速傳輸時(shí)，出錯(cuò)概率較低，效果還可以令人滿意。而當(dāng)傳輸數(shù)據(jù)速率較高或噪聲持續(xù)時(shí)間較長時(shí)，由于可能發(fā)生多位出錯(cuò)，差錯(cuò)檢驗(yàn)的結(jié)果很可能是錯(cuò)誤的。ASCII編碼

ASCII（AmericanStandardCodeforInformationInterchange，美國標(biāo)準(zhǔn)信息交換代碼）是基于拉丁字母的一套電腦編碼系統(tǒng)，它是現(xiàn)今最通用的單字節(jié)編碼系統(tǒng)。在計(jì)算機(jī)中，所有的數(shù)據(jù)在存儲和運(yùn)算時(shí)都要使用二進(jìn)制數(shù)表示（因?yàn)橛?jì)算機(jī)用高電平和低電平分別表示1和0），例如，像a、b、c、d這樣的52個(gè)字母（包括大寫）、以及0、1等數(shù)字還有一些常用的符號（例如*、#、@等）在計(jì)算機(jī)中存儲時(shí)都要使用二進(jìn)制數(shù)來表示，而具體用哪些二進(jìn)制數(shù)字表示哪個(gè)符號，當(dāng)然每個(gè)人都可以約定自己的一套（這就叫編碼），而大家如果要想互相通信而不造成混亂，那么大家就必須使用相同的編碼規(guī)則，于是美國有關(guān)的標(biāo)準(zhǔn)化組織就出臺了ASCII編碼，統(tǒng)一規(guī)定了上述常用符號用哪些二進(jìn)制數(shù)來表示。

ASCII碼使用指定的7位或8位二進(jìn)制數(shù)組合來表示128或256種可能的字符。標(biāo)準(zhǔn)ASCII碼也叫基礎(chǔ)ASCII碼，使用7位二進(jìn)制數(shù)來表示所有的大寫和小寫字母，數(shù)字0到9、標(biāo)點(diǎn)符號以及在美式英語中使用的特殊控制字符。例如，A的7位ASCII編碼為1000001。下圖為7位ASCII代碼表。d3d2d1d0位0d6d5d4位0000010100111001011101110000NULDELSP0＠P｀p0001SOHDC1！1AQaq0010STXDC2″2BRbr0011ETXDC3＃3CScs0100EOTDC4﹩4DTdt0101ENQNAK％5EUeu0110ACKSYN﹠6FVfv0111BELETB＇7GWgw1000BSCAN﹙8HXhx1001HTEM﹚9IYiy1010LFSUB﹡：JZjz1011VTESC＋﹔K［k﹛1100FFFS，＜L＼l｜1101CRGS－＝M］m｝1110SORS·＞N↑n～1111SIHS／﹖O←oDEL4、循環(huán)冗余碼校驗(yàn)

奇偶校驗(yàn)作為一種檢驗(yàn)碼雖然簡單，但是漏檢率太高。目前，在計(jì)算機(jī)網(wǎng)絡(luò)和數(shù)據(jù)通信中用得最廣泛的檢錯(cuò)碼是一種漏檢率低得多也便于實(shí)現(xiàn)的循環(huán)冗余碼CRC（CyclicRedundancyCode）。CRC是一種較復(fù)雜的校驗(yàn)方法，又稱多項(xiàng)式碼，是通過多項(xiàng)式除法檢測差錯(cuò)的方法。這種編碼對隨機(jī)差錯(cuò)和突發(fā)差錯(cuò)均能以較低的冗余度進(jìn)行嚴(yán)格的檢查，有很強(qiáng)的檢錯(cuò)能力。

CRC碼稱為多項(xiàng)式碼。這是因?yàn)槿魏我粋€(gè)由二進(jìn)制數(shù)位串組成的代碼都可以和一個(gè)只含有0和1兩個(gè)系數(shù)的多項(xiàng)式建立一一對應(yīng)的關(guān)系。x的最高冪次對應(yīng)二進(jìn)制數(shù)的最高位，以下各位對應(yīng)多項(xiàng)式的各冪次，有此冪次項(xiàng)對應(yīng)1，無此冪次項(xiàng)對應(yīng)0?？梢钥闯觯簒的最高冪次為R，轉(zhuǎn)換成對應(yīng)的二進(jìn)制數(shù)有R+1位。(因?yàn)閺膞的0次冪算起)

代碼1011011對應(yīng)的多項(xiàng)式為

x6+x4+x3+1

而多項(xiàng)式x5+x4+x2+x對應(yīng)的代碼為110110

CRC碼是由兩部分組成，前部分是信息碼，就是需要校驗(yàn)的信息，后部分是校驗(yàn)碼，如果CRC碼共長N個(gè)bit，信息碼長K個(gè)bit，就稱為(N,K)碼。對于一個(gè)給定的（N，K）碼，可以證明存在一個(gè)最高次冪為N-K=R的多項(xiàng)式G(x)，可根據(jù)其生成信息的校驗(yàn)碼，所以G(x)叫做這個(gè)CRC碼的生成多項(xiàng)式。

CRC編碼步驟：（1）給定一個(gè)生成多項(xiàng)式：G(x)=x4+x3+1,則x的最高次冪是R=4，轉(zhuǎn)換為二進(jìn)制數(shù)碼11001（有R+1=5位）（2）將原信息碼1011001(K=7bit)左移R位(K+R=N)（即后邊補(bǔ)k個(gè)0）得到F’(x)=10110010000（3）用F’(x)模2除以G(x)對應(yīng)的二進(jìn)制數(shù)碼，得余數(shù)R(x)，即為校驗(yàn)碼（4）令F’(x)+R(x)=T(x)，即將余數(shù)拼到信息碼左移后空出的位置，得到完整的CRC碼，并傳送T(x)（5）接受方用接收到的T(x)模2除以G(x)（6）察看結(jié)果為0則認(rèn)為無差錯(cuò)，否則就是有差錯(cuò)要求重傳。模2除法

模2除法與算術(shù)除法類似，但每一位除（減）的結(jié)果不影響其它位，即不向上一位借位。

多位模2除法采用模2減法，不帶借位的二進(jìn)制減法。循環(huán)冗余校驗(yàn)碼由于具有良好的代數(shù)結(jié)構(gòu)，計(jì)算機(jī)中易于實(shí)現(xiàn)，編碼器簡單，檢錯(cuò)能力強(qiáng)，故在微機(jī)通信中廣泛使用。循環(huán)冗余檢驗(yàn)碼的糾錯(cuò)能力與校驗(yàn)碼的位數(shù)有關(guān)，校驗(yàn)碼位數(shù)多，檢錯(cuò)能力就強(qiáng)。例1.CRC

屬于檢錯(cuò)碼還是糾錯(cuò)碼？如果某一數(shù)據(jù)通信系統(tǒng)采用

CRC校驗(yàn)方式，生成多項(xiàng)式G(x)為

X4

+X3+1

，目的結(jié)點(diǎn)接收到二進(jìn)制比特序列為

110111101（含CRC

校驗(yàn)碼），判斷傳輸過程中是否出現(xiàn)了錯(cuò)誤？并解釋原因。

答：屬于檢錯(cuò)碼。出現(xiàn)了差錯(cuò)，因?yàn)橛鄶?shù)為110。例2.利用標(biāo)準(zhǔn)CRC方法傳輸位流10011101，生成多項(xiàng)式為x3

+1，請給出實(shí)際被傳輸?shù)奈淮?。假設(shè)在傳輸過程中左邊第三位變反了，請證明這個(gè)錯(cuò)誤可以在接收端被檢測出來。

答：（1）模2除，得余數(shù)，即校驗(yàn)碼。（2）可以檢測出來，因?yàn)橛鄶?shù)是100.例3.如果某一數(shù)據(jù)通信系統(tǒng)采用CRC校驗(yàn)方式，生成多項(xiàng)式G(x)為X4

+X3+1，目的結(jié)點(diǎn)接收到二進(jìn)制比特序列為1101111101（含CRC校驗(yàn)碼）。請回答以下問題：（

1）該生成多項(xiàng)式對應(yīng)的二進(jìn)制比特序列是多少？（

2）如果接收到的二進(jìn)制比特序列長度正確，則發(fā)送端原始二進(jìn)制比特序列的長度是幾位？（

3）判斷傳輸過程中是否出現(xiàn)了差錯(cuò)？為什么？十進(jìn)制二進(jìn)制（35）D=(

)B用若干個(gè)2n相加方法；除2取余法35用8421編碼方法，轉(zhuǎn)換成的代碼序列：1000