數(shù)據(jù)通信技術(shù)任務(wù)1.4差錯控制技術(shù)一、差錯控制方法差錯控制的兩個方向糾錯0201檢錯一、差錯控制方法差錯控制方法2、差錯控制糾正機制1、差錯控制編碼一、差錯控制方法數(shù)據(jù)信息位在向信道發(fā)送之前，先按照某種關(guān)系附加上一定的冗余位，構(gòu)成一個碼字后再發(fā)送，這個過程稱為差錯控制編碼過程一、差錯控制方法接收端收到該碼字后，檢查信息位和附加的冗余位之間的關(guān)系以此判斷傳輸過程中是否有差錯發(fā)生，這個過程稱為檢驗過程當發(fā)現(xiàn)傳輸錯誤時，通常采用差錯控制機制進行糾正一、差錯控制方法差錯控制編碼檢錯碼檢錯碼是能自動發(fā)現(xiàn)差錯的編碼接收端能夠根據(jù)接收到的檢錯碼對接收到的數(shù)據(jù)進行檢查，進而判斷傳送的數(shù)據(jù)單元是否有錯當發(fā)現(xiàn)傳輸錯誤時，通常采用差錯控制機制進行糾正一、差錯控制方法差錯控制編碼檢錯碼在糾錯機制中使用，它的生成簡單，容易實現(xiàn)，編碼和解碼的速度較快，目前被廣泛應(yīng)用于有線通信（如計算機網(wǎng)絡(luò)）中常用的檢錯碼有：奇偶校驗碼和CRC循環(huán)冗余碼等檢錯碼一、差錯控制方法差錯控制編碼糾錯碼糾錯碼是不僅能發(fā)現(xiàn)差錯，而且能自動糾正差錯的編碼在糾錯碼編碼方式中，接收端不但能發(fā)現(xiàn)差錯，而且能夠確定二進制碼元發(fā)生錯誤的位置，從而加以糾正一、差錯控制方法差錯控制編碼在使用糾錯碼糾錯時，要在發(fā)送數(shù)據(jù)中含有大量的“附加位”（又稱“非信息”位），因此，其傳輸效率較低，實現(xiàn)起來復雜，編碼和解碼的速度慢，造價高糾錯碼一般應(yīng)用于無線通信場合。例如，漢明碼就是一種糾錯碼糾錯碼一、差錯控制方法差錯控制的兩種機制1、停止等待的ARQ協(xié)議方式2、連續(xù)的ARQ協(xié)議方式一、差錯控制方法在停止等待方式中，發(fā)送方在發(fā)送完一個數(shù)據(jù)幀后，要等待接收方的應(yīng)答幀的到來停止等待的ARQ協(xié)議方式一、差錯控制方法正確的應(yīng)答幀表示上一幀數(shù)據(jù)已經(jīng)被正確接收，發(fā)送方在接收到正確的應(yīng)答幀（ACK）信號之后，就可以發(fā)送下一幀數(shù)據(jù)停止等待的ARQ協(xié)議方式一、差錯控制方法如果收到的是表示出錯的應(yīng)答幀信號（NAK）則重發(fā)出錯的數(shù)據(jù)幀停止等待的ARQ協(xié)議方式一、差錯控制方法停止等待的ARQ協(xié)議方式時間送主機送主機DATA0ACKDATA1ACKAB(a)重發(fā)出錯送主機DATA0NCKDATA0ACKAB(b)重發(fā)丟失送主機DATA0DATA0ACKAB(c)outtACK丟失重發(fā)不送主機送主機DATA0DATA1ACKAB(d)outt停止等待的ARQ工作原理圖一、差錯控制方法停止等待的ARQ協(xié)議方式時間送主機送主機DATA0ACKDATA1ACKAB(a)1、數(shù)據(jù)在傳輸過程中不出差錯的正常情況如圖（a）所示，節(jié)點B收到一個正確的數(shù)據(jù)幀后，立即交付給主機B，并向主機A發(fā)送一個確認幀ACK。當主機A收到確認幀ACK后，再發(fā)送下一個數(shù)據(jù)幀。由此實現(xiàn)了接收端對發(fā)送端的流量控制。一、差錯控制方法停止等待的ARQ協(xié)議方式2、數(shù)據(jù)在傳輸過程中出現(xiàn)差錯的情況如圖（b）所示，接收端檢驗出收到的數(shù)據(jù)幀出現(xiàn)差錯時，向主機A發(fā)送一個否認幀NCK，以表示主機A應(yīng)重發(fā)出錯的那個數(shù)據(jù)幀。主機A可多次重發(fā)，直到收到主機B發(fā)來的確認幀ACK為止。重發(fā)出錯送主機DATA0NCKDATA0ACKAB(b)一、差錯控制方法停止等待的ARQ協(xié)議方式重發(fā)丟失送主機DATA0DATA0ACKAB(c)outt數(shù)據(jù)幀丟失的情況如圖（c）所示，A站發(fā)送的0號數(shù)據(jù)幀在傳輸過程中丟失了，發(fā)生幀丟失時，節(jié)點B不向節(jié)點A發(fā)送任何應(yīng)答幀。若到了超時計時器所設(shè)置的重傳時間。A站仍收不到接收站B的確認幀，A就重傳前面所發(fā)送的數(shù)據(jù)幀。一、差錯控制方法停止等待的ARQ協(xié)議方式ACK丟失重發(fā)不送主機送主機DATA0DATA1ACKAB(d)outt應(yīng)答幀丟失的情況如圖（d）所示，由于應(yīng)答幀丟失，超時重發(fā)使主機A重發(fā)數(shù)據(jù)幀，每發(fā)送一個新的數(shù)據(jù)幀，會將其發(fā)送序號加1。若接收端收到發(fā)送序號相同的數(shù)據(jù)幀，就應(yīng)將重復幀丟掉，以保證不會出現(xiàn)重復幀差錯。一、差錯控制方法連續(xù)的ARQ協(xié)議方式1拉回方式2選擇重發(fā)方式DATA0DATA1DATA2DATA3DATA4DATA5重傳DATA2重傳DATA3重傳DATA4重傳DATA5out超時重傳ACK1確認DATA0ACK2確認DATA1DATA2出錯丟棄DATA3不按序，拒收DATA4不按序，拒收DATA5不按序，拒收ACK3確認DATA2ACK4確認DATA3t連續(xù)ARQACK1ACK2ACK2ACK2ACK2ACK3ACK4一、差錯控制方法在拉回方式中，發(fā)送方可以連續(xù)向接收方發(fā)送數(shù)據(jù)幀，接收方對接收的數(shù)據(jù)幀進行校驗，然后向發(fā)送方發(fā)回應(yīng)答幀拉回方式連續(xù)的ARQ協(xié)議方式一、差錯控制方法如果發(fā)送方連續(xù)發(fā)送了1～5號數(shù)據(jù)幀，從應(yīng)答幀中得知2號幀的數(shù)據(jù)傳輸錯誤。那么，發(fā)送方將停止當前數(shù)據(jù)幀的發(fā)送，重發(fā)2、3、4、5號數(shù)據(jù)幀。拉回狀態(tài)結(jié)束后，再接著發(fā)送6號數(shù)據(jù)幀拉回方式連續(xù)的ARQ協(xié)議方式一、差錯控制方法選擇重發(fā)方式與拉回方式的不同之處在于：如果在發(fā)送完編號為5的數(shù)據(jù)幀時，接收到編號2的數(shù)據(jù)幀傳輸出錯的應(yīng)答幀，那么，發(fā)送方在發(fā)完5號數(shù)據(jù)幀后，只重發(fā)2號數(shù)據(jù)幀。選擇重發(fā)方式連續(xù)的ARQ協(xié)議方式一、差錯控制方法選擇重發(fā)完成之后，再接著發(fā)送編號為6的數(shù)據(jù)幀。顯然，選擇重發(fā)方式的效率將高于拉回方式選擇重發(fā)方式連續(xù)的ARQ協(xié)議方式奇偶校驗碼是一種最簡單的檢錯碼其編碼規(guī)則是：首先將所要傳送的信息分組，然后在一個碼組內(nèi)的諸信息元后面附加有關(guān)校驗碼元，使得該碼組中碼元“1”的個數(shù)為奇數(shù)或偶數(shù)前者稱為奇校驗，后者稱為偶校驗二、常用的檢錯控制編碼奇偶校驗碼二、常用的檢錯控制編碼奇偶校驗碼1、垂直奇偶校驗2、水平奇偶校驗3、垂直水平奇偶校驗二、常用的檢錯控制編碼垂直奇校驗發(fā)送方110000101100001011000010傳輸信道110000101100101011011010接受方接收的編碼無差錯接收的編碼中1的個數(shù)為偶數(shù)，因此出現(xiàn)差錯接收的編碼中1的個數(shù)為奇數(shù)，因此判斷為無差錯，但實際上出現(xiàn)了差錯，因此不能檢測出偶數(shù)個差錯（a）垂直奇校驗示例實際運用中，對數(shù)據(jù)信息的分組通常是按字符進行的，即一個字符構(gòu)成一組，又稱字符奇偶校驗。以7單位代碼為例，其編碼規(guī)則是在每個字符的7位信息碼后附加一個校驗位0或1，使整個字符中二進制位1的個數(shù)為奇數(shù)二、常用的檢錯控制編碼例如，設(shè)待傳送字符的比特序列為1100001，則采用奇校驗碼后的比特序列形式為11000010。接收方在收到所傳送的比特序列后，通過檢查序列中的1的個數(shù)是否仍為奇數(shù)來判斷傳輸是否發(fā)生了錯誤垂直奇校驗發(fā)送方110000101100001011000010傳輸信道110000101100101011011010接受方接收的編碼無差錯接收的編碼中1的個數(shù)為偶數(shù)，因此出現(xiàn)差錯接收的編碼中1的個數(shù)為奇數(shù)，因此判斷為無差錯，但實際上出現(xiàn)了差錯，因此不能檢測出偶數(shù)個差錯（a）垂直奇校驗示例二、常用的檢錯控制編碼水平奇校驗前7行為對應(yīng)字母的ASCII碼，最后一行是水平奇校驗碼（粗體）字母abcdefg校驗位11000011100010110001111001001100101110011011001110011111（b）水平奇校驗示例水平奇偶校驗也稱為組校驗，是將所發(fā)送的若干個字符組成字符組或字符塊，形式上看相當于一個矩陣，每行為一個字符，每列為所有字符對應(yīng)的相同位二、常用的檢錯控制編碼水平奇校驗如圖（b）所示。在這一組字符的末尾即最后一行附加上一個校驗字符，該校驗字符中的第i位分別是對應(yīng)組中所有字符第i位的校驗位。顯然，采用水平奇偶校驗，也只能檢驗出字符塊中某一列中的1位或奇數(shù)位出錯前7行為對應(yīng)字母的ASCII碼，最后一行是水平奇校驗碼（粗體）字母abcdefg校驗位11000011100010110001111001001100101110011011001110011111（b）水平奇校驗示例二、常用的檢錯控制編碼垂直水平奇偶校驗又稱方塊校驗，即既對每個字符做垂直校驗，同時也對整個字符塊做水平校驗，則奇偶校驗碼的檢錯能力可以明顯提高垂直水平奇校驗最后一行是水平奇校驗編碼，最后一列是垂直奇校驗編碼（均為粗體）字母abcdefg校驗位1100001011000100110001111100100011001011110011011100111000111110（c）垂直水平奇校驗示例二、常用的檢錯控制編碼圖（c）所示為一個垂直水平奇校驗的例子。采用這種校驗方法，如果有兩位傳輸出錯，則不僅從每個字符中的垂直校驗位中反映出來，同時，也在水平校驗位中得到反映。因此，這種方法有較強的檢錯能力，能使誤碼率降低2～4個數(shù)量級垂直水平奇校驗最后一行是水平奇校驗編碼，最后一列是垂直奇校驗編碼（均為粗體）字母abcdefg校驗位1100001011000100110001111100100011001011110011011100111000111110（c）垂直水平奇校驗示例二、常用的檢錯控制編碼循環(huán)冗余校驗碼循環(huán)冗余校驗碼（CycleRedundancyCheck，CRC）是一種被廣泛采用的多項式編碼。CRC碼由兩部分組成，前一部分是k＋1個比特的待發(fā)送信息，后一部分是r個比特的冗余碼二、常用的檢錯控制編碼循環(huán)冗余校驗碼由于前一部分是實際要傳送的內(nèi)容，因此是固定不變的，CRC碼的產(chǎn)生關(guān)鍵在于后一部分冗余碼的計算冗余碼的計算中要用到兩個多項式：f(x)和G(x)其中，f(x)是一個k階多項式，其系數(shù)是待發(fā)送的k＋1個比特序列；G(x)是一個r階的生成多項式，由發(fā)收雙方預(yù)先約定二、常用的檢錯控制編碼CRC校驗的基本工作原理發(fā)送方發(fā)送數(shù)據(jù)多項式f(x)生成多項式G(x)rf(x)

