《計(jì)算機(jī)通信技術(shù)》課件 第5章 差錯控制

《計(jì)算機(jī)通信技術(shù)》第5章差錯控制ErrorControl1本章內(nèi)容糾錯檢錯編碼原理

常用的校驗(yàn)編碼方法

差錯控制方法

ARQ的各種類型

信道的差錯特性

2糾錯檢錯編碼原理

差錯類型

校驗(yàn)碼的分類

編碼的糾檢錯能力

3差錯類型單比特錯只改變一個比特不影響鄰近的其它比特也稱為隨機(jī)差錯或獨(dú)立差錯突發(fā)錯連續(xù)發(fā)生的一串錯差錯之間有相關(guān)性突發(fā)長度B出錯的串長度4校驗(yàn)碼的分類

檢錯碼和糾錯碼分組碼和卷積碼線性碼和非線性碼系統(tǒng)碼和非系統(tǒng)碼5檢錯碼和糾錯碼

檢錯碼只能檢錯，不能糾錯糾錯碼能夠發(fā)現(xiàn)差錯知道是哪個比特傳輸出錯采取糾正措施6分組碼和卷積碼

分組碼附加的監(jiān)督位僅僅根據(jù)本組內(nèi)的信息代碼決定常用符號（M，N）表示N為每組內(nèi)信息的位數(shù)M是編碼后的總長度K=M-N為每組內(nèi)監(jiān)督位的數(shù)目卷積碼監(jiān)督位不僅與本組的信息有關(guān)，而且還與前若干組的信息有關(guān)糾錯能力強(qiáng)7線性碼和非線性碼

線性碼數(shù)據(jù)位與監(jiān)督位之間的關(guān)系為線性關(guān)系即滿足一組線性方程式非線性碼數(shù)據(jù)位與監(jiān)督位之間是非線性關(guān)系8系統(tǒng)碼和非系統(tǒng)碼

系統(tǒng)碼數(shù)據(jù)位在編碼后保持原來的形式不變非系統(tǒng)碼數(shù)據(jù)碼元改變了原來的位置監(jiān)督碼元可能會散落分布在數(shù)據(jù)碼元中9編碼術(shù)語海明距離兩個碼字之間對應(yīng)位不同的個數(shù)碼距某種編碼的碼距是全部碼字中兩兩之間海明距離的最小值。合法碼字如果一個碼字符合編碼規(guī)則，則稱該碼字是一個合法碼字。非法碼字10編碼的糾檢錯能力碼距d與編碼的檢錯和糾錯能力的關(guān)系是：

1.若d≥e+1，只要出錯位數(shù)不超過e，則可檢測出e個錯誤；

2.若d≥2t+1，只要出錯位數(shù)不超過t，則可糾正t個錯誤；

3.若d≥e+t+1（e>t），只要出錯位數(shù)不超過e，則可糾正t個錯誤，同時檢測出e個錯誤。11碼距與編碼糾檢錯能力的關(guān)系1.若d≥e+1，只要出錯位數(shù)不超過e，則可檢測出e個錯誤；

12碼距與編碼糾檢錯能力的關(guān)系2.若d≥2t+1，只要出錯位數(shù)不超過t，則可糾正t個錯誤；13碼距與編碼糾檢錯能力的關(guān)系3.若d≥e+t+1（e>t），只要出錯位數(shù)不超過e，則可糾正t個錯誤，同時檢測出e個錯誤。14常用的校驗(yàn)編碼方法

奇偶檢驗(yàn)碼方陣校驗(yàn)碼恒比碼校驗(yàn)和

