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

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

2、器的協(xié)議棧只有下面三有完整的協(xié)議層次，路由器的協(xié)議棧只有下面三層。數(shù)據(jù)進(jìn)入路由器后先從物理層上到網(wǎng)絡(luò)層，在網(wǎng)絡(luò)層的轉(zhuǎn)發(fā)表中找到下一跳層。數(shù)據(jù)進(jìn)入路由器后先從物理層上到網(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ù)鏈路層流動(dòng)只考慮數(shù)據(jù)在數(shù)據(jù)鏈路層流動(dòng) 當(dāng)主機(jī)當(dāng)主機(jī)H1向向H2發(fā)送數(shù)據(jù)時(shí)，我們可以想象數(shù)據(jù)是在數(shù)發(fā)送數(shù)據(jù)時(shí)，我們可以想象數(shù)據(jù)是在數(shù)據(jù)鏈路層從左向右水平傳送。即通過(guò)這樣的四段鏈路：據(jù)鏈路層從左向右水平傳送。即通過(guò)這樣的四段鏈路：H1鏈路層鏈路層R1鏈路層

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

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

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

6、可能提供可靠的交付、另一個(gè)數(shù)據(jù)鏈路層協(xié)議可能不提供可靠的交付。路層協(xié)議可能不提供可靠的交付。 數(shù)據(jù)鏈路層可能提供的服務(wù)包括：組幀、差錯(cuò)控制、流量控制、可靠傳數(shù)據(jù)鏈路層可能提供的服務(wù)包括：組幀、差錯(cuò)控制、流量控制、可靠傳輸和介質(zhì)訪問(wèn)控制。輸和介質(zhì)訪問(wèn)控制。北京化工大學(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ù)鏈路層的幀將其封裝。幀將其封裝。一一個(gè)幀有數(shù)據(jù)字段和首部字段組成，網(wǎng)絡(luò)層的分組就插在數(shù)據(jù)字段個(gè)幀有數(shù)據(jù)字段和首部字段組成，網(wǎng)絡(luò)層的分

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

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

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

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

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

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

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

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

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

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

17、/解決透明傳輸問(wèn)題 發(fā)送端的數(shù)據(jù)鏈路層在數(shù)據(jù)中出現(xiàn)控制字符發(fā)送端的數(shù)據(jù)鏈路層在數(shù)據(jù)中出現(xiàn)控制字符“SOH”或或“EOT”的前面插入一個(gè)轉(zhuǎn)義字符的前面插入一個(gè)轉(zhuǎn)義字符“ESC”(其十六進(jìn)制編碼其十六進(jìn)制編碼是是 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ù)當(dāng)中，那么應(yīng)在轉(zhuǎn)義字符前面插如果轉(zhuǎn)義字符也出現(xiàn)數(shù)據(jù)當(dāng)中，那么應(yīng)在轉(zhuǎn)義字符前面插入一個(gè)轉(zhuǎn)義字符。當(dāng)接收端收到連續(xù)的兩個(gè)轉(zhuǎn)義字符時(shí)，入

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

37、10100011010001”，7 7位的數(shù)據(jù)序列對(duì)應(yīng)位的數(shù)據(jù)序列對(duì)應(yīng)6 6次多項(xiàng)式：次多項(xiàng)式：M(x)=xM(x)=x6 6+x+x4 4+1+1 選定除式選定除式G(x)G(x)，被選作除式的多項(xiàng)式稱(chēng)為生成多項(xiàng)式，以下，被選作除式的多項(xiàng)式稱(chēng)為生成多項(xiàng)式，以下三個(gè)多項(xiàng)式已成為國(guó)際標(biāo)準(zhǔn)三個(gè)多項(xiàng)式已成為國(guó)際標(biāo)準(zhǔn) 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)作多項(xiàng)式除作多項(xiàng)式除式式X Xr rM(x)=G(x)M(x)=G(x)* *商商+R(x)+R(x)（相應(yīng)系數(shù)相除）（相應(yīng)系數(shù)相除） 。除法采用。除法采用“加

39、法不進(jìn)位，減法不借位加法不進(jìn)位，減法不借位”的規(guī)則，即相當(dāng)于異或操作的規(guī)則，即相當(dāng)于異或操作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ā)送序列。序列。接收方收到后，將接收序列用同樣的生成多項(xiàng)式去除接收方收到后，將接收序列用同樣的生成多項(xiàng)式去除 即即T(x)/G(x)T(x)/G(x)。若余式為零，則表示無(wú)差錯(cuò)；否則，說(shuō)。若余式為零，則表示無(wú)差錯(cuò)；否則，說(shuō)明傳輸過(guò)程中出現(xiàn)了錯(cuò)誤。明傳

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

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

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

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

44、發(fā)。.1檢錯(cuò)編碼檢錯(cuò)編碼例例2 2已知：接收碼字已知：接收碼字:1100111001:1100111001 多項(xiàng)式多項(xiàng)式:T(X)=X:T(X)=X9 9+X+X8 8+X+X5 5+X+X4 4+X+X3 3+1+1 生成碼生成碼P:P:1100111001 生成多項(xiàng)式生成多項(xiàng)式: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:/ 糾錯(cuò)碼與檢錯(cuò)碼相比其功能更強(qiáng)，它不但能檢錯(cuò)糾錯(cuò)碼與檢錯(cuò)碼相比其功能更強(qiáng)，它不但能檢錯(cuò)還能糾錯(cuò)。還能糾錯(cuò)。漢明碼漢明碼就是一種能夠糾正一位錯(cuò)誤的就是一種能夠糾正一位錯(cuò)誤的糾錯(cuò)碼。漢明碼是海明糾錯(cuò)碼。漢明碼是海明(H.W.Hamming)于于1950年年提出的一種碼制。在發(fā)送數(shù)據(jù)之前將數(shù)據(jù)按照漢提出的一種碼制。在發(fā)送數(shù)據(jù)之前將數(shù)據(jù)按照漢明碼制形成漢明碼，然后發(fā)送漢明碼，到達(dá)對(duì)方明碼制形成漢明碼，然后發(fā)送漢明

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

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

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

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

