計(jì)算機(jī)網(wǎng)絡(luò)3新

數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)二OO九年九月1第三章數(shù)據(jù)鏈路層本章重點(diǎn)：

數(shù)據(jù)鏈路層的主要功能和特點(diǎn)，通信過(guò)程中與數(shù)據(jù)鏈路層相關(guān)的操作，常用的差錯(cuò)控制編碼技術(shù)，數(shù)據(jù)鏈路層協(xié)議。

本章難點(diǎn)：

數(shù)據(jù)鏈路層在網(wǎng)絡(luò)通信中的作用，差錯(cuò)控制編碼技術(shù)。

數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室2第三章數(shù)據(jù)鏈路層本章內(nèi)容：

3.1數(shù)據(jù)鏈路層的功能3.2差錯(cuò)檢測(cè)與校正3.3數(shù)據(jù)鏈路層協(xié)議3.4協(xié)議描述與驗(yàn)證3.5數(shù)據(jù)鏈路層協(xié)議舉例

數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室3第三章數(shù)據(jù)鏈路層3.1數(shù)據(jù)鏈路層的功能3.1.1幀同步★3.1.2差錯(cuò)控制3.1.3流量控制★3.1.4鏈路管理★3.2差錯(cuò)檢測(cè)與校正3.3數(shù)據(jù)鏈路層協(xié)議3.4協(xié)議描述與驗(yàn)證3.5數(shù)據(jù)鏈路層協(xié)議舉例

數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室4數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室由差錯(cuò)控制碼產(chǎn)生的校驗(yàn)和可以檢查出一幀在傳輸中是否發(fā)生了錯(cuò)誤。一旦檢查出錯(cuò)誤后，通常采用反饋重發(fā)的方法來(lái)糾正錯(cuò)誤。

實(shí)現(xiàn)復(fù)雜一點(diǎn)的機(jī)制，要用：保留己發(fā)的幀：以便出錯(cuò)后重發(fā)計(jì)時(shí)器(timer)：避免無(wú)限等待幀編號(hào)：保證每幀最終都能正確地交付給接收方網(wǎng)絡(luò)層一次5第三章數(shù)據(jù)鏈路層3.1數(shù)據(jù)鏈路層的功能3.1.1幀同步★3.1.2差錯(cuò)控制3.1.3流量控制★3.1.4鏈路管理★3.2差錯(cuò)檢測(cè)與校正3.3數(shù)據(jù)鏈路層協(xié)議3.4協(xié)議描述與驗(yàn)證3.5數(shù)據(jù)鏈路層協(xié)議舉例

數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室6第三章數(shù)據(jù)鏈路層3.1

數(shù)據(jù)鏈路層的功能3.2差錯(cuò)檢測(cè)與校正3.2.1傳輸差錯(cuò)的特性3.2.2常用的簡(jiǎn)單差錯(cuò)控制編碼3.2.3海明碼3.2.4循環(huán)冗余碼3.3數(shù)據(jù)鏈路層協(xié)議3.4協(xié)議描述與驗(yàn)證3.5數(shù)據(jù)鏈路層協(xié)議舉例

數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室7數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室傳輸中的差錯(cuò)都是由于噪聲引起的。噪聲分類：信道所固有的，持續(xù)存在的隨機(jī)熱噪聲由于外界特定的短暫原因所造成的沖擊噪聲噪聲比較：隨機(jī)錯(cuò)通常較少，造成某些碼元的差錯(cuò)是孤立的沖擊噪聲的幅度可以相當(dāng)大，它是傳輸中產(chǎn)生差錯(cuò)的重要原因8數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室衡量一個(gè)信道質(zhì)量的重要參數(shù)是誤碼率：通常用10的負(fù)若干次方來(lái)標(biāo)志信道的誤碼率Pe。

