講義51糾錯(cuò)編碼原理

1、信息論講義糾錯(cuò)編碼原理從這一章開(kāi)始介紹有噪聲信道編碼的問(wèn)題，有噪聲信道編碼的主要目的是提高傳輸可靠性，增加抗干擾能力，因此也稱(chēng)為糾錯(cuò)編碼或抗干擾編碼。在這一章里將首先介紹信道編碼定理和糾錯(cuò)編碼的基本原理。信源編碼之后的碼字序列抗干擾能力很脆弱，在信道噪聲的影響下容易產(chǎn)生差錯(cuò)，為了提高通信系統(tǒng)的有效性和可靠性，要在信源編碼器和信道之間加上一個(gè)信道編碼器，5-1 譯碼準(zhǔn)則5-1-1 譯碼準(zhǔn)則的含義(1) 一個(gè)例子影響通信系統(tǒng)可靠性的一個(gè)重要問(wèn)題是譯碼方式，可以通過(guò)一個(gè)例子看一下；有一個(gè)BSC信道，如圖所示。 0 1-p=1/4 0 p=3/4 p=3/4 1 1-p=1/4 1對(duì)于這樣一個(gè)信道，如

2、果采用自然的譯碼準(zhǔn)則，即收0判0，收1判1；這時(shí)可以明顯看到，當(dāng)信源先驗(yàn)概率的等概時(shí)p(0)=p(1)=1/2；這時(shí)收到Y(jié)判X的后驗(yàn)概率等于信道轉(zhuǎn)移概率，系統(tǒng)正確的譯碼概率為1/4，錯(cuò)誤譯碼概率為3/4。但如果采用另一種譯碼準(zhǔn)則，收0判1，收1判0；則系統(tǒng)正確的譯碼概率為3/4，錯(cuò)誤譯碼概率為1/4，通信的可靠性提高了。(2) 譯碼準(zhǔn)則設(shè)一個(gè)有噪聲離散信道，輸入符號(hào)集X，輸出符號(hào)集Y，信道轉(zhuǎn)移概率為P(Y/X);p(yj/xi) X Y xi yj X:x1,x2,.,xn Y:y1,y2,ym P(Y/X):p(yj/xi); i=1,2,n; j=1,2,m這時(shí)定義一個(gè)收到y(tǒng)j后判定為xi

3、的單值函數(shù)，即： F(yj)=xi (i=1,2,n; j=1,2,m)；這個(gè)函數(shù)稱(chēng)為譯碼函數(shù)。它構(gòu)成一個(gè)譯碼函數(shù)組，這些函數(shù)的值組成了譯碼準(zhǔn)則。對(duì)于有n個(gè)輸入，m個(gè)輸出的信道來(lái)說(shuō)，可以有nm個(gè)不同的譯碼準(zhǔn)則。例如上面例子中有4中譯碼準(zhǔn)則分別為：A:F(0)=0;F(1)=0 B:F(0)=0;F(1)=1C:F(0)=1;F(1)=0 D:F(0)=1;F(1)=15-1-2 譯碼錯(cuò)誤概率當(dāng)譯碼準(zhǔn)則確定之后，當(dāng)接收端收到一個(gè)yj后，則按譯碼準(zhǔn)則譯成F(yj)=xi，這時(shí)如果發(fā)送的為xi則為正確譯碼，如果發(fā)送的不是xi則為錯(cuò)誤譯碼。所以接收到y(tǒng)j后正確譯碼的概率就是接收端收到y(tǒng)j后，推測(cè)發(fā)送端

4、發(fā)出xi的后驗(yàn)概率：Prj=PF(yj)=xi/yj而錯(cuò)誤譯碼的概率為收到y(tǒng)j后，推測(cè)發(fā)出除了xi之外其它符號(hào)的概率：Pej=Pe/yj=1-PF(yj)=xi/yj其中e表示除了xi之外的所有其它信源符號(hào)的集合。然后對(duì)所有的yj取平均，則平均正確譯碼概率為：同樣可以得到平均錯(cuò)誤譯碼概率為： 這就是平均錯(cuò)誤譯碼概率的基本表達(dá)式，在通信系統(tǒng)設(shè)計(jì)和分析時(shí)，總是希望得到最可能小的平均錯(cuò)誤譯碼概率。因此所有通信系統(tǒng)都將平均譯碼錯(cuò)誤概率作為系統(tǒng)可靠性的一個(gè)重要指標(biāo)。5-1-3 最大后驗(yàn)概率準(zhǔn)則由平均錯(cuò)誤譯碼概率的表達(dá)式可以看出，錯(cuò)誤譯碼概率與信道輸出端隨機(jī)變量Y的概率分布p(yj)有關(guān)，也與譯碼準(zhǔn)則有關(guān)

