《計(jì)算機(jī)網(wǎng)絡(luò)教程》第3章 數(shù)據(jù)鏈路層-2

《計(jì)算機(jī)網(wǎng)絡(luò)教程》電子教案 笫六講 海明碼與數(shù)據(jù)鏈路協(xié)議本講內(nèi)容第三章數(shù)據(jù)鏈路層

3.2差錯(cuò)檢測(cè)與校正

3.2.3常用的糾錯(cuò)碼----海明碼

3.3數(shù)據(jù)鏈路協(xié)議

3.3.1停等協(xié)議

3.3.2順序接收的管道協(xié)議

3.3.3選擇重傳協(xié)議

3.3.4流量控制的滑動(dòng)窗口機(jī)制3.2差錯(cuò)檢測(cè)與校正

常用的糾錯(cuò)碼----海明碼首先介紹一種簡單的糾錯(cuò)碼----正反碼

一種簡單的能夠糾正差錯(cuò)的編碼，其中冗余位的個(gè)數(shù)與信息位個(gè)數(shù)相同。冗余位與信息位或者完全相同或者完全相反，由信息位中“1”的個(gè)數(shù)來決定。例如電報(bào)通信中常用五單位電碼編成正反碼的規(guī)則如下：k=5,r=k=5,n=k+r=10；當(dāng)信息位中有奇數(shù)個(gè)“1”時(shí)，冗余位就是信息位的簡單重復(fù)；當(dāng)信息位中有偶數(shù)個(gè)“1”時(shí)，冗余位是信息位的反碼。具體說來，若信息位為01011，則碼字為0101101011；若信息位為10010，則碼字為1001001101。接收端的校驗(yàn)方法為：先將接收碼字中信息位和冗余位按位半加，得到一個(gè)k位的合成碼組（對(duì)上述具體的碼長為10的正反碼來說，就是得到一個(gè)5位的合成碼組）。若接收碼字中的信息位中有奇數(shù)個(gè)“1”，則就取合成碼組為校驗(yàn)碼組；若接收碼字中信息位中有偶數(shù)個(gè)“1”，則取合成碼組的反碼作為校驗(yàn)碼組。3.2差錯(cuò)檢測(cè)與校正（續(xù)）

常用的糾錯(cuò)碼----海明碼

正反碼校驗(yàn)碼組差錯(cuò)情況全“0”無差錯(cuò)4個(gè)“1”、1個(gè)“0”信息位中有一位差錯(cuò)，其位置對(duì)應(yīng)于校驗(yàn)碼組中“0”的位置4個(gè)“0”、1個(gè)“1”冗余位中有一位差錯(cuò)，其位置對(duì)應(yīng)于校驗(yàn)碼組中“1”的位置其它情況 差錯(cuò)在兩位或兩位以上3.2差錯(cuò)檢測(cè)與校正（續(xù)）

常用的糾錯(cuò)碼----海明碼

正反碼例子發(fā)送碼字為0101101011，傳輸中無差錯(cuò)，則合成碼組為01011⊕01011=00000，由于接收碼字的信息位中有3個(gè)“1”，故00000就是校驗(yàn)碼組，查前表知無差錯(cuò)。若傳輸中發(fā)生了一位差錯(cuò)，接收端收到1101101011，則合成碼組為11011⊕01011=10000，由于接收的碼字中信息位中有4個(gè)“1”，故校驗(yàn)碼組為01111。查前表知，信息位的第1位錯(cuò)，故可將接收到的1101101011糾正為0101101011。若傳輸中發(fā)生了兩位錯(cuò)，接收端收到1101111011，則合成碼組為11011⊕11011=00000，而此時(shí)校驗(yàn)碼組為11111，查前表可判斷出為兩位或兩位以上的差錯(cuò)。3.2差錯(cuò)檢測(cè)與校正（續(xù)）

常用的糾錯(cuò)碼----海明碼

