第八章 差錯控制編碼

1、第8章 差錯控制技術(shù)8.1 差錯控制的基本概念8.2 流量控制方法8.3 常用差錯控制編碼方法8.4 常用差錯控制方法8.5 差錯控制的性能估算和應(yīng)用v必要性：數(shù)據(jù)通信要求信息傳輸過程具有高度的可靠性即誤碼率足夠低；然而信號在傳輸過程中由于傳輸損耗（噪聲，衰損，失真）不可避免要產(chǎn)生一些差錯即出現(xiàn)誤碼。大體上分為：v隨機(jī)差錯：由信道的加性隨機(jī)噪聲引起的差錯 v突發(fā)差錯：某一段時間內(nèi)出現(xiàn)一連串的差錯 v混合差錯：既有隨機(jī)差錯又有突發(fā)差錯 差錯控制的基本概念v所謂差錯即為誤碼；差錯控制的核心是抗干擾編碼，簡稱差錯編碼。v基本思想：是通過對信息序列作某種變換，使原來彼此獨立、互不相關(guān)的信息碼元產(chǎn)生某種

2、規(guī)律性（相關(guān)性），從而在接收端根據(jù)這種規(guī)律性來檢查，進(jìn)而糾正傳輸信號序列中的差錯。v變換的方法不同就構(gòu)成了不同的編碼，即信道編碼 差錯控制的基本概念v通俗地講，差錯控制方法：對要傳送的二進(jìn)制數(shù)字信息中增加一些附加的信息，通過增加冗余度使得原來的信息可以檢錯或糾錯。v一般來講，加入的冗余度越多，檢錯糾錯能力（即差錯控制能力）越強(qiáng)，傳輸效率越低。 1.信息碼和監(jiān)督碼v信息碼（元）：發(fā)送用戶端欲發(fā)送的信息序列。 v監(jiān)督碼（元）:為了使信息碼元產(chǎn)生某種規(guī)律性，可按照某種規(guī)則在用戶信息序列中插入一定數(shù)量的新碼元，這種新碼元叫監(jiān)督碼（元）。信號在交到用戶之前應(yīng)當(dāng)去掉監(jiān)督碼元。7v插入監(jiān)督碼元的目的是使原來

3、彼此獨立、互不相關(guān)的信息碼元產(chǎn)生某種規(guī)律性（相關(guān)性）從而使接收端能夠根據(jù)這種規(guī)律性來檢測傳輸過程是否有誤。2.差錯控制的基本特點v引入差錯編碼控制后，實際傳輸?shù)?信息序列=（信息碼元+監(jiān)督碼元），稱為碼組。 v在信道容量既定的情況下，信息傳輸效率有所降低，但信息傳輸?shù)目煽啃杂兴岣?，既差錯控制編碼用降低傳輸效率的代價來提高傳輸?shù)目煽啃?。Why?同樣的信息量要用更多的比特位！同樣的信息量要用更多的比特位！3.差錯控制的理論基礎(chǔ)香農(nóng)信道編碼定理v香農(nóng)信道編碼定理香農(nóng)信道編碼定理 ：每個信道都具有確定的信道容量C，只要信息傳輸速率：lRb（bps）=C則理論上就一定存在一種編碼方式，使其譯碼差錯概率

4、（即誤碼率）Pe滿足：lPe=A e-n E(Rb)l式中l(wèi)n碼字長度（碼長） lE（Rb）誤差指數(shù)（當(dāng)Rb0）lA正系數(shù)lPeNeN誤碼率是指二進(jìn)制碼元在數(shù)據(jù)傳輸系統(tǒng)中被傳錯的概率 ；N為傳輸?shù)亩M(jìn)制碼元總數(shù)， Ne為被傳錯的碼元數(shù)。香農(nóng)信道編碼定理E（Rb）與Rb的關(guān)系如圖所示： C 使使E(Rb ) 或或 n 使使e-nE(Rb ) v可見根據(jù)定理,減小Pe 的方法：一是增加信道容量C，從而使E（Rb ）增加（通信硬件系統(tǒng)設(shè)計人員通常采用的方法）；另一種方法是只要Rb=e+1=e+1v定理定理3.23.2若一種碼的最小距離為若一種碼的最小距離為d d0 0 ，則它能糾正傳，則它能糾正傳輸

