講義51糾錯編碼原理

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

2、果采用自然的譯碼準則，即收0判0，收1判1；這時可以明顯看到，當信源先驗概率的等概時p(0)=p(1)=1/2；這時收到Y判X的后驗概率等于信道轉移概率，系統(tǒng)正確的譯碼概率為1/4，錯誤譯碼概率為3/4。但如果采用另一種譯碼準則，收0判1，收1判0；則系統(tǒng)正確的譯碼概率為3/4，錯誤譯碼概率為1/4，通信的可靠性提高了。(2) 譯碼準則設一個有噪聲離散信道，輸入符號集X，輸出符號集Y，信道轉移概率為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這時定義一個收到y(tǒng)j后判定為xi

3、的單值函數，即： F(yj)=xi (i=1,2,n; j=1,2,m)；這個函數稱為譯碼函數。它構成一個譯碼函數組，這些函數的值組成了譯碼準則。對于有n個輸入，m個輸出的信道來說，可以有nm個不同的譯碼準則。例如上面例子中有4中譯碼準則分別為：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 譯碼錯誤概率當譯碼準則確定之后，當接收端收到一個yj后，則按譯碼準則譯成F(yj)=xi，這時如果發(fā)送的為xi則為正確譯碼，如果發(fā)送的不是xi則為錯誤譯碼。所以接收到y(tǒng)j后正確譯碼的概率就是接收端收到y(tǒng)j后，推測發(fā)送端

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

5、。當信道信道轉移概率p(yj/xi)確定后，而且信源統(tǒng)計特性p(xi)確定之后，信道輸出端的p(yj)也就確定了。因為：p(xi,yj)=p(xi)p(yj/xi); 而p(yj)可以由p(xi,yj)的(i=1,2, n)求和得到。因此，在這種情況下，平均錯誤譯碼概率只與譯碼準則有關了。通過選擇譯碼準則可以使平均譯碼概率達到最小值。當式中的每一項的PF(yj)=xi/yj達到最大值時，平均錯誤譯碼概率就可以為最小值。設信源X的信源空間為：X,P:X:x1x2xnP(X):p(x1)p(x2)p(xn)信道的轉移矩陣為：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)收到每一個yj(j=1,2,m)后，推測發(fā)送為xi(i=1,2,n)的后驗概率共有n個，為：p(x1/yj),p(x2/yj),p(xn/yj)。這其中必有一個為最大的，設其為：p(x*/yj)，即有：p(x*/yj)p(xi/yj) (對一切的i)這表明：收到符號yj后就譯為輸入符號x*，即譯碼函數選為：F(yj)=a* (j=1,2,m)這種譯碼準則稱為“最大后驗概率準則”。利用這種準則就可以使平均譯碼錯誤概率公式中的s項求和的每一項：1-PF(yj) = xi/yj達到最小值1-F(yj)=

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

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

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

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

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

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

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

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

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

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

17、定比碼和七三定比碼的dmin=2，至少可以檢一位錯，實際上定比碼可以檢出所有奇數位錯碼，及一些偶數位錯碼。定比碼的漏檢為：偶數位錯誤，且一半1錯為0，一半0錯為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ā)現錯誤，必須利用ARQ系統(tǒng)才能實現抗干擾，它要求有反向信道，而前向糾錯碼的最大優(yōu)點就是不需要反向信道，并且實時性高。重復碼是一種最簡單的糾錯碼。在實際系統(tǒng)重有較廣泛的應用。(1) 一個例子：一個BSC信道，輸入為X=0，1，且為等概分布，信道模型為

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

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

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

21、義一種運算“*”，并滿足下列條件則稱為一個群(Group)。a,b,c,e,a-1G。§ 自閉性，c=a*b§ 結合律，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中任一元素的逆元是唯一的。有限群：群中元素的個數稱為元素的階，有限元素的群稱為有限群。（m階有限群）模運算：G=0，1為一個模2加法群，0+0=0，0+1=1，1+0=1，1+1=0 0是單位元，本身是逆元，滿足結合律，交換律和自閉性，為一個

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

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

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

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

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

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

28、a的階。§ 令a為有限域GF(q)的非零元素，則aq-1=1。§ 令a為有限域GF(q)的非零元素，且n為a的階，則q-1一定能被n除盡。本原元：如果有限域GF(q)中，非零元素a的階n=q-1，就稱a為GF(q)的本原元素。§ 本原元素的各次冪構成有限域FG(q)的所有元素。§ 每個有限域都有其本原元素。例如：有限域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的各次冪構成了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 域上多項式在編碼理論上大多采用二元有限域GF(2)的多項式，因此我們重點介紹這部分的知識。域上多項式：如果多項式f(x)=f0+f1x+f2x2+fnxn的系數取自二元有限域GF(2)，則稱f(x)為域FG(2)上的多項式。fi=0或fi=1;域上多項式計算：加法：如果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)的結果可以寫作： 其中：q(x)=x3+x2; r(x)=x2+x+1;利用展轉相除法（歐幾里得除法）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)除盡，則稱g(x)為f(x)的因式；f(x)為g(x)的倍式。多項式的模運算：如果GF(2)上多項式，F(x),N(x),Q(x),R(x)滿足：則稱在模N(x)條件下，F(x)=R(x)。不可約多項式：如果f(x)為GF(2)上的m次多項式，它不能被任何次數小于m，大于0的多項式除盡，則稱其為GF(2)上的不可約多項式，既約多項式。f(x)=x3+x+1; f(x)=x4+x+1;均為不可約多項式。§ GF(2)上的多項式若有偶數項，則一定可被x+1除盡。§ 對于任意m1,都存在m次不可約多項式。

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

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

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