5、。當(dāng)信道信道轉(zhuǎn)移概率p(yj/xi)確定后，而且信源統(tǒng)計(jì)特性p(xi)確定之后，信道輸出端的p(yj)也就確定了。因?yàn)椋簆(xi,yj)=p(xi)p(yj/xi); 而p(yj)可以由p(xi,yj)的(i=1,2, n)求和得到。因此，在這種情況下，平均錯(cuò)誤譯碼概率只與譯碼準(zhǔn)則有關(guān)了。通過(guò)選擇譯碼準(zhǔn)則可以使平均譯碼概率達(dá)到最小值。當(dāng)式中的每一項(xiàng)的PF(yj)=xi/yj達(dá)到最大值時(shí)，平均錯(cuò)誤譯碼概率就可以為最小值。設(shè)信源X的信源空間為：X,P:X:x1x2xnP(X):p(x1)p(x2)p(xn)信道的轉(zhuǎn)移矩陣為：y1y2ymP=x1p(y1/x1)p(y2/x1)p(ym/x1)x2p

6、(y1/x2)p(y2/x2)p(ym/x2)xnp(y1/xn)p(y2/xn)p(ym/xn)收到每一個(gè)yj(j=1,2,m)后，推測(cè)發(fā)送為xi(i=1,2,n)的后驗(yàn)概率共有n個(gè)，為：p(x1/yj),p(x2/yj),p(xn/yj)。這其中必有一個(gè)為最大的，設(shè)其為：p(x*/yj)，即有：p(x*/yj)p(xi/yj) (對(duì)一切的i)這表明：收到符號(hào)yj后就譯為輸入符號(hào)x*，即譯碼函數(shù)選為：F(yj)=a* (j=1,2,m)這種譯碼準(zhǔn)則稱(chēng)為“最大后驗(yàn)概率準(zhǔn)則”。利用這種準(zhǔn)則就可以使平均譯碼錯(cuò)誤概率公式中的s項(xiàng)求和的每一項(xiàng)：1-PF(yj) = xi/yj達(dá)到最小值1-F(yj)=

7、x*/yj。這時(shí)的平均錯(cuò)誤譯碼概率的最小值為：這個(gè)表達(dá)式平均錯(cuò)誤譯碼概率的最小值，是把每一個(gè)yj對(duì)應(yīng)的后驗(yàn)概率排除后再連續(xù)求和。§ 從表達(dá)式中可以看到，這個(gè)最小值與信源先驗(yàn)概率和信道轉(zhuǎn)移概率有關(guān)，特別是信道轉(zhuǎn)移概率，如果除了p(yj/x*)外，其它的項(xiàng)多很小，錯(cuò)誤譯碼概率會(huì)減小。5-1-4 最大似然準(zhǔn)則使用最大后驗(yàn)概率譯碼準(zhǔn)則必須已知后驗(yàn)概率，但信道的統(tǒng)計(jì)特性描述總是給出信道轉(zhuǎn)移概率，因此利用信道轉(zhuǎn)移概率的譯碼準(zhǔn)則。由概率中的貝葉斯定理可有： 這樣，根據(jù)最大后驗(yàn)概率譯碼準(zhǔn)則，如果 p(x*)p(yj/x*)p(xi)p(yj/xi) (i=1,2,n)就等于：p(x*/yj)p(xi

8、/yj)則選擇譯碼準(zhǔn)則：F(yj)=x* (j=1,2,n)這樣，可以看到當(dāng)信道輸入符號(hào)集X的先驗(yàn)概率為等概時(shí)p(xi)=1/n，比較上面三個(gè)式子，最大后驗(yàn)概率可以用最大信道轉(zhuǎn)移概率來(lái)取代。這時(shí)，在X的先驗(yàn)概率為等概時(shí)，如果p(yj/x*)是yj相應(yīng)的n個(gè)信道轉(zhuǎn)移概率 p(yj/x1),p(yj/x2),p(yj/xn)中的最大者，則我們就將yj譯成x*，這種譯碼方法稱(chēng)為“最大似然譯碼準(zhǔn)則”。最大似然譯碼準(zhǔn)則利用了信道轉(zhuǎn)移概率，而不用后驗(yàn)概率，將會(huì)更方便。這時(shí)的最小平均錯(cuò)誤譯碼概率為：將信道轉(zhuǎn)移矩陣P中每一列中的最大元素去掉，然后將其它元素相加后除以n。§ 為了減小錯(cuò)誤譯碼概率，主要

