第7章-差錯控制原理

1、第10章 差錯控制原理信道編碼，按一定的規(guī)則加入冗信道編碼，按一定的規(guī)則加入冗余度。（信源編碼是去掉信源的余度。（信源編碼是去掉信源的冗余度。）冗余度。）關于差錯控制關于差錯控制tt信道干擾 d(t)f (t)f (t)d(t)模擬信號(a) 模擬系統(tǒng)干擾示意圖tt信道干擾 d(t)f (t)f (t)d(t)數(shù)字信號(b) 數(shù)字系統(tǒng)干擾示意圖OOOO關于差錯控制關于差錯控制 常用差錯控制方式常用差錯控制方式差錯控制基本思想及方案差錯控制基本思想及方案l差錯控制編碼的基本思想：差錯控制編碼的基本思想：在信息碼元中加入在信息碼元中加入一些冗余碼元一些冗余碼元監(jiān)督碼元，這些冗余碼元不監(jiān)督碼元，這些

2、冗余碼元不含任何通信信息，但是在編碼過程中，用來監(jiān)含任何通信信息，但是在編碼過程中，用來監(jiān)督信息碼元，譯碼時利用特定的規(guī)律來鑒別傳督信息碼元，譯碼時利用特定的規(guī)律來鑒別傳輸是否發(fā)生錯誤，或者糾正錯誤，從而降低誤輸是否發(fā)生錯誤，或者糾正錯誤，從而降低誤碼率。碼率。l差錯控制兩種方案：差錯控制兩種方案：發(fā)現(xiàn)錯誤發(fā)現(xiàn)錯誤檢錯編碼；檢錯編碼；糾正錯誤糾正錯誤糾錯編碼。糾錯編碼。 差錯控制中常用名詞差錯控制中常用名詞（1）碼字碼字：由若干個碼元組成由若干個碼元組成，如，如10001100。（2）碼長碼長：碼字中碼元的數(shù)目。碼字中碼元的數(shù)目。（3）碼組碼組：多個碼字構成的集合，如：多個碼字構成的集合，如

3、0000,0001,0010,0100,1000。（4）碼距碼距：兩個等長碼字之間的對應位不同的：兩個等長碼字之間的對應位不同的個數(shù)，二進制的最小碼距也稱為漢明距離。個數(shù)，二進制的最小碼距也稱為漢明距離。（5）碼重碼重：碼字中碼字中“1”碼元的個數(shù)，碼元的個數(shù)，用用W表示，表示，例如碼字例如碼字11001的碼重的碼重W=3。 編碼一：編碼一：消息消息A-“0A-“0”；消息；消息B-“1B-“1”；最小碼距最小碼距 =1=1；若傳輸中產(chǎn)生錯碼（若傳輸中產(chǎn)生錯碼（“0 0”錯成錯成“1 1”或或“1 1”錯成錯成“0 0”），收端無法），收端無法發(fā)現(xiàn)，發(fā)現(xiàn)，該編碼無檢錯糾錯能力該編碼無檢錯糾錯能

4、力。 編碼二：編碼二： 消息消息A-“00A-“00”；消息；消息B-“11B-“11”（加了一位監(jiān)督位）；（加了一位監(jiān)督位）；最小碼距最小碼距 = 2= 2；若傳輸中產(chǎn)生一位錯碼，則變成若傳輸中產(chǎn)生一位錯碼，則變成“0101”或或“1010”，因，因“0101”和和“1010”為禁用碼組，為禁用碼組，收端譯碼時可以檢測出該碼有錯收端譯碼時可以檢測出該碼有錯，但無法確定錯碼，但無法確定錯碼位置，不能糾正。位置，不能糾正。編碼三：編碼三：消息消息A-“000A-“000”；消息；消息B-“111B-“111”（增加兩位監(jiān)督位）；（增加兩位監(jiān)督位）；最小碼距最小碼距 = 3= 3；傳輸中產(chǎn)生一位或

