第九章循環(huán)碼

1、第九章第九章 循環(huán)碼循環(huán)碼第九章第九章 循環(huán)碼循環(huán)碼 內(nèi)容提要內(nèi)容提要循環(huán)碼是線性分組碼中一個(gè)重要的子類。本章首循環(huán)碼是線性分組碼中一個(gè)重要的子類。本章首先提出了循環(huán)碼的定義以及循環(huán)碼的多項(xiàng)式描述先提出了循環(huán)碼的定義以及循環(huán)碼的多項(xiàng)式描述方法，論述了循環(huán)碼構(gòu)成的有關(guān)重要定理；接著方法，論述了循環(huán)碼構(gòu)成的有關(guān)重要定理；接著討論了循環(huán)碼的編譯碼方法及其實(shí)現(xiàn)電路，最后討論了循環(huán)碼的編譯碼方法及其實(shí)現(xiàn)電路，最后介紹了已獲得廣泛應(yīng)用的循環(huán)漢明碼等。介紹了已獲得廣泛應(yīng)用的循環(huán)漢明碼等。 9.1.1 循環(huán)碼的定義循環(huán)碼的定義 將任一碼字中的將任一碼字中的7個(gè)碼元排在一個(gè)圓周上，則從圓周的個(gè)碼元排在一個(gè)圓周上

2、，則從圓周的任一碼元開始，按順時(shí)針方向移動(dòng)一周，都將構(gòu)成該碼的任一碼元開始，按順時(shí)針方向移動(dòng)一周，都將構(gòu)成該碼的一個(gè)碼字。這就是循環(huán)碼的由來。（見圖一個(gè)碼字。這就是循環(huán)碼的由來。（見圖9.1） 9.1 9.1 循環(huán)碼的一般概念循環(huán)碼的一般概念定義定義9.1 一個(gè)線性分組碼，若具有下列特性，稱為一個(gè)線性分組碼，若具有下列特性，稱為循環(huán)循環(huán)碼碼。設(shè)碼字。設(shè)碼字c（cn-1，cn-2，c1，c0）若將碼元左移一位，得若將碼元左移一位，得c (1)（cn-2，c1，c0，cn-1）c (1)也是一個(gè)碼字。也是一個(gè)碼字。表表 8-2 (7,4)碼的碼字表碼的碼字表 圖圖9.1 9.1 （7，4）漢明碼的

3、碼字循環(huán)圖）漢明碼的碼字循環(huán)圖1000101:1100010:0110001:1011000:0101100:0010110:0001011:7654321c cc cc cc cc cc cc c0000000:15c c第一循環(huán)第一循環(huán)1001110:0100111:1010011:1101001:1110100:0111010:0011101:141312111098c cc cc cc cc cc cc c第二循環(huán)第二循環(huán)1111111:16c c9.1.2 循環(huán)碼的多項(xiàng)式描述循環(huán)碼的多項(xiàng)式描述設(shè)設(shè)c（cn-1 cn-2 c1 c0）是是（n，k）循環(huán)碼的一個(gè)碼字，則循環(huán)碼的一個(gè)碼字，

