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

1、/31第 5 講 數(shù)據(jù)鏈路層(1)/31知識回顧l 物理層的功能物理層的功能l 數(shù)據(jù)通信模型數(shù)據(jù)通信模型l 信道復(fù)用技術(shù)信道復(fù)用技術(shù)l 數(shù)字傳輸系統(tǒng)數(shù)字傳輸系統(tǒng)l 寬帶接入技術(shù)寬帶接入技術(shù)/31本講內(nèi)容及教學(xué)目標(biāo)l 理解數(shù)據(jù)鏈路層的功能。理解數(shù)據(jù)鏈路層的功能。l 掌握幀、鏈路等相關(guān)概念。掌握幀、鏈路等相關(guān)概念。l 掌握幀定界的方法。掌握幀定界的方法。l 理解數(shù)據(jù)鏈路層的三個基本問題。理解數(shù)據(jù)鏈路層的三個基本問題。l 掌握差錯檢測掌握差錯檢測CRC的計(jì)算方法。的計(jì)算方法。l 理解透明傳輸問題。理解透明傳輸問題。/31數(shù)據(jù)鏈路層的服務(wù)l 數(shù)據(jù)鏈路層數(shù)據(jù)鏈路層最基本的服務(wù)是將源計(jì)算機(jī)網(wǎng)絡(luò)層來的數(shù)據(jù)可

2、最基本的服務(wù)是將源計(jì)算機(jī)網(wǎng)絡(luò)層來的數(shù)據(jù)可靠的傳輸靠的傳輸?shù)较噜徆?jié)點(diǎn)的目標(biāo)計(jì)算機(jī)的網(wǎng)絡(luò)層。它為網(wǎng)絡(luò)層到相鄰節(jié)點(diǎn)的目標(biāo)計(jì)算機(jī)的網(wǎng)絡(luò)層。它為網(wǎng)絡(luò)層提供以下服務(wù)：提供以下服務(wù)：l 無確認(rèn)、無連接的服務(wù)無確認(rèn)、無連接的服務(wù) 源端可以不需要建立連接就向目的端發(fā)送獨(dú)立的數(shù)據(jù)幀，而目的端也不需要對收到的幀進(jìn)行確認(rèn)。以太網(wǎng)采用此服務(wù)。l 有確認(rèn)、無連接的服務(wù)有確認(rèn)、無連接的服務(wù) 源端可以不需要建立連接就向目的端發(fā)送獨(dú)立的數(shù)據(jù)幀，但目的端需要對收到的幀進(jìn)行確認(rèn)。l 面向連接的服務(wù)面向連接的服務(wù) 源端與目的端在通信前要先建立連接，然后在此連接上互相傳輸數(shù)據(jù)幀，每一個幀都被編號，數(shù)據(jù)鏈路層保證傳送的幀被對方收到，且只

3、收到一次，雙方通信完畢后拆除連接。電話網(wǎng)絡(luò)采用。/31數(shù)據(jù)鏈路層的主要功能l 為達(dá)到上述目的，數(shù)據(jù)鏈路層必須具備一系列相應(yīng)的功能，主要為達(dá)到上述目的，數(shù)據(jù)鏈路層必須具備一系列相應(yīng)的功能，主要有：如何將數(shù)據(jù)有：如何將數(shù)據(jù)組合成數(shù)據(jù)組合成數(shù)據(jù)塊；如何控制幀在物理信道上的傳輸，塊；如何控制幀在物理信道上的傳輸，包括如何包括如何處理傳輸差錯處理傳輸差錯，如何調(diào)節(jié)發(fā)送速率以使之與接收方相匹，如何調(diào)節(jié)發(fā)送速率以使之與接收方相匹配；在兩個網(wǎng)路實(shí)體之間提供數(shù)據(jù)鏈路通路的配；在兩個網(wǎng)路實(shí)體之間提供數(shù)據(jù)鏈路通路的建立、維持和釋放建立、維持和釋放管理管理。 具體如下：具體如下：l 鏈路管理鏈路管理l 幀定界幀定界l