5、兩位錯碼，都將變成禁用碼組，收端判決傳輸有錯。傳輸中產(chǎn)生一位或兩位錯碼，都將變成禁用碼組，收端判決傳輸有錯。該編碼具有檢出兩位錯碼的能力；該編碼具有檢出兩位錯碼的能力；該編碼具有糾正一位錯碼的能該編碼具有糾正一位錯碼的能力。力。例如收到例如收到110110，認為是，認為是111111。（大數(shù)法則）。（大數(shù)法則）分組碼分組碼l分組碼：將k個信息碼元劃分為一組，然后由這k個碼元按照一定的規(guī)則產(chǎn)生r個監(jiān)督碼元，從而構成長度nkr的碼組的集合。l分組碼表示：（n，k）。l最小碼距：一個碼組集合中，任何兩個碼組間漢明距離的最小值稱為該集合的最小碼距。記為d0。例:11101與10011之間的碼距d=3。

6、l碼組的最小距離越大，差錯控制能力就越強。l碼組集合（000，001，010，011，100，101，110，111）d0=1l碼組集合（000， 011，101，110）d0=2l碼組集合（000，111）d0=3常用差錯控制編碼（1 1）奇偶校驗碼）奇偶校驗碼（2 2）恒比碼）恒比碼（3 3）正反碼）正反碼（4 4）循環(huán)冗余校驗碼）循環(huán)冗余校驗碼（5 5）卷積碼）卷積碼原理原理：奇偶校驗編碼中，無論信息位有多少位，奇偶校驗編碼中，無論信息位有多少位， 校驗位只有一位。校驗位只有一位。碼組中碼組中“1”的個數(shù)為奇的個數(shù)為奇 數(shù)或偶數(shù)。數(shù)或偶數(shù)。奇校驗編碼，要滿足關系式：奇校驗編碼，要滿足關系

7、式：偶校驗編碼，要滿足關系式：偶校驗編碼，要滿足關系式：1021aaann0021aaann（1）奇偶校驗校驗位模2加l恒比碼中“1”的個數(shù)與“0”的個數(shù)保持不變。l接收端譯碼時只需計算接收碼組中接收端譯碼時只需計算接收碼組中“1”的個數(shù)，的個數(shù)，就可以知就可以知道傳輸過程中是否出現(xiàn)了錯誤。道傳輸過程中是否出現(xiàn)了錯誤。l可以可以檢測所有奇數(shù)個錯誤和部分偶數(shù)個錯誤。檢測所有奇數(shù)個錯誤和部分偶數(shù)個錯誤。l5中取3恒比碼如表。l優(yōu)點：簡單，實現(xiàn)容易。字符字符恒比碼恒比碼字符字符恒比碼恒比碼10101161010121100171110031011080111041101091001150011100

8、1101（2）恒比碼l正反碼監(jiān)督碼元取決于信息碼組中正反碼監(jiān)督碼元取決于信息碼組中“1”的數(shù)目的數(shù)目，或或者與信息碼元相同（正碼），者與信息碼元相同（正碼），或者與信息碼元相反或者與信息碼元相反（反碼）。（反碼）。l以以博多碼博多碼為例，為例，編碼規(guī)則：編碼規(guī)則：信息碼組中有奇數(shù)個信息碼組中有奇數(shù)個“1”時，監(jiān)督碼與信息碼相同；信息碼有偶數(shù)個時，監(jiān)督碼與信息碼相同；信息碼有偶數(shù)個“1”時監(jiān)督碼是信息碼的反碼。時監(jiān)督碼是信息碼的反碼。l例如，信息碼為例如，信息碼為11001，有奇數(shù)個，有奇數(shù)個“1”，則監(jiān)督碼亦為，則監(jiān)督碼亦為11001，發(fā)送碼組為，發(fā)送碼組為1100111001；信息碼為；信息

9、碼為11101，有偶數(shù)，有偶數(shù)個個“1”，則監(jiān)督碼為信息碼的反碼，則監(jiān)督碼為信息碼的反碼00010，發(fā)送碼組為，發(fā)送碼組為1100100010。（3）正反碼l譯碼規(guī)則：譯碼規(guī)則：接收端將接收碼組中的信息碼與監(jiān)督碼接收端將接收碼組中的信息碼與監(jiān)督碼模模2 2加，得到一個加，得到一個5 5bitbit的合成碼組，由其產(chǎn)生校驗的合成碼組，由其產(chǎn)生校驗碼組。碼組。l接收碼組中的信息碼有奇數(shù)個接收碼組中的信息碼有奇數(shù)個“1”1”，合成碼組就是校驗，合成碼組就是校驗碼組；接收碼組中的信息碼有偶數(shù)個碼組；接收碼組中的信息碼有偶數(shù)個“1”1”，合成碼組取，合成碼組取反為校驗碼組。根據(jù)校驗碼組中反為校驗碼組。根

