第五章循環(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)碼形式一、循環(huán)碼定義定義1：設(shè)CH是一個[n.k]線性分組碼，C1是其中的一個碼字，若C1的左(右)循環(huán)移位得到的n維向量也是CH中的一個碼字，則稱CH是循環(huán)碼。定義2：設(shè)是n維空間的一個k維子空間，若對任一恒有則稱Vn,k為循環(huán)子空間或循環(huán)碼問題一

如何尋找k維循環(huán)子空間？

如何設(shè)計[n,k]循環(huán)碼？——利用多項式和有限域的概念注：

1、GF(p)上的n維向量與GF(p)上的多項式之間有一一對應(yīng)的關(guān)系

2、模n多項式F(x)的剩余類構(gòu)成一個多項式剩余類環(huán)Fp[x]/F(x)，若在環(huán)中再定義一個數(shù)乘運算，即

則模F(x)的剩余類構(gòu)成一個n維線性空間，定義為剩余類線性結(jié)合代數(shù)。問題一轉(zhuǎn)化為

如何從模多項式xn-1的剩余類結(jié)合代數(shù)中尋找循環(huán)子空間？定理

以多項式xn-1為模的剩余類線性結(jié)合代數(shù)中，其一個子空間Vn,k為循環(huán)子空間(或循環(huán)碼)的充要條件是：Vn,k是一個理想。

循環(huán)碼是模xn-1的剩余類線性結(jié)合代數(shù)中的一個理想。問題二

如何從多項式剩余類環(huán)中

尋找理想？由于

1、多項式剩余類環(huán)中任何一個理想都是主理想——主理想中的所有元素可由某一個元素的倍式構(gòu)成

2、在主理想的所有元素中，至少可找到一個次數(shù)最低的首一多項式g(x),即生成多項式定義：生成多項式g(x)是模xn-1剩余類代數(shù)中，一個理想的次數(shù)最低的非零首一多項式，它是理想或循環(huán)碼的生成元。問題三

如何尋找生成多項式g(x)？循環(huán)碼模多項式xn-1剩余類線性結(jié)合代數(shù)中的理想生成多項式二、生成多項式和校驗多項式兩個定理定理1:GF(q)(q為素數(shù)或素數(shù)的冪)上的[n,k]循環(huán)碼中，存在唯一的n-k次首一多項式g(x)，每一個碼多項式C(x)必是g(x)的倍式，每一個小于等于(n-1)次的g(x)的倍式一定是碼多項式兩個定理定理2:GF(q)(q為素數(shù)或素數(shù)的冪)上[n,k]循環(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)碼兩個結(jié)論

結(jié)論1:找一個[n,k]循環(huán)碼，即是找一個n-k次首一多項式g(x)，且g(x)必是xn-1的因式。結(jié)論2:若C(x)是一個碼多項式，則反之，若，則C(x)必是一個碼多項式ExamplesGF(2)上，x7-1=(x+1)(x3+x+1)(x3+x2+1)

試求一個[7,4]循環(huán)碼。g(x)、xg(x)、x2

g(x)、x3g(x)、三、循環(huán)碼的生成矩陣和校驗矩陣g(x)決定生成矩陣，h(x)決定校驗矩陣四、循環(huán)碼的系統(tǒng)碼——模g(x)的除法問題由于生成矩陣G中的k行要求線性無關(guān)，因此在求余式時，可選擇k個線性無關(guān)的信息組(1,0,0,…,0)xk-1，(0,1,0,0,…0)xk-2,

…(0,0,0,…,0,1)1表示ri(x)的系數(shù)循環(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),…xk-1g(x)4、取上述k個多項式的系數(shù)即可構(gòu)成相應(yīng)的生成矩陣5、取h(x)的互反多項式h*(x),取h*(x),xh*(x),…

xn-k-1h*(x)

的系數(shù)即可構(gòu)成相應(yīng)的校驗矩陣可選擇k個線性無關(guān)的信息組(1,0,0,…,0)xk-1，(0,1,0,0,…0)xk-2,

…(0,0,0,…,0,1)1循環(huán)碼的編碼原理(2)表示ri(x)的系數(shù)由生成多項式的根定義循環(huán)碼設(shè)碼的生成多項式

g(x)=xr+gr-1xr-1+…+g1x+g0,

gi∈GF(q)它必在某一個GF(q)的擴域上完全分解，即它的根必在此擴域上?？紤]g(x)無重根的情況，即要求xn-1無重根。定理在GF(q)上多項式xn-1無重根的充要條件是(n,q)=1在GF(2)上要保證g(x)無重根的條件是xn-1中的n是奇數(shù)，因此二進(jìn)制循環(huán)碼中，碼長是奇數(shù)。g(x)=(x-a1)(x-a2)…(x-ar)，ai≠aj，ai∈GF(qm)每一碼多項式必以a1,a2,…,ar為根。則