例子：在一條話頻線路中，誤碼率若為，則意味著平均十萬(wàn)位中有一位出錯(cuò)。差錯(cuò)控制最常用的方法是差錯(cuò)控制編碼。9數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室差錯(cuò)控制編碼的原理：發(fā)送與接收的過(guò)程：發(fā)送時(shí)：信息位+冗余位構(gòu)成碼字發(fā)送；接收時(shí)：收到碼字后查看信息位和冗余位，并檢查它們之間的關(guān)系（校驗(yàn)過(guò)程），以發(fā)現(xiàn)傳輸過(guò)程中是否有差錯(cuò)發(fā)生。差錯(cuò)控制編碼分類：檢錯(cuò)碼指能自動(dòng)發(fā)現(xiàn)差錯(cuò)的編碼糾錯(cuò)碼指不僅能發(fā)現(xiàn)差錯(cuò)而且能自動(dòng)糾正差錯(cuò)的編碼10數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室衡量編碼性能的參數(shù)編碼效率R碼字中信息位所占的比例若碼字中信息位為k位，編碼時(shí)外加冗余位為r位，則編碼后得到的碼字長(zhǎng)為n=k+r位。

判定規(guī)律編碼效率越高，即R越大，則信道中用來(lái)傳送信息碼元的有效利用率就越高。11數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室數(shù)據(jù)通信中，利用編碼方法來(lái)進(jìn)行差錯(cuò)控制的方式，基本上有兩類：自動(dòng)請(qǐng)求重發(fā)ARQ（AutomaticReQuestforrepeat）接收端檢測(cè)出有差錯(cuò)時(shí)，就設(shè)法通知發(fā)送端重發(fā)，直到正確的碼字收到為止。前向糾錯(cuò)FEC（ForwardErrorCorrection）接收端不但能發(fā)現(xiàn)差錯(cuò)，而且能確定二進(jìn)制錯(cuò)碼元的位置，從而就可以加以糾正。12第三章數(shù)據(jù)鏈路層3.1

數(shù)據(jù)鏈路層的功能3.2差錯(cuò)檢測(cè)與校正3.2.1傳輸差錯(cuò)的特性3.2.2常用的簡(jiǎn)單差錯(cuò)控制編碼3.2.3海明碼3.2.4循環(huán)冗余碼3.3數(shù)據(jù)鏈路層協(xié)議3.4協(xié)議描述與驗(yàn)證3.5數(shù)據(jù)鏈路層協(xié)議舉例

數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室133.2.2常用的簡(jiǎn)單差錯(cuò)控制編碼將介紹奇偶校驗(yàn)碼、定比碼和正反碼等三種較為實(shí)用的簡(jiǎn)單編碼奇偶校驗(yàn)碼奇偶校驗(yàn)碼是通過(guò)增加冗余位來(lái)使得碼字中“1”的個(gè)數(shù)保持奇或偶數(shù)的編碼方法，是一種檢錯(cuò)碼分類：垂直奇偶校驗(yàn)水平奇偶校驗(yàn)水平垂直奇偶校驗(yàn)數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室14奇偶校驗(yàn)碼

－－－垂直奇偶校驗(yàn)垂直奇偶校驗(yàn)是將整個(gè)發(fā)送的信息塊分為定長(zhǎng)p位的若干段（比如說(shuō)q段），每段后面按“1”的個(gè)數(shù)為奇或偶數(shù)的規(guī)律加上一位奇偶位圖3.1垂直奇偶校驗(yàn)數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室15垂直奇偶校驗(yàn)圖中，pq位信息位（I11，I21，…，IP1，I12，…，Ipq）中，p位構(gòu)成一段（即圖中一列），共q段（即共有q列）。每段加上一位奇偶校驗(yàn)冗余位，即圖中的ri(i=1,2,…,q)。若用偶校驗(yàn)，則若用奇校驗(yàn)，則編碼效率：數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室16奇偶校驗(yàn)碼

－－－水平奇偶校驗(yàn)水平奇偶檢驗(yàn)。它是對(duì)各個(gè)信息段的相應(yīng)位橫向進(jìn)行編碼，產(chǎn)生一個(gè)奇偶校驗(yàn)冗余位。（i=1,2,…,p）或（i=1,2,…,p）編碼效率為圖3.2水平奇偶校驗(yàn)數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室17奇偶校驗(yàn)碼

－－－水平垂直奇偶校驗(yàn)同時(shí)進(jìn)行水平奇偶校驗(yàn)和垂直奇偶校驗(yàn)就構(gòu)成水平垂直奇偶校驗(yàn)

圖3.3水平垂直奇偶校驗(yàn)數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室18奇偶校驗(yàn)碼

