《計算機通信技術》課件 第5章 差錯控制

《計算機通信技術》第5章差錯控制ErrorControl1本章內容糾錯檢錯編碼原理

常用的校驗編碼方法

差錯控制方法

ARQ的各種類型

信道的差錯特性

2糾錯檢錯編碼原理

差錯類型

校驗碼的分類

編碼的糾檢錯能力

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

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

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

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

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

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

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碼距與編碼糾檢錯能力的關系1.若d≥e+1，只要出錯位數(shù)不超過e，則可檢測出e個錯誤；

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

奇偶檢驗碼方陣校驗碼恒比碼校驗和

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

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

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

25CRC碼的實現(xiàn)方法D：k位數(shù)據(jù)F：n-k位的FCSP：n-k+1位的生成多項式T：n位的幀，即D+F將k位的數(shù)據(jù)左移n-k位，低位補0，再用n-k+1位的生成多項式進行模2除，所得的n-k位余數(shù)就是FCS。26CRC碼的計算D(x)=x5+x4+x+1，G(x)=x4+x3+1，求CRC碼。數(shù)據(jù)：110011生成多項式：11001CRC碼：110011100127CRC碼算法的證明28生成多項式的選擇生成多項式的最高位和最低位必須為1。當CRC碼的任何一位發(fā)生錯誤時，被生成多項式做模2除后應該使余數(shù)不為0。不同位發(fā)生錯誤時，應該使余數(shù)不同。對余數(shù)繼續(xù)做模2除，應使余數(shù)循環(huán)。檢測單錯，要含一個以上的非零項檢測雙錯，要含一個三項因式檢測奇數(shù)錯，要含因式(x+1)29生成多項式標準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碼生成多項式為CRC-CCITT31CRC計算程序//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海明碼

糾錯碼多重奇偶校驗非系統(tǒng)碼33海明不等式對于只能糾正一位錯的校驗碼校驗位的位數(shù)K和數(shù)據(jù)位的位數(shù)N之間的關系由下面的海明不等式給出：34海明碼編碼規(guī)則校驗位放在第2i-1位置即，校驗位一般放在第1、2、4、8位數(shù)據(jù)位依次從低到高占據(jù)海明碼中剩下的位置被校驗的數(shù)據(jù)位的下標等于所有參與校驗該位的校驗位的下標之和。35海明碼編碼規(guī)則H7H6H5H4H3H2H1數(shù)據(jù)和校驗位D4D3D2P3D1P2P1參與校驗位號7=4+2+16=2+45=4+143=1+221參與校驗位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必須有反饋信道用于點對點的通信39ARQ類型停止等待ARQ重返N-ARQ選擇重發(fā)ARQ40FEC前向糾錯方式ForwardErrorCorrection糾錯碼適用于單工通信不需要反向信道41HEC混合糾錯HybridErrorCorrection反饋重傳糾錯和前向糾錯方式的綜合校驗碼的碼距必須大于或等于442其它差錯控制方式

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

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

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

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

考慮了等待應答時間后的效率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)路遲延沒有直接關系重發(fā)效率為（1-PB）54各種ARQ傳輸效率的比較

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

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

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