9、方法是改變信道轉(zhuǎn)移概率，5-2 信道編碼基本概念5-2-1 信道編碼定理定理：有噪聲信道編碼定理（Shannon第二編碼定理）如一個(gè)離散有噪聲信道有n個(gè)輸入符號(hào)，m個(gè)輸出符號(hào)，信道容量為C。當(dāng)信道的熵速率RC時(shí)，只要碼長(zhǎng)足夠長(zhǎng)，總可以找到一種編碼方法及譯碼準(zhǔn)則，使信道輸出端的平均錯(cuò)誤譯碼概率達(dá)到任意小，pe=。當(dāng)R>C時(shí)，則不可能找到一種編碼方法及譯碼準(zhǔn)則，使信道輸出端的平均錯(cuò)誤譯碼概率達(dá)到任意小。§ 編碼定理的證明比較復(fù)雜，用超球空間幾何方法。§ 這個(gè)定理是一個(gè)存在定理，指出錯(cuò)誤率趨于0的編碼方法是存在的。§ 定理表明，在錯(cuò)誤率趨于0的同時(shí)，還可以使R趨于

10、C，這是具有理論指導(dǎo)意義的。§ 這個(gè)定理的證明思想為：以二元編碼為例：5-2-2 信道編碼的基本概念（分組碼）(1) 碼字空間：如果原始信源空間有M個(gè)碼字，對(duì)其進(jìn)行q元等長(zhǎng)碼的信道編碼，碼長(zhǎng)為N，信道碼字空間的所有碼字為qN個(gè)，編碼器將在這qN個(gè)可用碼字中選擇M個(gè)碼字分別代表原始信源中的M個(gè)碼字，信道編碼碼字空間的這M個(gè)碼字稱(chēng)為“許用碼字”，而另外的qN-M個(gè)碼字稱(chēng)為“禁用碼字”。為了實(shí)現(xiàn)糾錯(cuò)編碼，一定有qN>M。這M個(gè)許用碼字也稱(chēng)為一個(gè)碼組，或稱(chēng)為碼字集合。(2) 漢明距離：(Hamming distance)在一個(gè)碼組（碼字集合）中，任意兩個(gè)等長(zhǎng)碼字之間，如果有d個(gè)相對(duì)應(yīng)的

11、碼元不同，則稱(chēng)d為這兩個(gè)碼字的漢明距離。例如：和為碼組X中的兩個(gè)不同碼字，X為一個(gè)長(zhǎng)度為N的二元碼組，其中：=a1,a2,aN ai0,1=b1,b2,bN bi0,1則與的漢明距離為： d=0表明為全同碼，d=N表明為全異碼，如果用模2加法的概念，有 (3) 最小碼距：在一個(gè)碼字集合中，任何兩個(gè)碼字之間的漢明距離組成一個(gè)元素集合，D(,),這個(gè)集合中的最小值稱(chēng)為這個(gè)碼字集合的最小漢明距離，簡(jiǎn)稱(chēng)最小碼距，記為：dmin。dmin=mind(,) ,X 例如：(4) 碼字重量（漢明重量）(Hamming weight)在二元編碼的碼字集合中，碼字中“1”碼元的個(gè)數(shù)稱(chēng)為這個(gè)碼字的重量。記為：W()

12、。利用碼字重量的概念，漢明距離可以表示為：d(,)=W()(5) 分組碼最小碼距與糾檢錯(cuò)能力的關(guān)系：一個(gè)分組碼的最小碼距為dmin，則其糾檢錯(cuò)能力為：若發(fā)現(xiàn)e個(gè)錯(cuò)誤，則要求dmine+1;若糾正t個(gè)錯(cuò)誤，則要求dmin2t+1;若糾正t個(gè)錯(cuò)誤，同時(shí)發(fā)現(xiàn)e個(gè)錯(cuò)誤，則要求dmint+e+1; t<e;例如：dmin=1; 無(wú)糾檢錯(cuò)能力； dmin=2; 檢一位錯(cuò)dmin=3; 糾一位錯(cuò)（或檢兩位錯(cuò)）dmin=4; 糾一位，同時(shí)檢兩位；dmin=5; 糾二位錯(cuò)（或檢4位錯(cuò)）dmin=6; 糾二位，同時(shí)檢3位；(t=2,e=3)dmin=7; 糾三位錯(cuò)（或檢兩位錯(cuò)）dmin=8; 糾三位，同時(shí)檢

