第5章 數(shù)據(jù)鏈路層(1)

1、北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/第第5 5章章 數(shù)據(jù)鏈路層數(shù)據(jù)鏈路層數(shù)據(jù)鏈路層功能數(shù)據(jù)鏈路層功能組幀組幀差錯控制差錯控制流量控制與可靠傳輸機制流量控制與可靠傳輸機制介質(zhì)訪問控制介質(zhì)訪問控制局域網(wǎng)局域網(wǎng)廣域網(wǎng)廣域網(wǎng)數(shù)據(jù)鏈路層設(shè)備數(shù)據(jù)鏈路層設(shè)備北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/在兩臺主機通過互聯(lián)網(wǎng)通信時，從源主機在兩臺主機通過互聯(lián)網(wǎng)通信時，從源主機H1開始，經(jīng)過一系列路由器（開始，經(jīng)過一系列路由器（R1、R2、R3），到目的主機），到目的主機H2結(jié)束。結(jié)束。 從協(xié)議的層次看，主機從協(xié)議的層次看，主機H1和和H2有完整的協(xié)議層次，路由

2、器的協(xié)議棧只有下面三有完整的協(xié)議層次，路由器的協(xié)議棧只有下面三層。數(shù)據(jù)進入路由器后先從物理層上到網(wǎng)絡(luò)層，在網(wǎng)絡(luò)層的轉(zhuǎn)發(fā)表中找到下一跳層。數(shù)據(jù)進入路由器后先從物理層上到網(wǎng)絡(luò)層，在網(wǎng)絡(luò)層的轉(zhuǎn)發(fā)表中找到下一跳的地址后，再下到物理層轉(zhuǎn)發(fā)數(shù)據(jù)。的地址后，再下到物理層轉(zhuǎn)發(fā)數(shù)據(jù)。北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/只考慮數(shù)據(jù)在數(shù)據(jù)鏈路層流動只考慮數(shù)據(jù)在數(shù)據(jù)鏈路層流動 當主機當主機H1向向H2發(fā)送數(shù)據(jù)時，我們可以想象數(shù)據(jù)是在數(shù)發(fā)送數(shù)據(jù)時，我們可以想象數(shù)據(jù)是在數(shù)據(jù)鏈路層從左向右水平傳送。即通過這樣的四段鏈路：據(jù)鏈路層從左向右水平傳送。即通過這樣的四段鏈路：H1鏈路層鏈路層R1鏈路層

3、、鏈路層、R1鏈路層鏈路層R2鏈路層、鏈路層、R2鏈鏈路層路層R3鏈路層和鏈路層和R3鏈路層鏈路層H2鏈路層。鏈路層。 北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/5.1數(shù)據(jù)鏈路層功能數(shù)據(jù)鏈路層功能一些術(shù)語一些術(shù)語 結(jié)點結(jié)點把主機和路由器統(tǒng)稱為結(jié)點把主機和路由器統(tǒng)稱為結(jié)點 物理鏈路物理鏈路 沿著通信路徑連接相鄰結(jié)點的通信信道。鏈路的中間沒有任何沿著通信路徑連接相鄰結(jié)點的通信信道。鏈路的中間沒有任何其他的交換結(jié)點。兩個主機通信時，通信路徑上要經(jīng)過許多獨其他的交換結(jié)點。兩個主機通信時，通信路徑上要經(jīng)過許多獨立的鏈路。立的鏈路。 邏輯鏈路邏輯鏈路 把實現(xiàn)數(shù)據(jù)傳輸協(xié)議的硬件和軟件

4、加到鏈路上，就構(gòu)成了數(shù)據(jù)把實現(xiàn)數(shù)據(jù)傳輸協(xié)議的硬件和軟件加到鏈路上，就構(gòu)成了數(shù)據(jù)鏈路，有人將其稱為邏輯鏈路。鏈路，有人將其稱為邏輯鏈路。 網(wǎng)絡(luò)適配器就是實現(xiàn)這些協(xié)議的硬件和軟件。一般的適配器包網(wǎng)絡(luò)適配器就是實現(xiàn)這些協(xié)議的硬件和軟件。一般的適配器包含了數(shù)據(jù)鏈路層和物理層這兩層的功能。鏈路層協(xié)議交換的數(shù)含了數(shù)據(jù)鏈路層和物理層這兩層的功能。鏈路層協(xié)議交換的數(shù)據(jù)單元稱為幀。據(jù)單元稱為幀。 北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/5.1數(shù)據(jù)鏈路層功能數(shù)據(jù)鏈路層功能所有的數(shù)據(jù)鏈路層的基本功能都是將數(shù)據(jù)幀通過單條鏈路從一個結(jié)點移所有的數(shù)據(jù)鏈路層的基本功能都是將數(shù)據(jù)幀通過單條鏈路從一個

5、結(jié)點移動到相鄰結(jié)點，但具體細節(jié)依賴于該鏈路上應(yīng)用的具體數(shù)據(jù)鏈路層協(xié)議。動到相鄰結(jié)點，但具體細節(jié)依賴于該鏈路上應(yīng)用的具體數(shù)據(jù)鏈路層協(xié)議。 鏈路層協(xié)議包括如以太網(wǎng)、鏈路層協(xié)議包括如以太網(wǎng)、802.11802.11無線局域網(wǎng)、令牌環(huán)和無線局域網(wǎng)、令牌環(huán)和PPPPPP。 鏈路層的一個重要特點是在通信路徑的不同鏈路上可能由不同的鏈鏈路層的一個重要特點是在通信路徑的不同鏈路上可能由不同的鏈路層協(xié)議來處理。需要著重注意的是不同的數(shù)據(jù)鏈路層協(xié)議的提供路層協(xié)議來處理。需要著重注意的是不同的數(shù)據(jù)鏈路層協(xié)議的提供功能是不同的。功能是不同的。例如一個數(shù)據(jù)鏈路層協(xié)議可能提供可靠的交付、另一個數(shù)據(jù)鏈例如一個數(shù)據(jù)鏈路層協(xié)議

6、可能提供可靠的交付、另一個數(shù)據(jù)鏈路層協(xié)議可能不提供可靠的交付。路層協(xié)議可能不提供可靠的交付。 數(shù)據(jù)鏈路層可能提供的服務(wù)包括：組幀、差錯控制、流量控制、可靠傳數(shù)據(jù)鏈路層可能提供的服務(wù)包括：組幀、差錯控制、流量控制、可靠傳輸和介質(zhì)訪問控制。輸和介質(zhì)訪問控制。北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/5.1數(shù)據(jù)鏈路層功能數(shù)據(jù)鏈路層功能1.1.組幀組幀 在網(wǎng)絡(luò)層分組在鏈路上傳輸前，鏈路層協(xié)議用數(shù)據(jù)鏈路層的在網(wǎng)絡(luò)層分組在鏈路上傳輸前，鏈路層協(xié)議用數(shù)據(jù)鏈路層的幀將其封裝。幀將其封裝。一一個幀有數(shù)據(jù)字段和首部字段組成，網(wǎng)絡(luò)層的分組就插在數(shù)據(jù)字段個幀有數(shù)據(jù)字段和首部字段組成，網(wǎng)絡(luò)層的分

