差錯檢驗與校正解讀課件

1、差錯檢驗與校正2.4差錯檢驗與校正第2章 數(shù)據(jù)通信基礎(chǔ)第1頁，共23頁。 計算機網(wǎng)絡(luò)的基本要求是高速而且無差錯的傳輸數(shù)據(jù)信息，而通信系統(tǒng)主要由一個個物理實體組成。一個物理實體從制造、裝配等都無法達到理想的理論值，而且通信系統(tǒng)在運作中，也會受到周圍環(huán)境的影響。因此數(shù)據(jù)在傳輸數(shù)據(jù)過程中發(fā)生差錯是不可避免的，解決這個問題的技術(shù)稱為差錯控制技術(shù) ，即把差錯控制在允許的范圍內(nèi)。通常差錯控制技術(shù)包括兩個主要內(nèi)容：差錯的檢驗差錯的校正第2頁，共23頁。1、差錯出現(xiàn)的可能原因 數(shù)據(jù)傳輸中出現(xiàn)差錯有多種原因，一般分為內(nèi)部因素和外部因素。 內(nèi)部因素有噪聲脈沖、脈動噪聲、衰減、延遲、失真等。機器設(shè)備本身的不理想、技

2、術(shù)不成熟 外部因素有電磁干擾、太陽噪聲、工業(yè)噪聲等。對信號影響較大。 噪聲脈沖：通信中出現(xiàn)的離散型噪聲的統(tǒng)稱。它由時間上無規(guī)則出現(xiàn)的突發(fā)性干擾組成。第3頁，共23頁。 一般來說，傳輸中的差錯都是由噪聲引起的。噪聲有兩大類：隨機熱噪聲和沖擊噪聲。隨機差錯：隨機熱噪聲 信道所固有的，持續(xù)存在的，隨機錯通常 較少。 突發(fā)差錯：沖擊噪聲 由于外界特定的短暫原因所造成的沖擊噪聲，沖擊噪聲的幅度可以相當(dāng)大 ，它是傳輸中產(chǎn)生差錯的重要原因 。第4頁，共23頁。2、兩種差錯控制技術(shù)檢錯法糾錯法在發(fā)送方的數(shù)據(jù)中增加一些用于檢查差錯的附加位。用于有反饋的傳輸機制中。實現(xiàn)方法簡單，速度快。在待發(fā)送數(shù)據(jù)中增加足夠多的

3、附加位，從而使得接收方能夠準確地檢測到差錯，并且可以自動地糾正差錯。用于無反饋信息的傳輸機制中，如漢明碼。第5頁，共23頁。 3、奇偶校驗 奇偶校驗(Parity Check)是一種校驗代碼傳輸正確性的方法，是一種最簡單的檢錯方法。根據(jù)被傳輸?shù)囊唤M二進制代碼的數(shù)位中“1”的個數(shù)是奇數(shù)或偶數(shù)來進行校驗。采用何種校驗是事先規(guī)定好的。采用奇數(shù)的稱為奇校驗，反之，稱為偶校驗。通常專門設(shè)置一個奇偶校驗位，用它使這組代碼中“1”的個數(shù)為奇數(shù)或偶數(shù)。若用奇校驗，則當(dāng)接收端收到這組代碼時，校驗“1”的個數(shù)是否為奇數(shù)，從而確定傳輸代碼的正確性。 第6頁，共23頁。 例如，在傳輸ASCII字符時，每個ASCII字

4、符用7為表示，最后加上一個奇偶校驗位總共成為8位。對于奇校驗來說，最后加上的奇偶位校驗使整個8位中1個數(shù)為奇數(shù)。 如發(fā)送1110001，采用奇校驗時，奇偶位校驗為1，即傳輸11100011。接收器檢查接收到的數(shù)據(jù)的1的個數(shù)為奇數(shù)，就認為 無錯誤發(fā)生。若采用偶校驗時，發(fā)送的二進制碼是？第7頁，共23頁。已知字符T的ASCII碼值的十進制表示為84，如果將最高位設(shè)置為奇校驗位，則字符M的ASCII碼值設(shè)置奇校驗位后，它的二進制表示為（ ） A.01001101 B.11001101 C.01101011 D.10111101 解答：M的ASCII碼77，二進制表示為01001101，里面有4個1所

