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

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

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

3.2成幀與幀定界

3.3差錯(cuò)檢測(cè)與校正方法

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

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

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可能出錯(cuò)

2012SPLENG

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

■鏈路層模型物理層

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

傳輸、進(jìn)入信道。

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

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

絡(luò)層

鏈路層

組織一個(gè)個(gè)分組，用比特傳輸

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

4傳輸信號(hào)2012SPLENG

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

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

Service（月艮務(wù)）

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

LinkControl（鏈路百空制）

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

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

ErrorContix）l（差錯(cuò)控制）

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

、接收：檢測(cè)DU是否出錯(cuò)，DU出錯(cuò)的處理

Framing（幀同步）

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

、接收：界定每個(gè)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：測(cè)量

總時(shí)間)

■物理層

■信道的速率Rb/s

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

路

—Minm-M

72012SPLENG

LinkLayerServices

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

連接請(qǐng)求

一一

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

連接確認(rèn)

?Frame

二_ack-

拆除請(qǐng)求

無確認(rèn)無連接有確認(rèn)無連接―------------一

^-—

拆除確認(rèn)

有確認(rèn)面向連接

2012SPLENG

LinkLayerServices

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

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

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

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

■信道效率：不等待確認(rèn)，可提高信道效率，但傳輸出錯(cuò)降低信道效率

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

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

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

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

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

■協(xié)議考慮：PDU編號(hào)，PDU中含源/目的地址、單幀確認(rèn)，差錯(cuò)檢

測(cè)與重傳

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

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

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

■適合于有大量Frame傳輸?shù)膱?chǎng)合

■協(xié)議考慮：PDU編號(hào)、確認(rèn)、差錯(cuò)控制（丟棄錯(cuò)幀和重復(fù)幀，請(qǐng)求

重發(fā)錯(cuò)幀）

92012SPLENG

3.2成幀F(xiàn)raming穗

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

?通俗理解：

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

-接收方：在bits中尋找標(biāo)記來識(shí)別幀的起與止

■需要特別考慮：

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

-否則可能會(huì)引起接收方的誤斷

■成幀方法：「如何分黨:"一個(gè)

■字符計(jì)數(shù)法

■字符填充首尾界定法11010110100101101100111101

■位填充首尾界定法11100101010111000101010010

11010101011011010100100100

■物理層編碼違例法

102012SPLENG

成幀

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

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

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

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

出Frame

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

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

序列，還原Frame

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

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

112012SPLENG

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

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

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

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

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

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

取Frame

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

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

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

12特殊pattern2012SPLENG

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

開始

■發(fā)送

開始■接收*檢測(cè)pattern

*否

發(fā)現(xiàn)

明描Framd

是Frame開始

*

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

是檢測(cè)

■pattern

Pattern變換

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

是Frame結(jié)束

否選擇

Pattern復(fù)原Frame

是■“易于變換

是

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

發(fā)送Frame，

■■易于反變換否

*

13結(jié)束士,LENG

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

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

■Pattern=mi1111（r稱為定界標(biāo)志F（Flag）

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

質(zhì)）

■變換：

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

■提取

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

■反變換

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

■采用0工工工工工10的特點(diǎn)：

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

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

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

成幀

位填充首尾定界法

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

01111110001010111101111101010111118111001001111110

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

00101011110111110101011111011110010

IMH1^'

152012SPLENG

位填充首尾定界法

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

幀體幀體

__________________入__________________,____________入____________

...01111110011111101001111010110101010111111010101110101110111111001111110...

...01101010...

F檢測(cè)結(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;測(cè)試第jbit

■msk<<=1;準(zhǔn)備測(cè)試下一bit

■Xmitb(c);sn++;

■if(c)cnt++;elseent=0;//計(jì)算連續(xù)1的個(gè)數(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é)傳輸實(shí)現(xiàn)Frame傳輸

■幀同步討論

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

■對(duì)Frame傳輸能力有較大的影響

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

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

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

■字符填充首尾定界法

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

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

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

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

■基本思想

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

■問題

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

■簡單、不可靠

DATA11101010001011100101010101011101010101011

發(fā)送0000010)1110101000101110000001100101010101011101010101011