7、組就插在數(shù)據(jù)字段中。一個幀可能包含尾部字段，我們把首部字段和尾部字段合并起中。一個幀可能包含尾部字段，我們把首部字段和尾部字段合并起來稱為首部字段。接收端在收到物理層上交的比特流后，能根據(jù)首來稱為首部字段。接收端在收到物理層上交的比特流后，能根據(jù)首部字段的標記，從收到的比特流中識別幀的開始和結(jié)束。幀的結(jié)構(gòu)部字段的標記，從收到的比特流中識別幀的開始和結(jié)束。幀的結(jié)構(gòu)由數(shù)據(jù)鏈路層協(xié)議規(guī)定。由數(shù)據(jù)鏈路層協(xié)議規(guī)定。北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/5.1數(shù)據(jù)鏈路層功能數(shù)據(jù)鏈路層功能2.差錯控制差錯控制由于通信鏈路中存在信號的衰減和電磁干擾，幀中的由于通信鏈路中存在信號的衰

8、減和電磁干擾，幀中的比特在傳輸過程中可能產(chǎn)生差錯，比特在傳輸過程中可能產(chǎn)生差錯，1接收方判斷為接收方判斷為0，0接收方判斷為接收方判斷為1。轉(zhuǎn)發(fā)有差錯的數(shù)據(jù)是沒有意義的，數(shù)據(jù)鏈路層的許多轉(zhuǎn)發(fā)有差錯的數(shù)據(jù)是沒有意義的，數(shù)據(jù)鏈路層的許多協(xié)議提供檢測是否存在差錯的機制。這是通過在幀中協(xié)議提供檢測是否存在差錯的機制。這是通過在幀中設(shè)置差錯檢測冗余位，讓接收結(jié)點對收到的幀進行差設(shè)置差錯檢測冗余位，讓接收結(jié)點對收到的幀進行差錯檢測來完成的。錯檢測來完成的。差錯糾正不僅能檢測是否幀中出現(xiàn)了差錯，而且能夠差錯糾正不僅能檢測是否幀中出現(xiàn)了差錯，而且能夠判決幀中的差錯出現(xiàn)在哪里并糾正這些錯誤。一些協(xié)判決幀中的差錯

9、出現(xiàn)在哪里并糾正這些錯誤。一些協(xié)議如議如ATM只為分組的首部提供鏈路層差錯糾正。只為分組的首部提供鏈路層差錯糾正。北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/5.1數(shù)據(jù)鏈路層功能數(shù)據(jù)鏈路層功能3.流量控制流量控制由于鏈路的每一結(jié)點具有有限的幀緩存，接收結(jié)點在由于鏈路的每一結(jié)點具有有限的幀緩存，接收結(jié)點在某個時間段收到幀的速率比其處理的速度快，沒有流某個時間段收到幀的速率比其處理的速度快，沒有流量控制，接收方的緩存會溢出，幀會丟失。量控制，接收方的緩存會溢出，幀會丟失。鏈路層協(xié)議提供流量控制機制，當接收方來不及處理鏈路層協(xié)議提供流量控制機制，當接收方來不及處理發(fā)送方發(fā)送的數(shù)

10、據(jù)時，及時控制發(fā)送方發(fā)送數(shù)據(jù)的速發(fā)送方發(fā)送的數(shù)據(jù)時，及時控制發(fā)送方發(fā)送數(shù)據(jù)的速率，旨在使收發(fā)方協(xié)調(diào)一致。率，旨在使收發(fā)方協(xié)調(diào)一致。北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/5.1數(shù)據(jù)鏈路層功能數(shù)據(jù)鏈路層功能4.可靠傳輸可靠傳輸當數(shù)據(jù)鏈路層提供可靠傳輸服務(wù)時，它保證將網(wǎng)絡(luò)當數(shù)據(jù)鏈路層提供可靠傳輸服務(wù)時，它保證將網(wǎng)絡(luò)層的分組無差錯地通過數(shù)據(jù)鏈路層。層的分組無差錯地通過數(shù)據(jù)鏈路層。鏈路層可靠傳輸?shù)姆?wù)時通過確認和重傳機制來獲鏈路層可靠傳輸?shù)姆?wù)時通過確認和重傳機制來獲得的。得的。鏈路層可靠地傳輸服務(wù)常用于容易產(chǎn)生高差錯率的鏈路層可靠地傳輸服務(wù)常用于容易產(chǎn)生高差錯率的鏈路，如無

11、線鏈路。鏈路，如無線鏈路。而低差錯率的鏈路，包括光纖、雙絞線和同軸電纜，而低差錯率的鏈路，包括光纖、雙絞線和同軸電纜，鏈路層的可靠傳輸被認為是不必要的開銷。因此許鏈路層的可靠傳輸被認為是不必要的開銷。因此許多有線的鏈路層協(xié)議不提供可靠的交付。多有線的鏈路層協(xié)議不提供可靠的交付。北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/5.1數(shù)據(jù)鏈路層功能數(shù)據(jù)鏈路層功能5.介質(zhì)訪問控制介質(zhì)訪問控制介質(zhì)訪問控制協(xié)議定義了幀在鏈路上傳輸?shù)囊?guī)則。介質(zhì)訪問控制協(xié)議定義了幀在鏈路上傳輸?shù)囊?guī)則。對于在鏈路的一端有一個發(fā)送方、另一端有一個接對于在鏈路的一端有一個發(fā)送方、另一端有一個接受方的點對點鏈路，

12、介質(zhì)訪問控制協(xié)議比較簡單，受方的點對點鏈路，介質(zhì)訪問控制協(xié)議比較簡單，甚至不存在。甚至不存在。對于多個結(jié)點共享單個廣播鏈路，就是被稱為多址對于多個結(jié)點共享單個廣播鏈路，就是被稱為多址訪問的問題，介質(zhì)訪問控制協(xié)議用來協(xié)調(diào)多個結(jié)點訪問的問題，介質(zhì)訪問控制協(xié)議用來協(xié)調(diào)多個結(jié)點的幀傳輸。的幀傳輸。北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/5.2組幀組幀 封裝成幀封裝成幀(framing)就是在一段數(shù)據(jù)的前后分別添加首就是在一段數(shù)據(jù)的前后分別添加首部和尾部，然后就構(gòu)成了一個幀。確定幀的界限。部和尾部，然后就構(gòu)成了一個幀。確定幀的界限。 首部和尾部的一個重要作用就是進行首部和尾部的