4、 流量控制流量控制l 差錯控制差錯控制l 將數(shù)據(jù)和控制信息區(qū)分開將數(shù)據(jù)和控制信息區(qū)分開l 透明傳輸透明傳輸l 尋址尋址/31 數(shù)據(jù)鏈路層的基本概念 l 在數(shù)據(jù)鏈路層中將這種在數(shù)據(jù)鏈路層中將這種數(shù)據(jù)塊稱為幀數(shù)據(jù)塊稱為幀，幀是數(shù)據(jù)鏈路層的，幀是數(shù)據(jù)鏈路層的傳送單位。傳送單位。l 鏈路鏈路(link)是一條無源的點(diǎn)到點(diǎn)的物理線路段，中間沒有任是一條無源的點(diǎn)到點(diǎn)的物理線路段，中間沒有任何其他的交換結(jié)點(diǎn)。何其他的交換結(jié)點(diǎn)。 一條鏈路只是一條通路的一個組成部分。l 數(shù)據(jù)鏈路數(shù)據(jù)鏈路(data link) 除了物理線路外，還必須有通信協(xié)議來除了物理線路外，還必須有通信協(xié)議來控制這些數(shù)據(jù)的傳輸。若把實(shí)現(xiàn)這些協(xié)

5、議的硬件和軟件加控制這些數(shù)據(jù)的傳輸。若把實(shí)現(xiàn)這些協(xié)議的硬件和軟件加到鏈路上，就構(gòu)成了到鏈路上，就構(gòu)成了數(shù)據(jù)鏈路數(shù)據(jù)鏈路。 現(xiàn)在最常用的方法是使用適配器（即網(wǎng)卡）來實(shí)現(xiàn)這些協(xié)議的硬件和軟件。 一般的適配器都包括了數(shù)據(jù)鏈路層和物理層這兩層的功能。 /31Functions of the Data Link Layer (2)Relationship between packets and frames./31Services Provided to Network Layer(a) Virtual communication.(b) Actual communication./31數(shù)據(jù)鏈路層數(shù)據(jù)鏈

6、路層使用的信道主要有以下兩種類型：數(shù)據(jù)鏈路層使用的信道主要有以下兩種類型：l 點(diǎn)對點(diǎn)信道點(diǎn)對點(diǎn)信道。這種信道使用一對一的點(diǎn)對點(diǎn)通信方。這種信道使用一對一的點(diǎn)對點(diǎn)通信方式。式。l 廣播信道廣播信道。這種信道使用一對多的廣播通信方式，。這種信道使用一對多的廣播通信方式，因此過程比較復(fù)雜。廣播信道上連接的主機(jī)很多，因此過程比較復(fù)雜。廣播信道上連接的主機(jī)很多，因此必須使用專用的共享信道協(xié)議來協(xié)調(diào)這些主機(jī)因此必須使用專用的共享信道協(xié)議來協(xié)調(diào)這些主機(jī)的數(shù)據(jù)發(fā)的數(shù)據(jù)發(fā) /31數(shù)據(jù)鏈路層的簡單模型局域網(wǎng)廣域網(wǎng)主機(jī) H1主機(jī) H2路由器 R1路由器 R2路由器 R3電話網(wǎng)局域網(wǎng)主機(jī) H1 向 H2 發(fā)送數(shù)據(jù)鏈路

7、層應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層物理層鏈路層應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層R1R2R3H1H2從層次上來看數(shù)據(jù)的流動/31數(shù)據(jù)鏈路層的簡單模型cont.局域網(wǎng)廣域網(wǎng)主機(jī) H1主機(jī) H2路由器 R1路由器 R2路由器 R3電話網(wǎng)局域網(wǎng)主機(jī) H1 向 H2 發(fā)送數(shù)據(jù)鏈路層應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層物理層鏈路層應(yīng)用層運(yùn)輸層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層鏈路層網(wǎng)絡(luò)層物理層R1R2R3H1H2僅從數(shù)據(jù)鏈路層觀察幀的流動/31數(shù)據(jù)鏈路層l 數(shù)據(jù)鏈路層像個數(shù)字管道。數(shù)據(jù)鏈路層像個數(shù)字管道。l 常常在兩個對等的數(shù)據(jù)鏈路層之間畫出一個數(shù)字管常常在兩個對等的數(shù)據(jù)鏈路層