－－－水平垂直奇偶校驗(yàn)（續(xù)）水平垂直奇偶校驗(yàn)的編碼效率為它能檢測(cè)出所有3位或3位以下的錯(cuò)誤（因?yàn)榇藭r(shí)至少在某一行或某一列上為一位錯(cuò)）、奇數(shù)位錯(cuò)、突發(fā)長(zhǎng)度≤p+1的突發(fā)錯(cuò)以及很大一部分偶數(shù)位錯(cuò)。數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室19例子由6個(gè)字符的7位ASCII編碼排列，再加上水平垂直奇偶校驗(yàn)位構(gòu)成下列矩陣（最后一列為水平奇偶校驗(yàn)位，最后一行為垂直奇偶校驗(yàn)位）:字符7位ASCII碼HP30X1X200110Y1100100X31+X41010110Y201X5X61111D100X710X80=0X9111X1011VP00111X111X12數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室20例子則X1X2X3X4處的比特分別為____；X5X6X7X8處的比特分別為____；X9X10XI1X12處的比特分別為____；Y1和Y2處的字符分別為____和____。答案X1X2X3X4=1110X5X6X7X8=1000X9X10X11X12=1011Y1即是“I”Y2即是“7”數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室21奇偶校驗(yàn)碼小結(jié)水平垂直奇偶校驗(yàn)不僅可檢錯(cuò)，還可用來(lái)糾正部分差錯(cuò)。垂直奇偶校驗(yàn)有時(shí)又稱為縱向奇偶校驗(yàn)水平奇偶校驗(yàn)有時(shí)又稱為橫向奇偶校驗(yàn)水平垂直奇偶校驗(yàn)則又稱為縱橫奇偶校驗(yàn)數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室22定比碼每個(gè)碼字中均含有相同數(shù)目的“1”（碼字長(zhǎng)一定，“1”的數(shù)目一定后，所含“0”的數(shù)目也就必然相同）。正由于每個(gè)碼字中“1”的個(gè)數(shù)與“0”的個(gè)數(shù)之比保持恒定，故得此名，有時(shí)也稱為恒比碼若n位碼字中“1”的個(gè)數(shù)恒定為m，還可稱為“n中取m”碼。這種碼在檢測(cè)時(shí)，只要計(jì)算接收碼字中“1”的數(shù)目，就能知道是否有差錯(cuò)在國(guó)際無(wú)線電報(bào)通信中廣泛采用的就是7中取3定比碼。這種碼字長(zhǎng)為7位，規(guī)定總有3個(gè)“1”。共有

種碼字，可用來(lái)分別代表26個(gè)英文字母和其它符號(hào)數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室23定比碼（n中取m）的編碼效率為對(duì)于7中取3碼來(lái)說(shuō)，其編碼效率是不高的。但是，定比碼能檢測(cè)出全部奇數(shù)位錯(cuò)以及部分偶數(shù)位錯(cuò)。實(shí)際上，除了碼字中“1”變成“0”和“0”變成“1”成對(duì)出現(xiàn)的差錯(cuò)外，所有其它差錯(cuò)都能被檢測(cè)出來(lái)，檢錯(cuò)能力還是很強(qiáng)的若信源產(chǎn)生的是隨機(jī)的二進(jìn)制數(shù)字序列，就不能采用定比碼了。數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室24正反碼一種簡(jiǎn)單的能夠糾正差錯(cuò)的編碼，其中冗余位的個(gè)數(shù)與信息位個(gè)數(shù)相同。冗余位與信息位或者完全相同或者完全相反，由信息位中“1”的個(gè)數(shù)來(lái)決定。校驗(yàn)的關(guān)鍵是記住其方法:在假設(shè)出錯(cuò)位數(shù)較少的前提下,計(jì)算合成碼組(由信息位與冗余位的半加和),再形成校驗(yàn)碼組(僅當(dāng)信息位中有偶數(shù)個(gè)“1”時(shí)取此合成碼組的反碼)，然后根據(jù)校驗(yàn)碼組查表判斷是否有差錯(cuò)及糾正部分差錯(cuò)。數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室25正反碼（續(xù)）校驗(yàn)碼組差錯(cuò)情況全“0”無(wú)差錯(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ò)在兩位或兩位以上數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室26正反碼的編碼效率較低，只有1/2。但其差錯(cuò)控制能力還是較強(qiáng)，如上述長(zhǎng)度為10的正反碼，能檢測(cè)出全部?jī)晌徊铄e(cuò)和大部分兩位以上的差錯(cuò)，并且還具有糾正一位差錯(cuò)的能力。由于正反碼的編碼效率較低，只能用于信息位較短的場(chǎng)合。下面將介紹兩種編碼效率較高的，且差錯(cuò)控制能力較強(qiáng)的糾錯(cuò)和檢錯(cuò)碼。數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室27第三章數(shù)據(jù)鏈路層3.1