13、一個重要作用就是進行幀定界幀定界。 幀結(jié)束幀首部IP 數(shù)據(jù)報幀的數(shù)據(jù)部分幀尾部 MTU數(shù)據(jù)鏈路層的幀長開始發(fā)送幀開始北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/5.2組幀組幀1.字節(jié)計數(shù)法字節(jié)計數(shù)法 這種幀同步方法以一個特殊字符表征一幀的起始，這種幀同步方法以一個特殊字符表征一幀的起始，并以一個專門字段來標明幀內(nèi)的字節(jié)數(shù)。并以一個專門字段來標明幀內(nèi)的字節(jié)數(shù)。 接受方可以通過對該特殊字符的識別從比特流中接受方可以通過對該特殊字符的識別從比特流中區(qū)分出幀的起始，并從專門字段中獲知該幀中隨區(qū)分出幀的起始，并從專門字段中獲知該幀中隨后跟隨的數(shù)據(jù)字節(jié)數(shù)，從而可確定出幀的終止位后跟隨

14、的數(shù)據(jù)字節(jié)數(shù)，從而可確定出幀的終止位置。置。北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/5.2組幀組幀 面向字節(jié)計數(shù)的同步規(guī)程的典型實例是面向字節(jié)計數(shù)的同步規(guī)程的典型實例是DEC公司的數(shù)字公司的數(shù)字數(shù)據(jù)通信報協(xié)議數(shù)據(jù)通信報協(xié)議DDCMP。 控制字符控制字符SOH標志數(shù)據(jù)幀的起始。標志數(shù)據(jù)幀的起始。 Count字段共有字段共有14位，用以指示幀中數(shù)據(jù)段中數(shù)據(jù)的位，用以指示幀中數(shù)據(jù)段中數(shù)據(jù)的字節(jié)數(shù)，數(shù)據(jù)段最大長度為字節(jié)數(shù)，數(shù)據(jù)段最大長度為8(214-1)=131064位，長位，長度必須為字節(jié)度必須為字節(jié)(即即8位位)的整倍數(shù)，的整倍數(shù)，DDCMP協(xié)議就是靠協(xié)議就是靠這個字節(jié)計

15、數(shù)來確定幀的終止位置的。這個字節(jié)計數(shù)來確定幀的終止位置的。 CRC1、CRC2分別對首部和數(shù)據(jù)部分進行雙重校驗分別對首部和數(shù)據(jù)部分進行雙重校驗 。 CRC2DataCRC1AddrSegAckFlagCountSOH16(位位)8-131064168882148北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/5.2組幀組幀2. 使用字符填充的首尾定界符法使用字符填充的首尾定界符法 該法用一些特定的字符來定界一幀的起始與終止。該法用一些特定的字符來定界一幀的起始與終止。為了不使數(shù)據(jù)信息位中出現(xiàn)的與特定字符相同的字為了不使數(shù)據(jù)信息位中出現(xiàn)的與特定字符相同的字符被誤判為幀的首尾定界

16、符，可以在這種數(shù)據(jù)字符符被誤判為幀的首尾定界符，可以在這種數(shù)據(jù)字符前填充一個轉(zhuǎn)義控制字符以示區(qū)別，從而達到數(shù)據(jù)前填充一個轉(zhuǎn)義控制字符以示區(qū)別，從而達到數(shù)據(jù)的透明性。的透明性。北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/用控制字符進行幀定界的方法舉例用控制字符進行幀定界的方法舉例 SOH裝在幀中的數(shù)據(jù)部分幀幀開始符幀結(jié)束符發(fā)送在前EOT北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/透明傳輸SOHEOT出現(xiàn)了“EOT”被接收端當作無效幀而丟棄被接收端誤認為是一個幀數(shù)據(jù)部分EOT完整的幀發(fā)送在前北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:

17、/解決透明傳輸問題 發(fā)送端的數(shù)據(jù)鏈路層在數(shù)據(jù)中出現(xiàn)控制字符發(fā)送端的數(shù)據(jù)鏈路層在數(shù)據(jù)中出現(xiàn)控制字符“SOH”或或“EOT”的前面插入一個轉(zhuǎn)義字符的前面插入一個轉(zhuǎn)義字符“ESC”(其十六進制編碼其十六進制編碼是是 1B)。 字節(jié)填充字節(jié)填充(byte stuffing)或或字符填充字符填充(character stuffing)接收端的數(shù)據(jù)鏈路層在將數(shù)據(jù)送往網(wǎng)絡(luò)層之前刪除插入的接收端的數(shù)據(jù)鏈路層在將數(shù)據(jù)送往網(wǎng)絡(luò)層之前刪除插入的轉(zhuǎn)義字符。轉(zhuǎn)義字符。 如果轉(zhuǎn)義字符也出現(xiàn)數(shù)據(jù)當中，那么應(yīng)在轉(zhuǎn)義字符前面插如果轉(zhuǎn)義字符也出現(xiàn)數(shù)據(jù)當中，那么應(yīng)在轉(zhuǎn)義字符前面插入一個轉(zhuǎn)義字符。當接收端收到連續(xù)的兩個轉(zhuǎn)義字符時，入

18、一個轉(zhuǎn)義字符。當接收端收到連續(xù)的兩個轉(zhuǎn)義字符時，就刪除其中前面的一個。就刪除其中前面的一個。 北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/SOHSOHEOTSOHESCESCEOTESCSOHESCESCESCSOH原始數(shù)據(jù)EOTEOT經(jīng)過字節(jié)填充后發(fā)送的數(shù)據(jù)字節(jié)填充字節(jié)填充字節(jié)填充字節(jié)填充發(fā)送在前幀開始符幀結(jié)束符用字節(jié)填充法解決透明傳輸?shù)膯栴} SOH北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/5.2組幀組幀3.使用比特填充的首尾定界符法使用比特填充的首尾定界符法 該法以一組特定的比特模式該法以一組特定的比特模式(如如01111110)來標志一來標志

19、一幀的起始與終止。幀的起始與終止。本節(jié)稍后要詳細介紹的本節(jié)稍后要詳細介紹的HDLC和和PPP協(xié)議就采用該協(xié)議就采用該法。為了不使信息位中出現(xiàn)的與該特定模式相似的法。為了不使信息位中出現(xiàn)的與該特定模式相似的比特串被誤判為幀的首尾標志，可以采用比特填充比特串被誤判為幀的首尾標志，可以采用比特填充的方法。的方法。 比如，采用特定模式比如，采用特定模式01111110，則對信息位中的任，則對信息位中的任何連續(xù)出現(xiàn)的何連續(xù)出現(xiàn)的5個個“1”，發(fā)送方自動在其后插入一個，發(fā)送方自動在其后插入一個“0”，而接受方則做該過程的逆操作，即每收到連，而接受方則做該過程的逆操作，即每收到連續(xù)續(xù)5個個“1”，則自動刪去