13、4位；(t=3,e=4 0 1 2 3 t=1 1 2 e=2 dmin=35-2-3 信道編碼方法§ 糾錯(cuò)編碼：根據(jù)一定的糾檢錯(cuò)要求，對(duì)原始碼字進(jìn)行某種變換，使其具有具有糾檢錯(cuò)能力，這種變換稱(chēng)為抗干擾編碼。§ 實(shí)現(xiàn)方法：信息位+監(jiān)督位=糾檢錯(cuò)編碼。§ 信道編碼的分類(lèi)：糾錯(cuò)碼/檢錯(cuò)碼前向糾錯(cuò)方式(FEC-forward error correction)反饋重傳方式(ARQ-automatic repeat request)混合糾錯(cuò)方式(HEC-hybrid error correction)在FEC中又可分為：分組碼(block code/group code)

14、卷積碼(convolutional code)在分組碼中常見(jiàn)的碼包括：Hamming CodeCyclic CodeBCH CodeGolay CodeReed-Solommon CodeReed-Muller Code5-3 簡(jiǎn)單的信道編碼檢錯(cuò)碼一般具有較少的監(jiān)督位，冗余度較小，只能檢出錯(cuò)誤，但不能糾正錯(cuò)誤。5-3-1 奇偶校驗(yàn)碼(Parity Check Code)也稱(chēng)為一致監(jiān)督檢錯(cuò)碼，是一種檢錯(cuò)分組碼。(1) 檢錯(cuò)原理：當(dāng)信息碼字位二元序列，碼字長(zhǎng)度位k，共有2k個(gè)碼字，可以在信息碼字后面加上一位監(jiān)督元，構(gòu)成長(zhǎng)度位n=k+1的檢錯(cuò)碼，X=x1,x2,xk,xk+1= x1,x2,xn對(duì)于

15、偶校驗(yàn)碼：監(jiān)督元為對(duì)于奇校驗(yàn)碼，監(jiān)督元為：§ 偶校驗(yàn)碼中有偶數(shù)個(gè)1，奇校驗(yàn)碼中有奇數(shù)個(gè)1；§ 奇偶校驗(yàn)碼的最小碼距為dmin=2 ;可檢一位錯(cuò)；§ 可用碼字=2n；許用碼字=2k，禁用碼字=2n-2k(2) 漏檢概率檢錯(cuò)碼不能發(fā)現(xiàn)錯(cuò)誤碼字的概率稱(chēng)為漏檢概率。奇偶校驗(yàn)碼不能發(fā)現(xiàn)偶數(shù)個(gè)碼元錯(cuò)誤，根據(jù)最小碼距分析至少檢一位錯(cuò)，實(shí)際上可以檢出所有奇數(shù)個(gè)錯(cuò)。假設(shè)信道誤碼率為pe，碼字漏檢概率為Pu，有： n為偶數(shù)； n為奇數(shù)；其中n為碼字長(zhǎng)度，有：當(dāng)信道誤碼率很小時(shí)，pe<<1; Pu=Cn2pe2。漏檢概率不僅與信道誤碼率有關(guān)，而且還與碼字長(zhǎng)度有關(guān)，實(shí)際上它是

16、一個(gè)誤字率的概念，應(yīng)當(dāng)配合ARQ系統(tǒng)使用，可以看到系統(tǒng)可靠性是很高的。(3) 編碼效率：； 實(shí)際上可知：編碼效率與信道傳輸效率是同一個(gè)概念：認(rèn)為信源符號(hào)為等概率條件。根據(jù)奇偶校驗(yàn)碼的原理，還有一些改進(jìn)方法：水平奇偶校驗(yàn)碼，垂直奇偶校驗(yàn)碼，群計(jì)數(shù)碼等，5-3-2 定比碼（等重碼，范德倫碼）(1) 五三定比碼與七三定比碼定比碼為一種簡(jiǎn)單檢錯(cuò)碼。五三定比碼（五單位碼）用于國(guó)內(nèi)電報(bào)系統(tǒng)，碼長(zhǎng)為5，其中1的個(gè)數(shù)為3。這種碼的許用碼字為：代表國(guó)內(nèi)電報(bào)系統(tǒng)中的數(shù)字09。七三定比碼（七單位碼）用于國(guó)際電報(bào)系統(tǒng)，碼長(zhǎng)為7，其中1的個(gè)數(shù)為3。這種碼的許用碼字為：代表26個(gè)英文字母和一些符號(hào)。(2) 漏檢概率：五三

17、定比碼和七三定比碼的dmin=2，至少可以檢一位錯(cuò)，實(shí)際上定比碼可以檢出所有奇數(shù)位錯(cuò)碼，及一些偶數(shù)位錯(cuò)碼。定比碼的漏檢為：偶數(shù)位錯(cuò)誤，且一半1錯(cuò)為0，一半0錯(cuò)為1；Pu=P2+P4+P2=P10.P01=C31pe(1-pe)3-1.C21pe(1-pe)2-1P4=C22C32pe4(1-pe)5-4(3) 編碼效率：5-3-3 重復(fù)碼檢錯(cuò)碼只能發(fā)現(xiàn)錯(cuò)誤，必須利用ARQ系統(tǒng)才能實(shí)現(xiàn)抗干擾，它要求有反向信道，而前向糾錯(cuò)碼的最大優(yōu)點(diǎn)就是不需要反向信道，并且實(shí)時(shí)性高。重復(fù)碼是一種最簡(jiǎn)單的糾錯(cuò)碼。在實(shí)際系統(tǒng)重有較廣泛的應(yīng)用。(1) 一個(gè)例子：一個(gè)BSC信道，輸入為X=0，1，且為等概分布，信道模型為

18、：0 p=1-pe=0.99 0 pe=0.01 pe=0.011 p=1-pe=0.99 1按最大似然譯碼準(zhǔn)則為：F(0)=0; F(1)=1;在信道誤碼率為pe=10-2條件下，其錯(cuò)誤譯碼概率為：Pemin=(1/n)(pe+pe)=(1/2)(0.01+0.01)=10-2可以看到這時(shí)系統(tǒng)誤碼率就等于信道誤碼率，這里沒(méi)有采用任何信道編碼。(2) 編譯碼方法重復(fù)碼的編碼方法為，將0編為000，1編為111。這時(shí)的可用碼字為23=8；分別為：X1=000 X2=001 X3=010 X4=100X5=011 X6=110 X7=101 X8=111而許用碼字為000和111，相當(dāng)于信道輸入為

19、X1=000，X2=111，而信道輸出端為：Y1=000；Y2=001；Y3=010；Y4=100Y5=011；Y6=110；Y7=101；Y8=111這時(shí)的信道轉(zhuǎn)移矩陣為：P=Y1Y2Y3Y4Y5Y6Y7Y8X1p13p12pp12pp12pp1p2p1p2p1p2p3X2p3p1p2p1p2p1p2p12pp12pp12pp13這時(shí)如果按最大似然法則譯碼，將為：F(Y1)=F(Y2)=F(Y3)=F(Y4)=X1=000F(Y5)=F(Y6)=F(Y7)=F(Y8)=X2=111錯(cuò)誤譯碼概率為：Pemin=(1/2) p3+ p2p1+ p2p1+ p2p1+ p2p1+ p2p1+ p2

20、p1+ p3= 3p2p1+ p3 3×10-4可見(jiàn)簡(jiǎn)單重復(fù)碼可以將錯(cuò)誤譯碼概率下降兩個(gè)數(shù)量級(jí)。這是三次重傳大數(shù)判別的方法；可以看出如果是五次重復(fù)碼，誤碼率還要降低。注：從這里的譯碼方法可以看到：最大似然譯碼準(zhǔn)則實(shí)際上是一種最小漢明距離的譯碼準(zhǔn)則。為了判別比較，一般重復(fù)碼都采用奇數(shù)次重復(fù)，然后按大數(shù)判決。(3) 編碼效率三次重復(fù)碼的編碼效率為：相當(dāng)于k=1,n=3 ; =k/n=1/3;同樣可知：五次重復(fù)碼=k/n=1/5;5-4 代數(shù)引論為了進(jìn)一步學(xué)習(xí)糾錯(cuò)編碼的原理和分析其性能，在這一節(jié)中我們復(fù)習(xí)一些有關(guān)的代數(shù)知識(shí)。5-4-1 群(Group)群的定義：如果一個(gè)元素集合G，在其中定

21、義一種運(yùn)算“*”，并滿(mǎn)足下列條件則稱(chēng)為一個(gè)群(Group)。a,b,c,e,a-1G。§ 自閉性，c=a*b§ 結(jié)合律，a*(b*c)=(a*b)*c§ 單位元（恒元），a*e=e*a=a§ 逆元 a*a-1=a-1*a=e如果還滿(mǎn)足交換律，a*b=b*a, 則稱(chēng)為交換群。定理1：群G中的單位元是唯一的。定理2：群G中任一元素的逆元是唯一的。有限群：群中元素的個(gè)數(shù)稱(chēng)為元素的階，有限元素的群稱(chēng)為有限群。（m階有限群）模運(yùn)算：G=0，1為一個(gè)模2加法群，0+0=0，0+1=1，1+0=1，1+1=0 0是單位元，本身是逆元，滿(mǎn)足結(jié)合律，交換律和自閉性，為一個(gè)

22、加法交換群。當(dāng)p為一個(gè)素?cái)?shù)，則集合G=1,2,p-1在模p乘法下為一個(gè)群。例如p=5,G=1,2,3,4為一個(gè)乘法群，*123411234224133314244321§ 全體實(shí)數(shù)集合為一個(gè)普通加法的交換群；§ 全體非零實(shí)數(shù)集合為一個(gè)普通乘法的交換群；子群：如果集合G在某種運(yùn)算*下為一個(gè)群，集合H為G中的一個(gè)非空子集。若H在運(yùn)算*下也滿(mǎn)足自閉性，結(jié)合律，單位元和逆元，則稱(chēng)H為G的一個(gè)子群。§ 偶數(shù)集合H:2n為整數(shù)加法群的一個(gè)子群。定理：如果集合G在運(yùn)算*下為一個(gè)群，H為一個(gè)子群，則G中的所有元素都可以由子群H中的元素表示。單位元：如果H為G的一個(gè)子群，則G中唯一