例子（續(xù)）又如，若傳輸中發(fā)生了四位錯(cuò)，接收端收到1101011010，則合成碼組為11010⊕11010=00000，而此時(shí)校驗(yàn)碼組也為00000，查表會(huì)認(rèn)為是無差錯(cuò)，也就是說對(duì)這種差錯(cuò)是漏撿了。再如，若傳輸中發(fā)生了三位錯(cuò)，接收端收到1101011011，則合成碼組為11010⊕11011=00001，此時(shí)校驗(yàn)碼組也為00001，查表會(huì)認(rèn)為是冗余位中有一位差錯(cuò)，其位置對(duì)應(yīng)于校驗(yàn)碼組中“1”的位置，從而將其誤糾為1101011010。實(shí)際上，任何一種檢錯(cuò)碼，都會(huì)發(fā)生漏檢的情況；而任何一種糾錯(cuò)碼，也都會(huì)發(fā)生誤糾的情況。漏檢率和誤糾率都是差錯(cuò)控制編碼的重要技術(shù)指標(biāo)，當(dāng)然是越小差錯(cuò)控制能力越強(qiáng)。3.2差錯(cuò)檢測(cè)與校正（續(xù)）

常用的糾錯(cuò)碼----海明碼正反碼的編碼效率較低，只有1/2。但其差錯(cuò)控制能力還是較強(qiáng)，如上述長度為10的正反碼，能檢測(cè)出全部兩位差錯(cuò)和大部分兩位以上的差錯(cuò)，并且還具有糾正一位差錯(cuò)的能力。由于正反碼的編碼效率較低，只能用于信息位較短的場(chǎng)合。下面將介紹兩種編碼效率較高的，且差錯(cuò)控制能力較強(qiáng)的糾錯(cuò)和檢錯(cuò)碼。3.2差錯(cuò)檢測(cè)與校正（續(xù)）

常用的糾錯(cuò)碼----海明碼介紹由R.Hamming在1950年首次提出也是一種可以糾正一位差錯(cuò)的編碼，但當(dāng)信息位足夠長時(shí)，它的編碼效率要比正反碼高得多回顧奇偶校驗(yàn)，若信息位為k=n-1位，加上一位偶校驗(yàn)位a0，構(gòu)成一個(gè)n位的碼字。在接收端校驗(yàn)時(shí)，可按關(guān)系式 若S=0，則無錯(cuò)；若S=1，則有錯(cuò)。上式可稱為監(jiān)督關(guān)系式，S稱為校正因子3.2差錯(cuò)檢測(cè)與校正（續(xù)）

常用的糾錯(cuò)碼----海明碼在奇偶校驗(yàn)情況下，只有一個(gè)監(jiān)督關(guān)系式，一個(gè)校正因子，其取值只有兩種（0或1），分別代表了無錯(cuò)和有錯(cuò)兩種情況，而不能指出差錯(cuò)所在的位置若增加冗余位，也相應(yīng)地增加監(jiān)督關(guān)系式和校正因子，就能區(qū)分更多的情況。信息位為k位，增加r位冗余位，構(gòu)成n=k+r位碼字。若希望用r個(gè)監(jiān)督關(guān)系式產(chǎn)生的r個(gè)校正因子來區(qū)分無錯(cuò)和在碼字中n個(gè)不同位置的一位錯(cuò)，則要求或

3.2差錯(cuò)檢測(cè)與校正（續(xù)）

常用的糾錯(cuò)碼----海明碼例子以k=4為例來說明，要滿足，則r≥3。現(xiàn)取r=3，則n=k+r=7。在4位信息位

后面加上3位冗余位

