《計算機通信網(wǎng) 》第3章 數(shù)據(jù)鏈路層

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

*3.1數(shù)據(jù)鏈路層概述

3.2成幀與幀定界

3.3差錯檢測與校正方法

3.4差錯與流量控制協(xié)議

3.5協(xié)議描述與驗證

3.6數(shù)據(jù)鏈路層協(xié)議案例

12012SPLENG

3.1數(shù)據(jù)鏈路層概述

-鏈路層模型

網(wǎng)絡(luò)層卜參W網(wǎng)絡(luò)層

本地連接

網(wǎng)絡(luò)層

3.1數(shù)據(jù)鏈路層概述

■DL面臨的環(huán)境

發(fā)送方接收方

可能裝入太快

取出跟不上網(wǎng)絡(luò)層

網(wǎng)絡(luò)層■

SAP取

數(shù)據(jù)鏈路層|數(shù)據(jù)鏈路層

幀幀

SAP<H>SAP

物理層物理層

信道有噪聲，

bits可能出錯

2012SPLENG

3.1數(shù)據(jù)鏈路層概述

■鏈路層模型物理層

實現(xiàn)了把比特傳輸轉(zhuǎn)換成信號

傳輸、進入信道。

網(wǎng)絡(luò)層

需要把一個個分組送到對方網(wǎng)

絡(luò)層

鏈路層

組織一個個分組，用比特傳輸

實現(xiàn)逐個分組的傳輸和接收

4傳輸信號2012SPLENG

3.1數(shù)據(jù)鏈路層概述

-鏈路層的基本任務(wù)

Service（月艮務(wù)）

為上面的實體提供分組傳輸服務(wù)

LinkControl（鏈路百空制）

雙方通過配合，實現(xiàn)：〉

鏈路的使用規(guī)則，流量控制、匯聚分發(fā)等

ErrorContix）l（差錯控制）

發(fā)送：組織DU（frame）,方便對方檢查錯誤

、接收：檢測DU是否出錯，DU出錯的處理

Framing（幀同步）

發(fā)送：轉(zhuǎn)換成特定的bit傳輸形式，將Frame送出〉

、接收：界定每個frame的位置，取出frame

mmmmmmmwmiinAsynchronous

Synchronous

BIOCR012SPLENG

3.1數(shù)據(jù)鏈路層概述

■鏈路層任務(wù)模型

NetworkLayerDU可用的通信功能DU

62012SPLENG

3.1數(shù)據(jù)鏈路層概述

■鏈路層效率定義

■鏈路層

■有效數(shù)據(jù)率r=WiVT(ni；第i幀bit數(shù)，T：測量

總時間)

■物理層

■信道的速率Rb/s

■鏈路層效率：7]=r/R(7]W])

路

—Minm-M

72012SPLENG

LinkLayerServices

■三種服務(wù)的示意圖

連接請求

一一

FrameFrame_-----------

連接確認

?Frame

二_ack-

拆除請求

無確認無連接有確認無連接―------------一

^-—

拆除確認

有確認面向連接

2012SPLENG

LinkLayerServices

■三種可能的服務(wù)

■無確認的無連接服務(wù)

■無需對方許可，直接向?qū)Ψ桨l(fā)送Frame,對方不需要反饋確認信息

■優(yōu)點：不受等待確認的拖累；缺點：frame傳輸可靠性不高

■信道效率：不等待確認，可提高信道效率，但傳輸出錯降低信道效率

■協(xié)議考慮：PDU中含源/目的地址

■有確認的無連接服務(wù)

■無需對方許可，直接向?qū)Ψ桨l(fā)送Frame,需要對方反饋確認信息

■優(yōu)點：通過重傳增加了可靠性；缺點：受等待應(yīng)答的拖累

-保持發(fā)送和確認間的正確對應(yīng)關(guān)系所采取的措施會大大降低信道使用效率

■協(xié)議考慮：PDU編號，PDU中含源/目的地址、單幀確認，差錯檢

測與重傳

-有確認的面向連接服務(wù)

■需事先與對方溝通，雙方建立起一套復(fù)雜的發(fā)送、確認機制來實現(xiàn)恢復(fù)差

錯、排除重復(fù)、維持順序的可靠通信

■適合于有大量Frame傳輸?shù)膱龊?/p>