5、以奇偶校驗取值為1，設(shè)置于最高位后就是B了。第8頁，共23頁。采用奇偶校驗時，若其中2位同時發(fā)生錯誤，則會發(fā)生沒有檢測錯誤的情況。所以奇偶檢驗雖然簡單，但并不是一種安全的差錯控制方法。一般，在低速傳輸時，出錯概率較低，效果還可以令人滿意。而當(dāng)傳輸數(shù)據(jù)速率較高或噪聲持續(xù)時間較長時，由于可能發(fā)生多位出錯，差錯檢驗的結(jié)果很可能是錯誤的。 第9頁，共23頁。ASCII編碼 ASCII（American Standard Code for Information Interchange，美國標準信息交換代碼）是基于拉丁字母的一套電腦編碼系統(tǒng)，它是現(xiàn)今最通用的單字節(jié)編碼系統(tǒng)。 在計算機中，所有的數(shù)據(jù)在存儲

6、和運算時都要使用二進制數(shù)表示（因為計算機用高電平和低電平分別表示1和0），例如，像a、b、c、d這樣的52個字母（包括大寫）、以及0、1等數(shù)字還有一些常用的符號（例如*、#、等）在計算機中存儲時都要使用二進制數(shù)來表示，而具體用哪些二進制數(shù)字表示哪個符號，當(dāng)然每個人都可以約定自己的一套（這就叫編碼），而大家如果要想互相通信而不造成混亂，那么大家就必須使用相同的編碼規(guī)則，于是美國有關(guān)的標準化組織就出臺了ASCII編碼，統(tǒng)一規(guī)定了上述常用符號用哪些二進制數(shù)來表示。第10頁，共23頁。 ASCII 碼使用指定的7 位或8 位二進制數(shù)組合來表示128 或256 種可能的字符。標準ASCII 碼也叫基礎(chǔ)A

7、SCII碼，使用7 位二進制數(shù)來表示所有的大寫和小寫字母，數(shù)字0 到9、標點符號以及在美式英語中使用的特殊控制字符。例如，A的7位ASCII編碼為1000001。下圖為7位ASCII代碼表。第11頁，共23頁。d3 d2 d1d0位0 d6 d5d4位0000010100111001011101110000NULDELSP0Pp0001SOHDC1！1AQaq0010STXDC22BRbr0011ETXDC33CScs0100EOTDC44DTdt0101ENQNAK5EUeu0110ACKSYN6FVfv0111BELETB7GWgw1000BSCAN8HXhx1001HTEM9IYiy10

8、10LFSUB：JZjz1011VTESCKk1100FFFS，Ll1101CRGSMm1110SORSNn1111SIHSOoDEL第12頁，共23頁。4、循環(huán)冗余碼校驗 奇偶校驗作為一種檢驗碼雖然簡單，但是漏檢率太高。目前，在計算機網(wǎng)絡(luò)和數(shù)據(jù)通信中用得最廣泛的檢錯碼是一種漏檢率低得多也便于實現(xiàn)的循環(huán)冗余碼CRC（Cyclic Redundancy Code）。CRC是一種較復(fù)雜的校驗方法，又稱多項式碼，是通過多項式除法檢測差錯的方法。這種編碼對隨機差錯和突發(fā)差錯均能以較低的冗余度進行嚴格的檢查，有很強的檢錯能力。 第13頁，共23頁。 CRC碼稱為多項式碼。這是因為任何一個由二進制數(shù)位串組