，構(gòu)成7位碼字。a2、a1和a0分別由4位信息位中某幾位半加得到。那末在校驗(yàn)時(shí)，a2、a1和a0就分別和這些位半加構(gòu)成三個(gè)不同的監(jiān)督關(guān)系式。在無錯(cuò)時(shí)，這三個(gè)關(guān)系式的值S2、S1和S0全為“0”。若a2錯(cuò)，則S2=1，而S1=S0=0；若a1錯(cuò)，則S1=1,而S2=S0=0；若a0錯(cuò)，則S0=1，而S2=S1=0。S2S1S0這三個(gè)校正因子其它4種編碼的值可用來區(qū)分a3、a4、a5或a6一位錯(cuò)。3.2差錯(cuò)檢測(cè)與校正（續(xù)）

常用的糾錯(cuò)碼----海明碼

例子（續(xù)）a2、a4、a5或a6的一位錯(cuò)都應(yīng)使S2=1,由此可以得到監(jiān)督關(guān)系式000001010011100101110111錯(cuò)碼位置無錯(cuò)3.2差錯(cuò)檢測(cè)與校正（續(xù)）

常用的糾錯(cuò)碼----海明碼

例子（續(xù)）在發(fā)送端編碼時(shí)，信息位a6、a5、a4和a3的值取決于輸入信號(hào)，是隨機(jī)的。冗余位a2、a1和a0的值應(yīng)根據(jù)信息位的取值按監(jiān)督關(guān)系式來決定，使上述三式中的S2、S1和S0取值為零由此可求得已知信息位后，按此三式即可算出各冗余位。對(duì)于各種信息位算出的冗余位如后表

信息位冗余位信息位冗余位00000001000111000101110011000010101101001000111101011001010011011000010101101110101001100111110100011100011111113.2差錯(cuò)檢測(cè)與校正（續(xù)）

常用的糾錯(cuò)碼----海明碼

例子（續(xù)）在接收端收到每個(gè)碼字后，按監(jiān)督關(guān)系式算出S2、S1和S0，若為全“0”則認(rèn)為無錯(cuò)。若不全為“0”，在一位錯(cuò)的情況下，可查表來判定是哪一位錯(cuò)，從而糾正之。例如碼字0010101傳輸中發(fā)生一位錯(cuò)，在接收端收到的為0011101，代入監(jiān)督關(guān)系式可算得S2=0、S1=1和S0=1，由查表得S2S1S0=011對(duì)應(yīng)于a3錯(cuò)，因而可將0011101糾正為0010101。但是，若碼字0010101傳輸中發(fā)生兩位錯(cuò)，在接收端收到的為0011111，代入監(jiān)督關(guān)系式可算得S2=0、S1=0和S0=1，查表得S2S1S0=001對(duì)應(yīng)于a0錯(cuò)，從而會(huì)將0011111糾正為0011110，這就是誤糾的情況。=16＞7+4+1=12再如，若碼字0010101傳輸中發(fā)生三位錯(cuò)，在接收端收到的為0101101，代入監(jiān)督關(guān)系式可算得S2=0、S1=0和S0=0，查表可得S2S1S0=000對(duì)應(yīng)于無錯(cuò)，從而認(rèn)為傳輸中無差錯(cuò)，這就是漏檢的情況。我們這個(gè)例子中正好=k+r+1，若

＞k+r+1則在查表中還有多余的位置可用來表示兩位以上的錯(cuò)誤，就可降低漏檢率了。比如，若k=7，則滿足

＞k+r+1的最小r為4。此時(shí)r23.2差錯(cuò)檢測(cè)與校正（續(xù)）

常用的糾錯(cuò)碼----海明碼上述例子中，k=4的海明碼的編碼效率為4/7；若k=7，則編碼效率為7/11。由此可見，信息位長度越長時(shí)編碼效率越高。只能糾正一位錯(cuò)，若用在糾正傳輸中出現(xiàn)突發(fā)性差錯(cuò)時(shí)可以采用下述方法：將連續(xù)P個(gè)碼字排成一個(gè)矩陣，每行一個(gè)碼字圖3.6海明碼用于糾正突發(fā)錯(cuò)誤的情況本講內(nèi)容第三章數(shù)據(jù)鏈路層 3.2差錯(cuò)檢測(cè)與校正 3.2.3常用的糾錯(cuò)碼----海明碼 3.3數(shù)據(jù)鏈路協(xié)議