5、錯誤個數(shù)（糾錯能力）輸錯誤個數(shù)（糾錯能力）t t應(yīng)滿足：應(yīng)滿足：d d0 0=2t+1=2t+1v定理定理3.33.3若一種碼的最小距離為若一種碼的最小距離為d0d0，則它的檢錯能，則它的檢錯能力和糾錯能力應(yīng)滿足：力和糾錯能力應(yīng)滿足： d d0 0 =e+t+1 =e+t+1 （e=te=t）v例3.1 求碼集合(000),(011),(101),(110)和(000),(111)最小距離d0及糾（檢）錯的能力。 實例（P58）解：最小距離解：最小距離實 例v檢錯和糾錯能力第一組：d0=2，e=d0 1=1，可檢測出一個錯，（定理1）第二組： d0 =3e=d0 1=2，可檢測出二個錯，（定理

6、1） t=(d0-1)/2=1，可糾正一個錯，（定理2） e+t=d0-1=2 ，令（t1個（3），最后可按下表，根據(jù)檢驗碼組中“1”的個數(shù)進(jìn)行判斷及糾正可能發(fā)現(xiàn)的錯碼 實例：v已知信息碼11010使用正反碼差錯控制方式，試問下列接收端收到的數(shù)據(jù)是否有錯？能否糾正？ 11010 11010 10010 11010 11010 01010 10000 11010v（1） 編碼：11010（信息碼）11010（監(jiān)督碼）11010 11010（正反碼）v（2） 解碼：接收端11010 11010 接收端10010 11010 接收端11010 01010 接收端10000 11010v判斷： v 1

7、1010 v + 11010v 00000v 結(jié)果為0，正確。v 10010 v + 11010v 01000v由于接收信息碼中為偶數(shù)個1，所以檢驗碼取反，10111，信息碼中有一位出錯，根據(jù)判決2，出錯位置就是檢驗碼組中0所對應(yīng)的位置，糾正后為11010v 11010 v + 01010v 10000v由于接收信息碼中為奇數(shù)個1，所以檢驗碼不變，根據(jù)判決3，監(jiān)督碼碼中有一位出錯，出錯位置就是檢驗碼組中1所對應(yīng)的位置，糾正后為11010v 10000 v + 01010v 01010v檢驗碼中1的個數(shù)1，根據(jù)判決4，無法判斷和糾錯v前面奇偶校驗對一個字符校驗一次，適合異步通訊；而CRC對一個數(shù)

8、據(jù)塊（frame）校驗一次，適合同步通訊。在串行同步通信中，幾乎都使用這種校驗方法。如磁盤信息的讀/寫等。 循環(huán)冗余校驗編碼（CRC） 循環(huán)冗余校驗編碼（CRC） vCyclic Redundancy checking (CRC)循環(huán)冗余校驗，又稱多項式碼。v在循環(huán)冗余校驗中，是通過在數(shù)據(jù)單元末尾加一串冗余比特，使得整個數(shù)據(jù)單元可以被另一個預(yù)定的二進(jìn)制數(shù)所整除。v 任何一個二進(jìn)制數(shù)序列可以和一個只含有0和1兩個系數(shù)的代數(shù)多項式建立起一一對應(yīng)的關(guān)系。多 項 式 多 項 式v 任何一個n位的二進(jìn)制數(shù)都可以用一個n-1 次的多項式來表示,這種多項式叫碼多項式碼多項式（又叫信息多項式） 。v碼多項式與

9、二進(jìn)制序列之間的一一對應(yīng)關(guān)系：（an-1 an-2a1a0）N A (x)= an-1Xn-1+an-2Xn-2 +a1X+a0X0碼多項式多項式 二進(jìn)制序列實例v以n=3位二進(jìn)制數(shù)為例 二進(jìn)制數(shù) 對應(yīng)多項式 000 001 010 011 100 101 111 01xx+1x2x2+1x2+ x+1n 1011011 x6+x4+x3+x+1n x5+x4+x2+x 110110vCRCCRC校驗的基本思想是：校驗的基本思想是： 根據(jù)欲發(fā)送的k位信息位構(gòu)成的報文，發(fā)送器生成一個r比特的序列，稱為幀校驗序列FCS,將r位FCS（即CRC碼）附加到k位信息序列之后作為實際發(fā)送的數(shù)據(jù)幀（k+r位