23、的單位元一定在H中。分元陪集：利用子群和陪集，可以用子群H的元素表示所有G中的元素。例：設(shè)G是整數(shù)集合，在普通加法+下為一個(gè)交換群，而H為G的一個(gè)子群，它由整數(shù)m的倍數(shù)構(gòu)成，那么，所有正整數(shù)均可用H中的元素表示，且劃分為子群H的若干個(gè)陪集。H:nm; n=0,±1,±2,。例如m=3,則子群H的元素為： H:0, ±3, ±6, ±9, ±12, ±15, ±18,利用分元陪集的方法，用H的元素表示G中的所有元素。§ 將子群H中的元素放在表的第一行，且單位元0放在首位，稱(chēng)為陪集首。§ 將H中沒(méi)有

24、的，但G中的元素1作為陪集首，放在表的第二行的首位，將陪集首分別與第一行的元素做加法運(yùn)算，組成的二個(gè)陪集。§ 將第一行，第二行中沒(méi)有的，但在群中有的元素2作為第二個(gè)陪集的陪集首，構(gòu)成第三個(gè)陪集。§ 這樣，利用分元陪集的方法，可以構(gòu)成所有G中的元素。陪集103-36-69-9陪集21+0=11+3=4-27-510-8陪集32+0=22+3=5-18-411-75-4-2 域(Field)域的定義：如果一個(gè)元素集合F，在其中定義加法和乘法兩種運(yùn)算，并滿(mǎn)足下列條件則稱(chēng)為一個(gè)域(Feild)。a,b,c,d,e,a-1G。§ 在加法下為一個(gè)交換群，滿(mǎn)足自閉性，交換律，結(jié)

