6第六章 差錯控制

第六章差錯控制差錯控制主要涉及3個方面的問題：糾錯編碼的理論和實(shí)現(xiàn)；差錯控制的方式；信道差錯分布的統(tǒng)計特性及其數(shù)學(xué)模型。在信號傳輸中，由于受到干擾、噪聲等原因產(chǎn)生碼型畸變，接收方不能正確辨識信號和恢復(fù)信息，產(chǎn)生錯誤是不可避免的。差錯控制就是采用可靠、有效的編碼以減少計算機(jī)通信系統(tǒng)中傳輸差錯的方法，其目的的是提高傳輸質(zhì)量。要想根本解決傳輸差錯問題，降低誤碼率，提高傳輸質(zhì)量，就要改善傳輸信道的電氣特性，使誤碼率達(dá)到要求。但出于經(jīng)濟(jì)和技術(shù)條件限制，這方面的努力效果不佳。在實(shí)際通信系統(tǒng)中，一般采用合適的數(shù)據(jù)編碼和各種差錯控制方式來確保傳輸信息的正確性。在差錯控制技術(shù)中，對消息數(shù)據(jù)進(jìn)行可靠有效的編碼是檢測錯誤和糾正錯誤的基礎(chǔ)，而采用適當(dāng)?shù)牟铄e控制方式，又是提高信息傳輸效率的重要途徑之一。共26頁16第六章差錯控制第六章差錯控制6.1糾錯檢錯編碼原理6.2常用的校驗(yàn)編碼方式6.3差錯控制方法6.4ARQ的各種類型6.5信道的差錯特性共26頁26第六章差錯控制6.1糾錯檢錯編碼原理一、差錯類型

