第四章 多項式環(huán)及循環(huán)碼

第四章多項式環(huán)及循環(huán)碼1一種特殊的線性分組碼循環(huán)算子L：對n重碼字A=(an-1,an-2,an-3,…,a2,a1,a0)，有B=L(A)=(bn-1,bn-2,bn-3,…,b2,b1,b0)=(an-2,an-3,…,a2,a1,a0,an-1)循環(huán)特性：對任意許用碼字C，則L(C)也是許用碼字循環(huán)碼：一個(n,k)線性碼C，如果每個碼字的循環(huán)移位仍是一個碼字,稱該碼為循環(huán)碼。2循環(huán)碼的描述問題：如何構造和描述一個循環(huán)碼？滿足什么樣條件的循環(huán)碼可以有較好的距離特性？3多項式的引入如果將碼字描述成n階多項式的形式，A(x)=an-1xn-1+an-2xn-2+an-3xn-3+…+a2x2+a1,x+a0，則循環(huán)算法就可以描述為L(A(x))=xA(x)mod(xn-1)便于描述：對任何一個多項式D(x)，有D(x)A(x)mod(xn-1)為許用碼字，這里并沒有限定D(x)的冪次，但可以肯定的一點是不同的D(x)A(x)mod(xn-1)是有限的，其個數(shù)由A(x)決定，這也決定了碼集的冗余度和糾錯能力，什么樣的A(x)可以得到什么樣的冗余度？哪些A(x)是等價的？4第一節(jié)多項式與多項式環(huán)5要求掌握的內容多項式剩余類環(huán)循環(huán)群6一、復習幾個概念同余、剩余類群環(huán)域7同余和剩余類(p23)同余：若整數(shù)a和b被同一正整數(shù)m除時，有相同的余數(shù)，則稱a、b關于模m同余，記為剩余類(Residue)：給定正整數(shù)m，可將全體整數(shù)按余數(shù)相同進行分類，可獲得m個剩余類，分別用8群(Group)的定義(p26)設G是一個非空集合，并在G內定義了一種代數(shù)運算“?！?，若滿足：1)封閉性。對任意，恒有2)結合律。對任意，恒有3)G中存在一恒等元e,對任意，使4)對任意，存在a的逆元，使則稱G構成一個群。若加法，恒等元用0表示，若為乘法，恒等元稱為單位元9環(huán)(Ring)的定義(p30)非空集合R中，若定義了兩種代數(shù)運算加和乘，且滿足：

1)集合R在加法運算下構成阿貝爾群

2)乘法有封閉性

3)乘法結合律成立，且加和乘之間有分配律10子環(huán)、理想和主理想(P101)子環(huán)：若環(huán)R中的子集S，在環(huán)R中的定義的代數(shù)運算也構成環(huán)，則稱S為R的子環(huán)。理想：S是R的一個子環(huán)，若S中的元素由某幾個元素及其所有可能的倍數(shù)構成，則S是一個理想主理想：若理想中的元素由一個元素的所有倍數(shù)及其線性組合生成，則稱這個理想為主理想。11二、多項式剩余類環(huán)(P103)有關多項式的幾個概念多項式的加法和乘法多項式剩余類環(huán)的定義12多項式

f(x)=fnxn+fn-1xn-1+…+f1x+f0其中i=0,1,…n，該多項式稱為域Fp上的多項式多項式次數(shù)degf(x)

系數(shù)不為零的x的最高次數(shù)稱為多項式f(x)的次數(shù)首一多項式最高次數(shù)的系數(shù)為1的多項式有關多項式的幾個概念13既約多項式設f(x)是次數(shù)大于零的多項式，若除常數(shù)和常數(shù)與本身的乘積以外，再不能被域Fp上的其他多項式整除，則稱f(x)為域Fp上的既約多項式

有關多項式的幾個概念14f(x)=fnxn+fn-1xn-1+…+f1x+f0g(x)=gnxn+gn-1xn-1+…+g1x+g0若對所有i,fi=gi,則f(x)=g(x)多項式加法f(x)+g(x)=(fn+

gn)xn+(fn-1

+

gn-1)xn-1+…+(f1

+

g1)x+(f0

+

g0)多項式乘法結論：按上述定義的加法和乘法運算，F(xiàn)p[x]構成一個具有單位元、無零因子的可換環(huán)多項式的加法和乘法15定義：以一個Fp上的多項式f(x)=fnxn+fn-1xn-1+…+f1x+f0為模的剩余類全體構成一個多項式剩余類環(huán)

Fp上的所有次數(shù)小于n-1的多項式構成n次多項式的剩余類全體

剩余類之間的加法和乘法運算規(guī)則多項式剩余類環(huán)16