C(ai)=cn-1ain-1+cn-2ain-2+…+c1ai+c0=0g(x)=LCM(m1(x),m2(x),…,mr(x))回顧共軛根系的概念設(shè)f(x)=fkxk+fk-1xk-1+…+f0,fi∈GF(p)。若p特征域的元素w是方程f(x)的根，f(w)=0,則對于一切自然數(shù)n,wp^n也必是f(x)的根。共軛根系最小多項式：系數(shù)取自GF(p)上，且以w為根的所有首一多項式中，次數(shù)最低的多項式稱為w的最小多項式，記為m(x)循環(huán)碼的編碼多項式乘法和除法電路循環(huán)碼的編碼電路(乘法和除法)一、多項式乘法和除法電路b0b1b2br-2b1br-1b1br輸出C(x)輸入A(x)a0,a1,…ak乘B(x)運算電路(利用校驗多項式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)運算電路多項式相乘相除電路當(dāng)H(x)、G(x)次數(shù)不同時＋＋＋輸入輸出1x21x3x二、循環(huán)碼編碼電路循環(huán)碼編碼電路循環(huán)碼編碼電路n-k

級編碼器基本原理：利用生成多項式g(x)若要求編成非系統(tǒng)碼形式，則利用乘法電路若要求編成系統(tǒng)碼形式，則利用除法電路n-k級乘法電路(非系統(tǒng)碼形式)取g(x),xg(x),…xk-1g(x)的系數(shù)可構(gòu)成生成矩陣Gn-k級乘法電路(非系統(tǒng)碼形式)若信息序列m=(m0,m1,…mk-1),則mG對應(yīng)的n維向量為：該n維向量正是多項式m(x)g(x)的系數(shù)g0g1g2gn-k-2b1gn-k-1b1gn-k輸出C(x)輸入m(x)m0,m1,…mk乘g(x)運算電路mk-1gn-k-1mk-1

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

(1,0,0,…,0)xk-1

(0,1,0,0,…0)xk-2

…(0,0,0,…,0,1)1循環(huán)碼的系統(tǒng)碼表示ri(x)的系數(shù)循環(huán)碼的系統(tǒng)碼n-k級乘法電路（系統(tǒng)碼形式）對任意信息多項式m(x),xn-km(x)除g(x)可得余式r(x)，m(x)的系數(shù)為信息序列m，r(x)的系數(shù)為m對應(yīng)的校驗比特若信息序列m=(mk-1,mk-2,…m0)；對應(yīng)的多項式m(x)=mk-1xk-1+mk-2xk-2+…+m0因此，循環(huán)碼的系統(tǒng)碼電路是信息多項式m(x)乘xn-k,除g(x)的實現(xiàn)電路輸入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)碼形式）門2GF(2)上，x7-1=(x+1)(x3+x+1)(x3+x2+1)，g(x)=x3+x+1，試畫一個[7,4]循環(huán)碼的n-k級系統(tǒng)碼形式的乘法編碼電路。Example＋＋輸入m(x)輸出c(x)門1門2k

級編碼器基本原理：利用校驗多項式h(x)；為系統(tǒng)碼編碼電路若信息序列m=(mk-1,mk-2,…m0)對應(yīng)的多項式m(x)=mk-1xk-1+mk-2xk-2+…+m0碼多項式C(x)=m(x)g(x),且C(x)為系統(tǒng)碼

h(x)C(x)=h(x)m(x)g(x)=m(x)(xn-1)=m(x)xn-m(x)=mk-1xn+k-1+mk-2xn+k-2+…+m0xn-(mk-1xk-1+mk-2xk-2+…m0)k

級編碼器h0

cn-1+h1

cn-1-1+

…+hkcn-1-k=0h0

cn-2+h1

cn-2-1+

…+hkcn-2-k=0h0

cn-3+h1

cn-3-1+

…+hkcn-3-k=0h0

ck

+h1

ck-1+

…+hkc0=0h(x)C(x)的乘積中，xn-1,xn-2,…xk次的系數(shù)為零xn-1的系數(shù)xn-2的系數(shù)xn-3的系數(shù)xk的系數(shù)k

級編碼器cn-1-k

=-

(h0

cn-1+h1

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)碼k級編碼電路k

級編碼器GF(2)上，x7-1=(x+1)(x3+x+1)(x3+x2+1)，g