■協(xié)議考慮：PDU編號、確認、差錯控制（丟棄錯幀和重復(fù)幀，請求

重發(fā)錯幀）

92012SPLENG

3.2成幀F(xiàn)raming穗

-成幀（或幀同步）：就是確定幀的界限（起與港

?通俗理解：

■發(fā)送方：在幀的前后各加入事先商定好的標記

-接收方：在bits中尋找標記來識別幀的起與止

■需要特別考慮：

-若數(shù)據(jù)與幀的起止標記相同時，發(fā)送方必須采取措施

-否則可能會引起接收方的誤斷

■成幀方法：「如何分黨:"一個

■字符計數(shù)法

■字符填充首尾界定法11010110100101101100111101

■位填充首尾界定法11100101010111000101010010

11010101011011010100100100

■物理層編碼違例法

102012SPLENG

成幀

-不同傳輸方式下的幀同步N

?同步傳輸方式（Sync,連續(xù)bit流）

■連續(xù)的bit流傳遞離散的Frame

■每個Frame都成為連續(xù)bit流中的一段，接收方識別并取

出Frame

■異步傳輸方式（Async,異步字節(jié)序列）

■每個Frame轉(zhuǎn)換為異步字節(jié)序列傳送，接收方收集字節(jié)

序列，還原Frame

■數(shù)據(jù)塊傳輸方式（Block）

■每個Frame形成一個數(shù)據(jù)塊傳送。

112012SPLENG

Sync信道的幀同步技術(shù)

■連續(xù)的bit流由若干Frame和它們間的空閑bit組成

■注意：frame中或空閑的bit都只有兩種取值：。或1

-關(guān)鍵問題：如何正確識別和提取bit流中的Frame部分？

■思路：假設(shè)空閑bit用某種特殊的bit模式(pattern)構(gòu)成，而

Frame幣不會由現(xiàn)該pattern,則接收方就能夠正確設(shè)別和提

取Frame

■但：應(yīng)該允許Frame包含任意數(shù)據(jù)，就肯定包含了這種Pattern。

■若能對Frame中出現(xiàn)的Pattern用某種變換方式消除，接收方提

取由Frame后，再通過反交換，恢復(fù)原來的Frame,該假設(shè)成

12特殊pattern2012SPLENG

Sync信道的幀同步技術(shù)

開始

■發(fā)送

開始■接收*檢測pattern

*否

發(fā)現(xiàn)

明描Framd

是Frame開始

*

否發(fā)現(xiàn)H存儲數(shù)據(jù)

是檢測

■pattern

Pattern變換

否發(fā)現(xiàn)

是Frame結(jié)束

否選擇

Pattern復(fù)原Frame

是■“易于變換

是

?■易于檢'測繼續(xù)

發(fā)送Frame，

■■易于反變換否

*

13結(jié)束士,LENG

Sync信道的幀同步技術(shù)

■位填充首尾定界法（’0'比特插入/刪除技術(shù)）奪

■Pattern=mi1111（r稱為定界標志F（Flag）

■Frame內(nèi)F的變換和反變換（利用F中連續(xù)6個‘17的性

質(zhì)）

■變換：

■Frame中如果出現(xiàn)連續(xù)5個'工，時，插入一個'0，

■提取

■從第一次出現(xiàn)非F開始，到重新出現(xiàn)F時的所有bit

■反變換

■Frame中出現(xiàn)連續(xù)5個時，刪除后面的1個'0，

■采用0工工工工工10的特點：

■變換與發(fā)送合一：發(fā)送連續(xù)5個加發(fā)一個'0，

廠接收與復(fù)原合一：連續(xù)接收5個V,下一bi曜楚”妒則

_____上-_」、?_t______I_____-r-tr___________、a、、._」LI_、r、__一__■____■_■_■_■_■___t______I,、、____

成幀

位填充首尾定界法

發(fā)送：在幀體部分出現(xiàn)連續(xù)5個1,無條件地插入一個0

01111110001010111101111101010111118111001001111110

接收：在幀體中掃描連續(xù)5個1,無條件去掉后面的0

00101011110111110101011111011110010

IMH1^'

152012SPLENG

位填充首尾定界法

■位填充（實現(xiàn)示意圖）

幀體幀體

__________________入__________________,____________入____________

