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

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

2、判 1；這時(shí)可以明顯看到， 當(dāng)信源先驗(yàn)概率的等概時(shí) p(0)=p(1)=1/2 ；這時(shí)收到 Y 判 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)YyjXxiX:x 1,x2, .,xnY:y 1,y2, ymP(Y/X):p(yj/xi); i=1,2,j=1,2n,; m這時(shí)定義一個(gè)收到 yj 后判定

3、為 xi 的單值函數(shù)， 即： F(yj)=xi (i=1,2, n; j=1,2, ；m) 這個(gè)函數(shù)稱為譯碼函數(shù)。它構(gòu)成一個(gè)譯碼函數(shù)組，這些函數(shù)的值組成了譯碼準(zhǔn)則。對(duì)于有 n 個(gè)輸入， m 個(gè)輸出的信道來說，可以有 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è) 發(fā)送的為 xi 則為正確譯碼， 如果發(fā)送的不是 概率就是接收端收到 yj 后，推測(cè)發(fā)送端發(fā)出yj 后，則按譯碼準(zhǔn)則譯成 F(yj)=

4、xi ，這時(shí)如果 xi 則為錯(cuò)誤譯碼。 所以接收到 yj 后正確譯碼的 xi 的后驗(yàn)概率：Prj=PF(yj)=xi/yj而錯(cuò)誤譯碼的概率為收到 yj 后，推測(cè)發(fā)出除了 xi 之外其它符號(hào)的概率：5-1信息論講義Pej=Pe/y j=1-PF(y j)=xi/yj其中 e 表示除了 xi 之外的所有其它信源符號(hào)的集合。 然后對(duì)所有的 yj 取平均，則平均正確譯碼概率為：mmPrP(yj)Prjp(yj) pF(yj) xi /yjj 1 j1同樣可以得到平均錯(cuò)誤譯碼概率為：mmPep(yj)Pe/ yjp(yj)1 PF(yj) xi/ yjj1 j 1這就是平均錯(cuò)誤譯碼概率的基本表達(dá)式， 在

5、通信系統(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)。當(dāng)信道信道轉(zhuǎn)移概率p(yj/xi) 確定后，而且信源統(tǒng)計(jì)特性 p(xi)確定之后，信道輸出端的 p(yj) 也就確定了。因?yàn)椋?p(xi,yj)=p(xi)p(yj/xi); 而 p(yj) 可以由 p(xi,yj) 的 (i=1,2, n)求和得到。因此， 在這種情況下， 平均錯(cuò)誤譯碼概率只與譯碼準(zhǔn)則有關(guān)了。

6、 通過選擇譯碼準(zhǔn)則可以 使平均譯碼概率達(dá)到最小值。當(dāng)式中的每一項(xiàng)的 PF(yj)=xi/yj 達(dá)到最大值時(shí)，平均錯(cuò)誤譯碼概率就可以為最小值。設(shè)信源 X 的信源空間為：X,P:信道的轉(zhuǎn)移矩陣為：P=X:P(X):x1x2x1x2p(x1)p(x2)y1 y2p(y 1/x 1)p(y2/x1)p(y 1/x 2)p(y2/x2)xn收到每一個(gè) yj(j=1,2,xnp(y 1/x n)p(y2/xn)m后) ，推測(cè)發(fā)送為 xi(i=1,2,p(x n)ymp(ym/x1)p(ym/x2)p(ym/xn)n的)后驗(yàn)概率共有 n 個(gè)，為：p(x*/yj) ，即有：p(x1/yj),p(x 2/yj)