10、據(jù)校驗碼組中“1”1”的數(shù)目按下表進行的數(shù)目按下表進行譯碼判決。譯碼判決。類型類型校驗碼組形式校驗碼組形式譯碼判決譯碼判決1全全“0”傳輸正確傳輸正確24個個“1”，1個個“0”校驗碼中校驗碼中“0”對應位置的對應位置的1位信息碼出錯位信息碼出錯34個個“0”，1個個“1”校驗碼中校驗碼中“1”對應位置的對應位置的1位監(jiān)督碼出錯位監(jiān)督碼出錯4其他其他大于大于1位的傳輸錯誤位的傳輸錯誤這種編碼方式能糾正這種編碼方式能糾正1位錯誤。位錯誤?！纠?接收碼組：接收碼組：0110101101、0101010111、0111010110，判斷傳輸是否有錯。，判斷傳輸是否有錯。 解：解： 1)1) 接收

11、碼組接收碼組01101011010110101101，信息碼中，信息碼中“1”1”個數(shù)為奇數(shù)（個數(shù)為奇數(shù)（3 3個），個），合成碼組為合成碼組為0000000000，校驗碼組亦為，符，校驗碼組亦為，符0000000000合表中第合表中第1 1種類種類型情況，傳輸正確。型情況，傳輸正確。2)2) 接收碼組接收碼組01010010101011110111，信息碼中，信息碼中“1”1”個數(shù)為偶數(shù)（個數(shù)為偶數(shù)（2 2個），個），合成碼組為合成碼組為1110111101，合成碼組取反，得校驗碼組，合成碼組取反，得校驗碼組0001000010，符，符合表中第合表中第3 3種類型情況，第種類型情況，第4 4

12、個監(jiān)督碼位出錯。個監(jiān)督碼位出錯。 3 3）接收碼組）接收碼組01110101100111010110，信息碼中，信息碼中“1”1”個數(shù)為奇數(shù)（個數(shù)為奇數(shù)（3 3個），個），合成碼組為合成碼組為1100011000，校驗碼組亦為，校驗碼組亦為1100011000，符合表中第，符合表中第4 4種類種類型情況，傳輸產(chǎn)生了多位錯誤。型情況，傳輸產(chǎn)生了多位錯誤。 （4）循環(huán)冗余碼）循環(huán)冗余碼l從數(shù)學的角度講，所有的數(shù)都可以用多項式來表從數(shù)學的角度講，所有的數(shù)都可以用多項式來表示，例如：示，例如： 125=1125=110102 2 + 2+ 210101 1 + 5+ 510100 0長度為長度為n n

13、的碼組可用一個的碼組可用一個x x的的n-1n-1次多項式表示，碼組次多項式表示，碼組中每位碼的數(shù)值就是中每位碼的數(shù)值就是n-1n-1次次多項式中相應的系數(shù)值，多項式中相應的系數(shù)值，這個對應多項式稱為這個對應多項式稱為數(shù)據(jù)數(shù)據(jù)多項式多項式。CRC原理：原理：l將將發(fā)送數(shù)據(jù)比特序列作為多項式發(fā)送數(shù)據(jù)比特序列作為多項式T T( (x x) )的系數(shù)，的系數(shù)，選選一一k k次冪生成多項式次冪生成多項式G G( (x x) )。l用用x xk k乘乘T T( (x x) )，得得T T( (x x) )x x k k。l然后用然后用G G( (x x) )去除去除T T( (x x) )x x k k