...01111110011111101001111010110101010111111010101110101110111111001111110...

...01101010...

F檢測結(jié)果△

接收"0”bit

幀提取

刪除移位寄存器

2012SPLENG

位填充首尾定界法告滑

■軟件模擬

■intSend(char*pF,intLen){

■inti,j,c,msk,sn;

■sn=0;

■for(i=0;i<Len;i++){//循環(huán)幀的字節(jié)長度

■msk=1;

■forQ=0;j<8;j++){//8bit

■c=pF[i]&msk?l:0;測試第jbit

■msk<<=1;準備測試下一bit

■Xmitb(c);sn++;

■if(c)cnt++;elseent=0;//計算連續(xù)1的個數(shù)

■if(ent==5){Xmitb(O);ent=O;sn++;}

■)

■)

■returnsn;//回送發(fā)送總bit數(shù)

"假定函數(shù)Xmitb(c)：向信道發(fā)送c(1bit)2012SPLENG

Async信道的幀同步技術(shù)

■描述

■以字節(jié)(8bit)為單位的傳輸方式

■逐字節(jié)傳輸實現(xiàn)Frame傳輸

■幀同步討論

■Frame間留有足夠的時間間隔，以區(qū)分各個Frame

■對Frame傳輸能力有較大的影響

■Frame間的時間間隔不夠大，幀與幀區(qū)分易出錯

■兩種典型幀同步技術(shù)

■字節(jié)計數(shù)法

■字符填充首尾定界法

□口□□□口陽州口門口miyjUiyi

成幀——字符計數(shù)法

■也可稱為字節(jié)計數(shù)法

-假設(shè)一個字符由8位二進制數(shù)表示

■基本思想

-在幀頭的第1個字節(jié)指明幀內(nèi)的字節(jié)數(shù)

■問題

■字節(jié)計數(shù)值可能在傳輸中出錯（被篡改）

■簡單、不可靠

DATA11101010001011100101010101011101010101011

發(fā)送0000010)1110101000101110000001100101010101011101010101011

I錯

接收1110101000101110000001100101010101011101010101011

192012SPLENG

字符填充首尾定界法

■思想

■與同步方式的位填充類似，不同的是以字節(jié)為單位

■方法：“定界字符”

■在幀體的前后都用某個特定的字節(jié)加以“定界”

■幀體中也可能出現(xiàn)該定界字符，通過變換消除

■接收時提取Frame后，通過反變換復(fù)原

■局限性：數(shù)據(jù)的長度總是以字符或其倍數(shù)為單位

■定界字符：F(Flag)=01111110

第曾第2幀

A