1、GF(2)上的多項式f(x)=x2+1的剩余類全體為：

2、GF(2)上的多項式f(x)=x2+x+1的剩余類全體為：對所定義的加法和乘法運算，前者構成剩余類環(huán)，后者構成域結論：若n次首一多項式f(x)在域Fp上既約，則f(x)的剩余類環(huán)構成一個有pn個元素的有限域Examples17兩個結論多項式環(huán)Fp[x]的一切理想均是主理想多項式剩余類環(huán)Fp[x]/f(x)中的每一個理想都是主理想。18第2節(jié)循環(huán)碼的描述19要求掌握的內容定義循環(huán)碼的代數(shù)性質循環(huán)碼的生成多項式和校驗多項式循環(huán)碼的生成矩陣和校驗矩陣循環(huán)碼的系統(tǒng)碼形式20定義1：設CH是一個[n.k]線性分組碼，C1是其中的一個碼字，若C1的左(右)循環(huán)移位得到的n維向量也是CH中的一個碼字，則稱CH是循環(huán)碼。定義2：設是n維空間的一個k維子空間，若對任一恒有則稱Vn,k為循環(huán)子空間或循環(huán)碼一、循環(huán)碼定義21將碼字看成如下多項式的系數(shù):循環(huán)碼碼字與多項式之間的關系因此，循環(huán)碼的每個碼字對應一個次數(shù)小于等于n-1的多項式。若，則V(x)為n-1次多項式，若vn-1=0。則V(x)為次數(shù)小于n-1的多項式。并且，碼字與多項式之間是一一對應的。22二、循環(huán)碼的代數(shù)性質假設有兩個碼多項式則有23二、循環(huán)碼的代數(shù)性質

定理4.1

循環(huán)碼C中次數(shù)最低的非零碼多項式是唯一的。由于循環(huán)碼是線性碼，因此證明：令為循環(huán)碼中次數(shù)最低的一個非零多項式。假設該多項式不唯一，即存在另一個次數(shù)為r的多項式是一個次數(shù)比r更低的碼多項式。24二、循環(huán)碼的代數(shù)性質

定理4.1

循環(huán)碼C中次數(shù)最低的非零碼多項式是唯一的。即證明：若則是一個次數(shù)比r更低的非零碼多項式。因此，g(x)是唯一的。這與假設相矛盾，因此必有25二、循環(huán)碼的代數(shù)性質

定理4.2

令為循環(huán)碼C中最低次數(shù)的非零碼多項式，則常數(shù)項g0一定等于1。證明：假設這與之前假設g(x)是次數(shù)最低的非零碼多項式相矛盾。則上式表明，如果將g(x)循環(huán)左移一位，可以得到一個次數(shù)低于r的非零碼多項式因此，必有26由定理4.2可知，次數(shù)最低的非零碼多項式具有如下形式考慮多項式，它們的次數(shù)分別為，且是g(x)的循環(huán)移位。因此，由循環(huán)碼的定義，它們一定是循環(huán)碼的碼多項式，且它們的線性組合也一定是一個碼多項式，即是一個碼多項式，其中27定理4-3

設是(n,k)循環(huán)碼的最低次數(shù)非零碼多項式，次數(shù)小于或等于n-1的多項式為碼多項式，當且僅當它是g(x)的倍式。證明：令是次數(shù)小于等于n-1的二進制多項式，且為g(x)的倍式。由于是碼多項式的線性組合，因此它一定是一個碼多項式。28證明：假設是循環(huán)碼中的碼多項式，我們可得到因此有由于和都是碼多項式，因此b(x)必為碼多項式。若，則b(x)必為次數(shù)小于g(x)的非零碼多項式，與g(x)為次數(shù)最低碼多項式相矛盾，因此b(x)=0。因此，碼多項式必為g(x)的倍式。29定理4-4(p147)

(n,k)循環(huán)碼中，有且僅有一個次數(shù)為n-k的碼多項式每一個碼多項式是g(x)的倍式，且每個次數(shù)不大于n-1且為g(x)的倍式的多項式必為一碼多項式。由于碼多項式是g(x)及其倍式的線性組合，即可知共有個元素，構成維數(shù)為n-r的線性空間，而[n,k]循環(huán)碼中共有個碼字。因此有即30注：由上述定理，

(n,k)循環(huán)碼的每一個碼多項式可表示為生成多項式的次數(shù)等于碼中校驗位的個數(shù)，即等于n-k.其中是待編碼的信息比特，v(x)是對應的碼多項式。因此，可利用乘以消息多項式來完成編碼，即一個[n,k]循環(huán)碼的碼字可由非零最小次數(shù)多項式完全確定，稱該多項式為循環(huán)碼的生成多項式。

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