4、則與其對(duì)應(yīng)的多項(xiàng)式與其對(duì)應(yīng)的多項(xiàng)式 c (x)cn-1xn-1cn-2xn-2c1xc0 (9 (91)1) 稱為碼字稱為碼字c的的碼字多項(xiàng)式碼字多項(xiàng)式（或碼多項(xiàng)式）。（或碼多項(xiàng)式）。 如果如果c（cn-1 cn-2 c1 c0）是（是（n，k）循環(huán)碼的一個(gè)碼循環(huán)碼的一個(gè)碼字，則字，則c (1)（cn-2 c1 c0 cn-1）也是該循環(huán)碼的一個(gè)碼字。也是該循環(huán)碼的一個(gè)碼字。這就是說這就是說c (x)cn-1xn-1cn-2xn-2c1xc0 和和 c (1) (x)cn-2xn-1c1x2c0 xcn-1都是（都是（n，k）循環(huán)碼的碼字多項(xiàng)式。循環(huán)碼的碼字多項(xiàng)式。 比較比較c(x)和和c (

5、1) (x)后可得后可得 c (1) (x)x c (x), , mod xn1 (9(92)2)以及以及 c(i) (x)xic (x) （i1, ,2,n1）, , mod xn1 (9 (93)3) 定理定理9.1 在以多項(xiàng)式在以多項(xiàng)式xn1為模的剩余類全體所構(gòu)成的為模的剩余類全體所構(gòu)成的n維線維線性空間性空間Vn中，其一個(gè)子空間中，其一個(gè)子空間Vn,k是一個(gè)循環(huán)子空間（循環(huán)碼）是一個(gè)循環(huán)子空間（循環(huán)碼）的充要條件是：的充要條件是：Vn,k是一個(gè)是一個(gè)理想理想。 一個(gè)（一個(gè)（n，k）循環(huán)碼的碼字多項(xiàng)式都是模循環(huán)碼的碼字多項(xiàng)式都是模xn1運(yùn)算下多運(yùn)算下多項(xiàng)式剩余類項(xiàng)式剩余類環(huán)環(huán)中的一個(gè)理想

6、，而且一定是一個(gè)中的一個(gè)理想，而且一定是一個(gè)主理想子環(huán)主理想子環(huán)。反之，多項(xiàng)式剩余類環(huán)的一個(gè)主理想子環(huán)也一定生成一個(gè)反之，多項(xiàng)式剩余類環(huán)的一個(gè)主理想子環(huán)也一定生成一個(gè)循環(huán)碼。循環(huán)碼。 9.1.3 9.1.3 循環(huán)碼的生成多項(xiàng)式循環(huán)碼的生成多項(xiàng)式定理定理9.2 GF( (2) )上的（上的（n，k）循環(huán)碼中，存在有唯一的循環(huán)碼中，存在有唯一的nk次首一多項(xiàng)式次首一多項(xiàng)式 g( (x) )xn-k gn-k-1xn-k-1 g1xg0使得每一個(gè)碼多項(xiàng)式使得每一個(gè)碼多項(xiàng)式c (x)都是都是g( (x) )的倍式，且每一低于的倍式，且每一低于或等于或等于n1次的次的g( (x) )倍式，一定是碼多項(xiàng)式

7、。倍式，一定是碼多項(xiàng)式。 定理定理9.3 （n，k）循環(huán)碼的生成多項(xiàng)式循環(huán)碼的生成多項(xiàng)式g( (x) )一定是一定是xn1的因式：的因式：xn1g( (x) )h( (x) )。反之，若反之，若g( (x) )為為nk次，且除次，且除盡盡xn1，則此則此g( (x) )一定生成一個(gè)（一定生成一個(gè)（n，k）循環(huán)碼。循環(huán)碼。定義定義9.2 若一個(gè)循環(huán)碼的所有碼字多項(xiàng)式都是一個(gè)次數(shù)若一個(gè)循環(huán)碼的所有碼字多項(xiàng)式都是一個(gè)次數(shù)最低的非零首一多項(xiàng)式最低的非零首一多項(xiàng)式g( (x) )的倍式，則稱的倍式，則稱g( (x) )生成該碼，生成該碼，并稱并稱g( (x) )為該碼的生成元或生成多項(xiàng)式。為該碼的生成元