10、），這個幀所對應(yīng)二進(jìn)制序列恰好能夠被某個預(yù)先確定的數(shù)（生成多項式）整除。接收器用相同的數(shù)去除傳來的幀。如果無余數(shù)，則認(rèn)為無差錯；如果余數(shù)不為0，則認(rèn)為傳輸出錯。vCRC碼生成和校驗基本分為三步：第一步：在數(shù)據(jù)單元(k位）的末尾加上r個0。r r是一個比預(yù)定除數(shù)的比特位數(shù)(r十1)少1的數(shù)。第二步：采用二進(jìn)制除法將新的加長的數(shù)據(jù)單元（k+r位)除以除數(shù)。由此除法產(chǎn)生的余數(shù)就是校驗碼。CRC碼的生成 自定義的生成多項式第三步：用從第二步得到的r個比特的CRC碼替換數(shù)據(jù)單元末尾附加的r個0。如果余數(shù)位數(shù)小于r，最左的缺省位數(shù)為0。如果除法過程根本未產(chǎn)生余數(shù)（也就是說，原始的數(shù)據(jù)單元本身就可以被除數(shù)整

11、除）那么以r個0作為CRC碼替換余數(shù)所在的位置。產(chǎn)生的比特模式正好能被除數(shù)整除。CRC碼的生成 vCRC碼校驗：到達(dá)接收方的數(shù)據(jù)單元首先到達(dá)的是數(shù)據(jù)，然后是CRC校驗碼。接收方將整個數(shù)據(jù)串當(dāng)作一個整體去除以用來產(chǎn)生循環(huán)冗余校驗余數(shù)的同一個除數(shù)。如果數(shù)據(jù)串無差錯地到達(dá)接收方，循環(huán)冗余校驗器將產(chǎn)生余數(shù)0。因此數(shù)據(jù)單元將通過檢驗。如果在傳輸中數(shù)據(jù)單元被改變，除法將產(chǎn)生非零余數(shù)，因此數(shù)據(jù)單元將通不過檢驗。CRC碼的校驗 自定義的生成多項式 0G(X)補(bǔ)0數(shù)比除數(shù)G(X)位數(shù)少1余數(shù),位數(shù)等于附加0數(shù),不夠補(bǔ)零v 111010100011010v CRC校驗碼 v 信息碼v CRC冗余校驗碼CRC校驗碼

12、的生成器和校驗器R bit 0數(shù)據(jù)g(x)CRC校驗碼r+1r余數(shù)先發(fā)數(shù)據(jù)位先發(fā)數(shù)據(jù)位后發(fā)校驗位后發(fā)校驗位g(x)余數(shù)r+1rK bit 數(shù)據(jù)0接收，非接收，非0拒絕拒絕數(shù)據(jù)發(fā)送方發(fā)送方接收方接收方v生成多項式G(x):求CRC碼時所用的“除數(shù)”所對應(yīng)的多項式叫生成多項式生成多項式。v在串行通信中通常使用下列三種生成多項式G（X）來產(chǎn)生CRC碼。CRC-16：G(x)=X16+X15+X2+1，美國二進(jìn)制同步系統(tǒng)中采用。CRC-CCITT：G(x)=X16+X12+X5+1，CCITT推薦。CRC-32：G(x)=X32+X26+X23+X22+ X16+X12+ X11+X10+X8+1X7

13、+ X5+X4+X2+X+ 1生成生成多項式多項式CRC碼性能 vCRC碼是很有效的差錯校驗方法。常用的CRC除數(shù)通常有13、17，或是33個比特，不可檢測的錯誤可能降低到幾乎近于零。vCRC接收電路再配上適當(dāng)?shù)挠布娐凡粌H可以檢錯，而且可以糾錯，糾錯能力很強(qiáng)特別適合檢測突發(fā)性錯誤，在數(shù)據(jù)通信中得到較廣泛的應(yīng)用?？偨Y(jié)CRC碼特點v可靠性好，不可檢測的錯誤可能降低到幾乎為零。v設(shè)備簡單，糾錯能力強(qiáng)，適合檢測突發(fā)性錯誤 卷卷 積積 碼碼v1.概述v2.編碼器v3.解碼器1. 概述v前面介紹的編碼方法都是線性分組碼，即監(jiān)督碼只負(fù)責(zé)監(jiān)督檢驗本碼組中的信息碼元。 v如果每組的監(jiān)督碼元不但與本組碼的信息碼