20、其后所跟的，則自動刪去其后所跟的“0”，以此恢復(fù)，以此恢復(fù)原始信息，實現(xiàn)數(shù)據(jù)傳輸?shù)耐该餍浴１忍靥畛浜苋菰夹畔?，實現(xiàn)數(shù)據(jù)傳輸?shù)耐该餍?。比特填充很容易由硬件來實現(xiàn)，性能優(yōu)于字符填充方法。易由硬件來實現(xiàn)，性能優(yōu)于字符填充方法。 北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/5.2組幀組幀4.違法編碼法違法編碼法該法在物理層采用特定的比特編碼方法時采用。該法在物理層采用特定的比特編碼方法時采用。 例如，曼徹斯特編碼方法，是將數(shù)據(jù)比特例如，曼徹斯特編碼方法，是將數(shù)據(jù)比特“1”編碼編碼成成“高高-低低”電平對，將數(shù)據(jù)比特電平對，將數(shù)據(jù)比特“0”編碼成編碼成“低低-高高”電平對。而電平

21、對。而“高高-高高”電平對和電平對和“低低-低低”電平對在數(shù)電平對在數(shù)據(jù)比特中是違法的。據(jù)比特中是違法的?？梢越栌眠@些違法編碼序列來定界幀的起始與可以借用這些違法編碼序列來定界幀的起始與終止。終止。 局域網(wǎng)局域網(wǎng)IEEE 802標準中就采用了這種方法。標準中就采用了這種方法。違法編碼法不需要任何填充技術(shù)，便能實現(xiàn)數(shù)違法編碼法不需要任何填充技術(shù)，便能實現(xiàn)數(shù)據(jù)的透明性，但它只適用采用冗余編碼的特殊據(jù)的透明性，但它只適用采用冗余編碼的特殊編碼環(huán)境。編碼環(huán)境。 北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/5.3差錯控制差錯控制信號在物理信道中傳輸時，線路本身電器特性造成的信號在物

22、理信道中傳輸時，線路本身電器特性造成的隨機噪聲、信號幅度的衰減、頻率和相位的畸變、電隨機噪聲、信號幅度的衰減、頻率和相位的畸變、電器信號在線路上產(chǎn)生反射造成的回音效應(yīng)、相鄰線路器信號在線路上產(chǎn)生反射造成的回音效應(yīng)、相鄰線路間的串擾以及各種外界因素（如大氣中的閃電、開關(guān)間的串擾以及各種外界因素（如大氣中的閃電、開關(guān)的跳火、外界強電流磁場的變化、電源的波動等）都的跳火、外界強電流磁場的變化、電源的波動等）都會造成會造成信號的失真信號的失真。在數(shù)據(jù)通信中，將會使接受端收。在數(shù)據(jù)通信中，將會使接受端收到的二進制數(shù)位和發(fā)送端實際發(fā)送的二進制數(shù)位不一到的二進制數(shù)位和發(fā)送端實際發(fā)送的二進制數(shù)位不一致，從而造

23、成由致，從而造成由“0”變成變成“1”或由或由“1”變成變成“0”的差的差錯。錯。北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/5.3 差錯控制差錯控制與語音、圖像傳輸不同，計算機通信要求極低的差與語音、圖像傳輸不同，計算機通信要求極低的差錯率。錯率。產(chǎn)生差錯的原因：產(chǎn)生差錯的原因： 信號衰減和熱噪聲信號衰減和熱噪聲 信道的電氣特性引起信號幅度、頻率、相位的信道的電氣特性引起信號幅度、頻率、相位的畸變；畸變； 信號反射，串擾；信號反射，串擾； 沖擊噪聲，閃電、大功率電機的啟停等。沖擊噪聲，閃電、大功率電機的啟停等。北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 htt

24、p:/5.3.1 5.3.1 基本概念基本概念什么是差錯？什么是差錯？q在通信中接收端收到的二進制數(shù)位（碼元）在通信中接收端收到的二進制數(shù)位（碼元）和發(fā)送端實際發(fā)送的數(shù)據(jù)不一致。和發(fā)送端實際發(fā)送的數(shù)據(jù)不一致。差錯檢測：判斷數(shù)據(jù)經(jīng)傳輸后是否有錯的手段和差錯檢測：判斷數(shù)據(jù)經(jīng)傳輸后是否有錯的手段和方法。方法。差錯控制：確保傳輸數(shù)據(jù)正確的方法和手段。差錯控制：確保傳輸數(shù)據(jù)正確的方法和手段。北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/ 在數(shù)據(jù)通信中，最常用的差錯控制方法是在數(shù)據(jù)在數(shù)據(jù)通信中，最常用的差錯控制方法是在數(shù)據(jù)中加入差錯控制編碼。中加入差錯控制編碼。我們將要發(fā)送的數(shù)據(jù)稱為信

25、息位。在向信道發(fā)送信息位我們將要發(fā)送的數(shù)據(jù)稱為信息位。在向信道發(fā)送信息位之前，先按照某種規(guī)則加上一定的冗余位（稱為差錯控之前，先按照某種規(guī)則加上一定的冗余位（稱為差錯控制編碼過程），構(gòu)成一個碼字再發(fā)送。制編碼過程），構(gòu)成一個碼字再發(fā)送。接收端收到碼字后查看信息位和冗余位，并檢查他們之接收端收到碼字后查看信息位和冗余位，并檢查他們之間的關(guān)系是否正確，即進行校驗，以確定傳輸過程中是間的關(guān)系是否正確，即進行校驗，以確定傳輸過程中是否有差錯發(fā)生。否有差錯發(fā)生。 差錯控制方法通常有差錯控制方法通常有自動請求重發(fā)自動請求重發(fā)技術(shù)、技術(shù)、 前向糾前向糾錯錯技術(shù)。技術(shù)。5.3.1 5.3.1 基本概念基本概念

26、北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/5.3.2 差錯控制方法差錯控制方法差錯控制方法：差錯控制方法：ARQARQ和和FECFECq自動請求重發(fā)自動請求重發(fā)ARQARQ：Automatic Request for Automatic Request for RepeatRepeatq接收方檢測錯誤，通知發(fā)送方重傳接收方檢測錯誤，通知發(fā)送方重傳q雙向信道，發(fā)送方緩存發(fā)送的數(shù)據(jù)雙向信道，發(fā)送方緩存發(fā)送的數(shù)據(jù)q前向糾錯前向糾錯FECFEC：Forward Error CorrectionForward Error Correctionq接收方不僅可以檢測錯誤，而且知道錯誤

27、的位置，接收方不僅可以檢測錯誤，而且知道錯誤的位置，從而改正錯誤從而改正錯誤q采用糾錯碼，無需反向信道，無需重發(fā)，但編碼采用糾錯碼，無需反向信道，無需重發(fā)，但編碼效率低效率低, ,糾錯設(shè)備復(fù)雜糾錯設(shè)備復(fù)雜北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/噪聲噪聲信源信源發(fā)送器發(fā)送器信道信道接收器接收器信宿信宿 發(fā)送端信源送出信息序列，一方面經(jīng)檢錯碼編碼器編碼由發(fā)送機送入信息，另一方面把它存入存儲器以備重傳。接收端經(jīng)檢錯碼譯碼接收端經(jīng)檢錯碼譯碼器對接收到的數(shù)據(jù)進行器對接收到的數(shù)據(jù)進行譯碼，判斷是否有錯。譯碼，判斷是否有錯。如無錯，則給出無錯信號，如無錯，則給出無錯信號，經(jīng)反饋信道