7、, pn/(yxj) 。 這其中必有一個(gè)為最大的，設(shè)其為：p(x*/yj) p(xi/yj)(對(duì)一切的 i)這表明：收到符號(hào) yj 后就譯為輸入符號(hào) x* ，即譯碼函數(shù)選為：F(yj)=a* (j=1,2, m) 這種譯碼準(zhǔn)則稱為“最大后驗(yàn)概率準(zhǔn)則” 。 利用這種準(zhǔn)則就可以使平均譯碼錯(cuò)誤概率公式中的 s 項(xiàng)求和的每一項(xiàng)： 1-PF(yj) = xi/yj 達(dá)到最小值 1-F(yj)=x*/yj 。這時(shí)的平均錯(cuò)誤譯碼概率的最小值為：mPeminp(yj) 1 p(x*/ yj)i1n m mp(xi,yj) p(x*, y j) i 1 j 1 j 15-2信息論講義mmp ( y j ) p

8、( y j ) p ( x * / y j ) i 1 i 1mm p ( xi , yj ) p (xi ) p ( yj / xi )j 1 i j 1 i 這個(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)則。由概率中的貝葉斯定理可有：p(xi / yj )p(x

9、i)p(yj / xi)p(yj)p(x* / yj )p(x*)p(yj / x )p(yj)這樣，根據(jù)最大后驗(yàn)概率譯碼準(zhǔn)則，如果 p(x*)p(yj/x*)p(xi)p(yj/xi)(i=1,2, n)就等于： p(x*/y j) p(x i/y j)則選擇譯碼準(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)移概率來取代。這時(shí)，在 X 的先驗(yàn)概率為等概時(shí)，如果 p(yj/x*) 是 yj 相應(yīng)的 n 個(gè)信道轉(zhuǎn)移概率 p(yj/x1),p(yj/x2), ,p(yj/xn

10、)中的最大者，則我們就將 yj 譯成 x* ，這種譯碼方法稱為“最大似然譯碼準(zhǔn)則” 。 最大似然譯碼準(zhǔn)則利用了信道轉(zhuǎn)移概率，而不用后驗(yàn)概率，將會(huì)更方便。 這時(shí)的最小平均錯(cuò)誤譯碼概率為：m1 mPeminp(xi)p(yj / xi)p(yj / xi)j 1 in j 1 i將信道轉(zhuǎn)移矩陣 P 中每一列中的最大元素去掉，然后將其它元素相加后除以 n。 為了減小錯(cuò)誤譯碼概率，主要方法是改變信道轉(zhuǎn)移概率，5-2 信道編碼基本概念5-2-1 信道編碼定理定理 ：有噪聲信道編碼定理( Shannon 第二編碼定理)如一個(gè)離散有噪聲信道有 n個(gè)輸入符號(hào)， m 個(gè)輸出符號(hào)， 信道容量為 C。當(dāng)信道的熵速

11、率 R C 時(shí)，只要碼長足夠長，總可以找到一種編碼方法及譯碼準(zhǔn)則，使信道輸出端的平均 錯(cuò)誤譯碼概率達(dá)到任意小， pe= 。當(dāng) R>C 時(shí)，則不可能找到一種編碼方法及譯碼準(zhǔn)則， 使信道輸出端的平均錯(cuò)誤譯碼概率達(dá)到任意小。5-3信息論講義編碼定理的證明比較復(fù)雜，用超球空間幾何方法。 這個(gè)定理是一個(gè)存在定理，指出錯(cuò)誤率趨于0 的編碼方法是存在的。定理表明，在錯(cuò)誤率趨于 0的同時(shí)，還可以使 R趨于 C，這是具有理論指導(dǎo)意義的。 這個(gè)定理的證明思想為：以二元編碼為例：5-2-2 信道編碼的基本概念(分組碼)(1) 碼字空間：如果原始信源空間有 M 個(gè)碼字，對(duì)其進(jìn)行 q 元等長碼的信道編碼，碼長為