(\

麗麗匹

PLENG

字符填充首尾定界法1等移

-將F變換為某個其它字節(jié)(x)存在問題：下

■幀體中其它字節(jié)也可能出現(xiàn)X,反變換X9F時就出錯

■Frame體中定界字符的變換方法

■一字節(jié)到兩字節(jié)的變換,變換后幀體中不出現(xiàn)F

■幀體中的F和x都需要變換：F-^xy;x^xz

■y和z是另外選取的兩個字符，對y、z不再需要變換

■分析

■若幀體中出現(xiàn)xy

■變換：xy^(xz)y；反變換：xzy—xy,正確復(fù)原

■可以驗證：對幀體中出現(xiàn)F,x,y,z的任意順序的組合，只

對其中的所有F和x進行變換，反變換時都能正確復(fù)原

212012SPLENG

字符填充首尾定界法

■處理幀體內(nèi)的特殊字符(RFC工662,異

步PPP)

■F=01111110(7e),定界字符

■X=Oinn(H(7d),稱為轉(zhuǎn)義字徉------^B=Frame[i++]

■y=01011110(5e)

■z=01011101(5d)

幀體

幀體填充后

22

I

練習(xí)

■分兩組：一組成幀，一組提取幀,

■分別用位填充法、計數(shù)法、字符填充法進行練習(xí)

■F=01111110,X、V、Z可自行定義

■可自定義若干幀來完成該練習(xí)

幀1:1001111111100000010111010100001001100011

幀2:110110110000000001100111

幀3:11000101111111111101001011011111

■思考

■字符填充法中，僅用F和x是否能夠?qū)崿F(xiàn)，如能實

現(xiàn)，給出實現(xiàn)方法，如不能實現(xiàn)，請說明不能實

現(xiàn)的理由

232012SPLENG

字符填充首尾定界法

FLAG有效載荷域FLAG

原始字符填充以后

FLAGAESCFLAGB教材

PP.159

AESCBAESCESCB

AESCFLAGBAESCESCESCFLAGB

AESCESCBAESCESCESCESCB

有標志字節(jié)作為分界的幀字節(jié)填充前后的4個字節(jié)序列例子

ENG

塊傳輸信道的幀同步技術(shù)

■,

通信方式是塊傳輸方式，每個塊就是一個Frame

■塊傳輸方式

■每個Frame都帶有前導(dǎo)bit序列(preamble)和后續(xù)bit序列

(postamble),以確保Frame的實和尾能正確檢測和接收

■因此需要確定：

■Preamble結(jié)束和Frame開始的比特位置

■Frame結(jié)束和postamble開始的bit位置

■同步技術(shù)

■違例編碼法：利用信息bit的碼型特性，用非正常碼型來進行界定位置

postamblepreamble

塊傳輸信道的幀同步技術(shù)

■例1：曼切斯特編碼（lb/2b,10M以太網(wǎng)）

o=1=違例J=和K=

■Block=010101JKFramebodyKJ010101

■例2：4b/5b編碼（100M以太網(wǎng)）

■4bit數(shù)據(jù)映射成5bit碼組

■0000^11110,0001901001,…，1111^11101

■空閑911111,定界符1911000,定界符2f10001

■Block=0UHB］定界符:LFrameBody定界符201010工

■例3：8b/10b編碼（1000M以太網(wǎng)）

■8bit數(shù)據(jù)映射成工Obit碼組

■從1024個碼組中只需選取256個來代表8bit的各個值

■剩余1024?256個碼組可作為控制、定界等多種功能

262012SPLENG

塊傳輸信道的幀同步技術(shù)成幀

校驗和法

■利用ATM信元固定、且長度較短（53字力的

特性

■信元前4字節(jié)是頭部，第5字節(jié)是校驗和，使用循

環(huán)冗余校驗

■設(shè)40位寄存器，計算校驗和

■正確則可能發(fā)現(xiàn)了一個信元

■不正確則移一位，再次計算，直到得到一個信元

?！剐旁^.信元體信元頭■信元體

Ibo

I

3.2成幀一討論與理解

■幀定界正確，請問幀一定無錯嗎？

■一個幀定界出錯，請問

■用字符計數(shù)法，后續(xù)的幀也不能正確識別嗎？為什么？

■用字符填充法和位填充法，情況又如何？

■位填充法比字符填充法有哪些優(yōu)越性？

282012SPLENG

Framing小結(jié)

■不同的成幀技術(shù)以適應(yīng)信道的不同傳輸體制

■需求：

■接收方易于提取、出錯時對后續(xù)幀的提取影響小

■較高的信道利用率、較簡單的實現(xiàn)

■位填充、字符計數(shù)、字符填充、違例編碼、校驗和

■與其它功能的關(guān)系

■實現(xiàn)的是信道上傳輸和接收幀的功能，不涉及幀的內(nèi)容

■鏈路層其它功能直接對幀的處理，不受傳輸體制影響

292012SPLENG

3.3差錯檢測與糾正

■信道傳輸過程中（誤碼：；Of）

■隨機干擾：隨機錯（均勻性）

■突發(fā)干擾：突發(fā)錯（一定的突發(fā)長度）

■出錯處理

■檢錯：驗證是否出現(xiàn)了誤碼

■糾錯：找到誤碼的位置，糾正之

原碼

...01111110011111101001111010110101010111111010101110101110111111001111110...

出錯后3III

0111111001111101001111101101010101111101010111010111111111001111110...

Bit錯可能造成：

幀體錯——幀錯誤

定界錯——幀錯誤、幀丟失、多余幀

信道異常（多于個信道失序

3061）-----2012SPLENG

3.3差錯檢測與糾正

■如何理解數(shù)據(jù)傳輸中的差錯？

■一位錯就等于全幀錯

■關(guān)于誤碼率Pb與誤幀率Pe

■假設(shè)

-幀長度為N比特，誤碼率為Pb（設(shè)每比特出錯獨立）

■則

■比特正確率為：1-Pb

■N比特正確率為

（1-Pb）'

-幀出錯率（誤幀率）（一幀中至少一位錯）為

N

Pe=1-（1-Pb）?NPb（幀出錯的概率與幀成近似成正比）

312012SPLENG

3.3差錯檢測與糾正

■差錯控制，意味著：

-首先檢測出差錯

-然后是糾正差錯

■檢測差錯

■采用冗余編碼技術(shù)進行差錯檢驗編碼

■糾錯碼：不僅能檢測差錯，且能知道錯在哪兒

■檢錯碼：只能檢測差錯，但不知錯在哪

■糾正差錯

■前向糾錯FEC(ForwardErrorCorrection)

■用糾錯碼，收方檢錯并自動糾錯

■自動請求重發(fā)ARQ(AutomaticRequestforRepeat)

■用檢錯碼，收方檢錯通知發(fā)方重發(fā)恢復(fù)差錯

、-計算機網(wǎng)絡(luò)中常采用

322012SPLENG

3.3差錯檢測與糾正

?假設(shè)

■待傳數(shù)據(jù)為m位

■為檢測差錯，所需要的冗余位（校驗位）為r位

■則

■傳輸碼長度n=m+r

■通常采用糾錯碼或檢錯碼，即：

■按某種算法計算出校驗位

■然后將m位數(shù)據(jù)和r位校驗碼形成傳輸碼

■接收方根據(jù)相同的算法重新計算校驗位，判斷是否出錯

332012SPLENG

3.3差錯檢測與糾正

■一種直觀簡單的糾錯方法

■每個bit重傳三次：1^111;0^000

■如果3bit中有工bit錯，我們可以糾正過來

■101、110>0111111

■001、010、100900090

■如果3bit中有2bit或3bit全錯，則無法糾正了

■101今111?000?無法知道是:Lbit還是2bit錯

■將每個bit重傳2n+l次，n越大，糾錯能力越

強（傳輸效率越低）

■不管n如何取，我們?nèi)圆恢朗欠裾娴募m正了錯誤，