·xG(x)＝Q(x)＋R(x)G(x)實際發(fā)送f(x)

·x＋R(x)，即數(shù)據(jù)字段＋冗余字段r接收方接收的數(shù)據(jù)f’(x)生成多項式G(x)rf’(x)

·xG(x)＝Q(x)＋R’(x)G(x)若R’(x)=R(x)，則接受正確若R’(x)≠R(x)，則接受出錯發(fā)送傳輸通道二、常用的檢錯控制編碼例如，假設(shè)實際要發(fā)送的信息序列是1010001101，收發(fā)雙方預(yù)先約定了一個5階（r＝5）的生成多項式G(x)＝x5＋x4＋x2＋1，那么可參照下面的步驟來計算相應(yīng)的CRC碼：（1）以發(fā)送的信息序列1010001101（10個比特）作為f(x)的系數(shù)，得到對應(yīng)的f(x)為9階多項式：f(x)＝1·x9＋0·x8十1·x7＋0·x6十0·x5＋0·x4＋1·x3＋1·x2十0·x十1（2）獲得xrf（x）的表達式x5f(x)＝x14＋x12＋x8＋x7＋x5，該表達式對應(yīng)的二進制序列為101000110100000，相當于信息序列向左移動r（=5）位，低位補0。二、常用的檢錯控制編碼11010101101101011010001101000001101010111011110101001110101101010011111011010100101100110101011001011010101110余數(shù)，即校檢序列（r=5位，r也是G(x)的階）。（3）計算x5f(x)/G(x)，得到r個比特的冗余序列：x5f(x)/G(x)=（101000110100000）/（110101），得余數(shù)為01110，即冗余序列。該冗余序列對應(yīng)的余式R(x)＝0·x4十x3＋x2＋x＋0·x0模2除法過程二、常用的檢錯控制編碼

（5）在接收端，對收到的序列進行校驗：對接收數(shù)據(jù)多項式用同樣的生成多項式進行同樣的求余運算若R’(x)＝R(x)則表示數(shù)據(jù)傳輸無誤，否則說明數(shù)據(jù)傳輸過程出現(xiàn)差錯（4）得到帶CRC校驗的發(fā)送序列：即將