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

常用的校驗編碼方法

差錯控制方法

ARQ的各種類型

信道的差錯特性

2糾錯檢錯編碼原理

差錯類型

校驗碼的分類

編碼的糾檢錯能力

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

檢錯碼和糾錯碼分組碼和卷積碼線性碼和非線性碼系統碼和非系統碼5檢錯碼和糾錯碼

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

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

線性碼數據位與監督位之間的關系為線性關系即滿足一組線性方程式非線性碼數據位與監督位之間是非線性關系8系統碼和非系統碼

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

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

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

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

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

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

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

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

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

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

糾錯碼多重奇偶校驗非系統碼33海明不等式對于只能糾正一位錯的校驗碼校驗位的位數K和數據位的位數N之間的關系由下面的海明不等式給出：34海明碼編碼規則校驗位放在第2i-1位置即，校驗位一般放在第1、2、4、8位數據位依次從低到高占據海明碼中剩下的位置被校驗的數據位的下標等于所有參與校驗該位的校驗位的下標之和。35海明碼編碼規則H7H6H5H4H3H2H1數據和校驗位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例如：數據1001P1=0P2=0P3=1海明碼：1001100接收譯碼S1=P1⊕D4⊕D2⊕D1S2=P2⊕D4⊕D3⊕D1S3=P3⊕D4⊕D3⊕D2若S3S2S1為000，則表示接收無錯37差錯控制方法

反饋重發糾錯（ARQ）前向糾錯（FEC）混合糾錯（HEC）

38ARQ

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

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

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

接收端所接收的數據比特數與發送端在相同時間內所發送的總比特數之比46編碼效率ηc

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

考慮了等待應答時間后的效率n為碼組的長度R為數據傳輸速率T為環路遲延時間48數據信息有效率ηs

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

49總傳輸效率

編碼效率ηc等待效率ηw數據信息有效率ηs

50重返N-ARQ

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

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

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

信道的差錯統計特性反饋信道對應答信號的影響

56信道的差錯統計特性