12、N，信道碼 字空間的所有碼字為 qN個(gè)，編碼器將在這 qN個(gè)可用碼字中選擇 M 個(gè)碼字分別代表原始信 源中的 M 個(gè)碼字， 信道編碼碼字空間的這 M 個(gè)碼字稱為 “許用碼字” ，而另外的 qN-M 個(gè)碼 字稱為“禁用碼字” 。為了實(shí)現(xiàn)糾錯(cuò)編碼， 一定有 qN>M 。這M 個(gè)許用碼字也稱為一個(gè)碼組， 或稱為碼字集合。(2) 漢明距離： (Hamming distance) 在一個(gè)碼組(碼字集合)中，任意兩個(gè)等長碼字之間，如果有 d 個(gè)相對(duì)應(yīng)的碼元不同， 則稱 d 為這兩個(gè)碼字的漢明距離。例如： 和為碼組 X 中的兩個(gè)不同碼字， X 為一個(gè)長度為 N 的二元碼組，其中： =a1 ,a2, a

13、Nai 0,1 =b1,b2, bNbi 0,1則與的漢明距離為：Nd( , )ai bi 0 d Ni1d=0 表明為全同碼， d=N 表明為全異碼，如果用模 2 加法的概念，有Nd( , ) ai bii1(3) 最小碼距： 在一個(gè)碼字集合中， 任何兩個(gè)碼字之間的漢明距離組成一個(gè)元素集合，D( ,),這個(gè)集合中的最小值稱為這個(gè)碼字集合的最小漢明距離，簡稱最小碼距，記為：dmin。dmin=mind( ,),X 例如：(4) 碼字重量(漢明重量) (Hamming weight) 在二元編碼的碼字集合中，碼字中“ 1”碼元的個(gè)數(shù)稱為這個(gè)碼字的重量。記為： W( ) 。利用碼字重量的概念，漢明

14、距離可以表示為： d(, )=W( )(5) 分組碼最小碼距與糾檢錯(cuò)能力的關(guān)系： 一個(gè)分組碼的最小碼距為 dmin ，則其糾檢錯(cuò)能力為： 若發(fā)現(xiàn) e 個(gè)錯(cuò)誤，則要求 dmin e+1;若糾正 t 個(gè)錯(cuò)誤，則要求 dmin 2t+1;若糾正 t 個(gè)錯(cuò)誤，同時(shí)發(fā)現(xiàn) e 個(gè)錯(cuò)誤，則要求 dmin t+e+1; t<e;例如：dmin=1; 無糾檢錯(cuò)能力； dmin=2; 檢一位錯(cuò)dmin=3; 糾一位錯(cuò)(或檢兩位錯(cuò))dmin=4; 糾一位，同時(shí)檢兩位；5-4信息論講義dmin=5; 糾二位錯(cuò)(或檢 4 位錯(cuò)) dmin=6; 糾二位，同時(shí)檢 3 位； (t=2,e=3) dmin=7; 糾三位

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

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

17、 x1,x2, ,xn對(duì)于偶校驗(yàn)碼：監(jiān)督元為kXn Xk 1 X1 X2XkXii1對(duì)于奇校驗(yàn)碼，監(jiān)督元為：5-5信息論講義kXn Xk 1 X1 X2 Xk Xi 1i1偶校驗(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ò)誤碼字的概率稱為漏檢概率。 奇偶校驗(yàn)碼不能發(fā)現(xiàn)偶數(shù)個(gè)碼元錯(cuò)誤， 根據(jù)最小碼距分析至少檢一位錯(cuò)， 實(shí)際上可以檢 出所有奇數(shù)個(gè)錯(cuò)。假設(shè)信道誤碼率為 pe，碼字漏檢概率為 Pu，有：n/2PuCn2ipe2i(1 pe)n 2in為偶數(shù)

18、；i1 ( n 1)/ 2n 為奇數(shù)；PuCn2iPe2i(1 pe )n 2ii1其中 n 為碼字長度，有：2i nn!(2i)!( n 2i)!Pu=Cn2pe2。而且還與碼字長度有關(guān)，實(shí)際上它是一個(gè)誤字率的概當(dāng)信道誤碼率很小時(shí)， pe<<1; 漏檢概率不僅與信道誤碼率有關(guān)，念，應(yīng)當(dāng)配合 ARQ 系統(tǒng)使用，可以看到系統(tǒng)可靠性是很高的。(3) 編碼效率：實(shí)際上可知：編碼效率與信道傳輸效率是同一個(gè)概念：R r H(X)log2k kC r Hmax(X) log2n n認(rèn)為信源符號(hào)為等概率條件。根據(jù)奇偶校驗(yàn)碼的原理， 還有一些改進(jìn)方法：水平奇偶校驗(yàn)碼， 垂直奇偶校驗(yàn)碼，群計(jì) 數(shù)碼等