單位錯：在給定的數(shù)據(jù)單元中只改變一個位，它是一種孤立的差錯狀態(tài)，不影響鄰近的其他位。單位錯是由熱噪聲等隨機(jī)噪聲引起的，也稱為隨機(jī)差錯或獨(dú)立差錯。突發(fā)錯：是指幾乎是連續(xù)發(fā)生的一串錯，出錯的串長度稱為突發(fā)長度B。長度為B的突發(fā)錯是指連續(xù)B位中的第1個和最后一個位錯，中間任意兩個相鄰錯誤位之間的正確位數(shù)小于規(guī)定的標(biāo)準(zhǔn)。突發(fā)錯的差錯之間有相關(guān)性，差錯是密集、成片出現(xiàn)的。二、校驗(yàn)碼的分類數(shù)據(jù)校驗(yàn)碼是一種能發(fā)現(xiàn)某些錯誤或能夠糾正本身某些錯誤的數(shù)據(jù)編碼方法，也稱抗干擾碼。校驗(yàn)碼采用冗余編碼方法，在所要傳送的數(shù)據(jù)序列中，按一定的規(guī)則加入一些新的碼元(稱為校驗(yàn)位或監(jiān)督位)，使這些多余碼元與數(shù)據(jù)碼元之間建共26頁36第六章差錯控制二、校驗(yàn)碼的分類立某種相關(guān)關(guān)系。接收端接收到校驗(yàn)碼后，按編碼規(guī)則進(jìn)行譯碼，如不符合編碼規(guī)則，就判定為出錯，并采取某種糾正措施。校驗(yàn)碼有不同的分類方式，主要有以下幾種。1、檢錯碼和糾錯碼檢錯碼：只能檢錯，不能糾錯；糾錯碼：不但能發(fā)現(xiàn)錯誤，而且能夠改正錯誤；一般來講，在校驗(yàn)碼中，監(jiān)督位所占比例越大，糾、檢錯的能力就越大。校驗(yàn)碼是以降低傳輸效率為代價而提高通信傳輸可靠性的。通常用編碼效率來衡量編碼的冗余度。編碼效率是數(shù)據(jù)位數(shù)與整個校驗(yàn)碼的位數(shù)之比。2、分組碼和卷積碼(根據(jù)數(shù)據(jù)位和監(jiān)督位的生成約束關(guān)系)分組碼：對要傳送的信息數(shù)據(jù)按適當(dāng)?shù)奈粩?shù)進(jìn)行分組，編碼時附加的監(jiān)督位僅僅由本組內(nèi)的信息代碼決定，如圖6-1所示。共26頁46第六章差錯控制2、分組碼和卷積碼碼組也稱為幀或包，碼組中的監(jiān)督位稱為塊校驗(yàn)序列(BCS)或幀校驗(yàn)序列(FCS)。卷積碼：也是分組的、但它的監(jiān)督位不僅與本組的信息有關(guān)，而且還與前若干組的信息有關(guān)。卷積碼的糾錯能力強(qiáng)、既可糾正隨機(jī)差錯，又可糾正突發(fā)差錯。卷積碼的譯碼算法比較復(fù)雜，不過都有現(xiàn)成的編譯碼器芯片。3、線性碼和非線性碼線性碼：指數(shù)據(jù)位與監(jiān)督位之間的關(guān)系為線性關(guān)系，即滿足一組線性方程式；非線性碼：數(shù)據(jù)位與監(jiān)督位之間是非線性關(guān)系。數(shù)據(jù)鏈路層碼組就是幀，其上就是包共26頁56第六章差錯控制4、系統(tǒng)碼和非系統(tǒng)碼系統(tǒng)碼：編碼中數(shù)據(jù)位的形式與原來一致的編碼，例如數(shù)據(jù)位碼元在前，監(jiān)督位碼元在后的編碼；非系統(tǒng)碼：數(shù)據(jù)位在編碼中的位置與原來不一致的編碼，例如監(jiān)督位碼元分布在數(shù)據(jù)位碼元中的編碼就是非系統(tǒng)編碼；三、編碼的糾檢錯能力1、碼重、碼組距和碼距碼重(碼組的重量):在校驗(yàn)碼中，碼組中非零碼元的個數(shù)稱為碼重。兩個碼組之間的距離就是兩個碼組中對應(yīng)位之間不相同的個數(shù)；碼距：該編碼全部碼組內(nèi)兩兩之間距離的最小值；2、碼距d與檢錯或糾錯能力的關(guān)系共26頁66第六章差錯控制2、碼距與檢錯或糾錯能力的關(guān)系合法碼組可能的合法碼組糾錯一般采用最大似然規(guī)則，即非法碼組離哪個合法碼組最近，就把該非法碼組糾正為那個合法碼組。出錯位不超過e個出錯位不超過t個出錯位不超過e個共26頁76第六章差錯控制3、接收方可能接收的碼組接收方接收了一個碼組后，會有3種情況發(fā)生：碼組在傳輸過程中無差錯發(fā)生；碼組在傳輸過程中有差錯發(fā)生，所發(fā)生的差錯被接收方檢測出。當(dāng)合法碼組出錯位不等于碼距或其整數(shù)倍數(shù)時，就變成了非法碼組，這時接收方就可以根據(jù)編碼規(guī)則發(fā)現(xiàn)錯誤；碼組在傳輸過程中有差錯發(fā)生，但接收方未能檢測出來；當(dāng)合法碼組的出錯位數(shù)正好等于碼距d或其倍數(shù)時，該合法碼組就有可能變成另外一個合法碼組，這時接收方就無法檢測出來。上述3種情況的發(fā)生概率與校驗(yàn)碼的碼距直接相關(guān)，也與差錯控制方法有關(guān)。例如d=3，使用檢錯差錯控制方法可以檢出2位錯；如果使用糾錯差錯控制方法可以糾正1位錯誤，如果這個時候發(fā)生兩位錯，經(jīng)過糾錯得到的碼就是錯誤碼。共26頁86第六章差錯控制6.2常用的校驗(yàn)編碼方式一、奇偶校驗(yàn)碼奇偶校驗(yàn)碼的碼距為2，無糾錯能力，但對所有的奇數(shù)位出錯都能檢測出來，核驗(yàn)電路也比較簡單。偶校驗(yàn)(even)；奇校驗(yàn)(odd)；傳號校驗(yàn)(mark)，校驗(yàn)位始終為1；空號校驗(yàn)(space)，校驗(yàn)位始終為0；無校驗(yàn)(none)。二、方陣校驗(yàn)碼右邊方陣碼的碼距為4，是一種糾錯碼，具有1位糾錯能力，同時能夠檢測2位錯。ASCII字符碼奇偶校驗(yàn)碼共26頁96第六章差錯控制三、恒比碼恒比碼就是使校驗(yàn)碼中的1和0的數(shù)目之比是一個常數(shù)。中國五單位保護(hù)電碼，見表6-1，能發(fā)現(xiàn)一位錯，其碼距為2。ARQ準(zhǔn)確計數(shù)編碼也是一種恒比碼，這種碼每個字符有7位，每個字符中所含1的個數(shù)相同，都為2個。四、校驗(yàn)和校驗(yàn)和(checksum，或稱檢查和)通常用于對數(shù)據(jù)塊的校驗(yàn)。它把數(shù)據(jù)塊中的每一個字符代碼都按二進(jìn)制加法求和，然后把所求得的和作為監(jiān)督位。校驗(yàn)和可以使用不同字節(jié)數(shù)，但是對高位進(jìn)位主要有以下幾種：按模加，不考慮高位的進(jìn)位；循環(huán)進(jìn)位，把高位的進(jìn)位當(dāng)作最低位再加進(jìn)去；共26頁106第六章差錯控制四、校驗(yàn)和(用一個程序?qū)崿F(xiàn)之)校驗(yàn)和除對高位進(jìn)位有不同處理之外，對校驗(yàn)和本身也有不同處理方式，例如TCP數(shù)據(jù)包和IP數(shù)據(jù)報把16位循環(huán)求和取補(bǔ)作為監(jiān)督位。五、CRC碼CRC碼的計算方法是用事先約定的一個生成多項式函數(shù)G(x)去除0、1數(shù)據(jù)串，舍棄商，將余數(shù)作為監(jiān)督位(通常稱為幀校驗(yàn)序列FCS)，由數(shù)據(jù)和FCS組成新的數(shù)據(jù)幀發(fā)送。接收端用同樣的生成多項式除以接收進(jìn)來的數(shù)據(jù)幀，若沒有余數(shù)．則認(rèn)為無錯。(代數(shù)編碼理論把二進(jìn)制序列看成一個多項式)設(shè)M為要傳輸?shù)臄?shù)據(jù)，有k位；P為生成多項式，有n+1位；F為FCS，有n位；T為CRC校驗(yàn)形成的數(shù)據(jù)項，有k+n位。無差錯時，T/P的余數(shù)為0。CRC碼的具體生成辦法是將k位數(shù)據(jù)左移n位，低位補(bǔ)0，再用n+1位的生成多項式進(jìn)行模2除，所得的n位余數(shù)就是FCS。共26頁116第六章差錯控制常用的生成多項式有：五、CRC碼理論證明，CRC碼的檢錯能力很強(qiáng)。r位生成多項式可檢測出所有的單錯、雙錯、奇數(shù)位錯和突發(fā)長度小于或等于r的突發(fā)錯，對于突發(fā)長度為r+1的突發(fā)錯的檢出概率是1-2-r-1，對于突發(fā)長度大于r十1的突發(fā)錯的檢出概率是(1-2-r)。根據(jù)以上假定可以得到如下運(yùn)算結(jié)果：共26頁126第六章差錯控制五、CRC碼待發(fā)送M的比特：1101011生成多項式：監(jiān)督位序列：1010；CRC碼：110101110102nMPQR共26頁136第六章差錯控制6.3差錯控制方法差錯控制的基礎(chǔ)就是發(fā)送具有檢錯或糾錯能力的校驗(yàn)碼。如果校驗(yàn)碼只有檢錯能力而無糾鍺能力，則需要反向信道(從接收端到發(fā)送端的信道)把檢測結(jié)果反饋給發(fā)送端。差錯控制方式有3種基本方法，如圖6-3所示。反饋重發(fā)糾錯前向糾錯混合糾錯共26頁146第六章差錯控制一、反饋重發(fā)(ARQ)糾錯方式(要求誤碼率很低的通信)無論對或錯反饋重發(fā)糾錯方式(ARQ)又叫自動請求重發(fā)方式，即通常所說的ARQ(Automatic-RepeatRequest)方式。適用于點(diǎn)對點(diǎn)通信，有三種形式：停止等待ARQ、重返N-ARQ和選擇重發(fā)ARQ。檢錯碼二、前向糾錯方式前向糾措(ForwardErrorCorrection，F(xiàn)EC)是發(fā)送端發(fā)送能夠糾錯的碼，接收端收到這個糾錯碼后，不僅能自動地發(fā)現(xiàn)錯誤，而且能根據(jù)譯碼規(guī)律自動地糾正數(shù)據(jù)傳輸中所出現(xiàn)的錯誤。適用于點(diǎn)對點(diǎn)通信共26頁156第六章差錯控制二、前向糾錯方式能單向通信；報文可連續(xù)傳送，無須等待確認(rèn)；不需要反向信道，可進(jìn)行一個用戶對多個用戶的通信(廣播或組搔)和輻射狀的通信網(wǎng)；發(fā)送端不需要暫存數(shù)據(jù)，通信緩沖器的容量可以小一些。優(yōu)點(diǎn)：缺點(diǎn)：譯碼設(shè)備比較復(fù)雜；靈活性差，所選的糾錯碼必須與信道的干擾情況緊密對應(yīng)；糾正較多錯誤時，冗余碼元增多，傳輸效率隨之下降。三、混和糾錯(要求碼距等于或大于4)混和糾錯(HybridErrorCorrection，HEC)是反饋重傳糾錯和前向糾錯方式的綜合?；旌霞m錯在一定程度上避免了FEC系統(tǒng)譯碼設(shè)備復(fù)雜和ARQ系統(tǒng)信息連慣性差的缺點(diǎn)，但仍要求有反饋信道，而且不能同播(點(diǎn)對點(diǎn)通信)。共26頁166第六章差錯控制四、其他差錯控制方式除了上述3種基本差錯控制方式外，還有一些不采用校驗(yàn)碼的方法，常用的有回送法、冗余法和多數(shù)表決法。這些方法的傳輸效率都比較低，但思路簡單，實(shí)現(xiàn)起來比較方便，如圖6-5所示?；厮头ɑ厮头ň褪墙邮斩税咽盏降臄?shù)據(jù)原封不動地通過反饋信道送回到發(fā)送端，發(fā)送端比較發(fā)送的與反饋回來的數(shù)據(jù)，從而發(fā)現(xiàn)錨誤，并且把傳錯的數(shù)據(jù)重發(fā)出去，達(dá)到使接收端正確接收數(shù)據(jù)的目的。冗余法冗余法是發(fā)送端把數(shù)據(jù)發(fā)送兩次，接收端收到后，比較這發(fā)送方檢錯接受方檢錯共26頁176第六章差錯控制兩份數(shù)據(jù)。與回送法的差別是判斷力在接收瑞，而回送法則判斷方在發(fā)送瑞。可以認(rèn)為是一種特殊ARQ檢錯方式。多數(shù)表決法按照冗余法的思路，當(dāng)發(fā)送的數(shù)據(jù)副本多增加一份時，其碼距也隨之增加。當(dāng)碼距大于或等于2時，就具有糾錯能力。由此可見，數(shù)據(jù)冗余的份數(shù)多于2份，則可以不用反饋通道而實(shí)現(xiàn)糾錯，而只在接收端進(jìn)行判斷和自動糾錯。通常采用的方法是，把數(shù)據(jù)發(fā)送奇數(shù)次，接收端收到這些冗余的數(shù)據(jù)后，對每一位用多數(shù)表決法進(jìn)行判斷，取多數(shù)為正確位。多數(shù)表決法看起來非常笨拙，但是在實(shí)際通信系統(tǒng)中經(jīng)常使用，只不過為了減少冗余，提供效率，常常只對最重要的字段進(jìn)行冗余。共26頁186第六章差錯控制6.4ARQ的各種類型ARQ糾錯系統(tǒng)的工作方式基本上可分為兩種：一種是半雙工，稱為等待發(fā)送系統(tǒng)；另一種是全雙工通信方式，稱為連續(xù)工作系統(tǒng)。停止等待ARQ是半雙工通信方式，重返N-ARQ和選擇重發(fā)ARQ是全雙工工作方式。一、停止等待ARQ停止等待ARQ也稱為停等ARQ、發(fā)送等待ARQ等。它是指發(fā)送端發(fā)出一個碼組后便停止發(fā)送，等待接收端的應(yīng)答響應(yīng)信號，若接收端回答是已正確接收(ACK)，則發(fā)送端便發(fā)送下一個碼組；若接收端回答的是未正確接收(NAK)，則發(fā)送端便把上一個碼組重發(fā)一遍，直至該碼組正確接收為止，如圖6-6所示。共26頁196第六章差錯控制傳輸效率h：編碼效率hC：就是一個碼組中的數(shù)據(jù)位數(shù)與總位數(shù)之比：等待效率hW：數(shù)據(jù)信息有效率hs：接收端平均正確接收一個碼組，發(fā)送端要發(fā)送幾個碼組，誤組率PB接收到的錯誤碼組與總發(fā)送碼組之比，顯然其中式子中各符號含義如下：共26頁206第六章差錯控制二、重返N-ARQ重返N-ARQ((GOBACKN-ARQ)的意思是發(fā)生錯誤時退回N個碼組，即重新發(fā)送這N個碼組，它采取連續(xù)發(fā)送方式，對每個發(fā)送出去的碼組不必立即等待具應(yīng)答信號。在收到應(yīng)答信號之前,發(fā)送方只能最多發(fā)送N個碼組。當(dāng)?shù)却l(fā)送的時間較長時，為了提高傳輸效率，常常采用這種方式。N的取值根據(jù)不同系統(tǒng)的具體情況而定。N的取法：重返N-ARQ的傳輸效率可由下式求得：三、選擇重發(fā)ARQ在重返N-ARQ中，不管已發(fā)出的碼組有多少個出錯，只要共26頁216第六章差錯控制有一個碼組出錯，便要重發(fā)N個碼組。如果設(shè)法只重發(fā)有錯碼組，其余N-1個正確的碼組先存儲起來，不再隨有錯碼組一起重發(fā)，省下的時間用來傳送新的碼組，就可以大大提高傳輸效率。這就是選擇重發(fā)ARQ(SRQ，也稱為選擇拒絕ARQ)的思想。SRQ按全雙工工作，需要對稱的雙向信道。三、選擇重發(fā)ARQSRQ的傳輸效率h為：在實(shí)際中還應(yīng)考慮降低傳輸效率的兩個因素：一是緩沖器的容量，二是應(yīng)答信號的超時。接收端的緩沖存儲器不可能無限長，當(dāng)某一碼組經(jīng)多次重發(fā)后仍不能正確接收而接收緩沖器已滿時，后面接收的碼組即使正確，接收端也要拒收并要求重發(fā)。當(dāng)反向通道傳輸出錯，應(yīng)答信號無法到達(dá)發(fā)送端時，也按重發(fā)處理。共26頁226第六章差錯控制四、各種ARQ方式選擇原則對于停止等待ARQ方式，當(dāng)碼組長度大于RT(單位為位)。即傳輸碼組的時間大于環(huán)路延遲時間時，其傳輸效率較高，在某些條件下甚至比其他ARQ方式的傳輸效率還高。但當(dāng)信道環(huán)路延遲時間增大或傳輸速率R提高時，即使信道質(zhì)量較好，其傳輸效率也將很快下降。對于重返2-ARQ方式，當(dāng)信道質(zhì)量較好時，其傳輸效率相當(dāng)高，只要RT值不大于碼組長度，其傳輸效率不受RT數(shù)值的影響。但當(dāng)信道差錯率較高時，其傳輸效率下降很快，這時如采用SRQ，其傳輸效率就最高。當(dāng)RT大于重返2-ARQ的碼組長度n時，信道較好時，用加長碼組為好；而信道較差時，用重返N-ARQ(N值根據(jù)需要來確定)為好，因?yàn)橹胤礜-ARQ方式的傳輸效率隨誤碼率增加而緩慢下降的。當(dāng)信道較差時(誤碼率在10-3左右)，并且RT值較大時，短碼組的重返N-ARQ方式比停止等待ARQ方式或長碼組的重返2-ARQ方式為好。共26頁236第六章差錯控制6.5信道的差錯特性一、信道的差錯統(tǒng)計特性1、誤碼率與誤組率2、信道的差錯分布類型隨機(jī)差錯：在信道上的差錯是隨機(jī)發(fā)生的，每個碼元是否有錯彼此無關(guān)。存在這種差錯的信道稱為無記憶信道或隨機(jī)信道，例如微波接力和衛(wèi)星轉(zhuǎn)發(fā)等信道。突發(fā)差錯：是在某一段時間內(nèi)差錯成片出現(xiàn)而在另一段時間內(nèi)差錯很少。線路接頭接觸不良、無線信道受雷電干擾等都會產(chǎn)生這類差錯。信道差錯的數(shù)學(xué)模型有很多種，在ARQ系統(tǒng)中使用較多的是二元對稱