25、合律，單位元為0，逆元。§ 在乘法下為一個(gè)交換群，滿(mǎn)足非零元素自閉性，交換律，結(jié)合律，單位元，逆元。§ 在加法乘法下滿(mǎn)足分配律，有限域：域中的元素個(gè)數(shù)m稱(chēng)為域的階，有限個(gè)元素的域稱(chēng)為有限域或叫作伽羅華域，記為GF(m)，GF-Galois Field，最小域：一個(gè)域中最少包含加法單位元和乘法單位元兩個(gè)元素，否則不能構(gòu)成域。例如：集合0,1在模二加法和乘法下構(gòu)成一個(gè)二元有限域GF(2)。素域：如果p為一個(gè)素?cái)?shù)，則正整數(shù)集合0,1,2,p-1，在模p加法和乘法下為一個(gè)階數(shù)為p的域，稱(chēng)為素域，記為GF(p)。GF(2)為一個(gè)素域。例如：GF(7)為一個(gè)素域，其運(yùn)算如下：模7加法模

26、7乘法+0123456.01234560012345600000000112345601012345622345601202461353345601230362514445601234041526355601234505316426601234560654321擴(kuò)展域：對(duì)于任何一個(gè)正整數(shù)m，可以將素域GF(p)擴(kuò)展成有pm個(gè)元素的域，稱(chēng)為域GF(p)的擴(kuò)展域，記為：GF(pm)。而且可以證明：任何有限域都是一個(gè)素域的擴(kuò)展域。有限域的特征：由于有限域GF(q)在加法下是自閉的，因此，考慮其乘法單位元1的加法運(yùn)算，1，1+1，1+1+1，, 1+1+1+1+1+.+1(k個(gè))，這些都是GF(q)中