9、成的代碼都可以和一個只含有0和1兩個系數(shù)的多項式建立一一對應(yīng)的關(guān)系。 x的最高冪次對應(yīng)二進制數(shù)的最高位，以下各位對應(yīng)多項式的各冪次，有此冪次項對應(yīng)1，無此冪次項對應(yīng)0。可以看出：x的最高冪次為R，轉(zhuǎn)換成對應(yīng)的二進制數(shù)有R+1位。(因為從x的0次冪算起) 代碼1011011對應(yīng)的多項式為 x6 + x4 + x3 +1 而多項式x5 + x4 + x2 + x對應(yīng)的代碼為110110 第14頁，共23頁。 CRC碼是由兩部分組成，前部分是信息碼，就是需要校驗的信息，后部分是校驗碼，如果CRC碼共長N個bit，信息碼長K個bit，就稱為(N,K)碼。對于一個給定的（N，K）碼，可以證明存在一個最高

10、次冪為N-K=R的多項式G(x)，可根據(jù)其生成信息的校驗碼，所以G(x)叫做這個CRC碼的生成多項式。 第15頁，共23頁。 CRC編碼步驟：（1）給定一個生成多項式：G(x)=x4+x3+1,則x的最高次冪是R=4，轉(zhuǎn)換為二進制數(shù)碼11001（有R+1=5位）（2）將原信息碼1011001(K=7bit)左移R位(K+R=N)（即后邊補k個0）得到F(x)=10110010000（3）用F(x)模2除以G(x)對應(yīng)的二進制數(shù)碼，得余數(shù)R(x) ，即為校驗碼（4）令F(x)+R(x)=T(x)，即將余數(shù)拼到信息碼左移后空出的位置，得到完整的CRC碼，并傳送T(x)（5）接受方用接收到的T(x)

11、模2除以G(x)（6）察看結(jié)果為0則認為無差錯，否則就是有差錯要求重傳。第16頁，共23頁。模2除法 模2除法與算術(shù)除法類似，但每一位除（減）的結(jié)果不影響其它位，即不向上一位借位。 多位模2除法采用模2減法，不帶借位的二進制減法。第17頁，共23頁。循環(huán)冗余校驗碼由于具有良好的代數(shù)結(jié)構(gòu)，計算機中易于實現(xiàn)，編碼器簡單，檢錯能力強，故在微機通信中廣泛使用。循環(huán)冗余檢驗碼的糾錯能力與校驗碼的位數(shù)有關(guān)，校驗碼位數(shù)多，檢錯能力就強。第18頁，共23頁。例1.CRC屬于檢錯碼還是糾錯碼？如果某一數(shù)據(jù)通信系統(tǒng)采用CRC校驗方式，生成多項式G(x)為X4+X3+1，目的結(jié)點接收到二進制比特序列為1101111

12、01（含CRC校驗碼），判斷傳輸過程中是否出現(xiàn)了錯誤？并解釋原因。 答：屬于檢錯碼。出現(xiàn)了差錯，因為余數(shù)為110。第19頁，共23頁。例2.利用標準CRC方法傳輸位流10011101，生成多項式為x3+1，請給出實際被傳輸?shù)奈淮?。假設(shè)在傳輸過程中左邊第三位變反了，請證明這個錯誤可以在接收端被檢測出來。 答：（1）模2除，得余數(shù)，即校驗碼。（2）可以檢測出來，因為余數(shù)是100.第20頁，共23頁。例3.如果某一數(shù)據(jù)通信系統(tǒng)采用CRC校驗方式，生成多項式G(x)為X4+X3+1，目的結(jié)點接收到二進制比特序列為1101111101（含CRC校驗碼）。請回答以下問題：（1）該生成多項式對應(yīng)的二進制比特序列是多少？（2）如果接收到的二進制比特序列長度正確，則發(fā)送端原始二進制比特序列的長度是幾位？（3）判斷傳輸過程中是否出現(xiàn)了差錯？為什么？第21頁，共23頁。十進制 二進制（35）D=( )B 用若干個2n相加方法；除2取余法35用8421編碼方法，轉(zhuǎn)換成的代碼序列：10001100110101第22頁，