循環(huán)碼的生成多項式為gx課件

第五章循環(huán)碼第五章循環(huán)碼要求掌握的內(nèi)容根據(jù)多項式會寫循環(huán)碼的生成矩陣和校驗矩陣會寫循環(huán)碼生成和校驗矩陣的系統(tǒng)形式會畫循環(huán)碼的編碼電路由生成多項式的根定義循環(huán)碼要求掌握的內(nèi)容第一節(jié)循環(huán)碼定義循環(huán)碼的生成多項式和校驗多項式循環(huán)碼的生成矩陣和校驗矩陣循環(huán)碼的系統(tǒng)碼形式第一節(jié)循環(huán)碼定義一、循環(huán)碼定義一、循環(huán)碼定義定義1：設CH是一個[n.k]線性分組碼，C1是其中的一個碼字，若C1的左(右)循環(huán)移位得到的n維向量也是CH中的一個碼字，則稱CH是循環(huán)碼。定義2：設是n維空間的一個k維子空間，若對任一恒有則稱Vn,k為循環(huán)子空間或循環(huán)碼定義1：設CH是一個[n.k]線性分組碼，C1是其中問題一

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

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

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

如何設計[n,k]循環(huán)碼？注：

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

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

則模F(x)的剩余類構成一個n維線性空間，定義為剩余類線性結合代數(shù)。注：2、模n多項式F(x)的剩余類構成一個多項式剩余問題一轉(zhuǎn)化為

如何從模多項式xn-1的剩余類結合代數(shù)中尋找循環(huán)子空間？問題一轉(zhuǎn)化為

如何從模多項式xn-1的剩余類結合代數(shù)中尋找循定理

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

循環(huán)碼是模xn-1的剩余類線性結合代數(shù)中的一個理想。定理以多項式xn-1為模的剩余類線性結合代數(shù)中，其一個問題二

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

尋找理想？問題二

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

尋找理想？由于

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

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

如何尋找生成多項式g(x)？問題三

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

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

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

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

…(0,0,0,…,0,1)1由于生成矩陣G中的k行要求線性無關，因此在求余式時，可選擇k表示ri(x)的系數(shù)表示ri(x)的系數(shù)循環(huán)碼的生成多項式為gx課件循環(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ù)即可構成相應的生成矩陣5、取h(x)的互反多項式h*(x),取h*(x),xh*(x),…

xn-k-1h*(x)

的系數(shù)即可構成相應的校驗矩陣循環(huán)碼的編碼原理(1)基本步驟([n,k])1、分解多項式x可選擇k個線性無關的信息組(1,0,0,…,0)xk-1，(0,1,0,0,…0)xk-2,

…(0,0,0,…,0,1)1循環(huán)碼的編碼原理(2)可選擇k個線性無關的信息組循環(huán)碼的編碼原理(2)表示ri(x)的系數(shù)表示ri(x)的系數(shù)由生成多項式的根定義循環(huán)碼設碼的生成多項式

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