34只能認為增大了糾正錯誤的概率如2SPLENG

3.3.1糾錯碼海明碼

■海明距離(HammingDistance)教材P16^^63

■兩個等長碼對應(yīng)位不同的個數(shù)，稱作這兩個碼的海明距

離

■例：0001111和0001100的海明距離為2

■某種編碼的任意兩個有效編碼之間的距離稱為該編

碼的海明距離

■結(jié)論1：檢出d個錯誤的檢錯碼，海明距離至少為d+工

■結(jié)論2：糾正d個錯誤的糾錯碼，海明距離至少為2d+：L

海明碼是一種能糾正一位錯的糾錯碼

352012SPLENG

3.3.1糾錯碼

■假設(shè)

■數(shù)據(jù)為m位

■則糾正一位錯的校驗碼「滿足

m+r+l<2r（證明：P163）

■例如:m=3,3+r+l<2rfr=3

■則海明碼碼長=m+r=6位

■海明碼的編碼為r與m的混排方式，規(guī)則為：

■檢驗位r的序號為2的整次幕1,2,4,8,……

■信息位m的序號為2的非整次寨，3,5,6,7…

■rlr21113r4m51Tl62012SPLENG

3.3.1糾錯碼一海明*

?假設(shè)數(shù)據(jù)為OIL該如何確定海明編碼?

■編碼應(yīng)為：rlr21Tl3r41Tl51Tl6

■現(xiàn)已知：m3m5m6=011

-關(guān)鍵是確定rl、r2和r4

■「的計算方法

■首先找出哪些與rl、r2和r4相關(guān)的數(shù)據(jù)位

■將數(shù)據(jù)位數(shù)拆成2的整次塞相加

-如3=1+2fm3與r1和r2相關(guān)

■然后將與某r相關(guān)的數(shù)據(jù)位模2加（異或），結(jié)果為該r值

■與「工相關(guān)的數(shù)據(jù)位：m3、m5則「工=0十1=]

■與「2相關(guān)的數(shù)據(jù)位：m3、m6WiJr2=0?l=l

■與r4相關(guān)的數(shù)據(jù)位：m5>m6則=4=1十1=0

■得出：011的海明編碼為工10011

372012SPLENG

3.3.1糾錯碼