14、元有關(guān)，而且還與前面若干組信息碼元有關(guān)，每個監(jiān)督碼元對它的前后碼元都實行監(jiān)督，前后相連，具有連環(huán)監(jiān)督的作用；因此我們稱為連環(huán)碼，即卷積碼。 v卷積碼由 P.Elias于1955年最先提出，整個編解碼過程一環(huán)扣一環(huán)，連鎖地進(jìn)行下去。 2.編碼器 (2,1,3)卷積碼編碼電路 （狀態(tài)標(biāo)識S0S3）: m1 m2 當(dāng)輸入5位信息10110時，輸出碼字和狀態(tài)轉(zhuǎn)移是 S0 1/11 S1 0/10 S21/00 S1 1/01 S3 0/01S2網(wǎng) 格 圖 00100111狀 態(tài) 轉(zhuǎn) 換 圖 卷積碼的維特比（Viterbi）解碼v基本思想：屬于最大似然算法，既把接收序列與所有可能的發(fā)送序列進(jìn)行比較，選擇

15、一種碼距最小的序列作為發(fā)送序列。v接收一段，計算和比較一段，選擇一段有最有可能的碼段，從而達(dá)到整個碼序列是一個最大似然值的序列。維特比算法v例：設(shè)卷積碼為(n, k, m) = (3, 1, 3)碼 現(xiàn)在的發(fā)送信息位為1101為了使移存器中的信息位全部移出，在信息位后面加入了3個“0”，即1101000編碼后的發(fā)送序列：111 110 010 100 001 011 000接收序列：111 010 010 110 001 011 000 (紅紅色為錯碼色為錯碼)v發(fā)送序列的約束長度為N = 3，所以首先需考察3個信息段，即考察3n 9比特，即接收序列前9位“111 010 010”。 v解碼第

16、1步由網(wǎng)格圖可見，沿路徑每一級有4種狀態(tài)a, b, c和d。每種狀態(tài)只有兩條路徑可以到達(dá)。故4種狀態(tài)共有8條到達(dá)路徑。比較網(wǎng)格圖中的這8條路徑和接收序列之間的漢明距離。例如，由出發(fā)點狀態(tài)a經(jīng)過3級路徑后到達(dá)狀態(tài)a的兩條路徑中上面一條為“000 000 000”。它和接收序列“111 010 010”的漢明距離等于5；下面一條為“111 001 011”,它和接收序列的漢明距離等于3。 110110110110011011011010010010101101101001001001001abcdabcd000000000000000111111111111111100100100將這8個比較結(jié)果

17、列表如下：比較到達(dá)每個狀態(tài)的兩條路徑的漢明距離，將距離小的一條路徑保留，稱為幸存路徑。這樣，就剩下4條路徑了，即表中第2, 4, 6和8條路徑。 序序號號路徑路徑對應(yīng)序列對應(yīng)序列漢明距離漢明距離幸存否？幸存否？1aaaa000 000 0005否否2abca111 001 0113是是3aaab000 000 1116否否4abcb111 001 1004是是5aabc000 111 0017否否6abdc111 110 0101是是7aabd000 111 1106否否8abdd111 110 1014是是v解碼第2步：繼續(xù)考察接收序列中的后繼3個比特“110” 計算4條幸存路徑上增加1級后

18、的8條可能路徑的漢明距離。計算結(jié)果列于下表中。表中總距離最小為2，其路徑是abdc+b，相應(yīng)序列為111 110 010 100。它和發(fā)送序列相同，故對應(yīng)發(fā)送信息位1101。 序號序號路徑路徑原幸存路徑的原幸存路徑的距離距離新增新增路徑段路徑段新增距離新增距離總距離總距離幸存否？幸存否？1abca+a3aa25否否2abdc+a1ca23是是3abca+b3ab14否否4abdc+b1cb12是是5abcb+c4bc37否否6abdd+c4dc15是是7abcb+d4bd04是是8abdd+d4dd26否否v在編碼時，信息位后面加了3個“0”，使寄存器中信息位全部移出。若把這3個“0”仍然看作