27、的元素，而域中的元素是有限個(gè)，因此必然存在兩個(gè)正整數(shù)m,n, m<n，使：或者說(shuō)：必然存在一個(gè)最小的正整數(shù)=n-m，我們稱(chēng)為域GF(q)的特征。§ 二元域GF(2)的特征=2；§ 素域GF(p)的特征=p；§ 有限域的特征是一個(gè)素?cái)?shù)；循環(huán)群：如果一個(gè)群存在一個(gè)元素，其各次冪構(gòu)成整個(gè)群，稱(chēng)為循環(huán)群。定理：有限域GF(q)的非零元素構(gòu)成一個(gè)循環(huán)群。設(shè)a是GF(q)中的一個(gè)非零元素，由于GF(q)的非零元素在乘法下為自閉的，所以a，a2，a3，也必然是GF(q)中的非零元素，又因?yàn)镚F(q)為有限元素，所以必然有一個(gè)最小的正整數(shù)n，使an=1。這個(gè)正整數(shù)n稱(chēng)為元素

28、a的階。§ 令a為有限域GF(q)的非零元素，則aq-1=1。§ 令a為有限域GF(q)的非零元素，且n為a的階，則q-1一定能被n除盡。本原元：如果有限域GF(q)中，非零元素a的階n=q-1，就稱(chēng)a為GF(q)的本原元素。§ 本原元素的各次冪構(gòu)成有限域FG(q)的所有元素。§ 每個(gè)有限域都有其本原元素。例如：有限域GF(7)，域中元素為0,1,2,3,4,5,6，其非零元素集合為1,2,3,4,5,6，考慮其中的非零元素a=3，可知：31=3，32=3·3=2，33=32·3=6，34=33·3=4，35=5，36=1

29、，可以看到3的各次冪構(gòu)成了GF(7)中所有非零元素，所以3的階n=q-1=6，3為GF(7)的本原元。如果取a=4，可知：41=4，42=2，43=1，即元素4的階為n=3，并且3可以除盡q-1=6。5-4-3 域上多項(xiàng)式在編碼理論上大多采用二元有限域GF(2)的多項(xiàng)式，因此我們重點(diǎn)介紹這部分的知識(shí)。域上多項(xiàng)式：如果多項(xiàng)式f(x)=f0+f1x+f2x2+fnxn的系數(shù)取自二元有限域GF(2)，則稱(chēng)f(x)為域FG(2)上的多項(xiàng)式。fi=0或fi=1;域上多項(xiàng)式計(jì)算：加法：如果f(x)=f0+f1x+f2x2+fnxn; g(x)=g0+g1x+g2x2+gnxn 則：f(x)+g(x)= (

30、f0+ g0)+(f1 +g1)x +(f2 +g2)x2+(fn+gn)xn乘法：如果f(x)=f0+f1x+f2x2+fnxn; g(x)=g0+g1x+g2x2+gmxm 則：f(x)g(x)=c(x)=c0+c1x+c2x2+cn+mxn+m;c0=f0g0c1=f0g1+f1g0cn+m=fngm除法：如果f(x)=1+x+x4+x5+x6; g(x)=1+x+x3;則f(x)/g(x)的結(jié)果可以寫(xiě)作： 其中：q(x)=x3+x2; r(x)=x2+x+1;利用展轉(zhuǎn)相除法（歐幾里得除法）x3+x2 x3+x+1x6+x5+x4 +x+1x6 +x4+x3 x5+ x3 +x+1 x5

