《信息論與編碼》PPT課件(I)

《《信息論與編碼》PPT課件(I)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第八章循環(huán)碼第八章循環(huán)碼內(nèi)容提要循環(huán)碼是線性分組碼中一個(gè)重要的子類。本章首先介紹抽象代數(shù)中與循環(huán)碼直接相關(guān)的基礎(chǔ)知識(shí)，主要包括有限域的概念、有限域的本原元及有限域的結(jié)構(gòu)；然后提出循環(huán)碼的定義以及循環(huán)碼的多項(xiàng)式描述方法，給出生成多項(xiàng)式和校驗(yàn)多項(xiàng)式的定義，論述了循環(huán)碼構(gòu)成的有關(guān)重要定理；接著討論循環(huán)碼的編譯碼方法及其實(shí)現(xiàn)電路；最后介紹已獲得廣泛應(yīng)用的循環(huán)漢明碼、BCH碼等。8.1有限域及其結(jié)構(gòu)8.1.1域的定義1．多項(xiàng)式幾個(gè)有關(guān)概念：（1）多項(xiàng)式：；（2）系數(shù)：fi∈K（集合）i=1,?2,?…,n；

2、（3）首一多項(xiàng)式：若多項(xiàng)式最高冪次項(xiàng)的系數(shù)fn=1，稱該多項(xiàng)式為首一多項(xiàng)式；（4）多項(xiàng)式f(x)的階次n記為??f(x)=n；（5）多項(xiàng)式因式分解：將多項(xiàng)式分解為若干個(gè)因式相乘，這種分解是唯一的；（6）即約多項(xiàng)式：階大于0且在給定集合K上除了常數(shù)和本身的乘積外，不能被其他多項(xiàng)式除盡的多項(xiàng)式。2．有關(guān)多項(xiàng)式的一些運(yùn)算（1）多項(xiàng)式帶余除法若p(x)不能整除a(x)，商Q(x)，余r(x)，記為：a(x)=Q(x)p(x)+r(x)??r(x)

3、(x)被p(x)所除，余數(shù)記為r(x)，稱為a(x)的模p(x)運(yùn)算，就稱為對(duì)多項(xiàng)式a(x)進(jìn)行模p(x)運(yùn)算的剩余類集合?！纠?.2】對(duì)系數(shù)取自K={0,1}的任意多項(xiàng)式a(x)進(jìn)行模p(x)=x3+x+1運(yùn)算，設(shè)所得余式為r(x)，因?yàn)?，則0≤??r(x)<3，因此剩余類集合就是所有階次小于3的多項(xiàng)式集合={0,1,x,x+1,x2,x2+1,x2+x,x2+x+1}。定義8.1域是一些元素的集合，在這些元素中定義了加法和乘法兩種運(yùn)算，且滿足如下11條性質(zhì)：（1）對(duì)加法它是一個(gè)交換群（滿足5條

4、性質(zhì)：封閉性、結(jié)合律、交換律、存在幺元、存在逆元）；（2）對(duì)乘法它也是一個(gè)交換群（滿足5條性質(zhì)：封閉性、結(jié)合律、交換律、存在幺元、存在逆元（除去0元素））；（3）對(duì)加法、乘法滿足分配律：a(b+c)=ab+ac，(a+b)c=ac+bc。1．整數(shù)在帶余運(yùn)算條件下構(gòu)成一個(gè)有限域必要條件：模d運(yùn)算，d必是一個(gè)素?cái)?shù)。2．多項(xiàng)式在余式運(yùn)算條件下構(gòu)成一個(gè)有限域多項(xiàng)式集合F[a(x)]被p(x)除所得的余式記為，則剩余類集合構(gòu)成一個(gè)域的充要條件是p(x)為即約多項(xiàng)式。若??p(x)=m，則是所有階次低于m的多

5、項(xiàng)式集合?！纠?.5】根據(jù)域的定義，判斷例8.2中的剩余類集合是否為有限域？（1）在中定義加法、乘法二種運(yùn)算，滿足結(jié)合律、交換律、分配律；（2）元素0為加法幺元，元素1為乘法幺元；（3）通過表8-5和表8-6可以看出對(duì)于加法、乘法運(yùn)算都滿足封閉性，且都存在逆元。因此是一個(gè)有限域?qū)⒑営洖閞(x)+01xx+1x2x2+1x2+xx2+x+1001xx+1x2x2+1x2+xx2+x+1110x+1xx2+1x2x2+x+1x2+xxxx+101x2+xx2+x+1x2x2+1x+1x+1x10x2+

6、x+1x2+xx2+1x2x2x2x2+1x2+xx2+x+101xx+1x2+1x2+1x2x2+x+1x2+x10x+1xx2+xx2+xx2+x+1x2x2+1xx+101x2+x+1x2+x+1x2+xx2+1x2x+1x10表8-5模p(x)=x3+x+1的加法表×1xx+1x2x2+1x2+xx2+x+111xx+1x2x2+1x2+xx2+x+1xxx2x2+xx+1１x2+x+1x2+1x+1x+1x2+xx2+1x2+x+1x21xx2x2x+1x2+x+1x2+xxx2+11x

7、2+1x2+11x2xx2+x+1x+1x2+xx2+xx2+xx2+x+11x2+1x+1xx2x2+x+1x2+x+1x2+1x1x2+xx2x+1表8-6模p(x)=x3+x+1的乘法表在上例中8.1.2有限域的本原元定義8.2在有限域GF(q)中，若某一元素的階為q=1，則稱此元素為本原元，記為α，即．則GF(q)中的其他所有非零元素都可寫成α的方冪。以本原元為根的即約多項(xiàng)式稱為本原多項(xiàng)式?！纠?.7】基域GF(2)={0,1}，擴(kuò)展域，生成多項(xiàng)，α是p(x)的根，即是所有階次小于3的多項(xiàng)

8、式集合，共有8個(gè)元素：將中的8個(gè)元素分別用剩余類、α的方冪、的線性組合及二進(jìn)制三維矢量表示列于表8-7中。剩余類方冪表示的線性組合二進(jìn)制三維矢量000000111001xαα010x2α2α2100x2+1α3α2+1101x2+x+1α4α2+α+1111x+1α6α+1011x2+xα6α2+α110表8-7GF(23)中元素的四種表示方法加法運(yùn)算宜采用線性組合表示，乘法運(yùn)算宜采用冪級(jí)數(shù)表示。8.1.3有限域的結(jié)構(gòu)定義8.3滿足pe=0的最小整數(shù)p稱為域的特征，其中e為乘法幺元