數(shù)據(jù)鏈路層的功能3.2差錯(cuò)檢測(cè)與校正3.2.1傳輸差錯(cuò)的特性3.2.2常用的簡(jiǎn)單差錯(cuò)控制編碼3.2.3海明碼3.2.4循環(huán)冗余碼3.3數(shù)據(jù)鏈路層協(xié)議3.4協(xié)議描述與驗(yàn)證3.5數(shù)據(jù)鏈路層協(xié)議舉例

數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室28數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室海明碼是一種多重(復(fù)式)奇偶檢錯(cuò)系統(tǒng)。它將信息用邏輯形式編碼，以便能夠檢錯(cuò)和糾錯(cuò)。用在海明碼中的全部傳輸碼字是由原來(lái)的信息和附加的奇偶校驗(yàn)位組成的。每一個(gè)這種奇偶位被編在傳輸碼字的特定位置上。推導(dǎo)并使用長(zhǎng)度為m位的碼字的海明碼，所需步驟如下：

確定最小的校驗(yàn)位數(shù)k，將它們記成D1、D2、…、Dk，每個(gè)校驗(yàn)位符合不同的奇偶測(cè)試規(guī)定。原有信息和k個(gè)校驗(yàn)位一起編成長(zhǎng)為m+k位的新碼字。選擇k校驗(yàn)位（0或1）以滿足必要的奇偶條件。對(duì)所接收的信息作所需的k個(gè)奇偶檢查。如果所有的奇偶檢查結(jié)果均為正確的，則認(rèn)為信息無(wú)錯(cuò)誤。29數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室校驗(yàn)位數(shù)：信息位為m位，校驗(yàn)位為k，碼字長(zhǎng)為m+k位，m和k滿足如下關(guān)系式：2k≥m＋k＋1碼字格式：理論上講可放在任何位置，但習(xí)慣上校驗(yàn)位被安排在1,2,4,8…位置上。

m=4，k=3時(shí)，信息位和校驗(yàn)位的分布情況。

30數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室k個(gè)校驗(yàn)位是通過(guò)對(duì)m+k位復(fù)合碼字進(jìn)行奇偶校驗(yàn)而確定的。其中：P1位負(fù)責(zé)校驗(yàn)海明碼的第1、3、5、7、…（P1、D1、D2、D4、…）位，（包括P1自己）P2負(fù)責(zé)校驗(yàn)海明碼的第2、3、6、7、…（P2、D1、D3、D4、…）位，（包括P2自己）P3負(fù)責(zé)校驗(yàn)海明碼的第4、5、6、7、…（P3、D2、D3、D4、…）位，（包括P3自己）31數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室對(duì)m=4，k=3，偶校驗(yàn)的例子，進(jìn)行三次偶性測(cè)試。這些測(cè)試（以A、B、C表示）在下圖所示各位的位置上進(jìn)行。A=B1⊕B3⊕B5⊕B7=0得P1=D1⊕D2⊕D4B=B2⊕B3⊕B6⊕B7=0得P2=D1⊕D3⊕D4C=B4⊕B5⊕B6⊕B7=0得P3=D2⊕D3⊕D432數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室1001100編碼后的海明碼---1-00校驗(yàn)位100-1--信息碼D4D3D2P3D1P2P1碼位類型B7B6B5B4B3B2B1碼字位置例子：若四位信息碼為1001，求編碼后的海明碼（m＝4，k＝3）？33數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室上面是發(fā)送方的處理，在接收方，也可根據(jù)這三個(gè)校驗(yàn)方程對(duì)接收到的信息進(jìn)行同樣的奇偶測(cè)試。A=B1⊕B3⊕B5⊕B7=0；B=B2⊕B3⊕B6⊕B7=0；C=B4⊕B5⊕B5⊕B7=0。若三個(gè)校驗(yàn)方程都成立,即方程式右邊都等于0，則說(shuō)明沒有錯(cuò)。若不成立即方程式右邊不等于0，說(shuō)明有錯(cuò)。34第三章數(shù)據(jù)鏈路層3.1