28、送至發(fā)送端，同經(jīng)反饋信道送至發(fā)送端，同時通知信宿接收譯碼后的信時通知信宿接收譯碼后的信息序列。息序列。如有錯，則給出有錯信號，如有錯，則給出有錯信號，經(jīng)反饋控制器通知信宿拒收經(jīng)反饋控制器通知信宿拒收信息，并通過反饋信道送至信息，并通過反饋信道送至發(fā)送端發(fā)送端發(fā)送端的判定信號檢發(fā)送端的判定信號檢測器檢測后，控制信測器檢測后，控制信源暫時停發(fā)新信息，源暫時停發(fā)新信息，并打開存儲器將傳輸并打開存儲器將傳輸中出錯的信息重發(fā)一中出錯的信息重發(fā)一遍遍(1)(1)自動請求重發(fā)自動請求重發(fā)ARQARQ北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/停等式停等式ARQ：發(fā)送后等待應(yīng)答，然后發(fā)送

29、下一個幀；：發(fā)送后等待應(yīng)答，然后發(fā)送下一個幀；回退回退N幀幀ARQ：接收到應(yīng)答后，從出錯的地方開始重新發(fā)：接收到應(yīng)答后，從出錯的地方開始重新發(fā)送以后的數(shù)據(jù)；送以后的數(shù)據(jù)；選擇性重傳選擇性重傳ARQ：接收到錯誤的幀的應(yīng)答時，只需要重新：接收到錯誤的幀的應(yīng)答時，只需要重新發(fā)送錯誤的幀。發(fā)送錯誤的幀。(1)(1)自動請求重發(fā)自動請求重發(fā)ARQARQ北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/(2)(2)前向糾錯技術(shù)前向糾錯技術(shù)FECFEC 前向糾錯是發(fā)送端發(fā)送能夠糾錯的數(shù)據(jù)，接收端收前向糾錯是發(fā)送端發(fā)送能夠糾錯的數(shù)據(jù)，接收端收到這些數(shù)據(jù)以后，通過錯碼譯碼器不僅能自動發(fā)現(xiàn)到這些數(shù)

30、據(jù)以后，通過錯碼譯碼器不僅能自動發(fā)現(xiàn)錯誤，并且能自動糾正傳輸中的錯誤，然后再把已錯誤，并且能自動糾正傳輸中的錯誤，然后再把已糾正的數(shù)據(jù)送給接收者。糾正的數(shù)據(jù)送給接收者。北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/ 由差錯控制的上述兩種方法引出來兩種不同的差錯由差錯控制的上述兩種方法引出來兩種不同的差錯控制編碼：控制編碼：檢錯碼檢錯碼和和糾錯碼糾錯碼。 其中，其中， 檢錯碼檢錯碼是能夠自動發(fā)現(xiàn)錯誤的編碼；是能夠自動發(fā)現(xiàn)錯誤的編碼； 糾錯碼糾錯碼是既能發(fā)現(xiàn)錯誤，又能自動糾正錯誤的編碼。是既能發(fā)現(xiàn)錯誤，又能自動糾正錯誤的編碼。 5.3.3 差錯控制編碼差錯控制編碼北京化工大學(xué)北

31、方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/常用檢錯碼：常用檢錯碼： （1）奇偶校驗）奇偶校驗（Parity Checking） 在原始數(shù)據(jù)字節(jié)的最高位增加一個奇偶校驗位，使在原始數(shù)據(jù)字節(jié)的最高位增加一個奇偶校驗位，使結(jié)果中結(jié)果中1的個數(shù)為奇數(shù)的個數(shù)為奇數(shù)(奇校驗奇校驗)或偶數(shù)或偶數(shù)(偶校驗偶校驗)。 例如例如1100010增加偶校驗位后為增加偶校驗位后為11100010 若接收方收到的字節(jié)奇偶校驗結(jié)果與規(guī)則結(jié)果不符，若接收方收到的字節(jié)奇偶校驗結(jié)果與規(guī)則結(jié)果不符，就知道傳輸中發(fā)生了錯誤。就知道傳輸中發(fā)生了錯誤。 只能用于面向字符的通信協(xié)議中。只能用于面向字符的通信協(xié)議中。5.3.3 差

32、錯控制編碼差錯控制編碼北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/實際數(shù)據(jù)傳輸中所采用的奇偶校驗碼分為：實際數(shù)據(jù)傳輸中所采用的奇偶校驗碼分為：垂直奇偶校驗垂直奇偶校驗水平奇偶校驗水平奇偶校驗水平垂直奇偶校驗水平垂直奇偶校驗5.3.3 差錯控制編碼差錯控制編碼北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/l垂直奇偶校驗垂直奇偶校驗是一字符為單是一字符為單位的校驗方法。例如，傳輸數(shù)位的校驗方法。例如，傳輸數(shù)據(jù)信息為據(jù)信息為“1010001”，采用偶，采用偶校驗時，附加位為校驗時，附加位為“1”，則發(fā)，則發(fā)送信息變?yōu)樗托畔⒆優(yōu)椤?1010001”；采；采用奇

33、校驗時，附加位為用奇校驗時，附加位為“0”，發(fā)送信息變?yōu)榘l(fā)送信息變?yōu)椤?1010001”； I11 I12 販 I1q I21 I22 販 I2q2 Ip1 Ip2 販 Ipq 販 販 販 r1 r2 販 rq 冗余位冗余位 信息位 發(fā)送順序發(fā)送順序 垂直奇偶校驗 1ppR 編碼效率：編碼效率：5.3.3 差錯控制編碼差錯控制編碼北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/ 水平奇偶校驗水平奇偶校驗是將是將若干字符組成一個若干字符組成一個信息塊，對該信息信息塊，對該信息塊的字符中對應(yīng)的塊的字符中對應(yīng)的位分別進行奇偶校位分別進行奇偶校驗，下表給出了水驗，下表給出了水平奇偶校