19、是信息位，則可以按照上述算法繼續(xù)解碼。這樣得到的幸存路徑網(wǎng)格圖示于下圖中。圖中的粗線仍然是漢明距離最小的路徑。 v若已知這3個碼元是（為結(jié)尾而補(bǔ)充的）“0”，則在解碼時就預(yù)先知道在接收這3個“0”碼元后，路徑必然應(yīng)該回到狀態(tài)a_000。而由圖可見，只有兩條路徑可以回到a狀態(tài)。所以，這時上圖可以簡化成：110011010010101101001001abcdabcd000 111100100000 011011001110011010010101101001001abcdabcd000 111100100000 011011001101v維特比譯碼能糾正部分錯，但并不能糾正所有可能發(fā)生的錯誤，當(dāng)

20、錯誤模式超出卷積碼的糾錯能力時，譯碼后的輸出序列就會帶有錯誤。 寄存器：是能夠寄存一組二進(jìn)制信息的邏輯部件。 由由D D型觸發(fā)器組成的型觸發(fā)器組成的4 4位寄存器位寄存器補(bǔ)充：寄存器補(bǔ)充：寄存器觸發(fā)器v能寄存一位二進(jìn)制信息的單元電路稱為觸發(fā)器。觸發(fā)器有兩個輸出端：“1”端和“0”端（見下頁圖）。兩個輸出端的極性總是相反 （“1”端為高電平，“0”端就為低電平；“1”端為低電平，“0”端就為高電平） v沒有外界作用，觸發(fā)器狀態(tài)保持不變，即所存的信息不變。在一定的外界作用下，觸發(fā)器能從一種狀態(tài)變到另一種狀在一定的外界作用下，觸發(fā)器能從一種狀態(tài)變到另一種狀態(tài)并保持住態(tài)并保持住。觸發(fā)器的輸出端觸發(fā)器的

21、輸出端D D型觸發(fā)器型觸發(fā)器D觸發(fā)器v在SET端（置“1”端）加一負(fù)脈沖，觸發(fā)器變?yōu)椤?”狀態(tài)。在CLR端（置“0”端）加一負(fù)脈沖，觸發(fā)器變?yōu)椤?”狀態(tài)。平常，SET端和CLR端為高電平。 vCP端為接收脈沖（或稱打入脈沖）輸入端。當(dāng)CP端沒有接收脈沖時，即一直處于固定的電位時，觸發(fā)器的狀態(tài)保持不變。在CP端加一接收脈沖，在脈沖的上升沿（由低變高）時，如果此刻代碼輸入端D為0，則觸發(fā)器變?yōu)?，如果D為1，則觸發(fā)器變?yōu)?。 v也就是說，接收的信息（或說成打入到觸發(fā)器中的信息）取決于接收脈沖的上升沿時刻代碼輸入端的狀態(tài)。接收脈沖過后D型觸發(fā)器的狀態(tài)保持不變。 由D觸發(fā)器構(gòu)成4位移位寄存器D觸發(fā)器實

22、現(xiàn)二分頻電路 差錯控制方法差錯控制方法 1 差錯控制方法 （1）自動請求重發(fā)(ARQ) 1. 停止等待ARQ 2. 返回N幀（Go-Back-N）ARQ 3. 選擇性重發(fā)ARQ （2）前向糾錯控制方法（FEC） （3） 混合糾錯控制方法（HEC) （4） 信息反饋 （5） 其它差錯控制方式2 差錯控制的性能估算和應(yīng)用v利用我們前面介紹的抗干擾編碼（或叫差錯控制編碼）來控制傳輸系統(tǒng)的傳輸差錯的方法，稱為差錯控制差錯控制。v差錯控制的兩種基本思想：一是通過差錯編碼，使得接收端譯碼器能發(fā)現(xiàn)錯誤并準(zhǔn)確地判斷差錯的位置從而自動糾正它們。 另一個就是在接收端能夠發(fā)現(xiàn)錯誤但無法自動糾錯，請求發(fā)送端重發(fā)數(shù)據(jù)等

23、方式來達(dá)到糾正錯誤的目的。v差錯控制的工作方式可分為四類：v自動請求重發(fā)（ARQ），前向糾錯（FEC），混合糾錯（HEC）和信息反饋（IRQ），另外還有諸如像冗余法，多數(shù)表決法（重復(fù)編碼）等，下面分別加以介紹。ARQ Auto Request for RetransmissionFEC Forward Error CorrectionHEC Hybrid Error CorrectionIRQ Information Repetition Request差錯控制方式分類差錯控制方式分類 （1）ARQ: 自動請求重發(fā)v又稱反饋重發(fā)v發(fā)送端首先對發(fā)送序列（信息碼信息碼）進(jìn)行差錯編碼，生成一個可以檢