數(shù)據(jù)鏈路層的功能3.2差錯(cuò)檢測(cè)與校正3.2.1傳輸差錯(cuò)的特性3.2.2常用的簡(jiǎn)單差錯(cuò)控制編碼3.2.3海明碼3.2.4循環(huán)冗余碼3.3數(shù)據(jù)鏈路層協(xié)議3.4協(xié)議描述與驗(yàn)證3.5數(shù)據(jù)鏈路層協(xié)議舉例

數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室35數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室循環(huán)冗余碼（CRC）又稱多項(xiàng)式碼。這是因?yàn)槿魏我粋€(gè)由二進(jìn)制數(shù)位串組成的代碼都可以和一個(gè)只含有0和1兩個(gè)系數(shù)的多項(xiàng)式建立一一對(duì)應(yīng)的關(guān)系。循環(huán)冗余校驗(yàn)碼（CRC）的基本原理是：在K位信息碼后再拼接R位的校驗(yàn)碼，整個(gè)編碼長(zhǎng)度為N位，因此，這種編碼又叫（N，K）碼。對(duì)于一個(gè)給定的（N，K）碼，可以證明存在一個(gè)最高次冪為N-K=R的多項(xiàng)式G(x)。根據(jù)G(x)可以生成K位信息的校驗(yàn)碼，而G(x)叫做這個(gè)CRC碼的生成多項(xiàng)式。36數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室校驗(yàn)碼的具體生成過(guò)程為：假設(shè)發(fā)送信息用信息多項(xiàng)式C(X)表示，將C(x)左移R位，則可表示成C(x)*2R，這樣C(x)的右邊就會(huì)空出R位，這就是校驗(yàn)碼的位置。通過(guò)C(x)*2R除以生成多項(xiàng)式G(x)得到的余數(shù)就是校驗(yàn)碼。

CRC碼的生成步驟

1、將x的最高冪次為R的生成多項(xiàng)式G(x)轉(zhuǎn)換成對(duì)應(yīng)的R+1位二進(jìn)制數(shù)。2、將信息碼左移R位，相當(dāng)與對(duì)應(yīng)的信息多項(xiàng)式C(x)*2R3、用生成多項(xiàng)式（二進(jìn)制數(shù)）對(duì)信息碼做模2除，得到R位的余數(shù)。4、將余數(shù)拼到信息碼左移后空出的位置，得到完整的CRC碼。

37例子假設(shè)使用的生成多項(xiàng)式是G(x)=x3+x+1。4位的原始報(bào)文為1010，求編碼后的報(bào)文。

解：1、將生成多項(xiàng)式G(x)=x3+x+1轉(zhuǎn)換成對(duì)應(yīng)的二進(jìn)制除數(shù)1011。2、此題生成多項(xiàng)式有4位（R+1），要把原始報(bào)文C(x)左移3（R）位變成10100003、用生成多項(xiàng)式對(duì)應(yīng)的二進(jìn)制數(shù)對(duì)左移4位后的原始報(bào)文進(jìn)行模2除被除數(shù)：1010000；除數(shù)：1011；商：1001；余數(shù)：011（校驗(yàn)碼）4、編碼后的報(bào)文（CRC）：1010011數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室38數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室CRC的檢錯(cuò)和糾錯(cuò)

在接收端收到了CRC碼后用生成多項(xiàng)式為G(x)去做模2除，若得到余數(shù)為0,則碼字無(wú)誤。若如果有一位出錯(cuò)，則余數(shù)不為0，而且不同位出錯(cuò)，其余數(shù)也不同。余數(shù)與出錯(cuò)位的對(duì)應(yīng)關(guān)系只與碼制及生成多項(xiàng)式有關(guān)，而與待測(cè)碼字（信息位）無(wú)關(guān)。011出錯(cuò)位余數(shù)收到的CRC碼字A1A2A3A4A5A6A711001011100100110011111000011101101111010110001010100101碼字正確000錯(cuò)誤001010100110111101無(wú)1234567圖（7，4）CRC碼的出錯(cuò)模式（G(x)＝1011）393.3某信道誤碼率為10-5，每幀長(zhǎng)度為10kbits，那末(1)若差錯(cuò)都是單個(gè)錯(cuò)，則在該信道上傳送的幀的平均出錯(cuò)率是多少？(2)若差錯(cuò)大多為突發(fā)錯(cuò)，平均突發(fā)長(zhǎng)度為100bits，則在該信道上傳送的幀的平均出錯(cuò)率是多少？3.9

