第五章循環(huán)碼

1、State Key Laboratory of Integrated Services Networks 第五章第五章 循環(huán)碼循環(huán)碼要求掌握的內(nèi)容根據(jù)多項式會寫循環(huán)碼的生成矩陣和校驗矩陣會寫循環(huán)碼生成和校驗矩陣的系統(tǒng)形式會畫循環(huán)碼的編碼電路由生成多項式的根定義循環(huán)碼第一節(jié) 循環(huán)碼定義循環(huán)碼的生成多項式和校驗多項式循環(huán)碼的生成矩陣和校驗矩陣循環(huán)碼的系統(tǒng)碼形式State Key Laboratory of Integrated Services Networks 一、循環(huán)碼定義一、循環(huán)碼定義 定義定義1：設(shè)設(shè)CH是一個是一個n.k線性分組碼，線性分組碼，C1是其是其中的一個碼字，若中的一個碼字，若

2、C1的左的左(右右)循環(huán)移位得到的循環(huán)移位得到的n維向量也是維向量也是CH中的一個碼字，則稱中的一個碼字，則稱CH是循環(huán)碼。是循環(huán)碼。nknVV,定義定義2：設(shè)設(shè)是是n維空間的一個維空間的一個k維子空間，維子空間，若對任一若對任一knnnVaaa,021,v恒有恒有knnnnVaaaa,10121,v則稱則稱Vn,k為為循環(huán)子空間循環(huán)子空間或或循環(huán)碼循環(huán)碼State Key Laboratory of Integrated Services Networks 問題一如何尋找k維循環(huán)子空間？如何設(shè)計n,k循環(huán)碼？ 利用多項式和有限域的概念pGFaaaainn,021 xfaxaxannnn022

3、11注：注： 1、GF(p)上的上的n維向量與維向量與GF(p)上的多項式之間有一一對上的多項式之間有一一對應(yīng)的關(guān)系應(yīng)的關(guān)系 2、模、模n 多項式多項式F(x)的剩余類構(gòu)成一個多項式剩余類環(huán)的剩余類構(gòu)成一個多項式剩余類環(huán)Fpx/F(x)，若在環(huán)中再定義一個數(shù)乘運算，即，若在環(huán)中再定義一個數(shù)乘運算，即 pGFccaxcaxcaaxaxacnnnnnnnn,0221102211 則模則模F(x)的剩余類構(gòu)成一個的剩余類構(gòu)成一個n維線性空間，定義為剩余類維線性空間，定義為剩余類線性結(jié)合代數(shù)。線性結(jié)合代數(shù)。State Key Laboratory of Integrated Services Netw

4、orks 問題一轉(zhuǎn)化為如何從模多項式xn-1的剩余類結(jié)合代數(shù)中尋找循環(huán)子空間？定理 以多項式以多項式xn-1為模的剩余類線性結(jié)合代數(shù)中，其一為模的剩余類線性結(jié)合代數(shù)中，其一個子空間個子空間Vn, k為循環(huán)子空間為循環(huán)子空間(或循環(huán)碼或循環(huán)碼)的充要條件的充要條件是：是：Vn,k是一個理想。是一個理想。 循環(huán)碼是模循環(huán)碼是模xn-1的剩余類線性結(jié)合代數(shù)中的一個的剩余類線性結(jié)合代數(shù)中的一個理想。理想。State Key Laboratory of Integrated Services Networks 問題二問題二如何從多項式剩余類環(huán)中如何從多項式剩余類環(huán)中尋找理想？尋找理想？ 由于由于 1、多

5、項式剩余類環(huán)中任何一個理想都是主理、多項式剩余類環(huán)中任何一個理想都是主理想想主理想中的所有元素可由某一個元素的主理想中的所有元素可由某一個元素的倍式倍式構(gòu)成構(gòu)成 2、在主理想的所有元素中，至少可找到一個、在主理想的所有元素中，至少可找到一個次數(shù)最低的首一多項式次數(shù)最低的首一多項式g(x),即即生成多項式生成多項式定義：生成多項式定義：生成多項式g(x)是模是模xn-1剩余類代數(shù)中，剩余類代數(shù)中，一個理想的次數(shù)最低的非零首一多項式，它是一個理想的次數(shù)最低的非零首一多項式，它是理想或循環(huán)碼的生成元。理想或循環(huán)碼的生成元。State Key Laboratory of Integrated Serv