■已知：011的海明編碼為工工001工（rlr2m3r4m5m

■假設(shè)：編碼在傳輸中出了一位錯

■110011錯成110010

■接收方的糾錯規(guī)則

-首先：對于每個ri,將ri和與之相關(guān)的數(shù)據(jù)位進行依次異或

■結(jié)果為1,則記錄Ai=i（i為r的序號）

■結(jié)果為0,則記錄Ai=O

■然后累加，計算ZAi的值，結(jié)果等于幾就是該對應(yīng)位出錯

■最后，將出錯位取反進行糾錯

■計算過程

■rl?m3十m5=l?0?1=0Al=0

■r2?m3十m6=1十0十0=1A2=2

■r4?m5?m6=0?1?0=1A4=4

■出錯位：SAi=Al+A2+A4=6

■晶I錯：110010—110011（差錯位取反）2O12SPLENG

3.3.2差錯檢測

■采用冗余編碼技術(shù)進行差錯檢驗編碼

■基本思想

■發(fā)送方：將待發(fā)數(shù)據(jù)按照某種規(guī)則加上一定的冗余位后,

進行傳輸，

■接收方：對收到的數(shù)據(jù)進行判斷，是否符合原規(guī)則，若

符合則無錯，不符合則出錯。

發(fā)送方接收方

線路傳輸

校驗C(x)=R(x)

無錯

計算校驗仍

計算校駛用I

C(x)#R(x)

7出錯

校驗碼R(x)C(x)R(x)

392012SPLENG

3.3.2差錯檢測一一檢錯碼

■奇偶校驗碼

■循環(huán)冗余碼CRC

■校驗和編碼

402012SPLENG

3.3.2差錯檢測一一奇偶校驗碼

■增加冗余位使信息碼中的“工”的個數(shù)為奇數(shù)或偶數(shù)

■奇校驗：“1”的個數(shù)為奇數(shù)

■偶校驗：的個數(shù)為偶數(shù)

■具體實現(xiàn)：信息位逐位進行模2加I（異或運算）

■al十a(chǎn)2十a(chǎn)3十a(chǎn)4十a(chǎn)5

■結(jié)果為0,偶校驗時校驗位為0,奇校驗時，校驗位為1

■結(jié)果為1,偶校驗時校驗位為1,奇校驗時，校驗位為0

■例信息字段奇校驗碼偶校驗碼

01100101100100110011

出錯為：001001,0、001001A

重新計算校驗和:

★

41不同則出錯2012SPLENG

糾正突發(fā)錯

數(shù)據(jù)組織成矩陣,

■發(fā)送時按列發(fā)送

■出現(xiàn)突發(fā)錯誤時，可按行糾正

1加101嗯01010

0D10110001001

100101001010

01001001000010

111010^1010101

422012SPLENG

3.3.2差錯檢測循環(huán)冗余碼蒸

■循環(huán)冗余碼(CRC:1011010

CyclicRedundancy

Code)教材p165~167