gi∈GF(q)它必在某一個GF(q)的擴域上完全分解，即它的根必在此擴域上。考慮g(x)無重根的情況，即要求xn-1無重根。由生成多項式的根定義循環(huán)碼設碼的生成多項式定理在GF(q)上多項式xn-1無重根的充要條件是(n,q)=1在GF(2)上要保證g(x)無重根的條件是xn-1中的n是奇數(shù)，因此二進制循環(huán)碼中，碼長是奇數(shù)。定理在GF(q)上多項式xn-1無重根的充要條件是(n,q)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)=(x-a1)(x-a2)…(x-ar)，ai≠ag(x)=LCM(m1(x),m2(x),…,mr(x))回顧共軛根系的概念設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)g(x)=LCM(m1(x),m2(x),…,mr(x))設循環(huán)碼的編碼多項式乘法和除法電路循環(huán)碼的編碼電路(乘法和除法)循環(huán)碼的編碼多項式乘法和除法電路一、多項式乘法和除法電路一、多項式乘法和除法電路循環(huán)碼的生成多項式為gx課件b0b1b2br-2b1br-1b1br輸出C(x)輸入A(x)a0,a1,…ak乘B(x)運算電路(利用校驗多項式h(x)編碼時會用到)b0b1b2br-2b1br-1b1br輸出C(x)輸入A(b0b1b2br-2b1br-1b1br輸出C(x)輸入A(x)a0,a1,…ak乘B(x)運算電路akb0akb1akbr-2akbr-1b0b1b2br-2b1br-1b1br輸出C(x)輸入A(-b1b1br-1輸出商q(x)輸入A(x)-b2-br-1-b0除B(x)運算電路a0,a1,…ak除式B(x)構成電路，被除式A(x)的系數(shù)依次送入電路-b1b1br-1輸出商q(x)輸入A(x)-b2-br-1h0h1h2hr-2b1hr-1b1hr輸入A(x)a0,a1,…ak-g1gr-1輸出商q(x)-g2-g0-gr-1-gr-1乘H(x),除g(x)運算電路h0h1h2hr-2b1hr-1b1hr輸入A(x)a0,a多項式相乘相除電路當H(x)、G(x)次數(shù)不同時＋＋＋輸入輸出1x21x3x多項式相乘相除電路當H(x)、G(x)次數(shù)不同時＋＋＋輸入輸二、循環(huán)碼編碼電路二、循環(huán)碼編碼電路循環(huán)碼編碼電路循環(huán)碼編碼電路n-k

級編碼器基本原理：利用生成多項式g(x)若要求編成非系統(tǒng)碼形式，則利用乘法電路若要求編成系統(tǒng)碼形式，則利用除法電路循環(huán)碼編碼電路循環(huán)碼編碼電路n-k級乘法電路(非系統(tǒng)碼形式)取g(x),xg(x),…xk-1g(x)的系數(shù)可構成生成矩陣Gn-k級乘法電路(非系統(tǒng)碼形式)取g(x),xg(x),…n-k級乘法電路(非系統(tǒng)碼形式)若信息序列m=(m0,m1,…mk-1),則mG對應的n維向量為：該n維向量正是多項式m(x)g(x)的系數(shù)n-k級乘法電路(非系統(tǒng)碼形式)若信息序列m=(m0,mg0g1g2gn-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-1g1g0g1g2gn-k-2b1gn-k-1b1gn-k輸出C(GF(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)GF(2)上，x7-1=(x+1)(x3+x+1)(x3+x由于生成矩陣G中的k行要求線性無關，因此在求余式時，可選擇k個線性無關的信息組

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

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

…(0,0,0,…,0,1)1循環(huán)碼的系統(tǒng)碼由于生成矩陣G中的k行要求線性無關，因此在求余式時，可選擇k表示ri(x)的系數(shù)循環(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對應的校驗比特若信息序列m=(mk-1,mk-2,…m0)；對應的多項式m(x)=mk-1xk-1+mk-2xk-2+…+m0因此，循環(huán)碼的系統(tǒng)碼電路是信息多項式m(x)乘xn-k,除g(x)的實現(xiàn)電路n-k級乘法電路（系統(tǒng)碼形式）對任意信息多項式m(x),x輸入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)碼形式）門2輸入m(x)m0,m1,…mk-1-g1gn-k-1-g2-GF(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門2GF(2)上，x7-1=(x+1)(x3+x+1)(x3+xk

級編碼器基本原理：利用校驗多項式h(x)；為系統(tǒng)碼編碼電路若信息序列m=(mk-1,mk-2,…m0)對應的多項式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級編碼器基本原理：利用校驗多項式h(x)；為系統(tǒng)碼編碼電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級編碼器h0cn-1+h1cn-1-1+…+hk

級編碼器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=1k級編碼器cn-1-k=-(h0cn-1+h1-h0-h1-h2-hk-2b1-hk-1輸入信息門cn-1cn-2cn-k-1cn-k循環(huán)碼k級編碼電路k

級編碼器-h0-h1-h2-hk-2b1-hk-1輸入信息門cn-1GF(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)碼的k級系統(tǒng)碼形式的編碼電路。Example＋＋輸入m(x)輸出c(x)門＋1xx4x2GF(2)上，x7-1=(x+1)(x3+x+1)(x3+x第三節(jié)幾類特殊的循環(huán)碼最小循環(huán)碼縮短循環(huán)碼準循環(huán)碼雙環(huán)循環(huán)碼第三節(jié)幾類特殊的循環(huán)碼最小循環(huán)碼特殊的循環(huán)碼最小循環(huán)碼一個理想中不再含有任何的非零理想，此理想對應的循環(huán)碼稱為最小循環(huán)碼或既約循環(huán)碼縮短循環(huán)碼對循環(huán)碼縮短得到的碼取[n,k]循環(huán)碼中前i位信息位為0的碼字，得到一個[n-i,k-i]縮短循環(huán)碼準循環(huán)碼一個[mn0,mk0]線性分組碼，若它的任一碼字左移或右移循環(huán)移位n0次后，得到的碼仍是該碼的一個碼字，則稱這類碼為準循環(huán)碼雙環(huán)循環(huán)碼由兩個循環(huán)矩陣Ik和P陣組成的G=[IkP]生成的碼特殊的循環(huán)碼最小循環(huán)碼Example[8,4]碼雙循環(huán)碼形式[8,4]碼準循環(huán)碼形式（n0=2）Example[8,4]碼雙循環(huán)碼形式Examples:設[7,4]循環(huán)碼的生成多項式為g(x)=x3+x2+1，試1)寫出它的校驗多項式h(x)2)求出的生成矩陣和校驗矩陣3)求出系統(tǒng)碼的生成矩陣和校驗矩陣4)畫出(n-k)級系統(tǒng)碼編碼電路和k級編碼電路Examples:設[7,4]循環(huán)碼的生成多項式為1)h(x)=(xn-1)/g(x)=x4+x2+x+12)h*(x)=x4+x3+x2+11)h(x)=(xn-1)/g(x)=x4+x2+x+12循環(huán)碼的生成多項式為gx課件循環(huán)碼的生成多項式為gx課件第五章循環(huán)碼第五章循環(huán)碼要求掌握的內(nèi)容根據(jù)多項式會寫循環(huán)碼的生成矩陣和校驗矩陣會寫循環(huán)碼生成和校驗矩陣的系統(tǒng)形式會畫循環(huán)碼的編碼電路由生成多項式的根定義循環(huán)碼要求掌握的內(nèi)容第一節(jié)循環(huán)碼定義循環(huán)碼的生成多項式和校驗多項式循環(huán)碼的生成矩陣和校驗矩陣循環(huán)碼的系統(tǒng)碼形式第一節(jié)循環(huán)碼定義一、循環(huán)碼定義一、循環(huán)碼定義定義1：設CH是一個[n.k]線性分組碼，C1是其中的一個碼字，若C1的左(右)循環(huán)移位得到的n維向量也是CH中的一個碼字，則稱CH是循環(huán)碼。定義2：設是n維空間的一個k維子空間，若對任一恒有則稱Vn,k為循環(huán)子空間或循環(huán)碼定義1：設CH是一個[n.k]線性分組碼，C1是其中問題一

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

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

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

如何設計[n,k]循環(huán)碼？注：

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

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

則模F(x)的剩余類構成一個n維線性空間，定義為剩余類線性結合代數(shù)。注：2、模n多項式F(x)的剩余類構成一個多項式剩余問題一轉(zhuǎn)化為

如何從模多項式xn-1的剩余類結合代數(shù)中尋找循環(huán)子空間？問題一轉(zhuǎn)化為

如何從模多項式xn-1的剩余類結合代數(shù)中尋找循定理

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

循環(huán)碼是模xn-1的剩余類線性結合代數(shù)中的一個理想。定理以多項式xn-1為模的剩余類線性結合代數(shù)中，其一個問題二

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

尋找理想？問題二

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

尋找理想？由于

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

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

如何尋找生成多項式g(x)？問題三

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

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

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

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

…(0,0,0,…,0,1)1由于生成矩陣G中的k行要求線性無關，因此在求余式時，可選擇k表示ri(x)的系數(shù)表示ri(x)的系數(shù)循環(huán)碼的生成多項式為gx課件循環(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ù)即可構成相應的生成矩陣5、取h(x)的互反多項式h*(x),取h*(x),xh*(x),…

xn-k-1h*(x)

的系數(shù)即可構成相應的校驗矩陣循環(huán)碼的編碼原理(1)基本步驟([n,k])1、分解多項式x可選擇k個線性無關的信息組(1,0,0,…,0)xk-1，(0,1,0,0,…0)xk-2,

…(0,0,0,…,0,1)1循環(huán)碼的編碼原理(2)可選擇k個線性無關的信息組循環(huán)碼的編碼原理(2)表示ri(x)的系數(shù)表示ri(x)的系數(shù)由生成多項式的根定義循環(huán)碼設碼的生成多項式

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

gi∈GF(q)它必在某一個GF(q)的擴域上完全分解，即它的根必在此擴域上?？紤]g(x)無重根的情況，即要求xn-1無重根。由生成多項式的根定義循環(huán)碼設碼的生成多項式定理在GF(q)上多項式xn-1無重根的充要條件是(n,q)=1在GF(2)上要保證g(x)無重根的條件是xn-1中的n是奇數(shù)，因此二進制循環(huán)碼中，碼長是奇數(shù)。定理在GF(q)上多項式xn-1無重根的充要條件是(n,q)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)=(x-a1)(x-a2)…(x-ar)，ai≠ag(x)=LCM(m1(x),m2(x),…,mr(x))回顧共軛根系的概念設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)g(x)=LCM(m1(x),m2(x),…,mr(x))設循環(huán)碼的編碼多項式乘法和除法電路循環(huán)碼的編碼電路(乘法和除法)循環(huán)碼的編碼多項式乘法和除法電路一、多項式乘法和除法電路一、多項式乘法和除法電路循環(huán)碼的生成多項式為gx課件b0b1b2br-2b1br-1b1br輸出C(x)輸入A(x)a0,a1,…ak乘B(x)運算電路(利用校驗多項式h(x)編碼時會用到)b0b1b2br-2b1br-1b1br輸出C(x)輸入A(b0b1b2br-2b1br-1b1br輸出C(x)輸入A(x)a0,a1,…ak乘B(x)運算電路akb0akb1akbr-2akbr-1b0b1b2br-2b1br-1b1br輸出C(x)輸入A(-b1b1br-1輸出商q(x)輸入A(x)-b2-br-1-b0除B(x)運算電路a0,a1,…ak除式B(x)構成電路，被除式A(x)的系數(shù)依次送入電路-b1b1br-1輸出商q(x)輸入A(x)-b2-br-1h0h1h2hr-2b1hr-1b1hr輸入A(x)a0,a1,…ak-g1gr-1輸出商q(x)-g2-g0-gr-1-gr-1乘H(x),除g(x)運算電路h0h1h2hr-2b1hr-1b1hr輸入A(x)a0,a多項式相乘相除電路當H(x)、G(x)次數(shù)不同時＋＋＋輸入輸出1x21x3x多項式相乘相除電路當H(x)、G(x)次數(shù)不同時＋＋＋輸入輸二、循環(huán)碼編碼電路二、循環(huán)碼編碼電路循環(huán)碼編碼電路循環(huán)碼編碼電路n-k

級編碼器基本原理：利用生成多項式g(x)若要求編成非系統(tǒng)碼形式，則利用乘法電路若要求編成系統(tǒng)碼形式，則利用除法電路循環(huán)碼編碼電路循環(huán)碼編碼電路n-k級乘法電路(非系統(tǒng)碼形式)取g(x),xg(x),…xk-1g(x)的系數(shù)可構成生成矩陣Gn-k級乘法電路(非系統(tǒng)碼形式)取g(x),xg(x),…n-k級乘法電路(非系統(tǒng)碼形式)若信息序列m=(m0,m1,…mk-1),則mG對應的n維向量為：該n維向量正是多項式m(x)g(x)的系數(shù)n-k級乘法電路(非系統(tǒng)碼形式)若信息序列m=(m0,mg0g1g2gn-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-1g1g0g1g2gn-k-2b1gn-k-1b1gn-k輸出C(GF(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)GF(2)上，x7-1=(x+1)(x3+x+1)(x3+x由于生成矩陣G中的k行要求線性無關，因此在求余式時，可選擇k個線性無關的信息組

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

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

…(0,0,0,…,0,1)1循環(huán)碼的系統(tǒng)碼由于生成矩陣G中的k行要求線性無關，因此在求余式時，可選擇k表示ri(x)的系數(shù)循環(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對應的校驗比特若信息序列m=(mk-1,mk-2,…m0)；對應的多項式m(x)=mk-1xk-1+mk-2xk-2+…+m0因此，循環(huán)碼的系統(tǒng)碼電路是信息多項式m(x)乘xn-k,除g(x)的實現(xiàn)電路n-k級乘法電路（系統(tǒng)碼形式）對任意信息多項式m(x),x輸入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)碼形式）門2輸入m(x)m0,m1,…mk-1-g1gn-k-1-g2-GF(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門2GF(2)上，x7-1=(x+1)(x3+x+1)(x3+xk

級編碼器基本原理：利用校驗多項式h(x)；為系統(tǒng)碼編碼電路若信息序列m=(mk-1,mk-2,…m0)對應的多項式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級編碼器基本原理：利用校驗多項式h(x)；為系統(tǒng)碼編碼電k

級編碼器h0

cn-1+h1

cn-1-1+

…+hkcn-1-k=0h0

cn