24、錯的校驗序列（監(jiān)督碼監(jiān)督碼），然后連同數(shù)據(jù)一起發(fā)送出去；（無法糾錯） v接收端根據(jù)校驗序列的編碼規(guī)則判決是否出錯，并把判決結(jié)果通過反饋通道傳回給發(fā)送端： ARQ傳輸差錯處理方法通常處理傳輸差錯的辦法如下：v肯定確認(rèn)：接收端收到一個幀后未發(fā)現(xiàn)錯誤，回送一個確認(rèn)信號，用ACK表示。v否定確認(rèn)：用NAK表示。v超時重發(fā)(Overtime)：發(fā)送端發(fā)出一個幀后開始計時，如果在規(guī)定的時間內(nèi)沒有收到應(yīng)答信號（ACK或NAK），則認(rèn)為發(fā)生幀丟失的或確認(rèn)信號丟失。必須重發(fā)。SourceDestinationACKNAKOvertime ARQ: 自動請求重發(fā)v1.停止-等待ARQv2.返回N幀（Go-Back

25、-N）ARQv3.選擇性重發(fā)ARQ1.停止-等待ARQv(1)基本概念：發(fā)送端：發(fā)送一幀數(shù)據(jù) 等待確認(rèn)（ACK/NAK） 重發(fā)上一幀或發(fā)送下一幀數(shù)據(jù)v獲得ACK之前，發(fā)送端必須備份已發(fā)送的一幀數(shù)據(jù)vTimer: avoid Deadlock frame lost接收端：等待接收數(shù)據(jù)，并校驗v正確，將接收到的數(shù)據(jù)幀上交網(wǎng)絡(luò)層并回送ACKv錯誤，丟棄接收到的數(shù)據(jù)幀并回送NAK?1.停止-等待ARQv解決問題Deadlock: TimerRepeated data frame: add NO. field （編號）n the data frame1.停止-等待ARQv狀態(tài)序號：收發(fā)雙方都維持一個狀態(tài)

26、序號，狀態(tài)序號，用用來記錄鏈路上期待正確來記錄鏈路上期待正確接收接收、確認(rèn)確認(rèn)的幀序號的幀序號v(2)操作要點：初始化：將收發(fā)兩端狀態(tài)序號狀態(tài)序號初始化為0狀態(tài)序號通過狀態(tài)序號通過1bit的數(shù)據(jù)來維持即可的數(shù)據(jù)來維持即可（序號非（序號非0即即1）發(fā)送端：每送出一個數(shù)據(jù)幀（數(shù)據(jù)幀的序號為本地狀態(tài)號，第一個數(shù)據(jù)幀序號為0），然后要更新本地狀態(tài)序號（設(shè)用V1(s)表示）中。 發(fā)送重復(fù)幀先恢復(fù)原來V1(s)接收端：每送出一個ACK幀，其序號應(yīng)當(dāng)提取本地新的狀態(tài)號V2(s) (剛剛更新過) 檢測出錯誤不更新V2(s) 1.停止-等待ARQ（兩者一至如何，兩者不一至如何？）答：若兩者一致，則說明是新的數(shù)據(jù)

27、幀，要更新本地狀態(tài)序號，并回送確認(rèn)幀。并且，準(zhǔn)備接收下一個數(shù)據(jù)幀。若發(fā)現(xiàn)不一致，則說明是重復(fù)幀，應(yīng)該丟棄之，并且不改變狀態(tài)序號的值，但仍需向發(fā)送端回送一個確認(rèn)幀。而幀的序號應(yīng)該為本地狀態(tài)序號的值。接收端：每收到一個數(shù)據(jù)幀數(shù)據(jù)幀，將其序號與本地的狀態(tài)序號V2(s)相比較。1.停止-等待ARQ發(fā)送端：每收到一個確認(rèn)幀確認(rèn)幀，將其序號與本地的狀態(tài)序號V1(s)相比較。（兩者一至如何，兩者不一至如何？）答：若兩者一至，則說明傳輸正確，可以發(fā)送新的一數(shù)據(jù)幀，并更新本地狀態(tài)序號；準(zhǔn)備接收下一數(shù)據(jù)幀。若發(fā)現(xiàn)不一至，說明是重復(fù)的確認(rèn)幀，只需丟棄即可，繼續(xù)等待所期望的確認(rèn)幀?？偨Y(jié)：發(fā)送端的狀態(tài)序號值等于下次準(zhǔn)備