若信息位為7位，要構(gòu)成能糾正一位錯(cuò)的海明碼，則至少要加上多少位冗余位？并寫出其監(jiān)督關(guān)系式。

3.11已知海明碼的監(jiān)督關(guān)系式為s0=a0+a3+a5+a6s1=a1+a4+a5+a6 s2=a2+a3+a4+a5接收端收到的碼字a6a5a4a3a2a1a0=1011110，在最多一位錯(cuò)的情況下，問(wèn)發(fā)送端發(fā)送的碼字是什么？3.14

已知循環(huán)冗余碼的生成多項(xiàng)式G（X）=x5+x4+x+1，若接收方收到的碼字為11，問(wèn)傳輸中是否有差錯(cuò)？

數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室40第三章數(shù)據(jù)鏈路層3.1

數(shù)據(jù)鏈路層的功能3.2差錯(cuò)檢測(cè)與校正3.2.1傳輸差錯(cuò)的特性3.2.2常用的簡(jiǎn)單差錯(cuò)控制編碼3.2.3海明碼3.2.4

循環(huán)冗余碼3.3數(shù)據(jù)鏈路層協(xié)議3.4協(xié)議描述與驗(yàn)證3.5數(shù)據(jù)鏈路層協(xié)議舉例

數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室41第三章數(shù)據(jù)鏈路層3.1

數(shù)據(jù)鏈路層的功能3.2差錯(cuò)檢測(cè)與校正3.3數(shù)據(jù)鏈路層協(xié)議3.3.1停等協(xié)議3.3.2順序接收的管道協(xié)議3.3.3選擇重傳協(xié)議3.4協(xié)議描述與驗(yàn)證3.5數(shù)據(jù)鏈路層協(xié)議舉例

數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室42一種無(wú)限制的單工協(xié)議鏈路是理想的傳輸通道，所傳輸?shù)臄?shù)據(jù)即不會(huì)出錯(cuò)，也不會(huì)丟失不管發(fā)送方以什么速率傳送數(shù)據(jù)，接收方都能及時(shí)接收數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室43一種無(wú)限制的單工協(xié)議數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室voidsender1(void){frames;packetbuffer;while(true){from_network_layer(&buffer);=buffer;to_physical_layer(&s);}}44一種無(wú)限制的單工協(xié)議數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室voidreceiver1(void){framer;event_typeevent;while(true){wait_for_event(&event);from_physical_layer(&r);to_network_layer(&);}}45一種單工的停等協(xié)議鏈路是理想的傳輸通道，所傳輸?shù)臄?shù)據(jù)即不會(huì)出錯(cuò)，也不會(huì)丟失即不需校驗(yàn)，也不需要重發(fā)數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室46一種單工的停等協(xié)議數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室voidsender2(void){frames;packetbuffer;event_typeevent;while(true){from_network_layer(&buffer);=buffer;to_physical_layer(&s);wait_for_event(&event);}}47一種單工的停等協(xié)議數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室voidreceiver2(void){framer,s;event_typeevent;while(true){wait_for_event(&event);from_physical_layer(&r);to_network_layer(&);to_physical_layer(&s);}}48對(duì)前面的改進(jìn)：必須將發(fā)送的數(shù)據(jù)幀編以序號(hào)來(lái)區(qū)分是新發(fā)送的幀還是重新發(fā)送的幀確認(rèn)幀Ack也應(yīng)加上序號(hào)以表示是確認(rèn)哪一幀用算法來(lái)描述己加上數(shù)據(jù)幀序號(hào)和確認(rèn)幀序號(hào)的停等協(xié)議執(zhí)行過(guò)程，如后面一頁(yè)所示：數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室49接受方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幀數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室50Sendernext_frame_to_send=0;while(true){transmit(framenext_frame_to_send);try{while(true){receive(ackn);if(n!=next_frame_to_send)continue;}}catch(timeout){retransmit(frame);}

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

frame_expected++;}數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室51停等協(xié)議的最大缺點(diǎn)是由于發(fā)送方要停下來(lái)等待Ack返回后再繼續(xù)發(fā)送而造成信道的浪費(fèi)。設(shè)信道容量是Bbps，幀長(zhǎng)度為L(zhǎng)bits，信號(hào)在信道中的往返傳播延遲時(shí)間（propagationdelay）是2R，并假定返回的Ack幀很短，不占用信道時(shí)間。在一個(gè)周期中實(shí)際用于發(fā)送的時(shí)間是L/B。而空等待的時(shí)間是2R。因此，信道的實(shí)際有效利用率只有

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