-對任意位二進制流，補充，000000(

m11000101

r個011100010模2力口

■用規(guī)定的r+1位除數(shù)進行求11000101

余計算，得到r位效驗碼01001110

00000000

■數(shù)據(jù)與r位效驗碼組成傳輸10011100

碼組11000101

-發(fā)送出去10110010

11000101

"TTTlHTnr

11000101

0101011(

m位數(shù)據(jù)0000000(

1010110

432012SPLENG

3.3.2差錯檢測一循環(huán)冗余碼

10110101010110

CRC校驗

■對收到的完整的數(shù)11000101I1011010101011C

據(jù)幀用發(fā)送方相同I11000101

11100000

的r+1位除數(shù)進行求11000101

余計算01001011

00000000

■余數(shù)為0則無錯10010110

11000101

10100111

11000101

11000101

11000101

0000000Q

0000000(1

000000。

442012SPLENG

3.3.2差錯檢測循環(huán)冗余碼管

■基于任何一個二進制位串組成的代碼，都可以與系

數(shù)只為0和1的多項式建立一一對應(yīng)的關(guān)系。

■一個K位的數(shù)據(jù)可以看成是從xKT?X。次系數(shù)為。和

1的多項式

X4X3X2X1X0

數(shù)據(jù):11011

多項式X4+x3+x+1

452012SPLENG

3.3.2差錯檢測循環(huán)冗余碼鋤

■1)基本思想：

■設(shè)：數(shù)據(jù)m位，對應(yīng)多項式M(x),校驗碼為r位，對應(yīng)多項式R(x)

■給定：生成多項式G(x),階數(shù)為r,r+1位，高位和低位系數(shù)為1

■發(fā)送方：將M(x)通過G(x)計算出帶校驗和的傳輸多項式T(x)

-接收方：將收到的帶校驗和的多項式T'(x)除以G(x),如有余數(shù)，

出錯，能除盡，無錯

■2)校驗碼與傳輸多項式的計算

■STEP1在m位數(shù)據(jù)之后加上r個0,數(shù)據(jù)位變成m+r位，對應(yīng)多項式

X「M(X)

■STEP2計算校驗碼多項式：xrM(x)/G(x)(對應(yīng)二進制位串模

2除)，余數(shù)為校驗碼，對應(yīng)多項式為R(x)

■STEP3計算傳輸多項式：T(x)=xrM(x)+R(x),對應(yīng)系

數(shù)位串為傳輸數(shù)據(jù)

★

462012SPLENG

3.3.2差錯檢測一循環(huán)冗余工

示例：數(shù)據(jù)：110110

■G(x)=x4+x+1對應(yīng)位串工001工(除數(shù))

■在數(shù)據(jù)后加4個0形成1101100000被除數(shù)，求余數(shù)

校驗：

110口11110011

100111101100000100111101100101

C1001110011

v

—?1000010000

1001110011

1100011010

1001110011

1011010011

1001110011

01010~

傳輸代碼（CRC碼）為：1101100101余數(shù)為口，表示校驗正確

472012SPLENG

3.3-2差錯檢測——冗余循環(huán)碼疆

■值得注意：

■多項式變?yōu)榇a字時，首位對應(yīng)最高次，中間的“0”不能丟

掉

■在計算中涉及的和均為模2運算（加、減結(jié)果一樣,

異或運算，相同為0,相異為工）

■模2除商工的原則：只要被除數(shù)的首位為工，且位數(shù)與除數(shù)相

同則商工，如上例中紅色雙向箭頭處（被除數(shù)為10000,除

數(shù)為1001工）

482012SPLENG

3.3-2差錯檢測——冗余循環(huán)碼耀

■CRC碼的檢錯性能（r個校驗位比特）

■所有單個錯

-所有2bit錯

-所有長度小于或等于r個bit的突發(fā)錯

■長度為r+1個比特的突發(fā)錯，漏檢率為：1/2^

■長度大于r+工比特的突發(fā)錯，漏檢率為：l/2r

■校驗和的計算一般都用硬件實現(xiàn)，有參考電路，也可用軟件

實現(xiàn)。硬件計算時是邊發(fā)邊計算，故通常校驗和在幀尾。

■常用的CRC多項式：

■CRC-8=x8+x2+x+1

■CRC-12=x12+x11+x3+x2+x+1

■CRC-16=x16+x15+x2+1

■CRC-CCITT=X16+x12+x5+1

■CRC-32

492012SPLENG

3.3-2差錯檢測——校驗和

■校驗和Checksum

■C語言：for(i=0;i<N;i++)Sum+=W[i]；

■基本思想：

■按一定大小進行累加

■累加結(jié)果產(chǎn)生進位，將進位累加到結(jié)果中

■最終累加結(jié)果取反，獲得校驗和

數(shù)據(jù)(16進制)ca73Oc1eca722201

計算16位校驗和ca73+Oc1e=d691

d691+ca72=1a103

1a103+2201=1c304

checksum=c304+1=3cfa

校驗后的數(shù)據(jù)：ca73Oc1eca7222013cfa

校驗=1+c304+3cfa=1+fffe=02012SPLENG

ErrorControl小結(jié)疆

-檢錯算法

■CRC,二進制異或除法，除數(shù)選擇重要

■Checksum,模65536力口法，軟件實現(xiàn)

■幀末尾附加了r-bit檢錯碼（也稱校驗碼）

-檢錯能力

■r越大，檢錯能力越強

■存在壞幀漏檢的概率

-應(yīng)用

■發(fā)現(xiàn)并丟棄傳輸中出現(xiàn)的壞幀，保證繼續(xù)處理的幀基

本上是正確的

Frame校驗碼

作業(yè)4

1、請寫出通常采用的成幀方法及各種成幀法淵

點。假設(shè)幀標記符出錯，請問哪種成幀方法將

不能檢測到后續(xù)所有的幀？為什么？

2、如果待傳數(shù)據(jù)為1111111000111111,假

設(shè)采用“位填充法”成幀，請寫出幀內(nèi)容。

3、假設(shè)待傳數(shù)據(jù)為100101,(1)計算校驗位r

的位數(shù)；(2)計算出傳輸該數(shù)據(jù)的海明碼

(要求步驟)

4、假設(shè)待傳數(shù)據(jù)為100101,采用CRC編碼，假

設(shè)生成多項式為G(X)=X4+1,計算出校驗

多項式R(X)o

522012SPLENG

3.4差錯與流量控制協(xié)議

■在計算機網(wǎng)絡(luò)中，差錯控制方式通常采用

自動請求重發(fā)（ARQ）

■ARQ基本思想：

-采用檢錯碼進行檢錯

■丟棄出錯的幀

■請求重傳出錯的幀■ARQ是一種保證PDU可靠傳輸?shù)募夹g(shù)