6、ices Networks 問題三問題三如何尋找生成多項式如何尋找生成多項式g(x)？循環(huán)碼循環(huán)碼模多項式模多項式xn-1剩余類線性結(jié)合代數(shù)中的理想剩余類線性結(jié)合代數(shù)中的理想生成多項式生成多項式State Key Laboratory of Integrated Services Networks 二、生成多項式和校驗多項式二、生成多項式和校驗多項式兩個定理兩個定理 定理定理1:GF(q)(q為素數(shù)或素數(shù)的冪為素數(shù)或素數(shù)的冪)上的上的n,k循環(huán)循環(huán)碼中，存在唯一的碼中，存在唯一的n-k次首一多項式次首一多項式g(x)，每一個，每一個碼多項式碼多項式C(x)必是必是g(x)的倍式，每一個小于等于

7、的倍式，每一個小于等于(n-1)次的次的g(x)的倍式一定是碼多項式的倍式一定是碼多項式兩個定理兩個定理 定理定理2:GF(q)(q為素數(shù)或素數(shù)的冪為素數(shù)或素數(shù)的冪)上上n,k循環(huán)碼的循環(huán)碼的生成多項式生成多項式g(x)一定是一定是xn-1的的n-k次因式：次因式： xn-1= g(x) h(x)。 反之，若反之，若g(x)為為n-k次多項式，且次多項式，且xn-1能被能被g(x)整除，整除，則則g(x)一定能生成一個一定能生成一個n,k循環(huán)碼循環(huán)碼兩個結(jié)論 結(jié)論1:找一個n,k循環(huán)碼，即是找一個n-k次首一多項式g(x)，且g(x)必是xn-1的因式。 xCxg結(jié)論結(jié)論2:若若C(x)是一個

8、碼多項式，則是一個碼多項式，則反之，若反之，若 xCxg，則，則C(x)必是一個碼多項式必是一個碼多項式Examples GF(2)上，x7-1=(x+1)(x3+x+1)(x3+x2+1) 試求一個7,4循環(huán)碼。g(x)、 xg(x)、x2 g(x)、 x3g(x)、State Key Laboratory of Integrated Services Networks 三、循環(huán)碼的生成矩陣和校驗矩陣 011gxgxgxgknknknkn 011hxhxhxhkkkk xhxgxn1g(x)決定生成矩陣，決定生成矩陣，h(x)決定校驗矩陣決定校驗矩陣nkknknknknknknggggggg