28、發(fā)送的數(shù)據(jù)幀的序號；而接收端的狀態(tài)序號表示當(dāng)前期望接收的數(shù)據(jù)幀的序號。鏈路數(shù)據(jù)傳輸過程：正常鏈路數(shù)據(jù)傳輸過程：數(shù)據(jù)幀出錯鏈路數(shù)據(jù)傳輸過程：數(shù)據(jù)幀丟失鏈路數(shù)據(jù)傳輸過程：確認(rèn)幀丟失2.返回N幀（Go-Back-N）ARQv(1)基本想法： 發(fā)送端連續(xù)發(fā)送data frame if有錯,則回退N幀繼續(xù)連續(xù)發(fā)送data frame（重發(fā)所有其它幀，不管它是否正確接收） v(2)緩沖區(qū)大?。喊l(fā)送端：需要一個能存儲N個數(shù)據(jù)幀的緩沖區(qū)（重發(fā)表），以便隨時準(zhǔn)備重發(fā)。接收端：對檢測出有錯的那個數(shù)據(jù)幀之后的N-1幀，不論正確與否都一律丟棄，故只需能夠存儲一個數(shù)據(jù)幀的緩沖區(qū)即可。（3）返回N幀ARQ示意圖12345

29、678934567891011121378910123456789345678910111213ACK1ACK2NAK3回退回退N幀重傳幀重傳NAK4NAK5NAK6NAK7NAK8NAK9ACK3ACK4ACK5ACK6NAK7回退回退N幀重傳幀重傳提交網(wǎng)絡(luò)層提交網(wǎng)絡(luò)層提交網(wǎng)絡(luò)層提交網(wǎng)絡(luò)層丟棄丟棄丟棄丟棄接收端接收端發(fā)送端發(fā)送端v回退N幀：N=滑動窗口大小v發(fā)送端:每收到ACK幀，繼續(xù)發(fā)送新數(shù)據(jù)每收到NAK幀，回退N幀，即重發(fā)出錯幀以及其后發(fā)送的 N-1 幀數(shù)據(jù)（不管它們是否正確）（4）傳輸過程幾種情況v數(shù)據(jù)幀和確認(rèn)幀都正常v數(shù)據(jù)幀出錯（丟失），返回NAK（啟動Timer）回退N幀v數(shù)據(jù)幀正

30、確而確認(rèn)幀出現(xiàn)錯誤 ：后繼收到的確認(rèn)幀為ACK后繼收到的確認(rèn)幀為NAKACK幀出現(xiàn)差錯，但數(shù)據(jù)確實有送到，使用更后面的ACK幀來確認(rèn)當(dāng)前ACK出錯的幀（一個ACK幀確認(rèn)多個數(shù)據(jù)幀）回退N幀（5）返回N幀ARQ操作要點v(1)數(shù)據(jù)幀和確認(rèn)幀都正常：不出現(xiàn)差錯或丟失（1）發(fā)送端連續(xù)發(fā)送數(shù)據(jù)幀而不等待確認(rèn)幀，直到收到第一幀的確認(rèn)幀為止決定下一步操作（2）發(fā)送端在重發(fā)表中保存N個數(shù)據(jù)幀的備份（3）重發(fā)表按FIFO規(guī)則操作（4）接收端對每一個正確接收到的數(shù)據(jù)幀返回一個確認(rèn)(ACK)幀（5）每一個數(shù)據(jù)幀包含一個唯一的序號（6）接收端保存一個接收序列表，保存最后正確接收到一幀數(shù)據(jù)（7）當(dāng)一收到相應(yīng)數(shù)據(jù)幀的確