■可用于各層協(xié)議中，不僅僅限于數(shù)據(jù)鏈路層

■對幀進行確認

■例如：

■典型的ARQ協(xié)議■X.25網(wǎng)絡(luò)的網(wǎng)絡(luò)層、數(shù)據(jù)鏈路層

■TCP/IP網(wǎng)絡(luò)中的傳送層

-停等協(xié)議

■回退N協(xié)議

-選擇性重傳協(xié)議

532012SPLENG

3.4差錯與流量控制協(xié)議

■3.4.1停一等協(xié)議

■3.4.2連續(xù)發(fā)送的滑動窗口協(xié)議的概念

■3.4.3回退N協(xié)議

■3.4.4選擇性重傳協(xié)議

■3.4.4雙向傳輸時的確認

■3.4.4流量控制

542012SPLENG

34?工停一等協(xié)議

■停一等協(xié)議：stopandwaitprotocol

■基本思想：

■每發(fā)送一個幀（PDU）,停下來等確認（應(yīng)答）

-收到肯定應(yīng)答，發(fā)送下一個新幀（PDU）

-收到否定應(yīng)答，重發(fā)上次的幀?數(shù)據(jù)鏈路層的

鏈路層鏈路層PDU也稱為幀

?后續(xù)討論中幀

和PDU等同

網(wǎng)

絡(luò)

層

552012SPLENG

3.4,停一等協(xié)議

協(xié)議需要考慮以下情況

■幀丟失，將導(dǎo)致：

■接收方收不到PDU

-發(fā)送方收不到應(yīng)答（ACK或NAK）

■應(yīng)答丟失，將導(dǎo)致：

-發(fā)送方收不到應(yīng)答（ACK或NAK）

■解決辦法：設(shè)置定時器T,超時重發(fā)

T

重傳

□重傳

562012SPLENG

3?4?1停一等協(xié)議

■還有問題要解決：

■連續(xù)丟失問題

■重發(fā)后仍收不到應(yīng)答或接收方仍收不到PDU,一直重發(fā)下去?

-解決辦法：設(shè)置重發(fā)次數(shù)Nmax

■重復(fù)收幀問題

■ACK丟失，重發(fā)PDU,接收方收到重復(fù)幀而不知道

-措施：為PDU編號（01即可區(qū)別）

PDU

TT

重傳新重傳重復(fù)PDU

PDU?丟棄

PDU無編號PDU有編號

會出錯不出錯2012SPLENG

3?4?1停一等協(xié)議

■還有問題要解決：

■過早超時問題

■重發(fā)定時器T在應(yīng)答到達發(fā)送方之前就超時

-導(dǎo)致接收方正確收到PDU,而發(fā)送方仍然重發(fā)

■如果過早超時，且ACK無編號，則

■出現(xiàn)發(fā)送PDU出錯

■措施：對應(yīng)答編號

■請同學(xué)自己分析以下情況：

重復(fù)PDU

■過早超時，但和都編號時,

PDUACK丟棄

停等協(xié)議將如何工作？

發(fā)送方誤以為是對PDU

(1)的應(yīng)答，故下一