定理4-5(p148):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)碼33三、生成多項式結論1:找一個[n,k]循環(huán)碼，即是找一個n-k次首一多項式g(x)，且g(x)必是xn-1的因式。結論2:若C(x)是一個碼多項式，則反之，若，則C(x)必是一個碼多項式34g(x)決定生成矩陣，h(x)決定校驗矩陣四、循環(huán)碼的生成矩陣和校驗矩陣353637ExamplesGF(2)上，x7-1=(x+1)(x3+x+1)(x3+x2+1)

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

g(x)、x3g(x)、38五、循環(huán)碼的系統(tǒng)碼(P151)39由于生成矩陣G中的k行要求線性無關，因此在求余式時，可選擇k個線性無關的信息組

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

(0,1,0,0,…0)xk-2,…(0,0,0,…,0,1)140表示ri(x)的系數(shù)4142循環(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ù)即可構成相應的校驗矩陣43可選擇k個線性無關的信息組

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

(0,1,0,0,…0)xk-2,…(0,0,0,…,0,1)1循環(huán)碼的編碼原理(2)44表示ri(x)的系數(shù)45第3節(jié)循環(huán)碼的編碼電路(P165,174)多項式乘法和除法電路循環(huán)碼的編碼電路(乘法和除法)46一、多項式乘法和除法電路4748b0b1b2br-2br-1br輸出C(x)輸入A(x)a0,a1,…ak乘B(x)運算電路(利用校驗多項式h(x)編碼時會用到)49b0b1b2br-2br-1br輸出C(x)輸入A(x)a0,a1,…ak乘B(x)運算電路akb0akb1akbr-2akbr-150-b1br-1輸出商q(x)輸入A(x)-b2-br-1-b0除B(x)運算電路a0,a1,…ak除式B(x)構成電路，被除式A(x)的系數(shù)依次送入電路51h0h1h2hr-2hr-1輸入A(x)a0,a1,…ak-g1gr-1輸出商q(x)-g2-g0-gr-1-gr-1乘H(x),除g(x)運算電路hr52二、循環(huán)碼編碼電路(P174)5354n-k

級編碼器基本原理：利用生成多項式g(x)若要求編成非系統(tǒng)碼形式，則利用乘法電路若要求編成系統(tǒng)碼形式，則利用除法電路55n-k級乘法電路(非系統(tǒng)碼形式)取g(x),xg(x),…xk-1g(x)的系數(shù)可構成生成矩陣G56n-k級乘法電路(非系統(tǒng)碼形式)若信息序列m=(mk-1,mk-2,…m0),則mG對應的n維向量為：該n

維向量正是多項式m(x)g(x)的系數(shù)57g0g1g2gn-k-2gn-k-1gn-k輸出C(x)輸入m(x)m0,m1,…mk-1乘g(x)運算電路mk-1gn-k-1mk-1

gn-k輸入m(x)是信息序列，g(x)為生成多項式mk-1g0mk-1g158ExamplesGF(2)上，x7-1=(x+1)(x3+x+1)(x3+x2+1)

試畫一個[7,4]循環(huán)碼的n-k級乘法編碼電路。59n-k級除法電路(系統(tǒng)碼形式)

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

(0,1,0,0,…0)xk-2,…(0,0,0,…,0,1)160表示ri(x)的系數(shù)61n-k級除法電路(系統(tǒng)碼形式)對任意信息多項式m(x),xn-km(x)除g(x)可得余式r(x)，m(x)的系數(shù)為信息序列mr(x)的系數(shù)為m對應的校驗比特62n-k級除法電路(系統(tǒng)碼形式)若信息序列m=(mk-1,mk-2,…m0)對應的多項式m(x)=mk-1xk-1+mk-2xk-2+…+m063n-k級除法電路(系統(tǒng)碼形式)綜上，循環(huán)碼的系統(tǒng)碼電路是信息多項式m(x)

乘xn-k,除g(x)的實現(xiàn)電路64輸入m(x)m0,m1,…mk-1-g1gn-k-1-g2-g0-gn-k-1-gn-k-2乘xn-k除g(x)運算電路門165k

級編碼器基本原理：利用校驗多項式h(x)為系統(tǒng)碼編碼電路66k

級編碼器若信息序列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)67k

級編碼器h(x)C(x)的乘積中，xn-1,xn-2,…

xk次的系數(shù)為零xn-1的系數(shù)h0

cn-1+h1

cn-1-1+…+hk

cn-1-k=0xn-2的系數(shù)h0

cn-2+h1

cn-2-1+…+hk

cn-2-k=0xn-3的系數(shù)h0

cn-3+h1

cn-3-1+…+hk

cn-3-k=0xk的系數(shù)h0

ck

+h1

ck-1+…+hk