《計算機網(wǎng)絡(luò)》 數(shù)據(jù)鏈路控制

集

世

靴

本章學(xué)習(xí)要點

i--------------

L流量控制的原理及方法

2.差錯檢測的原理及算法

3,差錯控制的方案

4.高級數(shù)據(jù)鏈路控制協(xié)議HDLC

數(shù)據(jù)鏈路控制是為有效進(jìn)行數(shù)據(jù)通信，對

傳輸鏈路上的信號發(fā)送進(jìn)行的控制和管理。

為此，要在物理接口之上增加數(shù)據(jù)鏈路控制

的邏輯層。

■差錯控制機制用來檢測和糾正錯誤。奇偶校

驗是一種最簡單的檢錯方法。循環(huán)冗余檢錯

CRC是一種最普遍最有效的檢錯方法。

數(shù)據(jù)傳輸中的差錯檢驗和糾正

字符代碼沿著傳輸線路向外傳送時，由于

電路設(shè)備的質(zhì)量不好，或線路上的電磁耦合噪

聲干擾等，難免發(fā)生差錯。如何及時地自動檢

驗差錯，并進(jìn)一步做到自動校正，這是數(shù)字通

信系統(tǒng)中一個重要的研究課題（稱為差錯控制

技術(shù)）。通常，其解決辦法就是采用抗干擾編

碼或糾錯編碼。

糾錯碼

糾錯碼是指在發(fā)送每一組信息時發(fā)送足夠的附加

位，接收端通過這些附加位在接收譯碼器的控制下不

僅可以發(fā)現(xiàn)錯誤，而且還能自動地糾正錯誤。如果采

用這種編碼，傳輸系統(tǒng)中不需反饋信道就可以實現(xiàn)一

個對多個用戶的通信，但譯碼器設(shè)備比較復(fù)雜，且因

所選用的糾錯碼與信道干擾情況有關(guān)。某些情況為了

糾正差錯，要求附加的冗余碼較多，這將會降低傳輸

的效率?，F(xiàn)在比較常見的糾錯編碼有：海明糾錯碼、

正反糾錯碼等。

檢錯碼

檢錯碼是指在發(fā)送每一組信息時發(fā)送一些附加位,

接收端通過這些附加位可以對所接收的數(shù)據(jù)進(jìn)行判斷

看其是否正確，如果存在錯誤，它不能糾正錯誤而是

通過反饋信道傳送一個應(yīng)答幀把這個錯誤的結(jié)果告訴

給發(fā)送端，讓發(fā)送端重新發(fā)送該信息，直至接收端收

到正確的數(shù)據(jù)為止。目前廣泛采用的檢錯碼有奇偶校

驗碼，方塊碼和循環(huán)冗余碼等。

奇偶校驗（VRC）

?奇偶校驗又叫字符校驗二是最簡單的一種校驗方法。它是在每個字符編碼的后面，

另外增加一個二進(jìn)位。該位叫做校驗位，其主要目的是使整個編碼中的“1”或“0”的

個數(shù)成為奇數(shù)或偶數(shù)。如果使編碼中“1”的個數(shù)成為奇數(shù)則叫做奇校驗，反之，則叫做

偶校驗。兩位同時出錯，無法檢錯。例如：

字符R的ASCII編碼為1010010

后面增加一位進(jìn)行奇校驗10100100

（使“工”的個數(shù)為奇數(shù)）

傳送時，其中一位出差錯10110100（奇校驗檢查出錯）

傳送時有兩位出差錯10111100（奇校驗不能檢錯）

由此可見，采用一位奇校驗（或偶校驗）只能檢驗出編碼中的一位差錯或奇數(shù)位差錯，

而不能檢驗出兩位或偶數(shù)位同時出錯。事實上，在傳輸過程中，偶然一位出錯的機會最

多，故這種簡單的檢驗方法還是很有用的。但這種辦法只能檢驗錯誤而不能糾正錯誤。

接收端檢測該校驗位以確定是否有差錯發(fā)生。奇偶校驗并不是一種十分安全可靠的檢錯

方法，如果有偶數(shù)個數(shù)據(jù)位在傳輸中同時出錯，接收端無法檢測出差錯的數(shù)據(jù)，所以其

檢錯概率最多為50%）。對于低速傳輸來說，奇偶校驗是一種令人滿意的檢錯法。通常

偶校驗常用于異步傳輸或低速傳輸，而奇校驗常用于同步傳輸。

方塊校驗(LRC)