14、 , ,得一個余數(shù)多項式得一個余數(shù)多項式R R( (x x) )。l將余數(shù)多項式加到數(shù)據(jù)多項式將余數(shù)多項式加到數(shù)據(jù)多項式T T( (x x) )之后，作為發(fā)之后，作為發(fā)送序列。送序列。l收端用同一收端用同一G G( (x x) )去除接收序列多項式去除接收序列多項式T T(x x) )x xk k ，得計算余數(shù)多項式得計算余數(shù)多項式R R(x x) )。l若若R R(x x) )與與R R( (x x) )相同，傳輸無錯；否則傳輸有錯。相同，傳輸無錯；否則傳輸有錯。l校驗過程校驗過程：（：（發(fā)端）發(fā)端） a. T(xa. T(x) )乘以乘以x xk k . . 意味著將意味著將T(x)T(x

15、)對應的數(shù)據(jù)比特序對應的數(shù)據(jù)比特序列左移列左移k k位。位。 b. T(x)xb. T(x)xk k 除以除以G(x),G(x), Q(xQ(x) )商，商，R(x)R(x)余數(shù)多項式。余數(shù)多項式。 c. c. 將將T(x)xT(x)xk k + R(x) + R(x)所對應的比特序列作為一個整所對應的比特序列作為一個整體發(fā)送發(fā)送。體發(fā)送發(fā)送。)()()()()(xGxRxQxGxxTkl校驗過程校驗過程：（：（收端收端）d. d. 對接收序列所對應的多項式對接收序列所對應的多項式T(x)xT(x)xk k 進行運算。進行運算。R(x)= R(xR(x)= R(x) )，傳輸正確；，傳輸正確；

16、R(x)R(xR(x)R(x), ), 傳輸有錯。傳輸有錯。)()( )()()( xGxRxQxGxxTk實際的實際的CRCCRC校驗碼生成采用二進制模校驗碼生成采用二進制模2 2算法得算法得到。加法不進位，減法不借位，即異或操作。到。加法不進位，減法不借位，即異或操作。例例:a. 發(fā)送數(shù)據(jù)序列發(fā)送數(shù)據(jù)序列 110011；b. G(x)=x4+x3+1，k=4, 對應的序列對應的序列 11001；c. 發(fā)送數(shù)據(jù)序列左移發(fā)送數(shù)據(jù)序列左移4位為位為 1100110000；d. 做除法做除法 e. 帶有校驗的發(fā)送序列帶有校驗的發(fā)送序列 ： 110011 1001 發(fā)序列發(fā)序列 校驗序列校驗序列f.

17、 校驗校驗 ，若沒有發(fā)生差錯，接收端收序列能被同一生，若沒有發(fā)生差錯，接收端收序列能被同一生成多項序列整除。成多項序列整除。l l 1 0 0 0 0 1l 1 1 0 1）1 1 0 0 1 1 1 0 0 1l 1 1 0 0 1l 1 1 0 0 1l 1 1 0 0 1l 0（5 5）卷積碼）卷積碼（1）編碼）編碼卷積碼卷積碼符號符號(n,k,m(n,k,m) )：n n為碼長為碼長，k k為碼組中信息位長為碼組中信息位長度，度，m m為相互關聯(lián)的碼組個數(shù)為相互關聯(lián)的碼組個數(shù)。信息位監(jiān)督位(2,1,6)卷積碼卷積碼（2) 卷積碼的圖解表示卷積碼的圖解表示1) 1) 樹狀圖樹狀圖（2，1

18、，3）卷積碼）卷積碼m m1 1，m m2 2為移位寄存器，起始狀為移位寄存器，起始狀態(tài)均為態(tài)均為0 0，即，即b b1 1b b2 2b b3 3為為000000。 c1 b1b2 b3 c2 b1b3 b111010000b3b20001111001100000 c1c2 11 01 01 00 10 11 00 00狀態(tài)狀態(tài) a b d c b c a an為碼長，k為碼組中信息位長度，m為相互關聯(lián)的碼組個數(shù)。 2 2） 網(wǎng)格圖網(wǎng)格圖 l網(wǎng)格圖把樹狀圖中相同的節(jié)點合并在一起，輸入比特輸入比特0，用實線表示；用實線表示；輸入比特1，用虛線表示。支路上標注的碼元為輸出比特，自上而下4行節(jié)點分別表示a，b，c，d四種狀態(tài)。 【例【例】（2，1，3）卷積碼編碼器，起始狀態(tài)為）卷積碼編碼器，起始狀態(tài)為a，輸入比特，輸入比特序列為序列為110100，求輸出序列和狀態(tài)變化路徑。，求輸出序列和狀態(tài)變化路徑。 l解：由（解：由（2 2，1 1，3 3）卷積碼網(wǎng)格圖，找出編碼時網(wǎng)格圖中）卷積碼網(wǎng)格圖，找出編碼時網(wǎng)格圖中的路徑，可得到輸出序列和狀態(tài)變化路徑。的路徑，可得到輸出序列和狀態(tài)變化路徑。 （3）譯碼）譯碼 l方法：方法：代數(shù)解碼和概率解碼。代數(shù)解碼和