第九章循環(huán)碼

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

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

4、則與其對應(yīng)的多項式與其對應(yīng)的多項式 c (x)cn-1xn-1cn-2xn-2c1xc0 (9 (91)1) 稱為碼字稱為碼字c的的碼字多項式碼字多項式（或碼多項式）。（或碼多項式）。 如果如果c（cn-1 cn-2 c1 c0）是（是（n，k）循環(huán)碼的一個碼循環(huán)碼的一個碼字，則字，則c (1)（cn-2 c1 c0 cn-1）也是該循環(huán)碼的一個碼字。也是該循環(huán)碼的一個碼字。這就是說這就是說c (x)cn-1xn-1cn-2xn-2c1xc0 和和 c (1) (x)cn-2xn-1c1x2c0 xcn-1都是（都是（n，k）循環(huán)碼的碼字多項式。循環(huán)碼的碼字多項式。 比較比較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 在以多項式在以多項式xn1為模的剩余類全體所構(gòu)成的為模的剩余類全體所構(gòu)成的n維線維線性空間性空間Vn中，其一個子空間中，其一個子空間Vn,k是一個循環(huán)子空間（循環(huán)碼）是一個循環(huán)子空間（循環(huán)碼）的充要條件是：的充要條件是：Vn,k是一個是一個理想理想。 一個（一個（n，k）循環(huán)碼的碼字多項式都是模循環(huán)碼的碼字多項式都是模xn1運算下多運算下多項式剩余類項式剩余類環(huán)環(huán)中的

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

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

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

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

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

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

12、這樣得到的碼字多項式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次多項式，而次多項式，而r( (x) )至多為至多為nk1次多項式，次

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)碼的編碼方法： 首先將信息元多項首先將信息元多項式式m( (x) )乘以乘以xn-k成為成為xn-km( (x) )；然后將然后將xn-km( (x) )除以生成多項式除以生成多項式g( (x) )得到余式得到余式r( (x) )，該余式就是該余式就是校驗元多項式，從而得到碼字多校驗元多項式，從而得到碼字多項式項式 c( (x) )x

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

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

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

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

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

19、g( (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) )伴隨式計算電路的一個重要性質(zhì)伴隨式計算電路的一個重要性質(zhì)：定理定理9.5 設(shè)設(shè)s( (x) )是接收碼字多項式是接收碼字多項式r( (x) )的伴隨式。則的伴隨式。則y( (x) )的一的一次循環(huán)移位次循環(huán)移位xy( (x) )（mod xn1）的伴隨式的伴隨式s(1)(1)( (x) )，是是s( (x) )在伴在伴隨式計算電路中無輸入時，右移一位的

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

21、0 0）現(xiàn)設(shè)錯誤圖樣現(xiàn)設(shè)錯誤圖樣 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除法電路中無輸入除法電路中無輸入時，右移一位的結(jié)果，也即自發(fā)運算的結(jié)果。時，右移一位的結(jié)果，也即自發(fā)運算的結(jié)果。圖圖9.5 9.5 （7，3）循環(huán)碼的伴隨式計算電路）循環(huán)碼的伴隨式計算電路 9.3.2 循環(huán)碼的譯碼循環(huán)碼的譯碼 把某一可糾正的錯誤圖樣把某一可糾正的錯誤

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