34、驗示例。平奇偶校驗示例。編碼效率：編碼效率：1qqR5.3.3 差錯控制編碼差錯控制編碼北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/l水平垂直奇偶校驗水平垂直奇偶校驗是是把水平和垂直兩個方向把水平和垂直兩個方向的奇偶校驗結(jié)合起來構(gòu)的奇偶校驗結(jié)合起來構(gòu)成的，即縱向每個字符成的，即縱向每個字符校驗一次，水平方向每校驗一次，水平方向每個信息塊發(fā)送完后其對個信息塊發(fā)送完后其對應(yīng)位也校驗一次（發(fā)送應(yīng)位也校驗一次（發(fā)送一個校驗碼）。一個校驗碼）。 編碼效率編碼效率) 1)(1(qppqR10001010字符字符1b1b2b3b4b5b6b7check11001011字符字符21101

35、1010字符字符310101011字符字符410001010字符字符510001010字符字符611101010字符字符700100001校驗校驗字符字符5.3.3 差錯控制編碼差錯控制編碼北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/（2）循環(huán)冗余校驗）循環(huán)冗余校驗 (CRC, Cyclic Redundancy Check) 差錯檢測原理：差錯檢測原理：將傳輸?shù)奈淮闯上禂?shù)為將傳輸?shù)奈淮闯上禂?shù)為0或或1的多項式。收發(fā)雙的多項式。收發(fā)雙方約定一個生成多項式方約定一個生成多項式G(x)，發(fā)送方在幀的末尾，發(fā)送方在幀的末尾加上加上校驗和校驗和，使帶校驗和的幀的多項式能被，使

36、帶校驗和的幀的多項式能被G(x)整除。接收方收到后，用整除。接收方收到后，用G(x)除多項式，若有余除多項式，若有余數(shù)，則傳輸有錯。數(shù)，則傳輸有錯。 校驗和是校驗和是16位或位或32位的位串。位的位串。 CRC校驗的關(guān)鍵是如何計算校驗和。校驗的關(guān)鍵是如何計算校驗和。5.3.3 差錯控制編碼差錯控制編碼北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/將要發(fā)送的二進制數(shù)序列看成是只有將要發(fā)送的二進制數(shù)序列看成是只有0 0和和1 1兩個系數(shù)的一個多兩個系數(shù)的一個多項式。項式。n n位的數(shù)據(jù)序列對應(yīng)位的數(shù)據(jù)序列對應(yīng)n-1n-1次多項式。如：二進制數(shù)序次多項式。如：二進制數(shù)序列為列為“

37、10100011010001”，7 7位的數(shù)據(jù)序列對應(yīng)位的數(shù)據(jù)序列對應(yīng)6 6次多項式：次多項式：M(x)=xM(x)=x6 6+x+x4 4+1+1 選定除式選定除式G(x)G(x)，被選作除式的多項式稱為生成多項式，以下，被選作除式的多項式稱為生成多項式，以下三個多項式已成為國際標準三個多項式已成為國際標準 CRC-12CRC-12： G(x)=xG(x)=x1212 +x +x1111 +x +x3 3 + x + x2 2 + x + 1 + x + 1 CRC-16CRC-16： G(x)=xG(x)=x1616 +x +x1515 + x + x2 2 + 1 + 1 CRC-CCI

38、TTCRC-CCITT： G(x)=xG(x)=x1616 +x +x1212 + x + x5 5 + 1 + 1 CRC-32 CRC-32 G（x）= x32+x26+x23+x22+x16+x12+x11+ x10 +x8+x7+x5+x4 + x2+x+1北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/將將M(x)M(x)乘以乘以 G(x)G(x)的最高冪次作為被除式，的最高冪次作為被除式， G(x)G(x)作多項式除作多項式除式式X Xr rM(x)=G(x)M(x)=G(x)* *商商+R(x)+R(x)（相應(yīng)系數(shù)相除）（相應(yīng)系數(shù)相除） 。除法采用。除法采用“加

39、法不進位，減法不借位加法不進位，減法不借位”的規(guī)則，即相當于異或操作的規(guī)則，即相當于異或操作R(x)R(x)作為冗余碼，加在原傳送數(shù)據(jù)后面作為冗余碼，加在原傳送數(shù)據(jù)后面: : T(x)= X T(x)= Xr rM(x) +R(x)= G(x) M(x) +R(x)= G(x) * *商商+R(x) +R(x) + R(x)R(x)，構(gòu)成發(fā)送，構(gòu)成發(fā)送序列。序列。接收方收到后，將接收序列用同樣的生成多項式去除接收方收到后，將接收序列用同樣的生成多項式去除 即即T(x)/G(x)T(x)/G(x)。若余式為零，則表示無差錯；否則，說。若余式為零，則表示無差錯；否則，說明傳輸過程中出現(xiàn)了錯誤。明傳

40、輸過程中出現(xiàn)了錯誤。01100001 1101001010110011 01100001 1101001010110011 北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/要發(fā)送的二進制數(shù)序列為要發(fā)送的二進制數(shù)序列為“10100011010001”，7 7位的數(shù)據(jù)位的數(shù)據(jù)序列對應(yīng)序列對應(yīng)6 6次多項式：次多項式： M(x)=xM(x)=x6 6+x+x4 4+1+1 選定的生成多項式為：選定的生成多項式為： G(x)=xG(x)=x4 4 +x +x2 2 +x+ 1 +x+ 1 （最高次數(shù)為（最高次數(shù)為4 4，相當于，相當于1011110111）被除多項式為：被除多項式為：

41、 M(x)xM(x)x4 4 x x1010+x+x8 8+x+x4 4 （相當于（相當于1010001101000100000000）北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/多項式除法后得到冗余碼為多項式除法后得到冗余碼為11011101，所以相應(yīng)的數(shù)據(jù)發(fā)送，所以相應(yīng)的數(shù)據(jù)發(fā)送序列為序列為1010001 11011101101000100000000101111011111011111010 0 001111110101011110111110101011110111101111011111010101111011111011101例例1.1.已知：已知：信息碼信息

42、碼MM：110011 110011 信息多項式：信息多項式：M(X)=XM(X)=X5 5+X+X4 4+X+1+X+1生成碼生成碼P P：1101 1101 生成多項式：生成多項式：P(X)=XP(X)=X3 3+X+X2 2+1 (n=3)+1 (n=3)求：冗余碼和碼字。求：冗余碼和碼字。 解：解：1 1）被除數(shù)是信息碼）被除數(shù)是信息碼M M 后添加后添加n=3n=3個個0 0，即，即110011000110011000。2 2）除數(shù)是）除數(shù)是P P即即11011101。3 3）用模）用模2 2運算。由計算結(jié)果知冗余碼是運算。由計算結(jié)果知冗余碼是001001，碼，碼字就是字就是11001

43、1001110011001。北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 .1檢錯編碼檢錯編碼接收端接收端：在在接收端把收到的數(shù)據(jù)以幀為單位進行接收端把收到的數(shù)據(jù)以幀為單位進行CRCCRC檢驗檢驗。用。用CRCCRC進行差錯檢驗的過程很簡單：接進行差錯檢驗的過程很簡單：接收方用收方用G(x)G(x)去除接收到得去除接收到得k+nk+n位比特。如果余數(shù)為位比特。如果余數(shù)為0 0，則認為正確而被收下得到信息碼；如果余數(shù)為非則認為正確而被收下得到信息碼；如果余數(shù)為非0 0，則接收方認為發(fā)生錯誤，就丟棄該幀，請求對方重則接收方認為發(fā)生錯誤，就丟棄該幀，請求對方重發(fā)。

