第五章循環(huán)碼

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

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

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

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

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

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

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

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

9、ggggggG01210110110000000 xgxgxxgxkk,21nknkkkkkkkhhhhhhhhhhhhh12101101100000000H xhxhxxhxknkn*2*1,kkkhxhxhxh110*)(State Key Laboratory of Integrated Services Networks 四、循環(huán)碼的系統(tǒng)碼 模g(x)的除法問(wèn)題 xgxrxxmxCknmod0 xgxxmxxmxCxrknknmod由于生成矩陣由于生成矩陣G中的中的k行要求線性無(wú)關(guān)，因此行要求線性無(wú)關(guān)，因此在求余式時(shí)，可選擇在求余式時(shí)，可選擇k個(gè)線性無(wú)關(guān)的信息組個(gè)線性無(wú)關(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、分解多項(xiàng)式、分解多項(xiàng)式xn-1=g(x)h(x)2、選擇其中的、選擇其中的n-k次多項(xiàng)式次多項(xiàng)式g(x)為生成多項(xiàng)式為生成多項(xiàng)式3、由、由g(x)可得到可得到k個(gè)多項(xiàng)式個(gè)多項(xiàng)式g(x), xg(x),

11、xk-1g(x)4、取上述、取上述k個(gè)多項(xiàng)式的系數(shù)即可構(gòu)成相應(yīng)的生成矩陣個(gè)多項(xiàng)式的系數(shù)即可構(gòu)成相應(yīng)的生成矩陣5、取、取h(x)的互反多項(xiàng)式的互反多項(xiàng)式h*(x),取取h*( x), xh*( x), xn-k-1h*( x) 的系數(shù)即可構(gòu)成相應(yīng)的校驗(yàn)矩陣的系數(shù)即可構(gòu)成相應(yīng)的校驗(yàn)矩陣可選擇可選擇k個(gè)線性無(wú)關(guān)的信息組個(gè)線性無(wú)關(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ù)由生成多項(xiàng)式的根定義循環(huán)碼設(shè)碼的生成多項(xiàng)式 g(x)=xr+gr-1xr-1+g1x+g0, giGF(q)它必在某一個(gè)GF(q)的擴(kuò)域上完全分解，即它的根必在此擴(kuò)域上。考慮g(x)無(wú)重根的情況，即要求xn-1無(wú)重根。定理在GF(q)上多項(xiàng)式xn-1無(wú)重根的充要條件是(n,q)=1在GF(2)上要保證g(x)無(wú)重根的條件是xn-1中的n是奇數(shù)，因此二進(jìn)制循環(huán)碼中，碼長(zhǎng)是奇數(shù)。g(x)=(x-a1)(x-a2)(x-ar)， aiaj，aiGF(qm)每一碼多項(xiàng)式必以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,則對(duì)于一切自然數(shù)則對(duì)于一切自然數(shù)n, wpn也必是也必是f(x)的根。的根。21,.,mmppppw w wwww共軛根系共軛根系最小多項(xiàng)式：系數(shù)取自最小多項(xiàng)式：系數(shù)取自GF(p)上，且以上，且以w為根的所有首一多項(xiàng)式為根的所有首一多項(xiàng)式中，次數(shù)最低的多項(xiàng)式稱為中，次

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

15、式h(x)編碼時(shí)會(huì)用到)b0b1b2br-2b1br-1b1br輸出C(x)輸入A(x)a0,a1,ak乘B(x)運(yùn)算電路akb0akb1akbr-2akbr-1-b1b1br-1輸出商q(x)輸入A(x)-b2-br-1-b0除B(x)運(yùn)算電路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)運(yùn)算電路多項(xiàng)式相乘相除電路多項(xiàng)式相乘相除電路當(dāng)當(dāng)H(x)、G(x)次數(shù)不同時(shí)次數(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 級(jí)編碼器級(jí)編碼器基本原理：利用生成多項(xiàng)式基本原理：利用生成多項(xiàng)式g(x)若要求編成若要求編成非系統(tǒng)碼非系統(tǒng)碼形式，則利用形式，則利用乘法電路乘法電路若要求編成若要求編成系統(tǒng)碼系統(tǒng)碼形式，則利用形式，則利用除法電路除法電路)()()(利用校驗(yàn)多項(xiàng)式編碼級(jí)編碼電路乘法電路實(shí)現(xiàn)非系統(tǒng)碼形式除法電路實(shí)現(xiàn)系統(tǒng)碼形式級(jí)編碼電路循環(huán)碼編碼電路kknn-k級(jí)乘法電路級(jí)乘法電路(非系統(tǒng)碼

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

18、列，g(x)為生成多項(xiàng)式mk-1 g0mk-1 g1GF(2)上，上，x7-1=(x+1)(x3+x+1)(x3+x2+1) ，g(x)=x3+x+1，試畫一個(gè)，試畫一個(gè)7,4循環(huán)碼的循環(huán)碼的n-k級(jí)乘級(jí)乘法編碼電路。法編碼電路。Example輸入輸入m(x)輸出輸出c(x)(mod()(111xgxxxxrnknk)(mod()(222xgxxxxrnknk)(mod()(0 xgxxxxrknknk由于生成矩陣由于生成矩陣G中的中的k行要求線性無(wú)關(guān)，因此在求行要求線性無(wú)關(guān)，因此在求余式時(shí)，可選擇余式時(shí)，可選擇k個(gè)線性無(wú)關(guān)的信息組個(gè)線性無(wú)關(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級(jí)乘法電路（系統(tǒng)碼形式）級(jí)乘法電路（系統(tǒng)碼形式）對(duì)任意信息多項(xiàng)式對(duì)任意信息多項(xiàng)式m(x), xn-km(x)除除g(x)可得余式可得余式r(x)，m(x)的系數(shù)為信息序列的系數(shù)為信息序列m，r(x) 的系數(shù)為的系數(shù)為m對(duì)應(yīng)的校驗(yàn)比特對(duì)應(yīng)的校驗(yàn)比特若信息序列若信息序列 m=(mk-1, mk-2,m0)；對(duì)應(yīng)的多項(xiàng)式；對(duì)應(yīng)的多項(xiàng)式m(x)=mk-1xk-1+ mk-2xk-2+m0因此，循環(huán)碼的

20、系統(tǒng)碼電路是信息多項(xiàng)式因此，循環(huán)碼的系統(tǒng)碼電路是信息多項(xiàng)式m(x)乘乘xn-k,除除g(x)的實(shí)現(xiàn)電路的實(shí)現(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)運(yùn)算電路運(yùn)算電路門1n-k級(jí)乘法電路（系統(tǒng)碼形式）級(jí)乘法電路（系統(tǒng)碼形式）門門2GF(2)上，上，x7-1=(x+1)(x3+x+1)(x3+x2+1) ，g(x)=x

21、3+x+1，試畫一個(gè)，試畫一個(gè)7,4循環(huán)碼的循環(huán)碼的n-k級(jí)系級(jí)系統(tǒng)碼形式的乘法編碼電路。統(tǒng)碼形式的乘法編碼電路。Example輸入輸入m(x)輸出輸出c(x)門門1門門2k 級(jí)編碼器級(jí)編碼器基本原理：利用校驗(yàn)多項(xiàng)式基本原理：利用校驗(yàn)多項(xiàng)式h(x)；為系統(tǒng)碼編；為系統(tǒng)碼編碼電路碼電路若信息序列若信息序列 m=(mk-1, mk-2,m0)對(duì)應(yīng)的多項(xiàng)式對(duì)應(yīng)的多項(xiàng)式m(x)=mk-1xk-1+ mk-2xk-2+m0碼多項(xiàng)式碼多項(xiàng)式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 級(jí)編碼器級(jí)編碼器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 級(jí)編碼器級(jí)編碼器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級(jí)編碼電路級(jí)編碼電路k 級(jí)編碼器級(jí)編碼器GF(2)上，上，x7-1=(x+1)(x3+x+1)(x3+x2+1) ，g(x)=x3+x+1， h(x)= x4+x2+x+1。試畫一個(gè)。試畫一個(gè)7,4循環(huán)碼的循環(huán)碼的k級(jí)系統(tǒng)碼形式的編碼電路。級(jí)系統(tǒng)碼形式的編碼電路。Example輸入輸入m(x)輸出輸出c(x)門門1xx4x2第三節(jié)第三節(jié) 幾類特殊的循環(huán)碼幾類特殊的循環(huán)碼最小循環(huán)碼最小循環(huán)碼縮短循環(huán)碼縮短循環(huán)碼準(zhǔn)循環(huán)碼準(zhǔn)循環(huán)碼雙環(huán)循環(huán)碼雙環(huán)循環(huán)碼特殊的循環(huán)碼特殊的循環(huán)碼最小循環(huán)碼最小循環(huán)碼 一個(gè)理想中不再含有任何的非零理想，此理想對(duì)應(yīng)的循環(huán)碼稱為一個(gè)理想中不再含有任何的非零理想，此理想對(duì)應(yīng)的循環(huán)碼稱為最小循環(huán)碼最小循環(huán)碼或或既約循環(huán)碼既約循環(huán)碼縮短循環(huán)碼縮短循環(huán)碼 對(duì)循環(huán)碼縮短得到的碼對(duì)循環(huán)碼縮短得到的碼 取取n, k循環(huán)碼中前循環(huán)碼中前