數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室52停等協(xié)議的捎帶確認(rèn)數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室53第三章數(shù)據(jù)鏈路層3.1

數(shù)據(jù)鏈路層的功能3.2差錯(cuò)檢測(cè)與校正3.3數(shù)據(jù)鏈路層協(xié)議3.3.1停等協(xié)議3.3.2順序接收的管道協(xié)議3.3.3選擇重傳協(xié)議3.4協(xié)議描述與驗(yàn)證3.5數(shù)據(jù)鏈路層協(xié)議舉例

數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室54使用管道協(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ā)，因而都要保留下來(lái)。這就要求發(fā)送方有較大的發(fā)送緩沖區(qū)保留準(zhǔn)備重發(fā)的幀

數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室55“回退n”（gobackn）數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室56回退n的缺陷：允許已發(fā)送未被確認(rèn)的幀越多，可能要退回來(lái)重發(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)了數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室57滑動(dòng)窗口（slidingwindow）協(xié)議若幀號(hào)取3位（即000~111，或0號(hào)到7號(hào)），發(fā)送窗口取值為2，則發(fā)送的過(guò)程圖中發(fā)送方陰影所示代表了發(fā)送窗口，而接收方陰影所示則可相應(yīng)地被視為接收窗口。在進(jìn)行的過(guò)程中，窗口位置一直在滑動(dòng)（停等協(xié)議可以看成是發(fā)送窗口等于1的滑動(dòng)窗口協(xié)議的特例）數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室58第三章數(shù)據(jù)鏈路層3.1

數(shù)據(jù)鏈路層的功能3.2差錯(cuò)檢測(cè)與校正3.3數(shù)據(jù)鏈路層協(xié)議3.3.1停等協(xié)議3.3.2順序接收的管道協(xié)議3.3.3選擇重傳協(xié)議3.4協(xié)議描述與驗(yàn)證3.5數(shù)據(jù)鏈路層協(xié)議舉例

數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室59選擇重傳（selectiverepeat）的工作原理：

數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室60選擇重傳協(xié)議的優(yōu)點(diǎn)：在某幀出錯(cuò)時(shí)減少了后面所有幀都要重傳的浪費(fèi)但接收方要有一個(gè)足夠大的緩沖區(qū)來(lái)暫存未按順序正確接收到的幀可以用滑動(dòng)窗口的觀點(diǎn)來(lái)統(tǒng)一看待停等、回退n和選擇重傳這三種協(xié)議，其差別僅在其窗口的大小

數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室61第三章數(shù)據(jù)鏈路層3.1

數(shù)據(jù)鏈路層的功能3.2差錯(cuò)檢測(cè)與校正3.3數(shù)據(jù)鏈路層協(xié)議3.4協(xié)議描述與驗(yàn)證3.5數(shù)據(jù)鏈路層協(xié)議舉例3.5.1HDLC—高級(jí)數(shù)據(jù)鏈路控制3.5.2因特網(wǎng)中的數(shù)據(jù)鏈路層—PPP：點(diǎn)對(duì)點(diǎn)協(xié)議3.5.3幀中繼

數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室62數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室HDLC基本工作原理HDLC的配置方式HDLC的幀格式HDLC的幀類型HDLC幀的校驗(yàn)63數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室基本工作原理最早由IBMSNA提出SDLC（SynchronousDataLinkControl)ISO根據(jù)SDLC，提出了HDLC（HighlevelDataLinkControl）是面向bit的同步通信協(xié)議64數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室HDLC的配置方法非平衡配置：又分為點(diǎn)對(duì)點(diǎn)和點(diǎn)對(duì)多點(diǎn)兩種。非平衡配置的特點(diǎn)是有一個(gè)主站及一個(gè)或多個(gè)從站組成，主站發(fā)出幀叫命令，從站發(fā)出幀叫響應(yīng)平衡配置：兩個(gè)站都是復(fù)合站，同時(shí)具有主站和從站的功能65數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室HDLC的幀格式幀標(biāo)志序列即01111110，作為幀的分隔標(biāo)志，如線路空閑，則用標(biāo)志序列填充，用位插入方法實(shí)現(xiàn)實(shí)現(xiàn)透明傳輸?shù)刂酚蛟诳偩€型多終端情況下，是終端的站號(hào)；在點(diǎn)對(duì)點(diǎn)的情況下，用來(lái)標(biāo)志命令和響應(yīng)控制域定義幀的類型、序號(hào)等和其它一些功能數(shù)據(jù)域用戶數(shù)據(jù)，長(zhǎng)度任意校驗(yàn)和CRC碼，ISO和CCITT有相似的生成多項(xiàng)式66數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室HDLC的幀類型HDLC的幀有三種類型，不同的類型其控制域的定義有些不同信息幀（I）：InformationFrame