9、ggggggG01210110110000000 xgxgxxgxkk,21nknkkkkkkkhhhhhhhhhhhhh12101101100000000H xhxhxxhxknkn*2*1,kkkhxhxhxh110*)(State Key Laboratory of Integrated Services Networks 四、循環(huán)碼的系統(tǒng)碼 模g(x)的除法問題 xgxrxxmxCknmod0 xgxxmxxmxCxrknknmod由于生成矩陣由于生成矩陣G中的中的k行要求線性無關(guān)，因此行要求線性無關(guān)，因此在求余式時，可選擇在求余式時，可選擇k個線性無關(guān)的信息組個線性無關(guān)的信息組 (1

10、,0,0,0) xk-1， (0,1,0,0,0) xk-2, (0,0,0,0,1) 1)(mod()(111xgxxxxrnknk)(mod()(222xgxxxxrnknk)(mod()(0 xgxxxxrknknk xrxrxrk10001000121G xri表示ri(x)的系數(shù)knTIPHknTkTTxrxrxrI)(,)(,)(21循環(huán)碼的編碼原理(1)基本步驟基本步驟(n,k)1、分解多項式、分解多項式xn-1=g(x)h(x)2、選擇其中的、選擇其中的n-k次多項式次多項式g(x)為生成多項式為生成多項式3、由、由g(x)可得到可得到k個多項式個多項式g(x), xg(x),

11、xk-1g(x)4、取上述、取上述k個多項式的系數(shù)即可構(gòu)成相應(yīng)的生成矩陣個多項式的系數(shù)即可構(gòu)成相應(yīng)的生成矩陣5、取、取h(x)的互反多項式的互反多項式h*(x),取取h*( x), xh*( x), xn-k-1h*( x) 的系數(shù)即可構(gòu)成相應(yīng)的校驗矩陣的系數(shù)即可構(gòu)成相應(yīng)的校驗矩陣可選擇可選擇k個線性無關(guān)的信息組個線性無關(guān)的信息組 (1,0,0,0) xk-1， (0,1,0,0,0) xk-2, (0,0,0,0,1) 1循環(huán)碼的編碼原理(2)(mod()(111xgxxxxrnknk)(mod()(222xgxxxxrnknk)(mod()(0 xgxxxxrknknk xrxrxrk10

12、001000121G xri表示ri(x)的系數(shù)由生成多項式的根定義循環(huán)碼設(shè)碼的生成多項式 g(x)=xr+gr-1xr-1+g1x+g0, giGF(q)它必在某一個GF(q)的擴域上完全分解，即它的根必在此擴域上?？紤]g(x)無重根的情況，即要求xn-1無重根。定理在GF(q)上多項式xn-1無重根的充要條件是(n,q)=1在GF(2)上要保證g(x)無重根的條件是xn-1中的n是奇數(shù)，因此二進制循環(huán)碼中，碼長是奇數(shù)。g(x)=(x-a1)(x-a2)(x-ar)， aiaj，aiGF(qm)每一碼多項式必以a1,a2,ar為根。則 C(ai)=cn-1ain-1+cn-2ain-2+c1

13、ai+c0=011112122110.1.1. . .1nnnnTnrrcaacaaHCcaac0g(x)=LCM(m1(x),m2(x),mr(x)回顧共軛根系的概念回顧共軛根系的概念設(shè)設(shè)f(x)=fkxk+fk-1xk-1+f0, fiGF(p)。若。若p特征域的元素特征域的元素w是方程是方程f(x)的根，的根，f(w)=0,則對于一切自然數(shù)則對于一切自然數(shù)n, wpn也必是也必是f(x)的根。的根。21,.,mmppppw w wwww共軛根系共軛根系最小多項式：系數(shù)取自最小多項式：系數(shù)取自GF(p)上，且以上，且以w為根的所有首一多項式為根的所有首一多項式中，次數(shù)最低的多項式稱為中，次

14、數(shù)最低的多項式稱為w的最小多項式，記為的最小多項式，記為m(x)循環(huán)碼的編碼多項式乘法和除法電路循環(huán)碼的編碼電路(乘法和除法)State Key Laboratory of Integrated Services Networks 一、多項式乘法和除法電路 011axaxaxAkkkk 011bxbxbxBrrrr 001001) 1(122112111baxbabaxbababaxbababaxbabaxbaxBxAxCirkrikirkirkrkrkrkrkrkrkrkrkrkb0b1b2br-2b1br-1b1br輸出C(x)輸入A(x)a0,a1,ak 乘B(x)運算電路(利用校驗多項

15、式h(x)編碼時會用到)b0b1b2br-2b1br-1b1br輸出C(x)輸入A(x)a0,a1,ak乘B(x)運算電路akb0akb1akbr-2akbr-1-b1b1br-1輸出商q(x)輸入A(x)-b2-br-1-b0除B(x)運算電路a0,a1,ak除式B(x)構(gòu)成電路，被除式A(x)的系數(shù)依次送入電路h0h1h2hr-2b1hr-1b1hr輸入A(x)a0,a1,ak-g1gr-1輸出商q(x)-g2-g0-gr-1-gr-1乘H(x),除g(x)運算電路多項式相乘相除電路多項式相乘相除電路當當H(x)、G(x)次數(shù)不同時次數(shù)不同時4( )1A xxx2( )1H xx3( )1

16、G xxx輸入輸入輸出輸出1x21x3xState Key Laboratory of Integrated Services Networks 二、循環(huán)碼編碼電路循環(huán)碼編碼電路循環(huán)碼編碼電路循環(huán)碼編碼電路循環(huán)碼編碼電路n-k 級編碼器級編碼器基本原理：利用生成多項式基本原理：利用生成多項式g(x)若要求編成若要求編成非系統(tǒng)碼非系統(tǒng)碼形式，則利用形式，則利用乘法電路乘法電路若要求編成若要求編成系統(tǒng)碼系統(tǒng)碼形式，則利用形式，則利用除法電路除法電路)()()(利用校驗多項式編碼級編碼電路乘法電路實現(xiàn)非系統(tǒng)碼形式除法電路實現(xiàn)系統(tǒng)碼形式級編碼電路循環(huán)碼編碼電路kknn-k級乘法電路級乘法電路(非系統(tǒng)碼

17、形式非系統(tǒng)碼形式)取g(x), xg(x),xk-1g(x)的系數(shù)可構(gòu)成生成矩陣G0110110110000000n kn kn kn kn kn kgggggggggggg Gn-k級乘法電路級乘法電路(非系統(tǒng)碼形式非系統(tǒng)碼形式)若信息序列 m=(m0, m1,mk-1),則mG對應(yīng)的n維向量為：002112212111gmgmgmgmgmgmgmknkknkknkknkknkknk該n維向量正是多項式m(x)g(x)的系數(shù)g0g1g2gn-k-2b1gn-k-1b1gn-k輸出C(x)輸入m(x)m0,m1,mk乘g(x)運算電路mk-1 gn-k-1mk-1 gn-k輸入m(x)是信息序

18、列，g(x)為生成多項式mk-1 g0mk-1 g1GF(2)上，上，x7-1=(x+1)(x3+x+1)(x3+x2+1) ，g(x)=x3+x+1，試畫一個，試畫一個7,4循環(huán)碼的循環(huán)碼的n-k級乘級乘法編碼電路。法編碼電路。Example輸入輸入m(x)輸出輸出c(x)(mod()(111xgxxxxrnknk)(mod()(222xgxxxxrnknk)(mod()(0 xgxxxxrknknk由于生成矩陣由于生成矩陣G中的中的k行要求線性無關(guān)，因此在求行要求線性無關(guān)，因此在求余式時，可選擇余式時，可選擇k個線性無關(guān)的信息組個線性無關(guān)的信息組 (1,0,0,0) xk-1 (0,1,0

19、,0,0) xk-2 (0,0,0,0,1) 1循環(huán)碼的系統(tǒng)碼循環(huán)碼的系統(tǒng)碼 xrxrxrk10001000121G xri表示ri(x)的系數(shù)GC),(021mmmkk循環(huán)碼的系統(tǒng)碼循環(huán)碼的系統(tǒng)碼n-k級乘法電路（系統(tǒng)碼形式）級乘法電路（系統(tǒng)碼形式）對任意信息多項式對任意信息多項式m(x), xn-km(x)除除g(x)可得余式可得余式r(x)，m(x)的系數(shù)為信息序列的系數(shù)為信息序列m，r(x) 的系數(shù)為的系數(shù)為m對應(yīng)的校驗比特對應(yīng)的校驗比特若信息序列若信息序列 m=(mk-1, mk-2,m0)；對應(yīng)的多項式；對應(yīng)的多項式m(x)=mk-1xk-1+ mk-2xk-2+m0因此，循環(huán)碼的

20、系統(tǒng)碼電路是信息多項式因此，循環(huán)碼的系統(tǒng)碼電路是信息多項式m(x)乘乘xn-k,除除g(x)的實現(xiàn)電路的實現(xiàn)電路knnknkknxmxmxmxmx02211)()()()()(mod()(mod()(mod()(mod()(0221102211xrmxrmxrmxgxmxgxmxgxmxgxmxkkkknnknkkn輸入m(x)m0,m1,mk-1-g1gn-k-1-g2-g0-gn-k-1-gn-k-2乘乘xn-k除除g(x)運算電路運算電路門1n-k級乘法電路（系統(tǒng)碼形式）級乘法電路（系統(tǒng)碼形式）門門2GF(2)上，上，x7-1=(x+1)(x3+x+1)(x3+x2+1) ，g(x)=x

21、3+x+1，試畫一個，試畫一個7,4循環(huán)碼的循環(huán)碼的n-k級系級系統(tǒng)碼形式的乘法編碼電路。統(tǒng)碼形式的乘法編碼電路。Example輸入輸入m(x)輸出輸出c(x)門門1門門2k 級編碼器級編碼器基本原理：利用校驗多項式基本原理：利用校驗多項式h(x)；為系統(tǒng)碼編；為系統(tǒng)碼編碼電路碼電路若信息序列若信息序列 m=(mk-1, mk-2,m0)對應(yīng)的多項式對應(yīng)的多項式m(x)=mk-1xk-1+ mk-2xk-2+m0碼多項式碼多項式C(x)= m(x)g(x),且且C(x)為系統(tǒng)碼為系統(tǒng)碼 h(x)C(x)= h(x)m(x)g(x) = m(x)(xn-1) = m(x)xn-m(x) = mk

22、-1xn+k-1+ mk-2xn+k-2+m0 xn -(mk-1xk-1+mk-2xk-2+m0)k 級編碼器級編碼器h0 cn-1 +h1 cn-1-1 + +hk cn-1-k=0h0 cn-2 +h1 cn-2-1 + +hk cn-2-k=0h0 cn-3 +h1 cn-3-1 + +hk cn-3-k=0h0 ck +h1 ck-1 + +hk c0=0h(x)C(x)的乘積中，的乘積中，xn-1, xn-2, xk次的系數(shù)為零次的系數(shù)為零xn-1的系數(shù)的系數(shù)xn-2的系數(shù)的系數(shù)xn-3的系數(shù)的系數(shù)xk的系數(shù)的系數(shù)k 級編碼器級編碼器cn-1-k = - (h0 cn-1 +h1

23、cn-1-1 + +hk-1 cn-1-(k-1)cn-2-k = - (h0 cn-2 +h1 cn-2-1 + +hk-1 cn-k-1)cn-3-k = - (h0 cn-3 +h1 cn-3-1 + +hk-1 cn-k-2)cn-k-(n-k) = - (h0 ck +h1 ck-1 + +hk-1 c1) 由于由于hk=1-h0-h1-h2-hk-2b1-hk-1輸入信息門cn-1cn-2cn-k-1cn-k循環(huán)碼循環(huán)碼k級編碼電路級編碼電路k 級編碼器級編碼器GF(2)上，上，x7-1=(x+1)(x3+x+1)(x3+x2+1) ，g(x)=x3+x+1， h(x)= x4+x2+x+1。試畫一個。試畫一個7,4循環(huán)碼的循環(huán)碼的k級系統(tǒng)碼形式的編碼電路。級系統(tǒng)碼形式的編碼電路。Example輸入輸入m(x)輸出輸出c(x)門門1xx4x2第三節(jié)第三節(jié) 幾類特殊的循環(huán)碼幾類特殊的循環(huán)碼最小循環(huán)碼最小循環(huán)碼縮短循環(huán)碼縮短循環(huán)碼準循環(huán)碼準循環(huán)碼雙環(huán)循環(huán)碼雙環(huán)循環(huán)碼特殊的循環(huán)碼特殊的循環(huán)碼最小循環(huán)碼最小循環(huán)碼 一個理想中不再含有任何的非零理想，此理想對應(yīng)的循環(huán)碼稱為一個理想中不再含有任何的非零理想，此理想對應(yīng)的循環(huán)碼稱為最小循環(huán)碼最小循環(huán)碼或或既約循環(huán)碼既約循環(huán)碼縮短循環(huán)碼縮短循環(huán)碼 對循環(huán)碼縮短得到的碼對循環(huán)碼縮短得到的碼 取取n, k循環(huán)碼中前循環(huán)碼中前