差錯檢驗與校正

1、差錯檢驗與校正2.42.4差錯檢驗與校正差錯檢驗與校正第第2 2章章 數據通信基礎數據通信基礎 計算機網絡的基本要求是高速而且無差錯的傳輸數據信息，而通信系統(tǒng)主要由一個個物理實體組成。一個物理實體從制造、裝配等都無法達到理想的理論值，而且通信系統(tǒng)在運作中，也會受到周圍環(huán)境的影響。因此數據在傳輸數據過程中發(fā)生差錯是不可避免的，解決這個問題的技術稱為差錯控制技術 ，即把差錯控制在允許的范圍內。通常差錯控制技術包括兩個主要內容：差錯的檢驗差錯的校正1 1、差錯出現的可能原因 數據傳輸中出現差錯有多種原因，一般分為內數據傳輸中出現差錯有多種原因，一般分為內部因素和外部因素。部因素和外部因素。 內部因素

2、有噪聲脈沖、脈動噪聲、衰減、延遲、內部因素有噪聲脈沖、脈動噪聲、衰減、延遲、失真等。機器設備本身的不理想、技術不成熟失真等。機器設備本身的不理想、技術不成熟 外部因素有電磁干擾、太陽噪聲、工業(yè)噪聲等。外部因素有電磁干擾、太陽噪聲、工業(yè)噪聲等。對信號影響較大。對信號影響較大。 噪聲脈沖噪聲脈沖：通信中出現的離散型噪聲的統(tǒng)稱。：通信中出現的離散型噪聲的統(tǒng)稱。它由時間上無規(guī)則出現的突發(fā)性干擾組成。它由時間上無規(guī)則出現的突發(fā)性干擾組成。 一般來說，傳輸中的差錯都是由噪聲引起的。噪聲有一般來說，傳輸中的差錯都是由噪聲引起的。噪聲有兩大類：隨機熱噪聲和沖擊噪聲。兩大類：隨機熱噪聲和沖擊噪聲。隨機差錯：隨機

3、熱噪聲隨機差錯：隨機熱噪聲 信道所固有的，持續(xù)存在的，隨機錯通常信道所固有的，持續(xù)存在的，隨機錯通常 較少。較少。 突發(fā)差錯：沖擊噪聲突發(fā)差錯：沖擊噪聲 由于外界特定的短暫原因所造成的沖擊噪聲，沖擊由于外界特定的短暫原因所造成的沖擊噪聲，沖擊噪聲的幅度可以相當大噪聲的幅度可以相當大 ，它是傳輸中產生差錯的重要原，它是傳輸中產生差錯的重要原因因 。2 2、兩種差錯控制技術檢錯法糾錯法在發(fā)送方的數據中增加在發(fā)送方的數據中增加一些用于檢查差錯的附一些用于檢查差錯的附加位。用于有反饋的傳加位。用于有反饋的傳輸機制中。輸機制中。實現方法簡單，速度快。實現方法簡單，速度快。在待發(fā)送數據中增加足夠在待發(fā)送數

4、據中增加足夠多的附加位，從而使得接多的附加位，從而使得接收方能夠準確地檢測到差收方能夠準確地檢測到差錯，并且可以自動地糾正錯，并且可以自動地糾正差錯。用于無反饋信息的差錯。用于無反饋信息的傳輸機制中，如漢明碼。傳輸機制中，如漢明碼。 3 3、奇偶校驗 奇偶校驗奇偶校驗(Parity Check)是一種校驗代碼傳輸正確性的方法，是一種最簡單的檢錯是一種校驗代碼傳輸正確性的方法，是一種最簡單的檢錯方法。根據被傳輸的一組二進制代碼的數位中方法。根據被傳輸的一組二進制代碼的數位中“1”的個數是奇數或偶數來進行校驗。的個數是奇數或偶數來進行校驗。采用何種校驗是事先規(guī)定好的。采用奇數的稱為奇校驗，反之，稱

5、為偶校驗。通常采用何種校驗是事先規(guī)定好的。采用奇數的稱為奇校驗，反之，稱為偶校驗。通常專門設置一個奇偶校驗位，用它使這組代碼中專門設置一個奇偶校驗位，用它使這組代碼中“1”的個數為奇數或偶數。若用奇校的個數為奇數或偶數。若用奇校驗，則當接收端收到這組代碼時，校驗驗，則當接收端收到這組代碼時，校驗“1”的個數是否為奇數，從而確定傳輸代碼的個數是否為奇數，從而確定傳輸代碼的正確性。的正確性。 例如，在傳輸例如，在傳輸ASCIIASCII字符字符時，每個時，每個ASCIIASCII字符字符用用7 7為表示，最后加上一個奇偶校驗位總共成為表示，最后加上一個奇偶校驗位總共成為為8 8位。對于奇校驗來說，

6、最后加上的奇偶位位。對于奇校驗來說，最后加上的奇偶位校驗使整個校驗使整個8 8位中位中1 1個數為奇數。個數為奇數。 如發(fā)送如發(fā)送11100011110001，采用奇校驗時，奇偶位校，采用奇校驗時，奇偶位校驗為驗為1 1，即傳輸，即傳輸1110001111100011。接收器檢查接收到。接收器檢查接收到的數據的的數據的1 1的個數為奇數，就認為的個數為奇數，就認為 無錯誤發(fā)無錯誤發(fā)生。若采用偶校驗時，發(fā)送的二進制碼是？生。若采用偶校驗時，發(fā)送的二進制碼是？已知字符T的ASCII碼值的十進制表示為84，如果將最高位設置為奇校驗位，則字符M的ASCII碼值設置奇校驗位后，它的二進制表示為（ ） A