I錯(cuò)

接收1110101000101110000001100101010101011101010101011

192012SPLENG

字符填充首尾定界法

■思想

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

■方法：“定界字符”

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

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

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

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

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

第曾第2幀

A

(\

麗麗匹

PLENG

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

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

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

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

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

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

■y和z是另外選取的兩個(gè)字符，對(duì)y、z不再需要變換

■分析

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

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

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

對(duì)其中的所有F和x進(jìn)行變換，反變換時(shí)都能正確復(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í)

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

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

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

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

幀1:1001111111100000010111010100001001100011

幀2:110110110000000001100111

幀3:11000101111111111101001011011111

■思考

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

現(xiàn)，給出實(shí)現(xiàn)方法，如不能實(shí)現(xiàn)，請(qǐng)說明不能實(shí)

現(xiàn)的理由

232012SPLENG

字符填充首尾定界法

FLAG有效載荷域FLAG

原始字符填充以后

FLAGAESCFLAGB教材

PP.159

AESCBAESCESCB

AESCFLAGBAESCESCESCFLAGB

AESCESCBAESCESCESCESCB

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

ENG

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

■,

通信方式是塊傳輸方式，每個(gè)塊就是一個(gè)Frame

■塊傳輸方式

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

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

■因此需要確定：

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

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

■同步技術(shù)

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

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個(gè)碼組中只需選取256個(gè)來代表8bit的各個(gè)值

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

262012SPLENG

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

校驗(yàn)和法

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

特性

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

環(huán)冗余校驗(yàn)

■設(shè)40位寄存器，計(jì)算校驗(yàn)和

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

■不正確則移一位，再次計(jì)算，直到得到一個(gè)信元

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

Ibo

I

3.2成幀一討論與理解

■幀定界正確，請(qǐng)問幀一定無錯(cuò)嗎？

■一個(gè)幀定界出錯(cuò)，請(qǐng)問

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

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

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

282012SPLENG

Framing小結(jié)

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

■需求：

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

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

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

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

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

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

292012SPLENG

3.3差錯(cuò)檢測(cè)與糾正

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

■隨機(jī)干擾：隨機(jī)錯(cuò)（均勻性）

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

■出錯(cuò)處理

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

■糾錯(cuò)：找到誤碼的位置，糾正之

原碼

...01111110011111101001111010110101010111111010101110101110111111001111110...

出錯(cuò)后3III

0111111001111101001111101101010101111101010111010111111111001111110...

Bit錯(cuò)可能造成：

幀體錯(cuò)——幀錯(cuò)誤

定界錯(cuò)——幀錯(cuò)誤、幀丟失、多余幀

信道異常（多于個(gè)信道失序

3061）-----2012SPLENG

3.3差錯(cuò)檢測(cè)與糾正

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

■一位錯(cuò)就等于全幀錯(cuò)

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

■假設(shè)

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

■則

■比特正確率為：1-Pb

■N比特正確率為

（1-Pb）'

-幀出錯(cuò)率（誤幀率）（一幀中至少一位錯(cuò)）為

N

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

312012SPLENG

3.3差錯(cuò)檢測(cè)與糾正

■差錯(cuò)控制，意味著：

-首先檢測(cè)出差錯(cuò)

-然后是糾正差錯(cuò)

■檢測(cè)差錯(cuò)

■采用冗余編碼技術(shù)進(jìn)行差錯(cuò)檢驗(yàn)編碼

■糾錯(cuò)碼：不僅能檢測(cè)差錯(cuò)，且能知道錯(cuò)在哪兒

■檢錯(cuò)碼：只能檢測(cè)差錯(cuò)，但不知錯(cuò)在哪

■糾正差錯(cuò)

■前向糾錯(cuò)FEC(ForwardErrorCorrection)

■用糾錯(cuò)碼，收方檢錯(cuò)并自動(dòng)糾錯(cuò)

■自動(dòng)請(qǐng)求重發(fā)ARQ(AutomaticRequestforRepeat)

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

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

322012SPLENG

3.3差錯(cuò)檢測(cè)與糾正

?假設(shè)

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

■為檢測(cè)差錯(cuò)，所需要的冗余位（校驗(yàn)位）為r位

■則

■傳輸碼長度n=m+r

■通常采用糾錯(cuò)碼或檢錯(cuò)碼，即：

■按某種算法計(jì)算出校驗(yàn)位

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

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

332012SPLENG

3.3差錯(cuò)檢測(cè)與糾正

■一種直觀簡單的糾錯(cuò)方法

■每個(gè)bit重傳三次：1^111;0^000

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

■101、110>0111111

■001、010、100900090

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

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

■將每個(gè)bit重傳2n+l次，n越大，糾錯(cuò)能力越

強(qiáng)（傳輸效率越低）

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

34只能認(rèn)為增大了糾正錯(cuò)誤的概率如2SPLENG

3.3.1糾錯(cuò)碼海明碼

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

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

離

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

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

碼的海明距離

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

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

海明碼是一種能糾正一位錯(cuò)的糾錯(cuò)碼

352012SPLENG

3.3.1糾錯(cuò)碼

■假設(shè)

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

■則糾正一位錯(cuò)的校驗(yàn)碼「滿足

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

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

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

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

■檢驗(yàn)位r的序號(hào)為2的整次幕1,2,4,8,……

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

■rlr21113r4m51Tl62012SPLENG

3.3.1糾錯(cuò)碼一海明*

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

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

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

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

■「的計(jì)算方法

■首先找出哪些與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糾錯(cuò)碼

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

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

■110011錯(cuò)成110010

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

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

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

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

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

■最后，將出錯(cuò)位取反進(jìn)行糾錯(cuò)

■計(jì)算過程

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

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

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

■出錯(cuò)位：SAi=Al+A2+A4=6

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

3.3.2差錯(cuò)檢測(cè)

■采用冗余編碼技術(shù)進(jìn)行差錯(cuò)檢驗(yàn)編碼

■基本思想

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

進(jìn)行傳輸，

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

符合則無錯(cuò)，不符合則出錯(cuò)。

發(fā)送方接收方

線路傳輸

校驗(yàn)C(x)=R(x)

無錯(cuò)

計(jì)算校驗(yàn)仍

計(jì)算校駛用I

C(x)#R(x)

7出錯(cuò)

校驗(yàn)碼R(x)C(x)R(x)

392012SPLENG

3.3.2差錯(cuò)檢測(cè)一一檢錯(cuò)碼

■奇偶校驗(yàn)碼

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

■校驗(yàn)和編碼

402012SPLENG

3.3.2差錯(cuò)檢測(cè)一一奇偶校驗(yàn)碼

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

■奇校驗(yàn)：“1”的個(gè)數(shù)為奇數(shù)

■偶校驗(yàn)：的個(gè)數(shù)為偶數(shù)

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

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

■結(jié)果為0,偶校驗(yàn)時(shí)校驗(yàn)位為0,奇校驗(yàn)時(shí)，校驗(yàn)位為1

■結(jié)果為1,偶校驗(yàn)時(shí)校驗(yàn)位為1,奇校驗(yàn)時(shí)，校驗(yàn)位為0

■例信息字段奇校驗(yàn)碼偶校驗(yàn)碼

01100101100100110011

出錯(cuò)為：001001,0、001001A

重新計(jì)算校驗(yàn)和:

★

41不同則出錯(cuò)2012SPLENG

糾正突發(fā)錯(cuò)

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

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

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

1加101嗯01010

0D10110001001

100101001010

01001001000010

111010^1010101

422012SPLENG

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

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

CyclicRedundancy

Code)教材p165~167