50、10),形成形成1111位碼字位碼字, ,要求簡(jiǎn)單地寫(xiě)出編碼過(guò)程要求簡(jiǎn)單地寫(xiě)出編碼過(guò)程. .并說(shuō)明在傳輸過(guò)程中并說(shuō)明在傳輸過(guò)程中, ,有一位錯(cuò)的情況下有一位錯(cuò)的情況下, ,如何能夠檢查出是哪一位是錯(cuò)的如何能夠檢查出是哪一位是錯(cuò)的? ?解解: m=7,n =11,r =4 編號(hào)編號(hào): 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、檢測(cè)位：數(shù)被檢測(cè)位：數(shù)據(jù)位據(jù)位檢測(cè)位檢測(cè)位5.3.3 差錯(cuò)控制編碼差錯(cuò)控制編碼北京化工大學(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是校驗(yàn)位是校驗(yàn)位!其余位是信息位其余位是信息位. (9)(10)(11) (1) (3)(5)(7)(9)(11) 1 0 1 0 0 1 0 1 0 0奇數(shù)個(gè)奇數(shù)個(gè)1偶數(shù)個(gè)偶數(shù)個(gè)1采用偶采用偶檢驗(yàn)哦檢驗(yàn)哦!5.3.3 差錯(cuò)控制編碼差錯(cuò)控制編碼檢驗(yàn)位的定位檢驗(yàn)位的定位 將將4 4個(gè)

52、四個(gè)分別編號(hào)為個(gè)四個(gè)分別編號(hào)為R R1 1, R, R2 2, R, R3 3, R, R4 4 按海明碼的編碼規(guī)則，這按海明碼的編碼規(guī)則，這4 4個(gè)冗余位應(yīng)分別插到數(shù)個(gè)冗余位應(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各檢驗(yàn)位取值的計(jì)算各檢驗(yàn)位取值的計(jì)算 海明碼的每個(gè)檢驗(yàn)位的值都是一組數(shù)據(jù)的奇偶校驗(yàn)海明碼的每個(gè)檢驗(yàn)位的值都是一組數(shù)據(jù)的奇偶校驗(yàn)位。位。檢驗(yàn)比特位檢驗(yàn)比特位R R 1 1, R, R2 2, R, R3 3, R, R4 4分別是分別是4 4組不同數(shù)據(jù)位的奇組不同數(shù)據(jù)位的奇偶校驗(yàn)位，偶校驗(yàn)位，采用二進(jìn)制數(shù)據(jù)來(lái)表示海明碼采用二進(jìn)制數(shù)據(jù)來(lái)表示海明碼11 11個(gè)數(shù)據(jù)位數(shù)個(gè)數(shù)據(jù)位數(shù) 有有00010001；00100010；00110011；01000100；01010101；01100110；01110111；10001000；10011001；1

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

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

56、偶位做偶校驗(yàn)，得到的偶校驗(yàn)碼為校驗(yàn)，得到的偶校驗(yàn)碼為R R 3 3的值的值R R4 4是對(duì)倒數(shù)第是對(duì)倒數(shù)第4 4位為位為1 1的位置，即第的位置，即第8 8、9 9、1010、11 11 （10001000；10011001；10101010；10111011）這）這4 4位作偶校驗(yàn)得到的校驗(yàn)位作偶校驗(yàn)得到的校驗(yàn)位的值位的值示例示例1 1：數(shù)據(jù)：數(shù)據(jù)10011011001101變成海明碼的編碼過(guò)程變成海明碼的編碼過(guò)程 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位作偶校驗(yàn)而得到的校驗(yàn)位R 1是0。在從低

57、位數(shù)起的第2、3、6、7、10、11這6位作偶校驗(yàn)而得到的校驗(yàn)位R 2是1。在從低位數(shù)起的第4、5、6、7這4位作偶校驗(yàn)而得到的校驗(yàn)位R 3是1。在從低位數(shù)起的第8、9、10、11這4位作偶校驗(yàn)而得到的校驗(yàn)位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)漢明碼檢錯(cuò)與糾錯(cuò)過(guò)程漢明碼檢錯(cuò)與糾錯(cuò)過(guò)程 將出錯(cuò)計(jì)數(shù)器置為將出錯(cuò)計(jì)數(shù)器置為0 0。 依次對(duì)每個(gè)校驗(yàn)位進(jìn)行奇偶校驗(yàn)，如果有錯(cuò)依次對(duì)每個(gè)校驗(yàn)位進(jìn)行奇偶校驗(yàn)，如果有錯(cuò)將校驗(yàn)位所對(duì)應(yīng)的編碼值加入計(jì)數(shù)器中。直到將校驗(yàn)位所對(duì)應(yīng)的編碼值加入計(jì)數(shù)器中。直到每個(gè)校驗(yàn)位檢查完為止。每個(gè)校驗(yàn)位檢查完為止。 如果出錯(cuò)計(jì)數(shù)器值為如果出錯(cuò)計(jì)數(shù)器值為0 0，則數(shù)據(jù)傳輸無(wú)錯(cuò)。反，則數(shù)據(jù)傳輸無(wú)錯(cuò)。反之如果計(jì)數(shù)器值不為之如果計(jì)數(shù)器值不為0 0，則數(shù)據(jù)傳輸有錯(cuò)，且，則數(shù)據(jù)傳輸有錯(cuò)，且出

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