7、.01001101 B.11001101 C.01101011 D.10111101 解 答 ： M 的 A S C I I 碼 7 7 ， 二 進 制 表 示 為01001101，里面有4個1所以奇偶校驗取值為1，設置于最高位后就是B了。采用奇偶校驗時，若其中2位同時發(fā)生錯誤，則會發(fā)生沒有檢測錯誤的情況。所以奇偶檢驗雖然簡單，但并不是一種安全的差錯控制方法。一般，在低速傳輸時，出錯概率較低，效果還可以令人滿意。而當傳輸數據速率較高或噪聲持續(xù)時間較長時，由于可能發(fā)生多位出錯，差錯檢驗的結果很可能是錯誤的。 ASCIIASCII編碼 ASCII（American Standard Code fo

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

9、述常用符號用哪些二進制數來表示。 ASCII 碼使用指定的7 位或8 位二進制數組合來表示128 或256 種可能的字符。標準ASCII 碼也叫基礎ASCII碼，使用7 位二進制數來表示所有的大寫和小寫字母，數字0 到9、標點符號以及在美式英語中使用的特殊控制字符。例如，A的7位ASCII編碼為1000001。下圖為7位ASCII代碼表。4 4、循環(huán)冗余碼校驗 奇偶校驗作為一種檢驗碼雖然簡單，但是漏檢率太高。目前，在計算機網絡和數據通信中用得最廣泛的檢錯碼是一種漏檢率低得多也便于實現的循環(huán)冗余碼CRC（Cyclic Redundancy Code）。CRC是一種較復雜的校驗方法，又稱多項式碼，

10、是通過多項式除法檢測差錯的方法。這種編碼對隨機差錯和突發(fā)差錯均能以較低的冗余度進行嚴格的檢查，有很強的檢錯能力。 CRC碼稱為多項式碼。這是因為任何一個由二進制數位串組成的代碼都可以和一個只含有0 0和1 1兩個系數的多項式建立一一對應的關系。 x x的最高冪次對應二進制數的最高位，以下各位對應多項式的各冪次，有此冪次項對應1 1，無此冪次項對應0 0?？梢钥闯觯簒 x的最高冪次為R R，轉換成對應的二進制數有R+1R+1位。( (因為從x x的0 0次冪算起) ) 代碼1011011對應的多項式為 x6 + x4 + x3 +1 而多項式x5 + x4 + x2 + x對應的代碼為11011

11、0 CRCCRC碼是由兩部分組成，前部分是信息碼，就是需要校驗的信息，后部分是校驗碼，如果CRCCRC碼共長N N個bitbit，信息碼長K K個bitbit，就稱為( (N N, ,K K) )碼。對于一個給定的（N N，K K）碼，可以證明存在一個最高次冪為N-K=RN-K=R的多項式G(x)G(x)，可根據其生成信息的校驗碼，所以G(x)G(x)叫做這個CRCCRC碼的生成多項式。 CRC編碼步驟：（1）給定一個生成多項式：G(x)=x4+x3+1,則x的最高次冪是R=4，轉換為二進制數碼11001（有R+1=5位）（2）將原信息碼1011001(K=7bit)左移R位(K+R=N)（即

12、后邊補k個0）得到F(x)=10110010000（3）用F(x)模2除以G(x)對應的二進制數碼，得余數R(x) ，即為校驗碼（4）令F(x)+R(x)=T(x)，即將余數拼到信息碼左移后空出的位置，得到完整的CRC碼，并傳送T(x)（5）接受方用接收到的T(x)模2除以G(x)（6）察看結果為0則認為無差錯，否則就是有差錯要求重傳。模2除法 模2除法與算術除法類似，但每一位除（減）的結果不影響其它位，即不向上一位借位。 多位模2除法采用模2減法，不帶借位的二進制減法。循環(huán)冗余校驗碼由于具有良好的代數結構，計算機中易于實現，編碼器簡單，檢錯能力強，故在微機通信中廣泛使用。循環(huán)冗余檢驗碼的糾錯

13、能力與校驗碼的位數有關，校驗碼位數多，檢錯能力就強。例1.CRC 屬于檢錯碼還是糾錯碼？如果某一數據通信系統(tǒng)采用 CRC校驗方式，生成多項式G(x)為 X4 +X3+1 ，目的結點接收到二進制比特序列為 110111101（含CRC 校驗碼），判斷傳輸過程中是否出現了錯誤？并解釋原因。 答：屬于檢錯碼。出現了差錯，因為余數為110。例 2 .利 用 標 準 C R C 方 法 傳 輸 位 流10011101，生成多項式為x3 +1，請給出實際被傳輸的位串。假設在傳輸過程中左邊第三位變反了，請證明這個錯誤可以在接收端被檢測出來。 答：（1）模2除，得余數，即校驗碼。（2）可以檢測出來，因為余數是

14、100.例3.如果某一數據通信系統(tǒng)采用CRC校驗方式，生成多項式G(x)為X4 +X3+1，目的結點接收到二進制比特序列為1101111101（含CRC校驗碼）。請回答以下問題：（ 1）該生成多項式對應的二進制比特序列是多少？（ 2）如果接收到的二進制比特序列長度正確，則發(fā)送端原始二進制比特序列的長度是幾位？（ 3）判斷傳輸過程中是否出現了差錯？為什么？十進制 二進制（35）D=( )B 用若干個2n相加方法；除2取余法35用8421編碼方法，轉換成的代碼序列：10001100110101數據通信中，利用編碼方法來進行差錯控制的方式，基本數據通信中，利用編碼方法來進行差錯控制的方式，基本上有兩類：上有兩類： 自動請求重發(fā)自動請求重發(fā)ARQARQ（Automatic ReQuest for repeatAutomatic Re