循環(huán)冗余校驗(yàn)碼15奇偶校驗(yàn)碼在字符上附加奇偶校驗(yàn)位奇偶校驗(yàn)碼是奇校驗(yàn)碼和偶校驗(yàn)碼的統(tǒng)稱偶校驗(yàn)：整個字符中有偶數(shù)個101奇校驗(yàn)：整個字符中有奇數(shù)個101只能檢測奇數(shù)位出錯，如果有偶數(shù)位出錯，檢測不到16奇偶校驗(yàn)碼奇校驗(yàn)：奇數(shù)個1則為0，否則為1偶校驗(yàn)：偶數(shù)個1則為0，否則為117原編碼奇校驗(yàn)偶校驗(yàn)00000000100000001000100001011100110011100010101010110100奇偶校驗(yàn)碼只能檢測奇數(shù)位出錯出錯則要求重傳18原編碼奇校驗(yàn)錯誤碼信息位出錯00000000101001校驗(yàn)位出錯00100010000101偶數(shù)位出錯00100010001000例題已知字符M的ASCII碼值的十進(jìn)制表示為77，如果將最高位設(shè)置為奇校驗(yàn)位，則字符M的ASCII碼值設(shè)置奇校驗(yàn)位后，它的二進(jìn)制表示為（）A.01001101B.11001101C.01101011D.10111101答案：B19方陣檢驗(yàn)碼垂直冗余校驗(yàn)VRC：就是字符奇偶校驗(yàn)；水平冗余校驗(yàn)LRC：就是對數(shù)據(jù)塊中每個字符的對應(yīng)位進(jìn)行奇偶校驗(yàn)。20恒比碼恒比碼就是使校驗(yàn)碼中的1和0的數(shù)目之比是一個常數(shù)。編碼生成時是查表接收檢驗(yàn)時是檢查每個編碼中1出現(xiàn)的次數(shù)是否正確21中國五單位保護(hù)電碼表22數(shù)字電碼數(shù)字電碼001101500111101011610101211001711100310110801110411010910011校驗(yàn)和

把數(shù)據(jù)塊中的每一個字符代碼都按二進(jìn)制加法求和例：傳送CA：1000011100000123IP數(shù)據(jù)報(bào)校驗(yàn)方式發(fā)送方校驗(yàn)和字段全設(shè)0；將IP報(bào)頭按16位分組，不足16位用0補(bǔ)足；將各組數(shù)據(jù)反碼求和；將得到的和的反碼填入校驗(yàn)和字段；接收方將IP報(bào)頭按16位分組，不足16位用0補(bǔ)足；將各組數(shù)據(jù)反碼求和，檢查得到的和是否是全1如果是全1則進(jìn)行下步處理，否則意味著包已變化從而丟棄之。

24循環(huán)冗余校驗(yàn)碼CRC用事先約定的一個生成多項(xiàng)式去除數(shù)據(jù)串，將余數(shù)作為幀校驗(yàn)序列（FCS）生成多項(xiàng)式：可以用一個二進(jìn)制串表示K位的二進(jìn)制串，和xk-1~x0的k-1階多項(xiàng)式對應(yīng)例如：代碼1010111對應(yīng)的多項(xiàng)式為x6+x4+x2+x+1多項(xiàng)式為x5+x3+x2+x+1對應(yīng)的代碼101111

25CRC碼的實(shí)現(xiàn)方法D：k位數(shù)據(jù)F：n-k位的FCSP：n-k+1位的生成多項(xiàng)式T：n位的幀，即D+F將k位的數(shù)據(jù)左移n-k位，低位補(bǔ)0，再用n-k+1位的生成多項(xiàng)式進(jìn)行模2除，所得的n-k位余數(shù)就是FCS。26CRC碼的計(jì)算D(x)=x5+x4+x+1，G(x)=x4+x3+1，求CRC碼。數(shù)據(jù)：110011生成多項(xiàng)式：11001CRC碼：110011100127CRC碼算法的證明28生成多項(xiàng)式的選擇生成多項(xiàng)式的最高位和最低位必須為1。當(dāng)CRC碼的任何一位發(fā)生錯誤時，被生成多項(xiàng)式做模2除后應(yīng)該使余數(shù)不為0。不同位發(fā)生錯誤時，應(yīng)該使余數(shù)不同。對余數(shù)繼續(xù)做模2除，應(yīng)使余數(shù)循環(huán)。檢測單錯，要含一個以上的非零項(xiàng)檢測雙錯，要含一個三項(xiàng)因式檢測奇數(shù)錯，要含因式(x+1)29生成多項(xiàng)式標(biāo)準(zhǔn)CRC-12=x12+x11+x3+x2+x+1CRC-16=x16+x15+x2+1CRC-CCITT=x16+x12+x5+1CRC-32=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+130CRC電路用硬件電路生成CRC碼生成多項(xiàng)式為CRC-CCITT31CRC計(jì)算程序//CRCcalculation，'x'isthebytetobeaddedtoCRC.//CCITTpolynomialusedforCRCcalculation：x16+x12+x5+1voidupdcrc（x）unsignedcharx;{externunsignedint