8、之間畫出一個數(shù)字管道，而在這條數(shù)字管道上傳輸?shù)臄?shù)據(jù)單位是幀。道，而在這條數(shù)字管道上傳輸?shù)臄?shù)據(jù)單位是幀。l 早期的數(shù)據(jù)通信協(xié)議曾叫作通信規(guī)程早期的數(shù)據(jù)通信協(xié)議曾叫作通信規(guī)程(procedure)。因此在數(shù)據(jù)鏈路層，規(guī)程和協(xié)議是同義語。因此在數(shù)據(jù)鏈路層，規(guī)程和協(xié)議是同義語。 結(jié)點(diǎn)結(jié)點(diǎn)幀幀/31成幀（幀同步）l 為了向網(wǎng)絡(luò)層提供服務(wù)，數(shù)據(jù)鏈路層必須使用物理層提供為了向網(wǎng)絡(luò)層提供服務(wù)，數(shù)據(jù)鏈路層必須使用物理層提供的服務(wù)。的服務(wù)。l 物理層物理層, 是以比特流進(jìn)行傳輸?shù)氖且员忍亓鬟M(jìn)行傳輸?shù)?，這種比特流并不保證在數(shù)，這種比特流并不保證在數(shù)據(jù)傳輸過程中沒有錯誤，接收到的位數(shù)量可能少于、等于據(jù)傳輸過程中沒有錯

9、誤，接收到的位數(shù)量可能少于、等于或者多于發(fā)送的位數(shù)量。而且它們還可能有不同的值，這或者多于發(fā)送的位數(shù)量。而且它們還可能有不同的值，這時數(shù)據(jù)鏈路層為了時數(shù)據(jù)鏈路層為了能實(shí)現(xiàn)數(shù)據(jù)有效的差錯控制，就采用了能實(shí)現(xiàn)數(shù)據(jù)有效的差錯控制，就采用了一種一種“幀幀”的數(shù)據(jù)塊進(jìn)行傳輸。的數(shù)據(jù)塊進(jìn)行傳輸。分段傳輸分段傳輸。l 采用采用幀格式傳輸，就必須有相應(yīng)的幀同步技術(shù)幀格式傳輸，就必須有相應(yīng)的幀同步技術(shù)，這就是數(shù)，這就是數(shù)據(jù)鏈路層的據(jù)鏈路層的“成幀成幀”（也稱為（也稱為“幀同步幀同步”）功能。）功能。/31成幀（幀同步）（續(xù)）l 采用幀傳輸方式的好處是采用幀傳輸方式的好處是 在發(fā)現(xiàn)有數(shù)據(jù)傳送錯誤時，只需將有差錯的

10、幀再次傳送，而不需要將全部數(shù)據(jù)的比特流進(jìn)行重傳，這就在傳送效率上將大大提高。 但同時也帶來了兩方面的問題：（1）如何識別幀的開始與結(jié)束；（2）在夾雜著重傳的數(shù)據(jù)幀中，接收方在接收到重傳的數(shù)據(jù)幀時是識別成新的數(shù)據(jù)幀，還是識別成已傳幀的重傳幀呢？這就要靠數(shù)據(jù)鏈路層的各種“幀同步”技術(shù)來識別了。l “幀同步幀同步”技術(shù)既可使接收方能從以上并不是完全技術(shù)既可使接收方能從以上并不是完全有序的比特流中準(zhǔn)確地區(qū)分出每一幀的開始和結(jié)束，有序的比特流中準(zhǔn)確地區(qū)分出每一幀的開始和結(jié)束，同時還可識別重傳幀。同時還可識別重傳幀。/31IP 數(shù)據(jù)報(bào)1010 0110幀取出數(shù)據(jù)鏈路層網(wǎng)絡(luò)層鏈路結(jié)點(diǎn) A結(jié)點(diǎn) B物理層數(shù)據(jù)鏈

11、路層結(jié)點(diǎn) A結(jié)點(diǎn) B幀(a)(b)發(fā)送幀接收鏈路IP 數(shù)據(jù)報(bào)1010 0110幀裝入數(shù)據(jù)鏈路層傳送的是幀/31封裝成幀l 封裝成幀封裝成幀(framing)就是在就是在一段數(shù)據(jù)的前后分別添加首部和一段數(shù)據(jù)的前后分別添加首部和尾部，然后就構(gòu)成了一個幀尾部，然后就構(gòu)成了一個幀。確定幀的界限。確定幀的界限。l 首部和尾部的一個重要作用就是進(jìn)行首部和尾部的一個重要作用就是進(jìn)行幀定界幀定界。 幀結(jié)束幀首部IP 數(shù)據(jù)報(bào)幀的數(shù)據(jù)部分幀尾部 MTU數(shù)據(jù)鏈路層的幀長開始發(fā)送幀開始/31用控制字符進(jìn)行幀定界的方法舉例 SOH裝在幀中的數(shù)據(jù)部分幀幀開始符幀結(jié)束符發(fā)送在前EOT/31透明傳輸方法SOHEOT出現(xiàn)了“E