又叫報文校驗或縱向(水平)冗余校驗LRC(levelredundancycode)0這種方法是

在垂直校驗的基礎(chǔ)上，在一批字符傳送之后，另外增加一個檢驗字符，該字符的編碼方

■去是使每一位縱向代碼中“1■”的個數(shù)成為奇數(shù)(或偶數(shù))。例如：

-奇偶校驗位(奇)

(VRC)

-字符工1010010R0

-字符21000001A1

■字符31001100L0

■字符41010000P1

-字符51001000H1

-字符61000010B1

方塊校驗符(奇)1111010Z1

■(LRC)

-采用這種校驗之后，如果其中有一個二進(jìn)位出錯，不僅從一橫行中的VRC校驗位中反映

出來，同時從一縱列的LRC校驗位中也反映出來，概括垂直和水平兩個校驗位的反映，

可以確知出錯的位置，從而加以校正。采用這種辦法之后，不僅可以檢驗出一位出錯，

而且可以自動糾正一位差錯，使誤碼率能降低2?4個數(shù)量級，糾錯效果十分顯著。

循環(huán)冗余校驗(CRC)

~循環(huán)冗余校驗法(CRC,circularredundancycode)不產(chǎn)生

奇偶校驗碼，而是把整個數(shù)據(jù)塊當(dāng)作一個連續(xù)的二進(jìn)制數(shù)據(jù)。從代數(shù)

結(jié)構(gòu)來說，將數(shù)據(jù)位串看成是系數(shù)為?；?的多項式，一個k位幀可以

看成是從xk-1到X。的k次多項式的系數(shù)序列，這個多項式的階數(shù)為

高位(最左邊)是xk-工項系數(shù)，下一位是xk-2的系數(shù)，以此類推。例

如，IIOOO工有6位，表示成多項式是X5+X4+X。。它的6個多項式系

數(shù)分別是1,1,0,0,0,和1。

多項式的運算法則是模2運算。按照它的運算法則，加法不進(jìn)位，

減法不借位。加法和減法兩者都與異或運算相同(相同數(shù)相加為0,

不同數(shù)相加為工)o這里可以看作是一報文碼多項式。在網(wǎng)絡(luò)中發(fā)送

數(shù)據(jù)塊多項式時，發(fā)送方和接收方必須事先商定一個“生成多項式”

G(x),生成多項式的最高位和最低位必須是1。要計算m位的數(shù)據(jù)

幀M(x)的校驗和，生成多項式必須比該校驗和的多項式短。

循環(huán)冗余校驗的基本思想

將校驗和加在數(shù)據(jù)幀的末尾，使這個帶校

驗和的數(shù)據(jù)幀的多項式能被生成多項式G(x)除

盡。當(dāng)接收方收到帶有校驗和的幀時，用G(x)

去除它，如果在傳送過程中無差錯，則也應(yīng)該

除盡，即余數(shù)應(yīng)為0；如果有余數(shù)，則傳輸出

錯，應(yīng)要求對方重新發(fā)送一次。

計算校驗和的算法

幅多項式G(x)為n階，在幀的末尾附加n個零,使幀為m+n

位，則相應(yīng)的多項式是2nM(X)。

-②按模2除法用對應(yīng)于G(x)的位串去除對應(yīng)于2nM(x)的位串。

■③按模2減法從對應(yīng)于2nM(X)的位串中減去余數(shù)。結(jié)果就是要傳送

帶校驗和的幀，叫多項式T(x)。

■后面的計算圖表示幀1101011011和G(x)=x4+x+l的算法。

-很清楚，T(x)能被G(x)除盡。在任何除法問題中，如果用被除數(shù)減

去余數(shù)，則剩下的部分是肯定能夠被除數(shù)除盡。例如，如果你用

100除以7,余數(shù)為2；如果先用100減去2,剩下的98就能被7除

盡?？梢哉J(rèn)為這種方法除了是G(x)整數(shù)倍數(shù)據(jù)的多項式差錯檢測不

至外，其他錯誤均能捕捉到，由此可看出它的檢錯率是非常高的。

循環(huán)冗余校驗(CRC)碼

1100001010

10011J11010110110000

10011

10011

10011

00001

口0口?？?/p>

00010

0000。

00101

00。?？?/p>

01011

0。000

o1O

-1OO1

幀：1101011011-o1o1o

OOOOO

除續(xù)：10011

o1OO

附加4個事后形成的串：11010110110000OO11

傳輸?shù)膸?1010110111110o111o

ooooo

111