8、或生成多項(xiàng)式。循環(huán)碼的生成矩陣常用多項(xiàng)式的形式來表示循環(huán)碼的生成矩陣常用多項(xiàng)式的形式來表示 1)(111xgxgxxgrrr)()()()()(21xgxxgxgxxgxxGkk其中其中 即即 例如例如(7,3)循環(huán)碼，循環(huán)碼，n=7, k=3, r=4, 其生成多項(xiàng)式其生成多項(xiàng)式及生成矩陣分別為及生成矩陣分別為 定理定理9.4 若若g( (x) )是（是（n，k）循環(huán)碼的生成多項(xiàng)式，循環(huán)碼的生成多項(xiàng)式，由由xn1g( (x) )h( (x) )，h( (x) )是是k次多項(xiàng)式，稱為次多項(xiàng)式，稱為校驗(yàn)校驗(yàn)多項(xiàng)式多項(xiàng)式。令。令h( (x) )hkxkhk-1xk-1h1xh0則則 (9(95)5

9、)為（為（nk） n階矩陣，稱為碼的階矩陣，稱為碼的校驗(yàn)矩陣校驗(yàn)矩陣。kkkhhhhhhhhh1010100000000H H監(jiān)督矩陣監(jiān)督矩陣 h(x)是常數(shù)項(xiàng)為是常數(shù)項(xiàng)為1的的k次多項(xiàng)式，稱為次多項(xiàng)式，稱為監(jiān)督監(jiān)督多項(xiàng)式多項(xiàng)式。同理，可得監(jiān)督矩陣。同理，可得監(jiān)督矩陣H )(*)(*)(*)(1xhxxhxhxxHkn（n，k）循環(huán)碼的生成多項(xiàng)式循環(huán)碼的生成多項(xiàng)式g( (x) )是一個(gè)次數(shù)最低的唯一是一個(gè)次數(shù)最低的唯一的首一多項(xiàng)式，其次數(shù)的首一多項(xiàng)式，其次數(shù)rnk正好是碼字中校驗(yàn)元的數(shù)目；正好是碼字中校驗(yàn)元的數(shù)目； 生成多項(xiàng)式生成多項(xiàng)式g( (x) )是是xn1的因式。要構(gòu)造一個(gè)（的因式。要構(gòu)

10、造一個(gè)（n，k）循環(huán)碼，就是要在循環(huán)碼，就是要在xn1的因式中找一個(gè)的因式中找一個(gè)nk次的首一多項(xiàng)次的首一多項(xiàng)式式g( (x) )，它的一切倍式就構(gòu)成一個(gè)（它的一切倍式就構(gòu)成一個(gè)（n，k）循環(huán)碼。反之，循環(huán)碼。反之，循環(huán)碼的每一個(gè)碼字多項(xiàng)式必是循環(huán)碼的每一個(gè)碼字多項(xiàng)式必是g( (x) )的倍式；的倍式； 綜上所述，綜上所述，有如下結(jié)論：有如下結(jié)論： 由由xn1g( (x) )h( (x) )，h( (x) )稱為校驗(yàn)多項(xiàng)式。對(duì)于任意稱為校驗(yàn)多項(xiàng)式。對(duì)于任意一個(gè)（一個(gè)（n，k）循環(huán)碼，必有循環(huán)碼，必有g(shù)( (x) )h( (x) )0 mod mod xn1及及 GH T 0 循環(huán)碼是線性分組碼

11、的一個(gè)循環(huán)碼是線性分組碼的一個(gè)子類子類。因此，所有線性分組。因此，所有線性分組碼的性質(zhì)均適用于循環(huán)碼。碼的性質(zhì)均適用于循環(huán)碼。 9.2 9.2 循環(huán)碼的編碼循環(huán)碼的編碼 9.2.1 9.2.1 利用生成多項(xiàng)式利用生成多項(xiàng)式g(x)g(x)實(shí)現(xiàn)編碼實(shí)現(xiàn)編碼 若已知若已知 g( (x) )gn-kxn-kgn-k-1xn-k-1g1xg0并設(shè)信息元多項(xiàng)式并設(shè)信息元多項(xiàng)式 m( (x) )mk-1xk-1mk-2xk-2m1xm0要編碼成系統(tǒng)循環(huán)碼形式，須用要編碼成系統(tǒng)循環(huán)碼形式，須用xn-k乘以乘以m( (x) )，再加上校驗(yàn)再加上校驗(yàn)元多項(xiàng)式元多項(xiàng)式r( (x) )，這樣得到的碼字多項(xiàng)式這樣得到

12、的碼字多項(xiàng)式c( (x) )為：為： c( (x) )xn-k m( (x) )r( (x) )mk-1xn-1mk-2xn-2m0 xn-krn-k-1xn-k-1r1xr0其中其中 r( (x) )rn-k-1xn-k-1r1xr0c( (x) )一定是一定是g( (x) )的倍式，即有的倍式，即有c( (x) )xn-km( (x) )r( (x) )q( (x) )g( (x) ) 或或 c( (x) )xn-km( (x) )r( (x) )0， mod g( (x) )注意到注意到g( (x) )為為nk次多項(xiàng)式，而次多項(xiàng)式，而r( (x) )至多為至多為nk1次多項(xiàng)式，次多項(xiàng)式，

13、必有必有 r( (x) )xn-km( (x) )， mod g( (x) (9) (96)6)即即r( (x) )必是必是x n-k m( (x) )除以除以g( (x) )的余式。的余式。 ( (96) )式指出了系統(tǒng)循環(huán)碼的編碼方法：式指出了系統(tǒng)循環(huán)碼的編碼方法： 首先將信息元多項(xiàng)首先將信息元多項(xiàng)式式m( (x) )乘以乘以xn-k成為成為xn-km( (x) )；然后將然后將xn-km( (x) )除以生成多項(xiàng)式除以生成多項(xiàng)式g( (x) )得到余式得到余式r( (x) )，該余式就是該余式就是校驗(yàn)元多項(xiàng)式，從而得到碼字多校驗(yàn)元多項(xiàng)式，從而得到碼字多項(xiàng)式項(xiàng)式 c( (x) )xn-km

14、( (x) )r( (x) )。9.2.2 9.2.2 除法電路除法電路 設(shè)設(shè)GF( (2) )上的二個(gè)多項(xiàng)式上的二個(gè)多項(xiàng)式a( (x) )akxkak-1xk-1a1xa0b( (x) )brxrbr-1xr-1b1xb0a( (x) )是被除式，是被除式，b( (x) )是除式。用圖是除式。用圖9.2所示的電路完成所示的電路完成a( (x) )除以除以b( (x) )的運(yùn)算的運(yùn)算 。圖圖9.2 9.2 除法電路的一般形式除法電路的一般形式 【例【例9.2】設(shè)被除式】設(shè)被除式a( (x) )x4x1，除式除式b( (x) )x3x21，完成完成二個(gè)多項(xiàng)式相除的運(yùn)算。二個(gè)多項(xiàng)式相除的運(yùn)算。11

15、111223334423xxxxxxxxxxxx11001101110011011110011011長(zhǎng)除法：長(zhǎng)除法： 多項(xiàng)式的系數(shù)運(yùn)算多項(xiàng)式的系數(shù)運(yùn)算 實(shí)現(xiàn)以上除法運(yùn)算的除法電路如圖實(shí)現(xiàn)以上除法運(yùn)算的除法電路如圖9.3所示所示 圖圖9.3 9.3 以以b( (x) )x3x21為除式的除法電路為除式的除法電路 9.2.3 編碼電路編碼電路 然后將然后將xn-km(x)除以生成多除以生成多項(xiàng)式項(xiàng)式g(x)得到余式得到余式r(x)，該余該余式就是校驗(yàn)元多項(xiàng)式，從而式就是校驗(yàn)元多項(xiàng)式，從而可得碼字多項(xiàng)式可得碼字多項(xiàng)式 c(x)xn-km(x)r(x)。 系統(tǒng)循環(huán)碼的編碼方法是：系統(tǒng)循環(huán)碼的編碼方法是

16、： 首先將信息元多首先將信息元多項(xiàng)式項(xiàng)式m(x)乘以乘以xn-k成為成為xn-km(x)；用電路實(shí)現(xiàn)編碼時(shí)可采用以用電路實(shí)現(xiàn)編碼時(shí)可采用以g( (x) )為除式的除法電路。作為為除式的除法電路。作為實(shí)例，圖實(shí)例，圖9.49.4示出了生成多項(xiàng)式示出了生成多項(xiàng)式g( (x) )x3x21 1的（的（7，4）循環(huán)碼的編碼電路。循環(huán)碼的編碼電路。 圖圖9.4 9.4 以以g( (x) )x3x21的（的（7，4）循環(huán)碼編碼器）循環(huán)碼編碼器 碼長(zhǎng)碼長(zhǎng)n=7的循環(huán)碼：的循環(huán)碼：6）5）4）（）（7,3）循環(huán)碼，生產(chǎn)多項(xiàng)式為）循環(huán)碼，生產(chǎn)多項(xiàng)式為 g(x)（x3x21)(x+1)碼多項(xiàng)式為碼多項(xiàng)式為) 1)

