數(shù)據(jù)通信基礎6.

1、1.6 差錯控制差錯控制1.6.1 差錯類型及基本控制方法差錯類型及基本控制方法 噪聲引入的隨機誤碼，均勻分布噪聲引入的隨機誤碼，均勻分布 由干擾、快衰落引起的突發(fā)誤碼由干擾、快衰落引起的突發(fā)誤碼 單比特錯誤單比特錯誤 多比特錯誤多比特錯誤 突發(fā)錯誤突發(fā)錯誤1)1) 自動請求重發(fā)自動請求重發(fā) ARQ(Automatic Request for Repeat)ARQ(Automatic Request for Repeat)2)2) 前向糾錯前向糾錯 FEC(Forward Error Correction)FEC(Forward Error Correction)3)3) 混合方式混合方式 H

2、EC(Hybrid FEC-ARQ)HEC(Hybrid FEC-ARQ)檢錯編碼存儲發(fā)收收發(fā)kIkI檢錯譯碼自動請求重發(fā)自動請求重發(fā)ARQARQ 由發(fā)端送出能夠發(fā)現(xiàn)錯誤的編碼，由收端判決傳輸中有無錯誤產(chǎn)生。由發(fā)端送出能夠發(fā)現(xiàn)錯誤的編碼，由收端判決傳輸中有無錯誤產(chǎn)生。 如果發(fā)現(xiàn)錯誤，則通過反向信道把這一判決結果反饋給發(fā)端。發(fā)端把收如果發(fā)現(xiàn)錯誤，則通過反向信道把這一判決結果反饋給發(fā)端。發(fā)端把收端認為錯誤的信息再次重發(fā)，從而達到正確傳輸?shù)哪康?。端認為錯誤的信息再次重發(fā)，從而達到正確傳輸?shù)哪康摹?其特點是需要反饋信道，譯碼設備簡單，對突發(fā)錯誤和信道干擾較嚴其特點是需要反饋信道，譯碼設備簡單，對突發(fā)錯

3、誤和信道干擾較嚴重重時有效，時有效， 但實時性差但實時性差. . 前向糾錯前向糾錯FECFEC 發(fā)端發(fā)送能夠糾正錯誤的碼，收端收到信碼后自動地糾正傳輸中發(fā)端發(fā)送能夠糾正錯誤的碼，收端收到信碼后自動地糾正傳輸中的錯誤。其特點是單向傳輸，實時性好。的錯誤。其特點是單向傳輸，實時性好。 譯碼設備較復雜，代碼效率低，適用于惡劣環(huán)境和可靠性要求高譯碼設備較復雜，代碼效率低，適用于惡劣環(huán)境和可靠性要求高的場合。的場合。 發(fā)端發(fā)端收端收端糾錯編碼糾錯編碼舉例：遙控天車舉例：遙控天車 在信息碼序列中加監(jiān)督碼就稱為差錯控制編碼，也叫糾錯編碼。不同的在信息碼序列中加監(jiān)督碼就稱為差錯控制編碼，也叫糾錯編碼。不同的編

4、碼方法，有不同的檢錯和糾錯能力，增加監(jiān)督碼元越多，檢（糾）錯能編碼方法，有不同的檢錯和糾錯能力，增加監(jiān)督碼元越多，檢（糾）錯能力越強。力越強。 差錯控制編碼原則上是降低差錯控制編碼原則上是降低 R Rb b來換取可靠性提高（降低來換取可靠性提高（降低P Pe e）。）。1.6.2 差錯控制編碼的基本原理差錯控制編碼的基本原理 存在噪聲干擾的信道，若信道容量為存在噪聲干擾的信道，若信道容量為C C，只要發(fā)送端以低于，只要發(fā)送端以低于C C的速率的速率R R發(fā)送信息（發(fā)送信息（R R為輸入道編碼器的二進制碼元速率），為輸入道編碼器的二進制碼元速率），則一定存在一種編碼方式，使編碼的錯誤概率則一定存

5、在一種編碼方式，使編碼的錯誤概率P Pe e隨著碼長隨著碼長n n的的增加將按指數(shù)下降，即增加將按指數(shù)下降，即 P Pe e e =e+1 =e+1 (2)(2)為糾正為糾正 t t 個錯碼，則要求最小碼距個錯碼，則要求最小碼距 d d0 0 =2t+1 =2t+1 (3)(3)為糾正為糾正 t t 個錯碼，同時為檢測個錯碼，同時為檢測 e e 個錯碼，則要求最小碼距個錯碼，則要求最小碼距 d d0 0 =e+t+1 ,et =e+t+1 ,et00，11碼距為碼距為 210，011位錯，但不知哪位錯。位錯，但不知哪位錯。000，111碼距為碼距為 3001，010，100 1位錯。位錯。11