crcaccum;//CRCresult，2byteunsignedshifter，flag;for（shifter=0x80;shifter;shifter>>=1）

{flag=（crcaccum&0x8000）;//Firstbit=1?

crcaccum<<=1;//leftshift1bit

crcaccum|=（（shifter&x）?1：0）;//addxtocrcaccumtailif（flag）crcaccum^=0x1021;//XORpolynomial}}32海明碼

糾錯碼多重奇偶校驗(yàn)非系統(tǒng)碼33海明不等式對于只能糾正一位錯的校驗(yàn)碼校驗(yàn)位的位數(shù)K和數(shù)據(jù)位的位數(shù)N之間的關(guān)系由下面的海明不等式給出：34海明碼編碼規(guī)則校驗(yàn)位放在第2i-1位置即，校驗(yàn)位一般放在第1、2、4、8位數(shù)據(jù)位依次從低到高占據(jù)海明碼中剩下的位置被校驗(yàn)的數(shù)據(jù)位的下標(biāo)等于所有參與校驗(yàn)該位的校驗(yàn)位的下標(biāo)之和。35海明碼編碼規(guī)則H7H6H5H4H3H2H1數(shù)據(jù)和校驗(yàn)位D4D3D2P3D1P2P1參與校驗(yàn)位號7=4+2+16=2+45=4+143=1+221參與校驗(yàn)位P3、P2、P1P3、P2P3、P1P3P2、P1P2P136P1=D4⊕D2⊕D1P2=D4⊕D3⊕D1P3=D4⊕D3⊕D2例如：數(shù)據(jù)1001P1=0P2=0P3=1海明碼：1001100接收譯碼S1=P1⊕D4⊕D2⊕D1S2=P2⊕D4⊕D3⊕D1S3=P3⊕D4⊕D3⊕D2若S3S2S1為000，則表示接收無錯37差錯控制方法

反饋重發(fā)糾錯（ARQ）前向糾錯（FEC）混合糾錯（HEC）

38ARQ

Automatic-RepeatRequest必須有反饋信道用于點(diǎn)對點(diǎn)的通信39ARQ類型停止等待ARQ重返N-ARQ選擇重發(fā)ARQ40FEC前向糾錯方式ForwardErrorCorrection糾錯碼適用于單工通信不需要反向信道41HEC混合糾錯HybridErrorCorrection反饋重傳糾錯和前向糾錯方式的綜合校驗(yàn)碼的碼距必須大于或等于442其它差錯控制方式

回送法冗余法多數(shù)表決法43ARQ的各種類型停止等待ARQ重返N-ARQ選擇重發(fā)ARQ44停止等待ARQ

等待接收端的應(yīng)答響應(yīng)信號正確接收（ACK）未正確接收（NAK）45傳輸效率

接收端所接收的數(shù)據(jù)比特?cái)?shù)與發(fā)送端在相同時間內(nèi)所發(fā)送的總比特?cái)?shù)之比46編碼效率ηc

考慮了控制比特?cái)?shù)和監(jiān)督碼元之后的效率如碼組的起止標(biāo)志n為碼組長度r為控制比特?cái)?shù)加監(jiān)督碼元數(shù)47等待效率ηw

考慮了等待應(yīng)答時間后的效率n為碼組的長度R為數(shù)據(jù)傳輸速率T為環(huán)路遲延時間48數(shù)據(jù)信息有效率ηs

考慮了傳輸差錯后的效率誤組率PB

49總傳輸效率

編碼效率ηc等待效率ηw數(shù)據(jù)信息有效率ηs

50重返N-ARQ

GOBACKN-ARQ發(fā)生錯誤時退回N個碼組，重新發(fā)送這N個碼組51重返N-ARQ的效率傳輸效率N的取值52選擇重發(fā)ARQ

SRQ，也稱為選擇拒絕ARQ只重發(fā)有錯碼組其余正確的碼組先存儲起來53選擇重發(fā)ARQ的傳輸效率傳輸效率與信道環(huán)路遲延沒有直接關(guān)系重發(fā)效率為（1-PB）54各種ARQ傳輸效率的比較

等待時間的影響減少開銷減少重傳次數(shù)選用最佳碼長55信道的差錯特性

信道的差錯統(tǒng)計(jì)特性反饋信道對應(yīng)答信號的影響

56信道的差錯統(tǒng)計(jì)特性