12、OT”被接收端當(dāng)作無效幀而丟棄被接收端誤認(rèn)為是一個幀數(shù)據(jù)部分EOT完整的幀發(fā)送在前/31解決透明傳輸問題l 發(fā)送端的數(shù)據(jù)鏈路層在數(shù)據(jù)中出現(xiàn)發(fā)送端的數(shù)據(jù)鏈路層在數(shù)據(jù)中出現(xiàn)控制字符控制字符“SOH”或或“EOT”的的前面插入一個轉(zhuǎn)義字符前面插入一個轉(zhuǎn)義字符“ESC”(其十六進(jìn)制編碼是其十六進(jìn)制編碼是 1B)。l 字節(jié)填充字節(jié)填充(byte stuffing)或或字符填充字符填充(character stuffing)接收端接收端的數(shù)據(jù)鏈路層在將數(shù)據(jù)送往網(wǎng)絡(luò)層之前刪除插入的轉(zhuǎn)義字符。的數(shù)據(jù)鏈路層在將數(shù)據(jù)送往網(wǎng)絡(luò)層之前刪除插入的轉(zhuǎn)義字符。l 如果轉(zhuǎn)義字符也出現(xiàn)在數(shù)據(jù)當(dāng)中，那么應(yīng)在轉(zhuǎn)義字符前面插入一個如

13、果轉(zhuǎn)義字符也出現(xiàn)在數(shù)據(jù)當(dāng)中，那么應(yīng)在轉(zhuǎn)義字符前面插入一個轉(zhuǎn)義字符。當(dāng)接收端收到連續(xù)的兩個轉(zhuǎn)義字符時，就刪除其中前面轉(zhuǎn)義字符。當(dāng)接收端收到連續(xù)的兩個轉(zhuǎn)義字符時，就刪除其中前面的一個。的一個。 l “透明傳輸透明傳輸”是指可以讓是指可以讓無論是哪種比特組合的數(shù)據(jù)，都可以在數(shù)無論是哪種比特組合的數(shù)據(jù)，都可以在數(shù)據(jù)鏈路上進(jìn)行有效傳輸據(jù)鏈路上進(jìn)行有效傳輸。這就需要在所傳數(shù)據(jù)中的比特組合恰巧與。這就需要在所傳數(shù)據(jù)中的比特組合恰巧與某一個控制信息完全一樣時，能采取相應(yīng)的技術(shù)措施，使接收方不某一個控制信息完全一樣時，能采取相應(yīng)的技術(shù)措施，使接收方不會將這樣的數(shù)據(jù)誤認(rèn)為是某種控制信息。以保證數(shù)據(jù)鏈路層的傳輸會將