44、發(fā)。.1檢錯編碼檢錯編碼例例2 2已知：接收碼字已知：接收碼字:1100111001:1100111001 多項式多項式:T(X)=X:T(X)=X9 9+X+X8 8+X+X5 5+X+X4 4+X+X3 3+1+1 生成碼生成碼P:P:1100111001 生成多項式生成多項式:P(X)=X:P(X)=X4 4+X+X3 3+1(n=4)+1(n=4)求：碼字的正確性。若正確，則指出冗余碼和信息碼。求：碼字的正確性。若正確，則指出冗余碼和信息碼。解：解：1)1)用碼字除以生成碼，用碼字除以生成碼，余數(shù)為余數(shù)為0 0，如圖，如圖5.65.6所示，所所示，所以碼字正確。以碼字正

45、確。 2)2)因因n=4n=4，所以冗余碼是：，所以冗余碼是：10011001，信息碼是，信息碼是:110011:110011北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/ 糾錯碼與檢錯碼相比其功能更強，它不但能檢錯糾錯碼與檢錯碼相比其功能更強，它不但能檢錯還能糾錯。還能糾錯。漢明碼漢明碼就是一種能夠糾正一位錯誤的就是一種能夠糾正一位錯誤的糾錯碼。漢明碼是海明糾錯碼。漢明碼是海明(H.W.Hamming)于于1950年年提出的一種碼制。在發(fā)送數(shù)據(jù)之前將數(shù)據(jù)按照漢提出的一種碼制。在發(fā)送數(shù)據(jù)之前將數(shù)據(jù)按照漢明碼制形成漢明碼，然后發(fā)送漢明碼，到達對方明碼制形成漢明碼，然后發(fā)送漢明

46、碼，到達對方后根據(jù)接收到的漢明碼進行解釋分析、判錯、糾后根據(jù)接收到的漢明碼進行解釋分析、判錯、糾錯。錯。(3)(3)常用糾錯碼：常用糾錯碼： 漢明碼漢明碼5.3.3 差錯控制編碼差錯控制編碼北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/漢明碼的組合規(guī)則漢明碼的組合規(guī)則 漢明碼是由數(shù)據(jù)與校驗位組合而成的。其組漢明碼是由數(shù)據(jù)與校驗位組合而成的。其組合規(guī)則為：將數(shù)據(jù)與校驗碼（奇偶校驗）自左合規(guī)則為：將數(shù)據(jù)與校驗碼（奇偶校驗）自左至右進行編碼，其中編號為至右進行編碼，其中編號為2的冪的位均為校的冪的位均為校驗位，其余為數(shù)據(jù)位。驗位，其余為數(shù)據(jù)位。 5.3.3 差錯控制編碼差錯控制編

47、碼(3)(3)常用糾錯碼：常用糾錯碼： 漢明碼漢明碼北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/(1)(1)漢明碼算法漢明碼算法將碼字數(shù)內(nèi)的位從最左邊開始按順序依次編號將碼字數(shù)內(nèi)的位從最左邊開始按順序依次編號, ,第第1 1位是位是1 1號號, ,第第2 2位是位是2 2號號, , 第第n n位是位是n n號號. .編號為編號為2 2的冪的位的冪的位(1(1號號位位,2,2號位號位,4,4號位號位,8,8號位等號位等) )是校驗位是校驗位, ,其余的位填入其余的位填入m m 位位數(shù)據(jù)。數(shù)據(jù)。每個校驗位的取值應(yīng)使得包括自己在內(nèi)的一些位的集合符每個校驗位的取值應(yīng)使得包括自己在

48、內(nèi)的一些位的集合符合規(guī)定的奇偶性合規(guī)定的奇偶性.(.(主要用于奇偶性校驗主要用于奇偶性校驗) )1 2 3 4 5 6 7 8 9 10 11 12校驗位校驗位5.3.3 差錯控制編碼差錯控制編碼北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/(1)(1)漢明碼算法漢明碼算法為了知道編號為為了知道編號為K K的數(shù)據(jù)位對哪些檢測位有影響的數(shù)據(jù)位對哪些檢測位有影響, ,將將編號編號K K 改寫成改寫成2 2的冪的和的冪的和( (如如:11=1+2+8, :11=1+2+8, 29=1+4+8+1629=1+4+8+16),1),1個位只由擴展式中所示編號的位檢個位只由擴展式中所示

49、編號的位檢測測( (編號為編號為1111的位的位, ,只能由只能由1,2,8 1,2,8 檢測位檢測檢測位檢測) )由于在每個校驗位的形成表達式中由于在每個校驗位的形成表達式中, ,除自身編號外除自身編號外, ,其余都是信息位的編號其余都是信息位的編號, ,因此只要信息位是確定的因此只要信息位是確定的, ,校驗位也可以唯一地確定校驗位也可以唯一地確定. .5.3.3 差錯控制編碼差錯控制編碼北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/例例: :根據(jù)海明編碼方法根據(jù)海明編碼方法, ,對對ASCIIASCII字符字符Z(Z(二進制編碼是二進制編碼是1011010),10110

50、10),形成形成1111位碼字位碼字, ,要求簡單地寫出編碼過程要求簡單地寫出編碼過程. .并說明在傳輸過程中并說明在傳輸過程中, ,有一位錯的情況下有一位錯的情況下, ,如何能夠檢查出是哪一位是錯的如何能夠檢查出是哪一位是錯的? ?解解: m=7,n =11,r =4 編號編號: 1=1,2=2,3=1+2,4=4,5=1+4,6=2+4,7=1+2+4,8=8,9=1+8, 10=2+8,11=1+2+8 于是有于是有: (1) (3)+(5)+(7)+(9)+(11) (2) (3)+(6)+(7)+(10)+(11) (4) (5)+(6)+(7) (8) (9)+(10)+(11)被

51、檢測位：數(shù)被檢測位：數(shù)據(jù)位據(jù)位檢測位檢測位5.3.3 差錯控制編碼差錯控制編碼北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/1 2 3 4 5 6 7 8 9 10 11 0 0 1 0 0 1 1 1 0 1 0 編碼編碼碼字碼字最終的最終的漢明碼漢明碼為什么此為什么此處是處是1?1,2,4,8是校驗位是校驗位!其余位是信息位其余位是信息位. (9)(10)(11) (1) (3)(5)(7)(9)(11) 1 0 1 0 0 1 0 1 0 0奇數(shù)個奇數(shù)個1偶數(shù)個偶數(shù)個1采用偶采用偶檢驗哦檢驗哦!5.3.3 差錯控制編碼差錯控制編碼檢驗位的定位檢驗位的定位 將將4 4個

