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

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

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

差錯(cuò)控制方法

ARQ的各種類型

信道的差錯(cuò)特性

2糾錯(cuò)檢錯(cuò)編碼原理

差錯(cuò)類型

校驗(yàn)碼的分類

編碼的糾檢錯(cuò)能力

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

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

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

分組碼附加的監(jiān)督位僅僅根據(jù)本組內(nèi)的信息代碼決定常用符號(hào)（M，N）表示N為每組內(nèi)信息的位數(shù)M是編碼后的總長度K=M-N為每組內(nèi)監(jiān)督位的數(shù)目卷積碼監(jiān)督位不僅與本組的信息有關(guān)，而且還與前若干組的信息有關(guān)糾錯(cuò)能力強(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)督碼元可能會(huì)散落分布在數(shù)據(jù)碼元中9編碼術(shù)語海明距離兩個(gè)碼字之間對應(yīng)位不同的個(gè)數(shù)碼距某種編碼的碼距是全部碼字中兩兩之間海明距離的最小值。合法碼字如果一個(gè)碼字符合編碼規(guī)則，則稱該碼字是一個(gè)合法碼字。非法碼字10編碼的糾檢錯(cuò)能力碼距d與編碼的檢錯(cuò)和糾錯(cuò)能力的關(guān)系是：

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

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

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

12碼距與編碼糾檢錯(cuò)能力的關(guān)系2.若d≥2t+1，只要出錯(cuò)位數(shù)不超過t，則可糾正t個(gè)錯(cuò)誤；13碼距與編碼糾檢錯(cuò)能力的關(guān)系3.若d≥e+t+1（e>t），只要出錯(cuò)位數(shù)不超過e，則可糾正t個(gè)錯(cuò)誤，同時(shí)檢測出e個(gè)錯(cuò)誤。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)：整個(gè)字符中有偶數(shù)個(gè)101奇校驗(yàn)：整個(gè)字符中有奇數(shù)個(gè)101只能檢測奇數(shù)位出錯(cuò)，如果有偶數(shù)位出錯(cuò)，檢測不到16奇偶校驗(yàn)碼奇校驗(yàn)：奇數(shù)個(gè)1則為0，否則為1偶校驗(yàn)：偶數(shù)個(gè)1則為0，否則為117原編碼奇校驗(yàn)偶校驗(yàn)00000000100000001000100001011100110011100010101010110100奇偶校驗(yàn)碼只能檢測奇數(shù)位出錯(cuò)出錯(cuò)則要求重傳18原編碼奇校驗(yàn)錯(cuò)誤碼信息位出錯(cuò)00000000101001校驗(yàn)位出錯(cuò)00100010000101偶數(shù)位出錯(cuò)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ù)塊中每個(gè)字符的對應(yīng)位進(jìn)行奇偶校驗(yàn)。20恒比碼恒比碼就是使校驗(yàn)碼中的1和0的數(shù)目之比是一個(gè)常數(shù)。編碼生成時(shí)是查表接收檢驗(yàn)時(shí)是檢查每個(gè)編碼中1出現(xiàn)的次數(shù)是否正確21中國五單位保護(hù)電碼表22數(shù)字電碼數(shù)字電碼001101500111101011610101211001711100310110801110411010910011校驗(yàn)和

把數(shù)據(jù)塊中的每一個(gè)字符代碼都按二進(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用事先約定的一個(gè)生成多項(xiàng)式去除數(shù)據(jù)串，將余數(shù)作為幀校驗(yàn)序列（FCS）生成多項(xiàng)式：可以用一個(gè)二進(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ā)生錯(cuò)誤時(shí)，被生成多項(xiàng)式做模2除后應(yīng)該使余數(shù)不為0。不同位發(fā)生錯(cuò)誤時(shí)，應(yīng)該使余數(shù)不同。對余數(shù)繼續(xù)做模2除，應(yīng)使余數(shù)循環(huán)。檢測單錯(cuò)，要含一個(gè)以上的非零項(xiàng)檢測雙錯(cuò)，要含一個(gè)三項(xiàng)因式檢測奇數(shù)錯(cuò)，要含因式(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海明碼

糾錯(cuò)碼多重奇偶校驗(yàn)非系統(tǒng)碼33海明不等式對于只能糾正一位錯(cuò)的校驗(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)位號(hào)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，則表示接收無錯(cuò)37差錯(cuò)控制方法

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

38ARQ

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

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

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

接收端所接收的數(shù)據(jù)比特?cái)?shù)與發(fā)送端在相同時(shí)間內(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)答時(shí)間后的效率n為碼組的長度R為數(shù)據(jù)傳輸速率T為環(huán)路遲延時(shí)間48數(shù)據(jù)信息有效率ηs

考慮了傳輸差錯(cuò)后的效率誤組率PB

49總傳輸效率

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

50重返N-ARQ

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

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

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

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

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