6、0，101，011 分組碼分組碼 分組碼一般可用分組碼一般可用( (n n, ,k k) )表示。表示。 k k是每組二進制信息碼元的數(shù)目是每組二進制信息碼元的數(shù)目. . n n是編碼碼組的碼元總位數(shù)，又稱為碼組長度，簡稱碼長。是編碼碼組的碼元總位數(shù)，又稱為碼組長度，簡稱碼長。 r r= =n n- -k k為每個碼組中的監(jiān)督碼元數(shù)目。為每個碼組中的監(jiān)督碼元數(shù)目。 分組碼可看作是對每段分組碼可看作是對每段k k位長的信息組以一定的規(guī)則增加位長的信息組以一定的規(guī)則增加r r個監(jiān)督元，個監(jiān)督元， 組成長為組成長為n n的碼字。的碼字。krn編碼效率編碼效率 用差錯控制編碼提高通信系統(tǒng)的可靠性，用差

7、錯控制編碼提高通信系統(tǒng)的可靠性， 是是以降低有效以降低有效性為代價換來的性為代價換來的。我們定義編碼效率。我們定義編碼效率R R來衡量有效性來衡量有效性: :R=k/nR=k/n其中其中, k, k是信息元的個數(shù)，是信息元的個數(shù)，n n為碼長。為碼長。 對糾錯碼的基本要求是對糾錯碼的基本要求是: : 檢錯和糾錯能力盡量強；檢錯和糾錯能力盡量強； 編編碼效率盡量高；編碼規(guī)律盡量簡單碼效率盡量高；編碼規(guī)律盡量簡單。實際中要根據(jù)具體指標要求，。實際中要根據(jù)具體指標要求，保證有一定糾、檢錯能力和編碼效率，并且易于實現(xiàn)。保證有一定糾、檢錯能力和編碼效率，并且易于實現(xiàn)。1.6.3 奇偶監(jiān)督碼奇偶監(jiān)督碼 奇

8、偶監(jiān)督碼是在原信息碼后面附加一個監(jiān)督元，奇偶監(jiān)督碼是在原信息碼后面附加一個監(jiān)督元， 使得碼使得碼組中組中“1”1”的個數(shù)是奇數(shù)或偶數(shù)?；蛘哒f，它是含一個監(jiān)督元，的個數(shù)是奇數(shù)或偶數(shù)。或者說，它是含一個監(jiān)督元，碼重為奇數(shù)或偶數(shù)的碼重為奇數(shù)或偶數(shù)的( (n n, ,n n-1)-1)系統(tǒng)分組碼。奇偶監(jiān)督碼又分系統(tǒng)分組碼。奇偶監(jiān)督碼又分為為奇監(jiān)督碼和偶監(jiān)督碼。奇監(jiān)督碼和偶監(jiān)督碼。An-1 An-2 A1A0An-1 An-2 A1 A0 =0 偶校驗偶校驗An-1 An-2 A1 A0 =1 奇校驗奇校驗 如果以上關系被破壞，則出現(xiàn)錯誤，因此能檢查出奇數(shù)如果以上關系被破壞，則出現(xiàn)錯誤，因此能檢查出奇數(shù)

9、個錯誤，但不能檢測偶數(shù)個錯誤。個錯誤，但不能檢測偶數(shù)個錯誤。 最小碼距為最小碼距為 d d0 0=2 =2 編碼效率編碼效率R=（n-1)/n水平奇偶監(jiān)督碼和垂直監(jiān)督碼（行列校驗）示例水平奇偶監(jiān)督碼和垂直監(jiān)督碼（行列校驗）示例for(i=0,fcs=0;in;i+) fcs=sendi; (1) (1) 可發(fā)現(xiàn)某行或某列上奇數(shù)個錯誤。可發(fā)現(xiàn)某行或某列上奇數(shù)個錯誤。(2)(2)能檢測出所有長度不大于方陣中行數(shù)（或列數(shù)）的突發(fā)錯誤。能檢測出所有長度不大于方陣中行數(shù)（或列數(shù)）的突發(fā)錯誤。例：例：4 4行行7 7列信息組的水平垂直偶校驗碼。列信息組的水平垂直偶校驗碼。 信息組信息組 校驗位校驗位 01

