第7章-差錯(cuò)控制原理

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

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

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

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

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

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

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

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

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

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

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

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

13、的碼組可用一個(gè)的碼組可用一個(gè)x x的的n-1n-1次多項(xiàng)式表示，碼組次多項(xiàng)式表示，碼組中每位碼的數(shù)值就是中每位碼的數(shù)值就是n-1n-1次次多項(xiàng)式中相應(yīng)的系數(shù)值，多項(xiàng)式中相應(yīng)的系數(shù)值，這個(gè)對(duì)應(yīng)多項(xiàng)式稱(chēng)為這個(gè)對(duì)應(yīng)多項(xiàng)式稱(chēng)為數(shù)據(jù)數(shù)據(jù)多項(xiàng)式多項(xiàng)式。CRC原理：原理：l將將發(fā)送數(shù)據(jù)比特序列作為多項(xiàng)式發(fā)送數(shù)據(jù)比特序列作為多項(xiàng)式T T( (x x) )的系數(shù)，的系數(shù)，選選一一k k次冪生成多項(xiàng)式次冪生成多項(xiàng)式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、 , ,得一個(gè)余數(shù)多項(xiàng)式得一個(gè)余數(shù)多項(xiàng)式R R( (x x) )。l將余數(shù)多項(xiàng)式加到數(shù)據(jù)多項(xiàng)式將余數(shù)多項(xiàng)式加到數(shù)據(jù)多項(xiàng)式T T( (x x) )之后，作為發(fā)之后，作為發(fā)送序列。送序列。l收端用同一收端用同一G G( (x x) )去除接收序列多項(xiàng)式去除接收序列多項(xiàng)式T T(x x) )x xk k ，得計(jì)算余數(shù)多項(xiàng)式得計(jì)算余數(shù)多項(xiàng)式R R(x x) )。l若若R R(x x) )與與R R( (x x) )相同，傳輸無(wú)錯(cuò)；否則傳輸有錯(cuò)。相同，傳輸無(wú)錯(cuò)；否則傳輸有錯(cuò)。l校驗(yàn)過(guò)程校驗(yàn)過(guò)程：（：（發(fā)端）發(fā)端） a. T(xa. T(x) )乘以乘以x xk k . . 意味著將意味著將T(x)T(x

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

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

17、 校驗(yàn)校驗(yàn) ，若沒(méi)有發(fā)生差錯(cuò)，接收端收序列能被同一生，若沒(méi)有發(fā)生差錯(cuò)，接收端收序列能被同一生成多項(xiàng)序列整除。成多項(xiàng)序列整除。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）編碼）編碼卷積碼卷積碼符號(hào)符號(hào)(n,k,m(n,k,m) )：n n為碼長(zhǎng)為碼長(zhǎng)，k k為碼組中信息位長(zhǎng)為碼組中信息位長(zhǎng)度，度，m m為相互關(guān)聯(lián)的碼組個(gè)數(shù)為相互關(guān)聯(lián)的碼組個(gè)數(shù)。信息位監(jiān)督位(2,1,6)卷積碼卷積碼（2) 卷積碼的圖解表示卷積碼的圖解表示1) 1) 樹(shù)狀圖樹(shù)狀圖（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為碼長(zhǎng)，k為碼組中信息位長(zhǎng)度，m為相互關(guān)聯(lián)的碼組個(gè)數(shù)。 2 2） 網(wǎng)格圖網(wǎng)格圖 l網(wǎng)格圖把樹(shù)狀圖中相同的節(jié)點(diǎn)合并在一起，輸入比特輸入比特0，用實(shí)線表示；用實(shí)線表示；輸入比特1，用虛線表示。支路上標(biāo)注的碼元為輸出比特，自上而下4行節(jié)點(diǎn)分別表示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)格圖，找出編碼時(shí)網(wǎng)格圖中）卷積碼網(wǎng)格圖，找出編碼時(shí)網(wǎng)格圖中的路徑，可得到輸出序列和狀態(tài)變化路徑。的路徑，可得到輸出序列和狀態(tài)變化路徑。 （3）譯碼）譯碼 l方法：方法：代數(shù)解碼和概率解碼。代數(shù)解碼和