31、認(rèn)(ACK)幀，發(fā)送端從重發(fā)表重刪除該數(shù)據(jù)幀v(2)數(shù)據(jù)幀出錯（幀受損壞、丟失）：（1）假設(shè)第假設(shè)第 N+1 幀數(shù)據(jù)出錯幀數(shù)據(jù)出錯（2）接收端立即返回 NAK(N+1)，指出最后正確接收到的是第 N 幀（3）接收端同時清除其后收到的的其它數(shù)據(jù)幀，直到收到正確的第(N+1)幀（4）為避免死鎖（ACK/NAK丟失），一般發(fā)送端在發(fā)送一幀數(shù)據(jù)的同時啟動定時器（5）一旦正確收到第(N+1)幀，接收端就繼續(xù)正常工作（6）發(fā)送端可以接收確認(rèn)、否認(rèn)幀（ACK/NAK）vACK：繼續(xù)發(fā)送后繼幀vNAK：回退N幀重發(fā)(8)返回N幀ARQ存在問題v返回N幀ARQ因連續(xù)發(fā)送數(shù)據(jù)幀而提高傳輸效率。v發(fā)送端要維持和滑動

32、窗口一樣大小的緩沖區(qū)，備份已發(fā)送的數(shù)據(jù)；并且重發(fā)時不管出錯數(shù)據(jù)幀其后的數(shù)據(jù)幀是否有錯，一律重發(fā)，使傳輸效率降低。v通信鏈路較差、誤碼率較大時，go_back_N就不一定優(yōu)于stop_and_wait（經(jīng)常回退）v另外在長傳播延時鏈路上go_back_N傳輸效率也較低。（重發(fā)N幀花費時間）3.選擇性重發(fā)ARQv在返回N幀ARQ的基礎(chǔ)上改進(jìn)而來，也是一種ARQ連續(xù)方案。 v發(fā)送端連續(xù)發(fā)送數(shù)據(jù)幀接收端接收確認(rèn)：ACK(N)連續(xù)發(fā)送NAK(N)發(fā)送端根據(jù)NAK（N）中N確認(rèn)重發(fā)出錯幀；只重發(fā)錯誤的幀只重發(fā)錯誤的幀，避免對后繼正確數(shù)據(jù)幀的多余重發(fā)，較返回N幀方案效率有明顯提高。 （1）選擇性重發(fā)ARQ示

33、意圖12345678931011612131415161761218141234567893101161213141516176ACK1ACK2NAK3ACK4ACK5NAK6ACK7ACK8ACK9ACK3ACK10NAK6ACK11重傳重傳與與4、5號幀一號幀一起提交網(wǎng)絡(luò)層起提交網(wǎng)絡(luò)層提交網(wǎng)絡(luò)層提交網(wǎng)絡(luò)層暫存與緩沖區(qū)中暫存與緩沖區(qū)中暫存與緩沖區(qū)中暫存與緩沖區(qū)中重傳重傳NAK12ACK13NAK14ACK15ACK16ACK17ACK6與與711號幀一號幀一起提交網(wǎng)絡(luò)層起提交網(wǎng)絡(luò)層重傳重傳重傳重傳（2）選擇性重發(fā)ARQ存在問題v選擇性重發(fā)ARQ在效率上獲得的增加，是以復(fù)雜的接收控制機(jī)制和巨大

34、的緩沖容量為代價的。v在鏈路較差以致較多出現(xiàn)單個數(shù)據(jù)幀連續(xù)出錯的情況下，重發(fā)幀和接收幀的緩存提取以及接收后的排序問題都比較復(fù)雜。v因此，應(yīng)用不如回退N幀ARQ廣泛。(3)GBN & SR控制技術(shù)比較vGo_Back_N ARQ :發(fā)送方需要較大的緩沖區(qū)，以便重傳 接收方緩沖區(qū)僅為1適于信道出錯率較少的情況vSelective Repeat ARQ接收方也需要較大的緩沖區(qū)，以便按正確順序?qū)⒎纸M提交網(wǎng)絡(luò)層適于信道質(zhì)量不好的情況ARQ技術(shù)的主要特點vARQ要求有反饋回路，系統(tǒng)需采用雙工通訊方式v控制規(guī)程和過程較復(fù)雜，但與FEC相比復(fù)雜性和成本要低的多v反饋重傳，效率較低，不適合于實時傳輸系統(tǒng) （2）前向糾錯控制方法FECv發(fā)送端逐行糾錯編碼，碼組冗余度大具有自動糾錯能力，然后發(fā)送這種能糾錯的碼v接收端譯碼并自動糾正傳輸差錯v特點：a 無反饋過程，可采用單工通訊b 傳輸系統(tǒng)延時小，實時性強(qiáng)c 糾錯碼，編碼冗余度大，傳輸效率有所下降d 控制規(guī)程簡單，但編譯碼設(shè)備較