19、，5-3-2 定比碼(等重碼，范德倫碼)5，其中 1 的個(gè)數(shù)為 3。這種碼的(1) 五三定比碼與七三定比碼 定比碼為一種簡單檢錯(cuò)碼。 五三定比碼(五單位碼)用于國內(nèi)電報(bào)系統(tǒng)，碼長為 許用碼字為：C535!3!(5 3)!10代表國內(nèi)電報(bào)系統(tǒng)中的數(shù)字 09。七三定比碼(七單位碼)用于國際電報(bào)系統(tǒng)，碼長為7，其中 1 的個(gè)數(shù)為 3。這種碼的5-6信息論講義許用碼字為：7!3!(7 3)!35代表 26 個(gè)英文字母和一些符號(hào)。(2) 漏檢概率：五三定比碼和七三定比碼的 dmin=2 ，至少可以檢一位錯(cuò)，實(shí)際上定比碼可以檢出所有 奇數(shù)位錯(cuò)碼，及一些偶數(shù)位錯(cuò)碼。定比碼的漏檢為：偶數(shù)位錯(cuò)誤，且一半1 錯(cuò)為

20、 0，一半 0 錯(cuò)為 1；Pu=P2+P4+1 3-1 1 2-1 P2=P10.P01=C3 pe(1-p e) .C2 pe(1-pe) P4=C22C32pe4(1-pe)5-4(3) 編碼效率：53H(X) log10Hmax(X) log25log10566%R H(X)C H max(X)log35772%5-3-3 重復(fù)碼 檢錯(cuò)碼只能發(fā)現(xiàn)錯(cuò)誤，必須利用 ARQ 系統(tǒng)才能實(shí)現(xiàn)抗干擾，它要求有反向信道，而前 向糾錯(cuò)碼的最大優(yōu)點(diǎn)就是不需要反向信道，并且實(shí)時(shí)性高。重復(fù)碼是一種最簡單的糾錯(cuò)碼。 在實(shí)際系統(tǒng)重有較廣泛的應(yīng)用。(1) 一個(gè)例子：1p=1-pe=0.991按最大似然譯碼準(zhǔn)則為：

21、F(0)=0;一個(gè) BSC 信道，輸入為 X=0 ，1 ，且為等概分布，信道模型為：F(1)=1;在信道誤碼率為 pe=10-2 條件下，其錯(cuò)誤譯碼概率為： -2Pemin=(1/n)(p e+pe)=(1/2)(0.01+0.01)=10 -2可以看到這時(shí)系統(tǒng)誤碼率就等于信道誤碼率，這里沒有采用任何信道編碼。(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)于信道輸入為 X1=0

22、00 ，X2=111，而信道輸出端為： Y1=000 ； Y2=001 ；Y3=010 ；Y4=100Y5=011 ；Y6=110 ；Y7=101 ； Y8=111 這時(shí)的信道轉(zhuǎn)移矩陣為：5-7信息論講義Y1 Y2 Y3 Y4 Y5 Y6 Y7 Y8PX1p133X2p3222 p1 p1 p1 p p p p21p p21p p12pp21p p21p p12p222 p1 p1 p1 p p p3p3p1這時(shí)如果按最大似然法則譯碼，將為：F(Y1)=F(Y2)=F(Y3)=F(Y4)=X1=000F(Y5)=F(Y6)=F(Y7)=F(Y8)=X2=111 錯(cuò)誤譯碼概率為：3 2 2 2