14、這樣的數(shù)據(jù)誤認(rèn)為是某種控制信息。以保證數(shù)據(jù)鏈路層的傳輸是透明的。是透明的。/31SOHSOHEOTSOHESCESCEOTESCSOHESCESCESCSOH原始數(shù)據(jù)EOTEOT經(jīng)過字節(jié)填充后發(fā)送的數(shù)據(jù)字節(jié)填充字節(jié)填充字節(jié)填充字節(jié)填充發(fā)送在前幀開始符幀結(jié)束符用字節(jié)填充法解決透明傳輸?shù)膯栴} SOH/31差錯檢測l 在傳輸過程中可能會產(chǎn)生在傳輸過程中可能會產(chǎn)生比特差錯比特差錯：1 可能會變成可能會變成 0 而而 0 也可也可能變成能變成 1。l 在一段時間內(nèi)，傳輸錯誤的比特占所傳輸比特總數(shù)的比率稱為在一段時間內(nèi)，傳輸錯誤的比特占所傳輸比特總數(shù)的比率稱為誤碼率誤碼率 BER (Bit Error R

15、ate)。l 誤碼率與信噪比有很大的關(guān)系。誤碼率與信噪比有很大的關(guān)系。l 為了保證數(shù)據(jù)傳輸?shù)目煽啃?，在?jì)算機(jī)網(wǎng)絡(luò)傳輸數(shù)據(jù)時，必須為了保證數(shù)據(jù)傳輸?shù)目煽啃?，在?jì)算機(jī)網(wǎng)絡(luò)傳輸數(shù)據(jù)時，必須采用各種差錯檢測措施采用各種差錯檢測措施。 l 在數(shù)據(jù)通信過程可能會因物理鏈路性能和網(wǎng)絡(luò)通信環(huán)境等因素，在數(shù)據(jù)通信過程可能會因物理鏈路性能和網(wǎng)絡(luò)通信環(huán)境等因素，難免會出現(xiàn)一些傳送錯誤，但為了確保數(shù)據(jù)通信的準(zhǔn)確，又必難免會出現(xiàn)一些傳送錯誤，但為了確保數(shù)據(jù)通信的準(zhǔn)確，又必須須使得這些錯誤發(fā)生的機(jī)率盡可能使得這些錯誤發(fā)生的機(jī)率盡可能低。這一功能也是在數(shù)據(jù)鏈低。這一功能也是在數(shù)據(jù)鏈路層實(shí)現(xiàn)的，就是它的路層實(shí)現(xiàn)的，就是它的“

16、差錯控制差錯控制”功能。功能。/31差錯檢測與校正l 信號在任何信道上傳輸都存在著傳輸差錯，這些差錯由多信號在任何信道上傳輸都存在著傳輸差錯，這些差錯由多種物理現(xiàn)象引起，解決差錯問題的方法有種物理現(xiàn)象引起，解決差錯問題的方法有兩種兩種： 一種是在要發(fā)送的數(shù)據(jù)中加入一定的冗余位，使接收方能知道數(shù)據(jù)是否出錯，但不知道是哪里出錯，這種編碼方法叫差錯檢測碼，或簡稱檢錯碼。如CRC 另一種是在要發(fā)送的數(shù)據(jù)中加入足夠多的冗余位，使接收方能糾正出錯的位，這種編碼方法叫差錯校正碼，或簡稱糾錯碼。如海明碼。/31糾錯碼海明碼l 定義：一幀由定義：一幀由m個數(shù)據(jù)位（即報(bào)文）和個數(shù)據(jù)位（即報(bào)文）和r個冗余位（即校驗(yàn)

17、位）組成，設(shè)個冗余位（即校驗(yàn)位）組成，設(shè)總長度為總長度為n（n=m+r)，此長度為，此長度為n的單元常稱為的單元常稱為n位碼字。位碼字。l 定義：兩個碼字不同的位的數(shù)目稱為定義：兩個碼字不同的位的數(shù)目稱為海明距離海明距離 例如，10001001 與10110001它們的海明距離為3。l 對于對于n位碼字的集合，只有位碼字的集合，只有2m個碼字是有效的，在任意兩個有效碼字間個碼字是有效的，在任意兩個有效碼字間找出具有最小海明距離的兩個碼字，該海明距離便定義為全部碼字的海找出具有最小海明距離的兩個碼字，該海明距離便定義為全部碼字的海明距離。明距離。l 一種編碼的檢錯和糾錯能力取決于編碼后碼字的海明

18、距離的大小。一種編碼的檢錯和糾錯能力取決于編碼后碼字的海明距離的大小。 為了檢測出d個比特的錯，需要使用距離為d+1的編碼。 例如：數(shù)據(jù)后加奇偶校驗(yàn)位，編碼后的海明距離為2，能檢測1比特錯。l 為了糾正為了糾正d d個比特的錯，必須用距離為個比特的錯，必須用距離為2d+12d+1的編碼。的編碼。 例如有4個有效碼字：它們是0000000000，0000011111，1111100000，1111111111，海明距離為5，能糾正2比特錯。/31糾正單比特錯的校驗(yàn)位下界l 設(shè)計(jì)一種編碼，它有設(shè)計(jì)一種編碼，它有m個信息位和個信息位和r個校驗(yàn)位，當(dāng)個校驗(yàn)位，當(dāng)r滿足什么滿足什么條件時，能糾正所有單比