31、 +x3+x2 x2+x+1如果r(x)=0，即f(x)能被g(x)除盡，則稱(chēng)g(x)為f(x)的因式；f(x)為g(x)的倍式。多項(xiàng)式的模運(yùn)算：如果GF(2)上多項(xiàng)式，F(xiàn)(x),N(x),Q(x),R(x)滿(mǎn)足：則稱(chēng)在模N(x)條件下，F(xiàn)(x)=R(x)。不可約多項(xiàng)式：如果f(x)為GF(2)上的m次多項(xiàng)式，它不能被任何次數(shù)小于m，大于0的多項(xiàng)式除盡，則稱(chēng)其為GF(2)上的不可約多項(xiàng)式，既約多項(xiàng)式。f(x)=x3+x+1; f(x)=x4+x+1;均為不可約多項(xiàng)式。§ GF(2)上的多項(xiàng)式若有偶數(shù)項(xiàng)，則一定可被x+1除盡。§ 對(duì)于任意m1,都存在m次不可約多項(xiàng)式。

32、7; GF(2)上的任意m次不可約多項(xiàng)式，一定能除盡xn+1，其中n=2m-1。例如：x3+x+1,可以除盡x7+1。本原多項(xiàng)式：如果n=2m-1，f(x)為GF(2)上的m次不可約多項(xiàng)式，且f(x)可除盡xn+1，則稱(chēng)f(x)為本原多項(xiàng)式。§ 不可約多項(xiàng)式不一定是本原多項(xiàng)式，本原多項(xiàng)式一定為不可約的。§ m次本原多項(xiàng)式是不唯一的。性質(zhì)：對(duì)于GF(2)上的多項(xiàng)式f(x)，有f(x)2=f(x2)。5-4-4 GF(2)上的矢量空間域上矢量空間：令V是一個(gè)矢量集合，在其上定義一個(gè)加法運(yùn)算。令F是一個(gè)域，在域中的元素和V中的元素之間定義了一個(gè)乘法運(yùn)算。如果集合V滿(mǎn)足下例條件，稱(chēng)

33、其為域F上的矢量空間（線性空間）。§ V是加法可交換群；§ F中的任意元素a和V中的元素Vi的乘積，aVi是V中的元素；§ 滿(mǎn)足分配律：a,bF; Vi,VjV; a(Vi+Vj)=aVi+aVj; (a+b) Vi=aVi+bVi;§ 滿(mǎn)足結(jié)合律：(ab) Vi=a(bVi);§ F中的單位元為1，1Vi=Vi。V中的單位元為0矢量。域上矢量空間的性質(zhì)：§ 0為F上的零元，則0Vi=0;§ c為F上的任意標(biāo)量，則c0=0;§ c為F上的任意標(biāo)量和V中的任意矢量Vi，(-c) Vi=c(-Vi)=-(cVi);GF

34、(2)上的矢量空間：一個(gè)有n個(gè)分量的序列；(a0,a1,an-1)其中每個(gè)分量是二元域上的元素(ai=0,1)，這個(gè)序列稱(chēng)為GF(2)上的n-重。GF(2)上共有2n個(gè)n-重。令Vn表示這2n個(gè)n-重的集合，則可以證明Vn是GF(2)上的一個(gè)矢量空間。例如：n=5, GF(2)上的5-重矢量空間V5由32個(gè)矢量組成。(00000),(00001),(11111)。這個(gè)空間中任意兩個(gè)矢量之和仍然是這個(gè)空間中的矢量。GF(2)中的元素0，1乘上空間中的任意矢量仍然是這個(gè)空間中的矢量。V的子空間：如果V是F上的矢量空間，V的一個(gè)子集也是F上的一個(gè)矢量空間，則稱(chēng)S為V的一個(gè)子空間。例如：V5上的子集，(00000),(00111),(11010),(11101)為一個(gè)子空間。線性組合：令V1,V2,Vk是F上矢量空間V中的k個(gè)矢量。令a1,a2ak是F中的k個(gè)標(biāo)量。則: a1V1+a2V2+akVk稱(chēng)為的線性組合。如果：除非a1=a2=ak=0,否則a1V1+a2V2+akVk0