監(jiān)控幀（S）：SupervisoryFrame

無(wú)序號(hào)幀（U）：UnnumberedFrame67數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室HDLC——信息幀（I）P/F(Poll/Final)位：P主機(jī)查詢哪個(gè)終端要發(fā)送數(shù)據(jù)F發(fā)送端發(fā)送數(shù)據(jù)的最后一幀用F捎帶確認(rèn)幀號(hào)：即下一個(gè)期望接收幀號(hào)，意味著以前幀的接收和確認(rèn)0當(dāng)前發(fā)送幀號(hào)P/F捎帶確認(rèn)幀號(hào)68數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室HDLC——監(jiān)控幀（S）監(jiān)控幀有四種格式：

RRREJRNRSREJ1000P/F捎帶確認(rèn)號(hào)1001P/F捎帶確認(rèn)號(hào)1010P/F捎帶確認(rèn)號(hào)1011P/F捎帶確認(rèn)號(hào)69數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室HDLC——無(wú)序號(hào)幀（S）控制字段的1、2bit都為1的幀為無(wú)序號(hào)幀無(wú)序號(hào)幀用于控制鏈路本身。如呼叫、確認(rèn)和斷開連接等控制無(wú)序號(hào)幀中用5位（3、4、6、7、8）來(lái)表示無(wú)序號(hào)幀的類型，但32種可能的類型中有些是保留的，并且，不同的協(xié)議中，無(wú)序號(hào)類型區(qū)別很大

70數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室HDLC幀的校驗(yàn)CRC校驗(yàn)生成多項(xiàng)式為x16+x12+x5+1校驗(yàn)范圍

FACIFCSF校驗(yàn)范圍71第三章數(shù)據(jù)鏈路層3.1

數(shù)據(jù)鏈路層的功能3.2差錯(cuò)檢測(cè)與校正3.3數(shù)據(jù)鏈路層協(xié)議3.4協(xié)議描述與驗(yàn)證3.5數(shù)據(jù)鏈路層協(xié)議舉例3.5.1HDLC—高級(jí)數(shù)據(jù)鏈路控制3.5.2因特網(wǎng)中的數(shù)據(jù)鏈路層SLIP：串行線路IPPPP：點(diǎn)對(duì)點(diǎn)協(xié)議3.5.3幀中繼

數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室72數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室因特網(wǎng)模型因特網(wǎng)中的網(wǎng)絡(luò)互連73數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室因特網(wǎng)模型因特網(wǎng)中的家庭用戶的入網(wǎng)74數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室SLIP——串行線路IPSLIP——串行線路IP（SerialLineIP）協(xié)議簡(jiǎn)單，無(wú)差錯(cuò)控制，只適用于IP,通信的每一方必須事先知道對(duì)方的IP地址，只支持低速的業(yè)務(wù)（19.2K），未成為標(biāo)準(zhǔn)75數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室PPP——點(diǎn)對(duì)點(diǎn)協(xié)議PPP的功能PPP的組成部分PPP的幀格式PPP的鏈路控制協(xié)議PPP的工作過(guò)程76數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室PPP——功能PPP是Internet標(biāo)準(zhǔn)（RFC166116621663）處理錯(cuò)誤監(jiān)測(cè)支持多種協(xié)議連接時(shí)允許協(xié)商IP地址允許身份驗(yàn)證77數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)山財(cái)計(jì)算機(jī)應(yīng)用教研室PPP——組成部分PPP提供了串行點(diǎn)對(duì)點(diǎn)鏈路上傳輸數(shù)據(jù)報(bào)的方法