19、特錯？條件時，能糾正所有單比特錯？ 對對2m個有效碼字的任何一個而言，有個有效碼字的任何一個而言，有n個與該碼字距離為個與該碼字距離為1的無效碼字，的無效碼字，所以所以2m個有效碼字每一個都對應(yīng)有個有效碼字每一個都對應(yīng)有n+1個各不相同的位圖，個各不相同的位圖，n位碼字的位碼字的總的位圖是總的位圖是2n個。個。（n+1）2m=2n，n=m+r代入代入（m+r+1）2m=n+1 糾正單比特誤碼的校驗(yàn)位下界糾正單比特誤碼的校驗(yàn)位下界/31海明編碼l 海明在海明在1950年提出一種編碼來糾正單比特錯的編碼。年提出一種編碼來糾正單比特錯的編碼。l 該編碼是將碼字內(nèi)的位從左到右依次編號，編號為該編碼是將

20、碼字內(nèi)的位從左到右依次編號，編號為2的冪的的冪的位是校驗(yàn)位（如第位是校驗(yàn)位（如第1，2，4，8），其余為信息位。），其余為信息位。l 每個校驗(yàn)位的取值應(yīng)使得包括自己在內(nèi)的一些集合服從規(guī)每個校驗(yàn)位的取值應(yīng)使得包括自己在內(nèi)的一些集合服從規(guī)定的奇偶性。定的奇偶性。l 集合的選取如下：集合的選取如下： 對編號為K的信息位來說，K可以分解成2的冪的和，如編號為11，11=1+2+8，即第11位由1，2，8校驗(yàn)位校驗(yàn)，它同時屬于1，2，8所在的集合。/31改進(jìn)的奇偶校驗(yàn)l 對數(shù)據(jù)位組成一個對數(shù)據(jù)位組成一個L位寬，位寬，K位高的長方形距陣來發(fā)送，然后對每一列單獨(dú)計(jì)位高的長方形距陣來發(fā)送，然后對每一列單獨(dú)計(jì)算

21、奇偶位，并附在最后一行作為冗余位。算奇偶位，并附在最后一行作為冗余位。X X X X X XXX X X X X XXX X X X X XXX X X X X XXR R R R R R.R奇偶位K行L列檢錯率：1.該方法可以檢測長度為L的突發(fā)性錯誤，但不能檢測長度為L+1的突發(fā)性錯誤。2.假設(shè)L列中任意一列檢測出錯的概率為1/2，那么，整個數(shù)據(jù)塊的錯判率為（1/2）L 。該方法用在ICMP報(bào)頭檢驗(yàn)中。/31海明編碼舉例上例中，m=7，r=4，n=11，顯然24=11+1，采用偶校驗(yàn) 3=1+2，5=1+46=2+4，7=1+2+49=1+8，10=2+811=1+2+8校驗(yàn)位：1（3，5，

22、7，9，11） 2 （3，6，7，10，11） 4 （5，6，7） 8 （9，10，11）能糾正單比特錯！在接收方，如果校驗(yàn)位1不滿足偶校驗(yàn)，而其他校驗(yàn)位都滿足，則第1位出錯，/31檢錯碼l 在實(shí)際通信中使用糾錯碼好還是檢錯碼好呢？在實(shí)際通信中使用糾錯碼好還是檢錯碼好呢？l 例題例題 假設(shè)一個信道誤碼率是10-6，且出錯是孤立產(chǎn)生的（即只有單比特錯），數(shù)據(jù)塊長度為1000比特，如果采用糾錯編碼，需要10個校驗(yàn)位（2101011），傳送1M數(shù)據(jù)需要10000個校驗(yàn)位；如果采用檢錯編碼，每個數(shù)據(jù)塊只需一個奇偶校驗(yàn)位，傳送1M數(shù)據(jù)只需1000個校驗(yàn)位和一個重傳的數(shù)據(jù)1001位，共需要2001比特。l

23、 在多數(shù)通信中采用檢錯編碼，但在單工信道中需要糾錯編在多數(shù)通信中采用檢錯編碼，但在單工信道中需要糾錯編碼。碼。/31多項(xiàng)式編碼（循環(huán)冗余碼CRC）l CRC（Cyclic Redundancy Check)l CRC編碼的一般操作編碼的一般操作 給定一個m比特的幀或報(bào)文，發(fā)送方生成r比特的序列（也稱為幀檢驗(yàn)序列FCS，F(xiàn)rame Check Series），形成（m+r）的碼字，該碼字能被某個事先確定的數(shù)整除。接收方用相同的數(shù)去除收到的幀，如果無余數(shù)，則認(rèn)為數(shù)據(jù)幀無差錯。l 多項(xiàng)式表示：即將多項(xiàng)式表示：即將k比特的數(shù)據(jù)用比特的數(shù)據(jù)用k項(xiàng)多項(xiàng)式表示，它的各項(xiàng)多項(xiàng)式表示，它的各項(xiàng)為項(xiàng)為X k-1X

