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

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

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

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

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

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

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

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

9、ggggggG01210110110000000 xgxgxxgxkk,21nknkkkkkkkhhhhhhhhhhhhh12101101100000000H xhxhxxhxknkn*2*1,kkkhxhxhxh110*)(State Key Laboratory of Integrated Services Networks 四、循環碼的系統碼 模g(x)的除法問題 xgxrxxmxCknmod0 xgxxmxxmxCxrknknmod由于生成矩陣由于生成矩陣G中的中的k行要求線性無關，因此行要求線性無關，因此在求余式時，可選擇在求余式時，可選擇k個線性無關的信息組個線性無關的信息組 (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)的系數knTIPHknTkTTxrxrxrI)(,)(,)(21循環碼的編碼原理(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個多項式的系數即可構成相應的生成矩陣個多項式的系數即可構成相應的生成矩陣5、取、取h(x)的互反多項式的互反多項式h*(x),取取h*( x), xh*( x), xn-k-1h*( x) 的系數即可構成相應的校驗矩陣的系數即可構成相應的校驗矩陣可選擇可選擇k個線性無關的信息組個線性無關的信息組 (1,0,0,0) xk-1， (0,1,0,0,0) xk-2, (0,0,0,0,1) 1循環碼的編碼原理(2)(mod()(111xgxxxxrnknk)(mod()(222xgxxxxrnknk)(mod()(0 xgxxxxrknknk xrxrxrk10

12、001000121G xri表示ri(x)的系數由生成多項式的根定義循環碼設碼的生成多項式 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是奇數，因此二進制循環碼中，碼長是奇數。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)回顧共軛根系的概念回顧共軛根系的概念設設f(x)=fkxk+fk-1xk-1+f0, fiGF(p)。若。若p特征域的元素特征域的元素w是方程是方程f(x)的根，的根，f(w)=0,則對于一切自然數則對于一切自然數n, wpn也必是也必是f(x)的根。的根。21,.,mmppppw w wwww共軛根系共軛根系最小多項式：系數取自最小多項式：系數取自GF(p)上，且以上，且以w為根的所有首一多項式為根的所有首一多項式中，次數最低的多項式稱為中，次

14、數最低的多項式稱為w的最小多項式，記為的最小多項式，記為m(x)循環碼的編碼多項式乘法和除法電路循環碼的編碼電路(乘法和除法)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)構成電路，被除式A(x)的系數依次送入電路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)次數不同時次數不同時4( )1A xxx2( )1H xx3( )1

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

17、形式非系統碼形式)取g(x), xg(x),xk-1g(x)的系數可構成生成矩陣G0110110110000000n kn kn kn kn kn kgggggggggggg Gn-k級乘法電路級乘法電路(非系統碼形式非系統碼形式)若信息序列 m=(m0, m1,mk-1),則mG對應的n維向量為：002112212111gmgmgmgmgmgmgmknkknkknkknkknkknk該n維向量正是多項式m(x)g(x)的系數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循環碼的循環碼的n-k級乘級乘法編碼電路。法編碼電路。Example輸入輸入m(x)輸出輸出c(x)(mod()(111xgxxxxrnknk)(mod()(222xgxxxxrnknk)(mod()(0 xgxxxxrknknk由于生成矩陣由于生成矩陣G中的中的k行要求線性無關，因此在求行要求線性無關，因此在求余式時，可選擇余式時，可選擇k個線性無關的信息組個線性無關的信息組 (1,0,0,0) xk-1 (0,1,0

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

20、系統碼電路是信息多項式因此，循環碼的系統碼電路是信息多項式m(x)乘乘xn-k,除除g(x)的實現電路的實現電路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級乘法電路（系統碼形式）級乘法電路（系統碼形式）門門2GF(2)上，上，x7-1=(x+1)(x3+x+1)(x3+x2+1) ，g(x)=x

21、3+x+1，試畫一個，試畫一個7,4循環碼的循環碼的n-k級系級系統碼形式的乘法編碼電路。統碼形式的乘法編碼電路。Example輸入輸入m(x)輸出輸出c(x)門門1門門2k 級編碼器級編碼器基本原理：利用校驗多項式基本原理：利用校驗多項式h(x)；為系統碼編；為系統碼編碼電路碼電路若信息序列若信息序列 m=(mk-1, mk-2,m0)對應的多項式對應的多項式m(x)=mk-1xk-1+ mk-2xk-2+m0碼多項式碼多項式C(x)= m(x)g(x),且且C(x)為系統碼為系統碼 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次的系數為零次的系數為零xn-1的系數的系數xn-2的系數的系數xn-3的系數的系數xk的系數的系數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循環碼循環碼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循環碼的循環碼的k級系統碼形式的編碼電路。級系統碼形式的編碼電路。Example輸入輸入m(x)輸出輸出c(x)門門1xx4x2第三節第三節 幾類特殊的循環碼幾類特殊的循環碼最小循環碼最小循環碼縮短循環碼縮短循環碼準循環碼準循環碼雙環循環碼雙環循環碼特殊的循環碼特殊的循環碼最小循環碼最小循環碼 一個理想中不再含有任何的非零理想，此理想對應的循環碼稱為一個理想中不再含有任何的非零理想，此理想對應的循環碼稱為最小循環碼最小循環碼或或既約循環碼既約循環碼縮短循環碼縮短循環碼 對循環碼縮短得到的碼對循環碼縮短得到的碼 取取n, k循環碼中前循環碼中前