23、2 2 2 3 2 3 Pemin=(1/2) p + p p1+ p p1+ p p1+ p p1+ p p1+ p p1+ p = 3p p1+ p-4 3×10-4 可見簡單重復(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;R log 2 1C log 23 3同樣可知：五次重復(fù)碼 =k/

24、n=1/5;5-4 代數(shù)引論為了進(jìn)一步學(xué)習(xí)糾錯(cuò)編碼的原理和分析其性能， 在這一節(jié)中我們復(fù)習(xí)一些有關(guān)的代數(shù)知 識(shí)。5-4-1 群 (Group)群的定義 ：如果一個(gè)元素集合 G，在其中定義一種運(yùn)算“ * ”，并滿足下列條件則稱為 一個(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如果還滿足交換律， a*b=b*a, 則稱為交換群。定理 1： 群 G 中的單位元是唯一的。定理 2：群 G 中任一元素的逆元是唯一的。有限群 ：群中元素的個(gè)數(shù)稱為元素的階，有限元素的

25、群稱為有限群。( m 階有限群)模運(yùn)算 ：G=0 ，1為一個(gè)模 2 加法群，0+0=0 ，0+1=1，1+0=1，1+1=0 0 是單位元，本身是逆元，滿足結(jié)合律，交換律和自 閉性，為一個(gè)加法交換群。當(dāng) p 為一個(gè)素?cái)?shù)，則集合 G=1,2 , p-1在模 p 乘法下為一個(gè)群。例如 p=5,G=1,2,3,4 為一個(gè)乘法群，5-8信息論講義123411234224133314244321全體實(shí)數(shù)集合為一個(gè)普通加法的交換群； 全體非零實(shí)數(shù)集合為一個(gè)普通乘法的交換群；子群 ：如果集合 G 在某種運(yùn)算 *下為一個(gè)群，集合 H 為 G 中的一個(gè)非空子集。若 H 在運(yùn)算 *下也滿足自閉性，結(jié)合律，單位元和

26、逆元，則稱H 為G 的一個(gè)子群。偶數(shù)集合 H:2n 為整數(shù)加法群的一個(gè)子群。定理：如果集合 G在運(yùn)算 *下為一個(gè)群， H 為一個(gè)子群，則 G中的所有元素都可以由 子群 H 中的元素表示。單位元：如果 H 為G的一個(gè)子群，則 G中唯一的單位元一定在 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,則

27、子群 H 的元素為： H:0, ±3, ±6, ±9, ±12, ±15, ±18, 利用分元陪集的方法，用 H 的元素表示 G 中的所有元素。將子群 H 中的元素放在表的第一行，且單位元0 放在首位，稱為陪集首。將 H 中沒有的，但 G 中的元素 1 作為陪集首，放在表的第二行的首位，將陪集首 分別與第一行的元素做加法運(yùn)算，組成的二個(gè)陪集。將第一行，第二行中沒有的，但在群中有的元素 2 作為第二個(gè)陪集的陪集首，構(gòu)成 第三個(gè)陪集。這樣，利用分元陪集的方法，可以構(gòu)成所有 G 中的元素。陪集 103-36-69-9 陪集 21+0=11+

28、3=4-27-510-8 陪集 32+0=22+3=5-18-411-7 5-4-2 域 (Field)域的定義 ： 如果一個(gè)元素集合 F，在其中定義加法和乘法兩種運(yùn)算，并滿足下列條件 則稱為一個(gè)域 (Feild) 。 a,b,c,d,e,a-1 G。在加法下為一個(gè)交換群，滿足自閉性，交換律，結(jié)合律，單位元為 0，逆元。 在乘法下為一個(gè)交換群，滿足非零元素自閉性，交換律，結(jié)合律，單位元，逆元。 在加法乘法下滿足分配律，有限域 ：域中的元素個(gè)數(shù) m 稱為域的階， 有限個(gè)元素的域稱為有限域或叫作伽羅華域， 記為 GF(m) ，GF-Galois Field ，最小域 ： 一個(gè)域中最少包含加法單位元