17、()(2342210 xxxxaxaaxc9.3 9.3 循環(huán)碼的譯碼循環(huán)碼的譯碼 當(dāng)碼字當(dāng)碼字c通過噪聲信道傳送時(shí)，會(huì)受到干擾而產(chǎn)生錯(cuò)誤。如信道通過噪聲信道傳送時(shí)，會(huì)受到干擾而產(chǎn)生錯(cuò)誤。如信道產(chǎn)生的錯(cuò)誤圖樣是產(chǎn)生的錯(cuò)誤圖樣是e，譯碼器收到的譯碼器收到的n重接收矢量是重接收矢量是y，則表示為則表示為y c e上式也可寫成多項(xiàng)式形式：上式也可寫成多項(xiàng)式形式： y(x) )c( (x) )e( (x) (9) (97)7) 循環(huán)碼的譯碼可按以下三個(gè)步驟進(jìn)行：循環(huán)碼的譯碼可按以下三個(gè)步驟進(jìn)行：（）（）根據(jù)伴隨式根據(jù)伴隨式s( (x) )找出對(duì)應(yīng)的估值錯(cuò)誤圖樣找出對(duì)應(yīng)的估值錯(cuò)誤圖樣 ；)( xe（）（

18、）計(jì)算計(jì)算 ，得到估值碼字，得到估值碼字 。若。若，則譯碼正確，否則，若，則譯碼正確，否則，若 ，則譯碼錯(cuò)誤。，則譯碼錯(cuò)誤。)( )()( xexyxc)( xc)()( xcxc)()( xcxc（）（）由接收到的由接收到的y( (x) )計(jì)算伴隨式多項(xiàng)式計(jì)算伴隨式多項(xiàng)式s( (x) )；9.3.1 9.3.1 伴隨式計(jì)算伴隨式計(jì)算 對(duì)于（對(duì)于（n，k）循環(huán)碼，可以定義碼的生成多項(xiàng)式循環(huán)碼，可以定義碼的生成多項(xiàng)式g( (x) )除以除以接收碼字多項(xiàng)式接收碼字多項(xiàng)式y(tǒng)( (x) )的余式為伴隨式多項(xiàng)式的余式為伴隨式多項(xiàng)式s( (x) )，寫寫 s( (x) )y( (x) ) mod g( (

19、x) (9) (98)8)由于由于 y( (x) )c( (x) )e( (x) )而而 c( (x) ) mod g( (x) )0于是于是 s( (x) )e( (x) ) mod g( (x) (9) (99)9) s( (x) )伴隨式計(jì)算電路的一個(gè)重要性質(zhì)伴隨式計(jì)算電路的一個(gè)重要性質(zhì)：定理定理9.5 設(shè)設(shè)s( (x) )是接收碼字多項(xiàng)式是接收碼字多項(xiàng)式r( (x) )的伴隨式。則的伴隨式。則y( (x) )的一的一次循環(huán)移位次循環(huán)移位xy( (x) )（mod xn1）的伴隨式的伴隨式s(1)(1)( (x) )，是是s( (x) )在伴在伴隨式計(jì)算電路中無輸入時(shí)，右移一位的結(jié)果（稱

20、為自發(fā)運(yùn)算）：隨式計(jì)算電路中無輸入時(shí)，右移一位的結(jié)果（稱為自發(fā)運(yùn)算）： s(1)(1)( (x) )xs( (x) ) mod g( (x) ) (9 (911)11) 【例【例9.3】以】以g( (x) )x4x3x21為生成多項(xiàng)式的（為生成多項(xiàng)式的（7，3）循環(huán)碼）循環(huán)碼（示于表（示于表9.1），能糾正一個(gè)錯(cuò)誤。），能糾正一個(gè)錯(cuò)誤。 設(shè)傳送出現(xiàn)一個(gè)錯(cuò)，錯(cuò)誤圖樣設(shè)傳送出現(xiàn)一個(gè)錯(cuò)，錯(cuò)誤圖樣e（0 0 0 1 0 0 0），），即即e( (x) )x3，其伴隨式其伴隨式 s( (x) )e( (x) ) mod g( (x) ) x3 mod (x4x3x21)x3， 即即s （1 0 0 0）

21、現(xiàn)設(shè)錯(cuò)誤圖樣現(xiàn)設(shè)錯(cuò)誤圖樣 e1（0 0 1 0 0 0 0）, ,即即e(1)(1)( (x) )xe( (x) )x4，相應(yīng)的伴隨式相應(yīng)的伴隨式 s(1)(1)( (x) )x4 mod (x4x3x21)x3x21, ,即即 s1（1 1 0 1）s1是是s在圖在圖9.59.5所示的所示的g( (x) )x4x3x21除法電路中無輸入除法電路中無輸入時(shí)，右移一位的結(jié)果，也即自發(fā)運(yùn)算的結(jié)果。時(shí)，右移一位的結(jié)果，也即自發(fā)運(yùn)算的結(jié)果。圖圖9.5 9.5 （7，3）循環(huán)碼的伴隨式計(jì)算電路）循環(huán)碼的伴隨式計(jì)算電路 9.3.2 循環(huán)碼的譯碼循環(huán)碼的譯碼 把某一可糾正的錯(cuò)誤圖樣把某一可糾正的錯(cuò)誤圖樣e(

22、 (x) )及其所有的小于等于及其所有的小于等于n1次的循環(huán)移位歸成一類，用一個(gè)錯(cuò)誤圖樣來代表。譯碼時(shí)次的循環(huán)移位歸成一類，用一個(gè)錯(cuò)誤圖樣來代表。譯碼時(shí)只要計(jì)算這個(gè)錯(cuò)誤圖樣的伴隨式，該類中其它錯(cuò)誤圖樣的只要計(jì)算這個(gè)錯(cuò)誤圖樣的伴隨式，該類中其它錯(cuò)誤圖樣的伴隨式都可由該伴隨式在伴隨式都可由該伴隨式在g( (x) )除法電路中循環(huán)移位來得到。除法電路中循環(huán)移位來得到。 若（若（7，3）循環(huán)碼譯碼器按錯(cuò)誤圖樣（循環(huán)碼譯碼器按錯(cuò)誤圖樣（1 0 0 0 0 0 0）設(shè)計(jì)，于是設(shè)計(jì)，于是 s( (x) )e( (x) ) mod g( (x) ) x6 mod (x4x3x21)x3x2x， 即即 s（1 1 1 0）其譯碼器電路示于圖其譯碼器電路示于圖9.6。圖圖9.6 9.6 （7，3）循環(huán)碼譯碼器）循環(huán)碼譯碼器 9.3.3 Meggit譯碼器譯碼器 循環(huán)碼譯碼器的缺點(diǎn)無法對(duì)接收到的碼字實(shí)現(xiàn)連續(xù)的譯循環(huán)碼譯碼器的缺點(diǎn)無法對(duì)接收到的碼字實(shí)現(xiàn)連續(xù)的譯碼輸出。改進(jìn)的譯碼器稱作碼輸出。改進(jìn)的譯碼器稱作Meggit通用譯碼器通用譯碼器，其結(jié)構(gòu)如圖，其結(jié)構(gòu)如圖9.7，可實(shí)現(xiàn)連續(xù)的譯碼輸出。，可實(shí)現(xiàn)連續(xù)的