-對(duì)任意位二進(jìn)制流，補(bǔ)充，000000(

m11000101

r個(gè)011100010模2力口

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

余計(jì)算，得到r位效驗(yàn)碼01001110

00000000

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

碼組11000101

-發(fā)送出去10110010

11000101

"TTTlHTnr

11000101

0101011(

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

1010110

432012SPLENG

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

10110101010110

CRC校驗(yàn)

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

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

11100000

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

余計(jì)算01001011

00000000

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

11000101

10100111

11000101

11000101

11000101

0000000Q

0000000(1

000000。

442012SPLENG

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

■基于任何一個(gè)二進(jìn)制位串組成的代碼，都可以與系

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

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

1的多項(xiàng)式

X4X3X2X1X0

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

多項(xiàng)式X4+x3+x+1

452012SPLENG

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

■1)基本思想：

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

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

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

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

出錯(cuò)，能除盡，無錯(cuò)

■2)校驗(yàn)碼與傳輸多項(xiàng)式的計(jì)算

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

X「M(X)

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

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

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

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

★

462012SPLENG

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

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

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

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

校驗(yàn)：

110口11110011

100111101100000100111101100101

C1001110011

v

—?1000010000

1001110011

1100011010

1001110011

1011010011

1001110011

01010~

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

472012SPLENG

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

■值得注意：

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

掉

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

異或運(yùn)算，相同為0,相異為工）

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

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

數(shù)為1001工）

482012SPLENG

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

■CRC碼的檢錯(cuò)性能（r個(gè)校驗(yàn)位比特）

■所有單個(gè)錯(cuò)

-所有2bit錯(cuò)

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

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

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

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

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

■常用的CRC多項(xiàng)式：

■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差錯(cuò)檢測(cè)——校驗(yàn)和

■校驗(yàn)和Checksum

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

■基本思想：

■按一定大小進(jìn)行累加

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

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

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

計(jì)算16位校驗(yàn)和ca73+Oc1e=d691

d691+ca72=1a103

1a103+2201=1c304

checksum=c304+1=3cfa

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

校驗(yàn)=1+c304+3cfa=1+fffe=02012SPLENG

ErrorControl小結(jié)疆

-檢錯(cuò)算法

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

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

■幀末尾附加了r-bit檢錯(cuò)碼（也稱校驗(yàn)碼）

-檢錯(cuò)能力

■r越大，檢錯(cuò)能力越強(qiáng)

■存在壞幀漏檢的概率

-應(yīng)用

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

本上是正確的

Frame校驗(yàn)碼

作業(yè)4

1、請(qǐng)寫出通常采用的成幀方法及各種成幀法淵

點(diǎn)。假設(shè)幀標(biāo)記符出錯(cuò)，請(qǐng)問哪種成幀方法將

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

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

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

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

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

(要求步驟)

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

設(shè)生成多項(xiàng)式為G(X)=X4+1,計(jì)算出校驗(yàn)

多項(xiàng)式R(X)o

522012SPLENG

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

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

自動(dòng)請(qǐng)求重發(fā)（ARQ）

■ARQ基本思想：

-采用檢錯(cuò)碼進(jìn)行檢錯(cuò)

■丟棄出錯(cuò)的幀

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

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

■對(duì)幀進(jìn)行確認(rèn)

■例如：

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

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

-停等協(xié)議

■回退N協(xié)議

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

532012SPLENG

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

■3.4.1停一等協(xié)議

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

■3.4.3回退N協(xié)議

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

■3.4.4雙向傳輸時(shí)的確認(rèn)

■3.4.4流量控制

542012SPLENG

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

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

■基本思想：

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

-收到肯定應(yīng)答，發(fā)送下一個(gè)新幀（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è)置定時(shí)器T,超時(shí)重發(fā)

T

重傳

□重傳

562012SPLENG

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

■還有問題要解決：

■連續(xù)丟失問題

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

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

■重復(fù)收幀問題

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

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

PDU

TT

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

PDU?丟棄

PDU無編號(hào)PDU有編號(hào)

會(huì)出錯(cuò)不出錯(cuò)2012SPLENG

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

■還有問題要解決：

■過早超時(shí)問題

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

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

■如果過早超時(shí)，且ACK無編號(hào)，則

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

■措施：對(duì)應(yīng)答編號(hào)

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

重復(fù)PDU

■過早超時(shí)，但和都編號(hào)時(shí),

PDUACK丟棄

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

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

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