29、和乘法單位元兩個(gè)元素，否則不能構(gòu)成域。 例如：集合 0,1 在模二加法和乘法下構(gòu)成一個(gè)二元有限域GF(2) 。素域：如果 p為一個(gè)素?cái)?shù)，則正整數(shù)集合 0,1,2, -1p ，在模 p 加法和乘法下為一個(gè) 階數(shù)為 p 的域，稱為素域，記為 GF(p) 。 GF(2) 為一個(gè)素域。+0123456001234561123456022345601例如： GF(7) 為一個(gè)素域，其運(yùn)算如下： 模 7 加法0123456000000001012345620246135模 7 乘法5-9信息論講義3345601244560123556012346601234534560 30 40 50 66 21 53

30、 15 45 12 66 43 24321擴(kuò)展域 ：對(duì)于任何一個(gè)正整數(shù) m，可以將素域 GF(p) 擴(kuò)展成有 pm個(gè)元素的域，稱為域 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)中的元素，而域 中的元素是有限個(gè)，因此必然存在兩個(gè)正整數(shù) m,n, m<n ，使：mnn m1 1 or 1 0i 1i 1i 1或者說：必然存在一個(gè)最小的正整數(shù) =n-m，我們稱 為域

31、 GF(q)的特征。二元域 GF(2)的特征 =2；素域 GF(p) 的特征 =p；有限域的特征是一個(gè)素?cái)?shù)；循環(huán)群 ： 如果一個(gè)群存在一個(gè)元素，其各次冪構(gòu)成整個(gè)群，稱為循環(huán)群。定理 ：有限域 GF(q)的非零元素構(gòu)成一個(gè)循環(huán)群。設(shè) a 是 GF(q) 中的一個(gè)非零元素， 由于 GF(q)的非零元素在乘法下為自閉的， 所以 a，a2， a3，也必然是 GF(q)中的非零元素，又因?yàn)?GF(q) 為有限元素，所以必然有一個(gè)最小的正 整數(shù) n，使 an=1。這個(gè)正整數(shù) n 稱為元素 a 的階。令 a 為有限域 GF(q) 的非零元素，則 aq-1=1 。令 a為有限域 GF(q)的非零元素，且 n

32、為 a的階，則 q-1 一定能被 n除盡。本原元 ：如果有限域 GF(q)中，非零元素 a的階 n=q-1 ，就稱 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 ，可 以看到 3的各次冪構(gòu)成了 GF(7)中所有非零元素， 所以 3的階 n=q-1=6，3為 GF(7)

33、的本原元。如果取 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)=f 0+f 1x+f 2x2+ +fnxn 的系數(shù)取自二元有限域 GF(2) ，則稱 f(x)為域 FG(2)上的多項(xiàng)式。 fi=0 或 fi=1;域上多項(xiàng)式計(jì)算 ： 加法：如果 f(x)=f 0+f1x+f 2x2+fnxn;g(x)=g0+g1x+g2x2+gnxn 則：f(x)+g(x)= (f 0+ g 0)+(f 1 +g

34、1)x +(f2 +g2)x2+(fn+gn)xn乘法：如果 f(x)=f 0+f1x+f 2x2+fnxn;g(x)=g0+g1x+g2x2+gmxm 則：2 n+m f(x)g(x)=c(x)=c0+c 1x+c 2x + +cn+mx ;c0 =f 0g0 c1=f0g1+f1g0cn+m=f ngm5-10信息論講義除法：如果 f(x)=1+x+x 4+x 5+x6; g(x)=1+x+x 則 f(x)/g(x) 的結(jié)果可以寫作：f (x) q(x) r(x)其中： q(x)=x 3+x2;g(x) g(x)3x +x+1r(x)=x 2+x+1;利用展轉(zhuǎn)相除法(歐幾里得除法) 32