52、四個分別編號為個四個分別編號為R R1 1, R, R2 2, R, R3 3, R, R4 4 按海明碼的編碼規(guī)則，這按海明碼的編碼規(guī)則，這4 4個冗余位應(yīng)分別插到數(shù)個冗余位應(yīng)分別插到數(shù)據(jù)單元的據(jù)單元的2 20 0, 2, 21 1, 2, 22 2, 2, 23 3位置上，即位置上，即R R 1 1, R, R2 2, R, R3 3, R, R4 4將被將被分別插入到數(shù)據(jù)單元的分別插入到數(shù)據(jù)單元的D D1 1，D D2 2，D D4 4，D D8 8的位置上。的位置上。各冗余位在各冗余位在11 11位海明碼中的位置位海明碼中的位置 1 (20) 2(21) 3 4(22) 5 6 7 8

53、(23) 9 10 11 R1R2dR3dddR4ddd各檢驗位取值的計算各檢驗位取值的計算 海明碼的每個檢驗位的值都是一組數(shù)據(jù)的奇偶校驗海明碼的每個檢驗位的值都是一組數(shù)據(jù)的奇偶校驗位。位。檢驗比特位檢驗比特位R R 1 1, R, R2 2, R, R3 3, R, R4 4分別是分別是4 4組不同數(shù)據(jù)位的奇組不同數(shù)據(jù)位的奇偶校驗位，偶校驗位，采用二進制數(shù)據(jù)來表示海明碼采用二進制數(shù)據(jù)來表示海明碼11 11個數(shù)據(jù)位數(shù)個數(shù)據(jù)位數(shù) 有有00010001；00100010；00110011；01000100；01010101；01100110；01110111；10001000；10011001；1

54、0101010，10111011這這11 11種情況種情況對這對這11 11種情況中位數(shù)最低位為種情況中位數(shù)最低位為1 1的位置進行偶校驗，的位置進行偶校驗，即對即對00010001；00110011；01010101；01110111；10011001，10111011這這6 6個數(shù)個數(shù)據(jù)位做偶校驗，得到的偶校驗碼為據(jù)位做偶校驗，得到的偶校驗碼為R R 1 1的值的值即即R R 1 1為對從低位數(shù)起的第為對從低位數(shù)起的第1 1、3 3、5 5、7 7、9 9、1111這這6 6位作偶位作偶校驗而得到的校驗位。校驗而得到的校驗位。對這對這11 11種情況中位數(shù)的次低位為種情況中位數(shù)的次低位為1

55、 1、即倒數(shù)第、即倒數(shù)第2 2位為位為1 1的位進行偶校驗，的位進行偶校驗，即對即對00100010；00110011；01100110；01110111；0101001010；10111011（第（第2 2、3 3、6 6、7 7、1010、11 11）這）這6 6個數(shù)據(jù)位做偶校驗，得到個數(shù)據(jù)位做偶校驗，得到的偶校驗校驗位的值為的偶校驗校驗位的值為R R 2 2的值的值依此類推依此類推對這對這11 11種情況中倒數(shù)第種情況中倒數(shù)第3 3位為位為1 1（01000100；01010101；01100110；01110111）的位置，即第）的位置，即第4 4、5 5、6 6、7 7這這4 4位做

56、偶位做偶校驗，得到的偶校驗碼為校驗，得到的偶校驗碼為R R 3 3的值的值R R4 4是對倒數(shù)第是對倒數(shù)第4 4位為位為1 1的位置，即第的位置，即第8 8、9 9、1010、11 11 （10001000；10011001；10101010；10111011）這）這4 4位作偶校驗得到的校驗位作偶校驗得到的校驗位的值位的值示例示例1 1：數(shù)據(jù)：數(shù)據(jù)10011011001101變成海明碼的編碼過程變成海明碼的編碼過程 1 2 3 4 5 6 7 8 9 10 111 2 3 4 5 6 7 8 9 10 11在從低位數(shù)起的第1、3、5、7、9、11這6位作偶校驗而得到的校驗位R 1是0。在從低

57、位數(shù)起的第2、3、6、7、10、11這6位作偶校驗而得到的校驗位R 2是1。在從低位數(shù)起的第4、5、6、7這4位作偶校驗而得到的校驗位R 3是1。在從低位數(shù)起的第8、9、10、11這4位作偶校驗而得到的校驗位R 4是0。由數(shù)據(jù)1001101得到的海明碼為01110010101R1R21R3001R41010R21R3001R4101011R3001R41010111001R4101011100101010001 0010 0011 0100 0101 0110 0111 1000 1001 1010 10110001 0010 0011 0100 0101 0110 0111 1000 100

58、1 1010 10110001 0010 0011 0100 0101 0110 0111 1000 1001 1010 10110001 0010 0011 0100 0101 0110 0111 1000 1001 1010 10110001 0010 0011 0100 0101 0110 0111 1000 1001 1010 10110001 0010 0011 0100 0101 0110 0111 1000 1001 1010 10110001 0010 0011 0100 0101 0110 0111 1000 1001 1010 10110001 0010 0011 0100

59、 0101 0110 0111 1000 1001 1010 1011北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/(2)(2)漢明碼檢錯與糾錯過程漢明碼檢錯與糾錯過程 將出錯計數(shù)器置為將出錯計數(shù)器置為0 0。 依次對每個校驗位進行奇偶校驗，如果有錯依次對每個校驗位進行奇偶校驗，如果有錯將校驗位所對應(yīng)的編碼值加入計數(shù)器中。直到將校驗位所對應(yīng)的編碼值加入計數(shù)器中。直到每個校驗位檢查完為止。每個校驗位檢查完為止。 如果出錯計數(shù)器值為如果出錯計數(shù)器值為0 0，則數(shù)據(jù)傳輸無錯。反，則數(shù)據(jù)傳輸無錯。反之如果計數(shù)器值不為之如果計數(shù)器值不為0 0，則數(shù)據(jù)傳輸有錯，且，則數(shù)據(jù)傳輸有錯，且出

60、錯計數(shù)器值即為出錯數(shù)據(jù)位的編碼。出錯計數(shù)器值即為出錯數(shù)據(jù)位的編碼。 將出錯數(shù)據(jù)位的數(shù)據(jù)取反即可。將出錯數(shù)據(jù)位的數(shù)據(jù)取反即可。注意注意: :漢明碼只能糾正一位錯，若多位出錯則無能為力。漢明碼只能糾正一位錯，若多位出錯則無能為力。5.3.3 差錯控制編碼差錯控制編碼北京化工大學(xué)北方學(xué)院信息院北京化工大學(xué)北方學(xué)院信息院 http:/【例例】 已知數(shù)據(jù)已知數(shù)據(jù)“11001100”在發(fā)送前，編碼后得到的漢明碼是在發(fā)送前，編碼后得到的漢明碼是“101110001100”（這里采用偶校驗），經(jīng)信道傳輸?shù)竭_接收端后，（這里采用偶校驗），經(jīng)信道傳輸?shù)竭_接收端后，設(shè)定由于噪聲干擾或其它方面的原因，數(shù)據(jù)被改為設(shè)定由