24、0，它的系數(shù)為數(shù)據(jù)中對應(yīng)位的，它的系數(shù)為數(shù)據(jù)中對應(yīng)位的0或或1。l 例如：例如：110001可表示成可表示成X5+X4+1/31循環(huán)冗余檢驗(yàn)的原理 l 在數(shù)據(jù)鏈路層傳送的幀中，廣泛使用了在數(shù)據(jù)鏈路層傳送的幀中，廣泛使用了循環(huán)冗余循環(huán)冗余檢驗(yàn)碼檢驗(yàn)碼 CRC 的檢錯技術(shù)。的檢錯技術(shù)。l 在發(fā)送端，先把數(shù)據(jù)劃分為組。假定每組在發(fā)送端，先把數(shù)據(jù)劃分為組。假定每組 k 個比個比特。特。 l 假設(shè)待傳送的一組數(shù)據(jù)假設(shè)待傳送的一組數(shù)據(jù) M = 101001（現(xiàn)在（現(xiàn)在 k = 6）。）。我們在我們在 M 的后面再添加供差錯檢測用的的后面再添加供差錯檢測用的 n 位位冗余冗余碼碼一起發(fā)送。一起發(fā)送。 /31

25、冗余碼的計(jì)算 l 用二進(jìn)制的模用二進(jìn)制的模 2 運(yùn)算進(jìn)行運(yùn)算進(jìn)行 2n 乘乘 M 的運(yùn)算，這相當(dāng)?shù)倪\(yùn)算，這相當(dāng)于在于在 M 后面添加后面添加 n 個個 0。l 得到的得到的 (k + n) 位的數(shù)除以事先選定好的長度為位的數(shù)除以事先選定好的長度為 (n + 1) 位的位的除數(shù)除數(shù) P，得出，得出商商是是 Q 而而余數(shù)余數(shù)是是 R，余數(shù)，余數(shù) R 比除數(shù)比除數(shù) P 少少1 位，即位，即 R 是是 n 位。位。 /31冗余碼的計(jì)算舉例 l 現(xiàn)在現(xiàn)在 k = 6, M = 101001。l 設(shè)設(shè) n = 3, 除數(shù)除數(shù) P = 1101，l 被除數(shù)是被除數(shù)是 2nM = 101001000。 l 模

26、模 2 運(yùn)算的結(jié)果是：運(yùn)算的結(jié)果是：商商 Q = 110101， 余數(shù)余數(shù) R = 001。l 把余數(shù)把余數(shù) R 作為作為冗余碼冗余碼添加在數(shù)據(jù)添加在數(shù)據(jù) M 的后面發(fā)送出去。發(fā)送的后面發(fā)送出去。發(fā)送的數(shù)據(jù)是：的數(shù)據(jù)是：2nM + R 即：即：101001001，共，共 (k + n) 位。位。 /31 1101010110 Q 商 除數(shù) P 110101 101000110100000 2nM 被除數(shù) 110101 111011 110101 111010 110101 111110 110101 101100 110101 110010 110101 01110 R 余數(shù)循環(huán)冗余檢驗(yàn)的原理說明 /31接收端對收到的每一幀進(jìn)行 CRC 檢驗(yàn) l (1) 若得出的余數(shù)若得出的余數(shù) R = 0，則判定這個幀沒有差錯，就，則判定這個幀沒有差錯，就接受接受(accept)。l (2) 若余數(shù)若余數(shù) R 0，則判定這個幀有差錯，就，則判定這個幀有差錯，就丟棄丟棄。l 但這種檢測方法并不能確定究竟是哪一個或哪幾個比但這種檢測方法并不能確定究竟是哪一個或哪幾個比特出現(xiàn)了差錯。特出現(xiàn)了差錯。l 只要經(jīng)過嚴(yán)格的挑選，并使用位數(shù)足夠多的除