3.3.1停等協(xié)議

3.3.2順序接收的管道協(xié)議

3.3.3選擇重傳協(xié)議

3.3.4流量控制的滑動(dòng)窗口機(jī)制3.3數(shù)據(jù)鏈路協(xié)議將由簡單到復(fù)雜介紹三個(gè)數(shù)據(jù)鏈路層的協(xié)議。簡單的模型該模型中有兩個(gè)主機(jī)A和B交換報(bào)文。它們各自連接到一個(gè)節(jié)點(diǎn)機(jī)，分別為節(jié)點(diǎn)機(jī)A和B。節(jié)點(diǎn)A和B之間有物理信道直接相連，通過在其上建立的數(shù)據(jù)鏈路可以交換由報(bào)文構(gòu)成的幀。

3.3數(shù)據(jù)鏈路協(xié)議

停等協(xié)議最簡單的停等（stop-and-wait）協(xié)議

這個(gè)協(xié)議規(guī)定發(fā)送方每發(fā)送一幀后就要停下來，等待對(duì)方已正確接收的確認(rèn)（Acknowledgement，Ack）幀返回后才能繼續(xù)發(fā)送下一幀(下面使用類java語言)Senderwhile(1){ transmit(frame); try{ receive(ack); }catch(timeout){ retransmit(frame); } getnewframe}Receiverwhile(1){ receive(frame); transmit(ack);}3.3數(shù)據(jù)鏈路協(xié)議（續(xù)）

停等協(xié)議

對(duì)前面的改進(jìn)：必須將發(fā)送的數(shù)據(jù)幀編以序號(hào)來區(qū)分是新發(fā)送的幀還是重新發(fā)送的幀確認(rèn)幀Ack也應(yīng)加上序號(hào)以表示是確認(rèn)哪一幀用類JAVA代碼來描述己加上數(shù)據(jù)幀序號(hào)和確認(rèn)幀序號(hào)的停等協(xié)議執(zhí)行過程，如后面一頁所示：3.3數(shù)據(jù)鏈路協(xié)議（續(xù)）

停等協(xié)議Sendernext_frame_to_send=0;while(1){transmit(framenext_frame_to_send);try{while(1){receive(ackn);if(n!=next_frame_to_send)continue;}}catch(timeout){retransmit(frame);}

next_frame_to_send++;}Receiverframe_expected=0;while(1){receive(framen);ack(framen);if(n!=frame_expected)continue;

frame_expected++;}再加上接收方校驗(yàn)的過程后停等協(xié)議發(fā)送方和接收方運(yùn)行的流程示意圖接受方0→期待幀號(hào)期待幀號(hào)⊕1→期待幀號(hào)恢復(fù)報(bào)文送主機(jī)等待校驗(yàn)和檢查收到幀的Seq=期待幀號(hào)確認(rèn)幀號(hào)Ack=Seq(返回)不對(duì)對(duì)對(duì)不對(duì)數(shù)據(jù)幀到達(dá)0→發(fā)送幀號(hào)從主機(jī)取報(bào)文裝配幀(seq=發(fā)送幀號(hào))發(fā)送,并置計(jì)時(shí)器等待Ack=發(fā)送幀號(hào)發(fā)送幀號(hào)⊕1→發(fā)送幀號(hào)發(fā)送方對(duì)不對(duì)計(jì)時(shí)器超時(shí)發(fā)送數(shù)據(jù)幀返回Ack幀3.3數(shù)據(jù)鏈路協(xié)議（續(xù)）