10、11001 0111001 0 0 0010101 0010101 1 1 0101011 0101011 0 0 1010101 1010101 0 0 垂直偶校驗字符垂直偶校驗字符 10100101010010 奇奇 01011010101101011100101110010 0 001010100101011 1 010101101010110 0 101010110101010 101001010 101001011.6.4 線性分組碼線性分組碼 (7,4)分組碼：設其碼字為分組碼：設其碼字為A=a6 a5 a4 a3 a2 a1 a0 前前 4 位是信息元，后位是信息元，后 3 位是

11、監(jiān)督元，可用下列線性方程組來描述該分組碼，位是監(jiān)督元，可用下列線性方程組來描述該分組碼，產(chǎn)生監(jiān)督元。產(chǎn)生監(jiān)督元。 a6+ a5 + a 4+ a 2=0a6 + a5 + a 4+ a 1=0a6 + a5 + a 4+ a 0=00001001101010101100101110123456aaaaaaa矩陣形式矩陣形式00TTTHAAH或 H H矩陣各行是線性無關的。通過監(jiān)督矩陣可以知道監(jiān)督碼和信息碼矩陣各行是線性無關的。通過監(jiān)督矩陣可以知道監(jiān)督碼和信息碼的監(jiān)督關系。的監(jiān)督關系。()TTTTTSBHAE HAHEHEH=+=+= 設發(fā)送碼組設發(fā)送碼組A=A=a an n-1-1, ,a a

12、n n-2-2, , ,a a1 1, ,a a0 0 接收碼組接收碼組B B= =b bn n-1-1, ,b bn n-2-2, , ,b b1 1, ,b b0 0， 收發(fā)碼組之差定收發(fā)碼組之差定義為錯誤圖樣義為錯誤圖樣E E， 也稱為誤差矢量，也稱為誤差矢量， 則則校正子校正子S：1.6.5 循環(huán)冗余檢驗碼循環(huán)冗余檢驗碼 CRCCRC（Cyclic Redundancy Check Cyclic Redundancy Check ） 收發(fā)雙方約定一個生成多項式收發(fā)雙方約定一個生成多項式g(x) g(x) ，發(fā)送方在幀的末尾加上校驗，發(fā)送方在幀的末尾加上校驗和，使帶校驗和的幀的多項式能被

13、和，使帶校驗和的幀的多項式能被g(x)g(x)整除整除。接收方收到后，用多項接收方收到后，用多項式除以式除以g(x) g(x) ，若有余數(shù)，則傳輸有錯。，若有余數(shù)，則傳輸有錯。M（X）. X n-k /g（x）=q（X）+r（x ）/g（x）M（X） . X n-k + r（x ）M（X） . X n-k + r（x ）M（X） . X n-k /g（x）=q（X）+r（x ）/g（x）若若r（x ） = r（x ） 則認為無錯則認為無錯定理：定理：在一個在一個(n，k)循環(huán)碼中，存在一個且只有一個循環(huán)碼中，存在一個且只有一個(n-k)次的碼多項式次的碼多項式g(x)=xn-k+gn-k-1x

14、n-k-1+.g2x2+g1x+1滿足下列兩個條件：滿足下列兩個條件：此循環(huán)碼中任一碼多項式都是此循環(huán)碼中任一碼多項式都是g(x)的倍式；的倍式；任意一個任意一個(n-1)次或次或(n-1)次以下又是次以下又是g(x)倍式的多項式必定是此循環(huán)碼的倍式的多項式必定是此循環(huán)碼的一個碼多項式；一個碼多項式；例：設發(fā)送碼例：設發(fā)送碼M(x)=111, g(x)=xM(x)=111, g(x)=x4 4+x+x3 3+x+x2 2+1+11)1) M(x)M(x)* *x xn n-k-k=1110000=11100002)2) M(x)M(x)* *x xn n-k -k /g(x)=100+0100

15、/11101/g(x)=100+0100/111013)3) M(x)M(x)* *x xn n- - +r(x)= 111 +r(x)= 111 01000100 100100 11101 1110000 11101 1110000 11101 11101 01000100CRCCRC生成電路示意生成電路示意a b c d0 0 0 000 0 0 011 0 1 1 10 1 0 110 0 1 0 abcd+uint crc16r(unsigned char *ptr, unsigned char len)unsigned char i;while(len-!=0)for(i=0 x01;i!=0;i = 1; crc = 0 x8408;else crc = 1;if(*ptr&i)!=0) crc = 0 x8408;ptr+;return(crc);CRCCRC程序生成示意程序生成示意常用的常用