35、x +x 654x +x +x +x+16 4 3 x +x +x 53 x + x +x+15 3 2x +x +xx2+x+1如果 r(x)=0 ，即 f(x)能被 g(x)除盡，則稱 g(x)為 f(x) 的因式； f(x) 為 g(x)的倍式。多項(xiàng)式的模運(yùn)算 ： 如果 GF(2)上多項(xiàng)式， F(x),N(x),Q(x),R(x) 滿足：F(x)N(x)Q(x)R(x)N(x)則稱在模 N(x) 條件下， F(x)=R(x) 。不可約多項(xiàng)式 ：如果 f(x) 為 GF(2) 上的 m 次多項(xiàng)式，它不能被任何次數(shù)小于m，大于0 的多項(xiàng)式除盡，則稱其為 GF(2) 上的不可約多項(xiàng)式，既約多項(xiàng)

36、式。f(x)=x 3+x+1; f(x)=x 4+x+1; 均為不可約多項(xiàng)式。GF(2) 上的多項(xiàng)式若有偶數(shù)項(xiàng)，則一定可被 x+1 除盡。對(duì)于任意 m1,都存在 m 次不可約多項(xiàng)式。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， 則稱 f(x) 為本原多項(xiàng)式。不可約多項(xiàng)式不一定是本原多項(xiàng)式，本原多項(xiàng)式一定為不可約的。m 次本原多項(xiàng)式是不唯一的。22性質(zhì)：對(duì)于 GF(2)上的多項(xiàng)式 f(x) ，有f(x)

37、2=f(x 2)。5-4-4 GF(2) 上的矢量空間域上矢量空間 ：令V是一個(gè)矢量集合，在其上定義一個(gè)加法運(yùn)算。令F 是一個(gè)域，在域中的元素和 V 中的元素之間定義了一個(gè)乘法運(yùn)算。如果集合 V 滿足下例條件， 稱其為 域 F 上的矢量空間(線性空間) 。V 是加法可交換群；F 中的任意元素 a 和V 中的元素 Vi 的乘積， aVi 是 V 中的元素；滿足分配律： a,bF; Vi,Vj V ; a?(Vi+Vj)=a? V i+a?Vj; (a+b) ?Vi=a?Vi+b?Vi; 滿足結(jié)合律： (a?b) ?Vi=a?(b?Vi);F 中的單位元為 1，1?Vi=Vi。V 中的單位元為 0

38、 矢量。域上矢量空間的性質(zhì) ：0 為 F 上的零元，則 0?Vi=0;c為 F 上的任意標(biāo)量，則 c?0=0;c為 F 上的任意標(biāo)量和 V 中的任意矢量 Vi ， (-c) ?Vi=c?(-Vi)=- (c?Vi);5-11信息論講義GF(2) 上的矢量空間 ：一個(gè)有 n 個(gè)分量的序列；(a0,a1, an-1) 其中每個(gè)分量是二元域上的元素 (ai=0,1)，這個(gè)序列稱為 GF(2) 上的 n-重。GF(2)上共有 2n個(gè) n-重。令 V n表示這 2n個(gè) n-重的集合，則可以證明 Vn是 GF(2)上的 一個(gè)矢量空間。例如： n=5, GF(2)上的 5-重矢量空間 V5由 32個(gè)矢量組成

39、。(00000),(00001), (11。111)這個(gè)空間中任意兩個(gè)矢量之和仍然是這個(gè)空間中的矢量。GF(2)中的元素 0，1 乘上空間中的任意矢量仍然是這個(gè)空間中的矢量。V 的子空間 ：如果 V 是 F 上的矢量空間， V 的一個(gè)子集也是 F 上的一個(gè)矢量空間，則稱 S 為V 的 一個(gè)子空間。例如： V 5上的子集， (00000),(00111),(11010),(11101) 為一個(gè)子空間。線性組合 ：令 V1,V2,Vk是 F上矢量空間 V中的 k個(gè)矢量。令 a1,a2ak是F中的 k 個(gè)標(biāo)量。則 : a1V1+a2V2+ +akV k稱為的線性組合。如果：除非 a1=a2= =ak=0, 否則 a1V1+a2V2+akVk0；則稱 V