停等協(xié)議停等協(xié)議的最大缺點(diǎn)是由于發(fā)送方要停下來等待Ack返回后再繼續(xù)發(fā)送而造成信道的浪費(fèi)。設(shè)信道容量是Bbps，幀長度為Lbits，信號(hào)在信道中的往返傳播延遲時(shí)間（propagationdelay）是2R，并假定返回的Ack幀很短，不占用信道時(shí)間。在一個(gè)周期中實(shí)際用于發(fā)送的時(shí)間是L/B。而空等待的時(shí)間是2R。因此，信道的實(shí)際有效利用率只有

停等協(xié)議的信道利用率

實(shí)際上，若由于信道差錯(cuò)而收不到Ack而造成超時(shí)重傳以及有效傳送的數(shù)據(jù)必須加上幀頭（包括用于校驗(yàn)的冗余位）構(gòu)成幀來發(fā)送，它們也都會(huì)造成信道有效利用率的損失。B為信道容量（b/s） R為單程傳播延遲時(shí)間（s） L為數(shù)據(jù)幀長度（bits） 并設(shè)

D為幀內(nèi)有效數(shù)據(jù)的長度（bits）

H為幀頭的長度（bits） 顯然有，L=H+D。 另外，可以認(rèn)為Ack幀不含有用戶數(shù)據(jù)，故其長度亦為H。又令

T表示等待Ack的超時(shí)間隔時(shí)間（s）

P1和P2分別表示數(shù)據(jù)幀和Ack幀出錯(cuò)或丟失的概率 則每個(gè)數(shù)據(jù)幀不能正確發(fā)送和收到確認(rèn)ACK的概率為從而可求得最終發(fā)送成功所需的平均發(fā)送次數(shù)為

或者說，平均重傳次數(shù)為

在時(shí)間內(nèi)，真正用來發(fā)送有效用戶數(shù)據(jù)的時(shí)間僅為D/B，即信道有效利用率為信通利用率的分析超時(shí)間隔T必須取得足夠大，即T≥H/B+2R，才能使得在發(fā)送成功時(shí)不會(huì)由于太早超時(shí)而誤重傳。為了使U達(dá)到最大，可取T=H/B+2R。此時(shí)有停等協(xié)議的捎帶確認(rèn)3.3數(shù)據(jù)鏈路協(xié)議

順序接收的管道協(xié)議使用管道協(xié)議：可以提高信道的有效利用率，就要允許發(fā)送方不等確認(rèn)幀返回就再連續(xù)發(fā)送若干幀由于允許連續(xù)發(fā)出多個(gè)未被確認(rèn)的幀，幀號(hào)就不能僅采用一位（只有0和1兩種幀號(hào)），而要采用多位幀號(hào)才能區(qū)分凡是被發(fā)送出去尚未被確認(rèn)的幀都可能出錯(cuò)或丟失而要求重發(fā)，因而都要保留下來。這就要求發(fā)送方有較大的發(fā)送緩沖區(qū)保留準(zhǔn)備重發(fā)的幀3.3數(shù)據(jù)鏈路協(xié)議（續(xù)）

順序接收的管道協(xié)議“回退n”（gobackn）3.3數(shù)據(jù)鏈路協(xié)議（續(xù)）

順序接收的管道協(xié)議回退n的缺陷：允許已發(fā)送未被確認(rèn)的幀越多，可能要退回來重發(fā)的幀也越多改進(jìn)：發(fā)送窗口為了控制發(fā)送方的發(fā)送速度以及受發(fā)送緩沖區(qū)大小的制約等因素都要求對(duì)發(fā)送方已發(fā)出但尚未經(jīng)確認(rèn)的幀的數(shù)目加以限制，這個(gè)數(shù)目就是“發(fā)送窗口”落在這個(gè)窗口內(nèi)的幀號(hào)就是等待接收返回的Ack信息的幀號(hào)。由于幀號(hào)只有有限的位數(shù)，到一定時(shí)間后就又反復(fù)循環(huán)了3.3數(shù)據(jù)鏈路協(xié)議

選擇重傳協(xié)議選擇重傳（selectiverepeat）的