讲义51纠错编码原理讲解

1、信息论讲义纠错编码原理从这一章开始介绍有噪声信道编码的问题， 有噪声信道编码的主要目的是提高传输可靠 性，增加抗干扰能力， 因此也称为纠错编码或抗干扰编码。 在这一章里将首先介绍信道编码 定理和纠错编码的基本原理。信源编码之后的码字序列抗干扰能力很脆弱， 在信道噪声的影响下容易产生差错， 为了 提高通信系统的有效性和可靠性，要在信源编码器和信道之间加上一个信道编码器， 5-1 译码准则5-1-1 译码准则的含义(1) 一个例子 影响通信系统可靠性的一个重要问题是译码方式，可以通过一个例子看一下； 有一个 BSC 信道，如图所示。对于这样一个信道， 如果采用自然的译码准则，即收 0判 0，收 1

2、判 1；这时可以明显看到， 当信源先验概率的等概时 p(0)=p(1)=1/2 ；这时收到 Y 判 X 的后验概率等于信道转移概率， 系统正确的译码概率为 1/4，错误译码概率为 3/4。但如果采用另一种译码准则，收0 判 1，收 1 判 0 ；则系统正确的译码概率为 3/4，错误译码概率为 1/4，通信的可靠性提高了。p(yj/xi)Yyj(2) 译码准则 设一个有噪声离散信道，输入符号集X，输出符号集 Y ，信道转移概率为 P(Y/X);XxiX:x 1,x2, .,xnY:y 1,y2, ymP(Y/X):p(yj/xi); i=1,2,j=1,2n,; m这时定义一个收到 yj 后判定

3、为 xi 的单值函数， 即： 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 译码错误概率当译码准则确定之后，当接收端收到一个 发送的为 xi 则为正确译码， 如果发送的不是 概率就是接收端收到 yj 后，推测发送端发出yj 后，则按译码准则译成 F(yj)=

4、xi ，这时如果 xi 则为错误译码。 所以接收到 yj 后正确译码的 xi 的后验概率：Prj=PF(yj)=xi/yj而错误译码的概率为收到 yj 后，推测发出除了 xi 之外其它符号的概率：5-1信息论讲义Pej=Pe/y j=1-PF(y j)=xi/yj其中 e 表示除了 xi 之外的所有其它信源符号的集合。 然后对所有的 yj 取平均，则平均正确译码概率为：mmPrP(yj)Prjp(yj) pF(yj) xi /yjj 1 j 1同样可以得到平均错误译码概率为：mmPep(yj)Pe/ yjp(yj)1 PF(yj) xi/ yjj 1 j 1这就是平均错误译码概率的基本表达式，

5、 在通信系统设计和分析时， 总是希望得到最可能小 的平均错误译码概率。 因此所有通信系统都将平均译码错误概率作为系统可靠性的一个重要 指标。5-1-3 最大后验概率准则由平均错误译码概率的表达式可以看出，错误译码概率与信道输出端随机变量 Y 的概 率分布 p(yj) 有关，也与译码准则有关。当信道信道转移概率p(yj/xi) 确定后，而且信源统计特性 p(xi)确定之后，信道输出端的 p(yj) 也就确定了。因为： p(xi,yj)=p(xi)p(yj/xi); 而 p(yj) 可以由 p(xi,yj) 的 (i=1,2, n)求和得到。因此， 在这种情况下， 平均错误译码概率只与译码准则有关

6、了。 通过选择译码准则可以 使平均译码概率达到最小值。当式中的每一项的 PF(yj)=xi/yj 达到最大值时，平均错误译码概率就可以为最小值。设信源 X 的信源空间为：X,P:信道的转移矩阵为：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收到每一个 yj(j=1,2,xnp(y 1/x n)p(y2/xn)m后) ，推测发送为 xi(i=1,2,p(x n)ymp(ym/x1)p(ym/x2)p(ym/xn)n的)后验概率共有 n 个，为：p(x*/yj) ，即有：p(x1/yj),p(x 2/y

7、j), pn/(yxj) 。 这其中必有一个为最大的，设其为：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)=x*/yj 。这时的平均错误译码概率的最小值为：mPeminp(yj) 1 p(x*/ yj)i1n m mp(xi, y j) p(x*, y j) i 1 j 1 j 15-2信息论讲义mmp ( y j

8、) p ( y j ) p ( x * / y j ) i 1 i 1mm p(xi , yj ) p (xi ) p( yj / xi )j 1 i j 1 i 这个表达式平均错误译码概率的最小值，是把每一个yj 对应的后验概率排除后再连续求和。从表达式中可以看到，这个最小值与信源先验概率和信道转移概率有关，特别是信 道转移概率，如果除了 p(yj/x*) 外，其它的项多很小，错误译码概率会减小。5-1-4 最大似然准则 使用最大后验概率译码准则必须已知后验概率， 但信道的统计特性描述总是给出信道转 移概率，因此利用信道转移概率的译码准则。由概率中的贝叶斯定理可有：p(xi / yj )p(

9、xi)p(yj / xi)p(yj)p(x* / yj )p(x*)p(yj / x )p(yj)这样，根据最大后验概率译码准则，如果 p(x*)p(yj/x*)p(xi)p(yj/xi)(i=1,2, n)就等于： p(x*/y j) p(x i/y j)则选择译码准则： 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/x

10、n)中的最大者，则我们就将 yj 译成 x* ，这种译码方法称为“最大似然译码准则” 。 最大似然译码准则利用了信道转移概率，而不用后验概率，将会更方便。 这时的最小平均错误译码概率为：m1 mPeminp(xi)p(yj /xi)p(yj / xi)j 1 inj 1 i将信道转移矩阵 P 中每一列中的最大元素去掉，然后将其它元素相加后除以 n。 为了减小错误译码概率，主要方法是改变信道转移概率，5-2 信道编码基本概念5-2-1 信道编码定理定理 ：有噪声信道编码定理( Shannon 第二编码定理)如一个离散有噪声信道有 n个输入符号， m 个输出符号， 信道容量为 C。当信道的熵速 率

11、 R C 时，只要码长足够长，总可以找到一种编码方法及译码准则，使信道输出端的平均 错误译码概率达到任意小， pe= 。当 RC 时，则不可能找到一种编码方法及译码准则， 使信道输出端的平均错误译码概率达到任意小。5-3信息论讲义编码定理的证明比较复杂，用超球空间几何方法。 这个定理是一个存在定理，指出错误率趋于0 的编码方法是存在的。定理表明，在错误率趋于 0的同时，还可以使 R趋于 C，这是具有理论指导意义的。 这个定理的证明思想为：以二元编码为例：5-2-2 信道编码的基本概念(分组码)(1) 码字空间： 如果原始信源空间有 M 个码字，对其进行 q 元等长码的信道编码，码长为 N，信道

12、码 字空间的所有码字为 qN个，编码器将在这 qN个可用码字中选择 M 个码字分别代表原始信 源中的 M 个码字， 信道编码码字空间的这 M 个码字称为 “许用码字” ，而另外的 qN-M 个码 字称为“禁用码字” 。为了实现纠错编码， 一定有 qNM 。这 M 个许用码字也称为一个码组， 或称为码字集合。(2) 汉明距离： (Hamming distance) 在一个码组(码字集合)中，任意两个等长码字之间，如果有 d 个相对应的码元不同， 则称 d 为这两个码字的汉明距离。例如： 和为码组 X 中的两个不同码字， X 为一个长度为 N 的二元码组，其中： =a1 ,a2, aNai 0,1

13、 =b1,b2, bNbi 0,1则与的汉明距离为：Nd( , )ai bi 0 d Ni1d=0 表明为全同码， d=N 表明为全异码，如果用模 2 加法的概念，有Nd( , ) ai bii1(3) 最小码距： 在一个码字集合中， 任何两个码字之间的汉明距离组成一个元素集合，D( ,),这个集合中的最小值称为这个码字集合的最小汉明距离，简称最小码距，记为：dmin。dmin=mind( ,),X 例如：(4) 码字重量(汉明重量) (Hamming weight) 在二元编码的码字集合中，码字中“ 1”码元的个数称为这个码字的重量。记为： W( ) 。利用码字重量的概念，汉明距离可以表示为

14、： d(, )=W( )(5) 分组码最小码距与纠检错能力的关系： 一个分组码的最小码距为 dmin ，则其纠检错能力为： 若发现 e 个错误，则要求 dmin e+1;若纠正 t 个错误，则要求 dmin 2t+1;若纠正 t 个错误，同时发现 e 个错误，则要求 dmin t+e+1; te;例如：dmin=1; 无纠检错能力； dmin=2; 检一位错dmin=3; 纠一位错(或检两位错)dmin=4; 纠一位，同时检两位；5-4信息论讲义dmin=5; 纠二位错(或检 4 位错) dmin=6; 纠二位，同时检 3 位； (t=2,e=3) dmin=7; 纠三位错(或检两位错) dm

15、in=8; 纠三位，同时检 4 位； (t=3,e=45-2-3 信道编码方法 纠错编码：根据一定的纠检错要求，对原始码字进行某种变换，使其具有具有纠检 错能力，这种变换称为抗干扰编码。实现方法：信息位 +监督位 =纠检错编码。 信道编码的分类：纠错码 /检错码前向纠错方式 (FEC-forward error correction)反馈重传方式 (ARQ-automatic repeat request)混合纠错方式 (HEC-hybrid error correction)在 FEC 中又可分为：分组码 (block code/group code)卷积码 (convolutional c

16、ode) 在分组码中常见的码包括： Hamming CodeCyclic CodeBCH CodeGolay CodeReed-Solommon CodeReed-Muller Code5-3 简单的信道编码 检错码一般具有较少的监督位，冗余度较小，只能检出错误，但不能纠正错误。5-3-1 奇偶校验码 (Parity Check Code) 也称为一致监督检错码，是一种检错分组码。(1) 检错原理：当信息码字位二元序列， 码字长度位 k，共有 2k 个码字， 可以在信息码字后面加上一位 监督元，构成长度位 n=k+1 的检错码， X=x 1,x2, ,xk ,xk+1 = x1,x2, ,xn

17、对于偶校验码：监督元为kXn Xk 1 X1 X2XkXii1对于奇校验码，监督元为：5-5信息论讲义kXn Xk 1 X1 X2 Xk Xi 1i1偶校验码中有偶数个 1，奇校验码中有奇数个 1； 奇偶校验码的最小码距为 dmin=2 ; 可检一位错； 可用码字 =2n；许用码字 =2k，禁用码字 =2n-2k(2) 漏检概率 检错码不能发现错误码字的概率称为漏检概率。 奇偶校验码不能发现偶数个码元错误， 根据最小码距分析至少检一位错， 实际上可以检 出所有奇数个错。假设信道误码率为 pe，码字漏检概率为 Pu，有：n/2PuCn2ipe2i(1 pe)n 2in为偶数；i1 ( n 1)/

18、 2n 为奇数；PuCn2iPe2i(1 pe )n 2ii1其中 n 为码字长度，有：2i nn!(2i)!( n 2i)!Pu=Cn2pe2。而且还与码字长度有关，实际上它是一个误字率的概当信道误码率很小时， pe1; 漏检概率不仅与信道误码率有关，念，应当配合 ARQ 系统使用，可以看到系统可靠性是很高的。(3) 编码效率：实际上可知：编码效率与信道传输效率是同一个概念：R r H(X)log2k kC r Hmax(X) log2n n认为信源符号为等概率条件。根据奇偶校验码的原理， 还有一些改进方法：水平奇偶校验码， 垂直奇偶校验码，群计 数码等， 5-3-2 定比码(等重码，范德伦

19、码)5，其中 1 的个数为 3。这种码的(1) 五三定比码与七三定比码 定比码为一种简单检错码。 五三定比码(五单位码)用于国内电报系统，码长为 许用码字为：C535!3!(5 3)!10代表国内电报系统中的数字 09。七三定比码(七单位码)用于国际电报系统，码长为7，其中 1 的个数为 3。这种码的5-6信息论讲义许用码字为：7!3!(7 3)!35代表 26 个英文字母和一些符号。(2) 漏检概率：五三定比码和七三定比码的 dmin=2 ，至少可以检一位错，实际上定比码可以检出所有 奇数位错码，及一些偶数位错码。定比码的漏检为：偶数位错误，且一半1 错为 0，一半 0 错为 1；Pu=P2

20、+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 重复码 检错码只能发现错误，必须利用 ARQ 系统才能实现抗干扰，它要求有反向信道，而前 向纠错码的最大优点就是不需要反向信道，并且实时性高。重复码是一种最简单的纠错码。 在实际系统重有较广泛的应用。(1) 一个例子：1p=1-pe=0.991按最大似然译码准则为： F(0)=0;一个 BSC 信道，输

21、入为 X=0 ，1 ，且为等概分布，信道模型为：F(1)=1;在信道误码率为 pe=10-2 条件下，其错误译码概率为： -2Pemin=(1/n)(p e+pe)=(1/2)(0.01+0.01)=10 -2可以看到这时系统误码率就等于信道误码率，这里没有采用任何信道编码。(2) 编译码方法 重复码的编码方法为，将 0编为 000，1 编为 111。 这时的可用码字为 23=8；分别为：X1=000 X2=001 X3=010 X4=100X5=011 X6=110 X7=101 X8=111 而许用码字为 000 和 111， 相当于信道输入为 X1=000 ，X2=111，而信道输出端为

22、： Y1=000 ； Y2=001 ；Y3=010 ；Y4=100Y5=011 ；Y6=110 ；Y7=101 ； Y8=111 这时的信道转移矩阵为：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这时如果按最大似然法则译码，将为：F(Y1)=F(Y2)=F(Y3)=F(Y4)=X1=000F(Y5)=F(Y6)=F(Y7)=F(Y8)=X2=111 错误译码概率为：3 2 2 2 2 2 2 3 2 3 Pemin=

23、(1/2) p + p p1+ p p1+ p p1+ p p1+ p p1+ p p1+ p = 3p p1+ p-4 310-4 可见简单重复码可以将错误译码概率下降两个数量级。 这是三次重传大数判别的方法；可以看出如果是五次重复码，误码率还要降低。 注：从这里的译码方法可以看到：最大似然译码准则实际上是一种最小汉明距离的译 码准则。为了判别比较，一般重复码都采用奇数次重复，然后按大数判决。(3) 编码效率 三次重复码的编码效率为：相当于 k=1,n=3 ; =k/n=1/3;R log 2 1C log 23 3同样可知：五次重复码 =k/n=1/5;5-4 代数引论为了进一步学习纠错编

24、码的原理和分析其性能， 在这一节中我们复习一些有关的代数知 识。5-4-1 群 (Group)群的定义 ：如果一个元素集合 G，在其中定义一种运算“ * ”，并满足下列条件则称为 一个群 (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

25、 ，1为一个模 2 加法群，0+0=0 ，0+1=1，1+0=1，1+1=0 0 是单位元，本身是逆元，满足结合律，交换律和自 闭性，为一个加法交换群。当 p 为一个素数，则集合 G=1,2 , p-1在模 p 乘法下为一个群。例如 p=5,G=1,2,3,4 为一个乘法群，5-8信息论讲义123411234224133314244321全体实数集合为一个普通加法的交换群； 全体非零实数集合为一个普通乘法的交换群；子群 ：如果集合 G 在某种运算 *下为一个群，集合 H 为 G 中的一个非空子集。若 H 在运算 *下也满足自闭性，结合律，单位元和逆元，则称H 为G 的一个子群。偶数集合 H:2

26、n 为整数加法群的一个子群。定理：如果集合 G在运算 *下为一个群， H 为一个子群，则 G中的所有元素都可以由 子群 H 中的元素表示。单位元：如果 H 为G的一个子群，则 G中唯一的单位元一定在 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, 利

27、用分元陪集的方法，用 H 的元素表示 G 中的所有元素。将子群 H 中的元素放在表的第一行，且单位元0 放在首位，称为陪集首。将 H 中没有的，但 G 中的元素 1 作为陪集首，放在表的第二行的首位，将陪集首 分别与第一行的元素做加法运算，组成的二个陪集。将第一行，第二行中没有的，但在群中有的元素 2 作为第二个陪集的陪集首，构成 第三个陪集。这样，利用分元陪集的方法，可以构成所有 G 中的元素。陪集 103-36-69-9 陪集 21+0=11+3=4-27-510-8 陪集 32+0=22+3=5-18-411-7 5-4-2 域 (Field)域的定义 ： 如果一个元素集合 F，在其中定

28、义加法和乘法两种运算，并满足下列条件 则称为一个域 (Feild) 。 a,b,c,d,e,a-1 G。在加法下为一个交换群，满足自闭性，交换律，结合律，单位元为 0，逆元。 在乘法下为一个交换群，满足非零元素自闭性，交换律，结合律，单位元，逆元。 在加法乘法下满足分配律，有限域 ：域中的元素个数 m 称为域的阶， 有限个元素的域称为有限域或叫作伽罗华域， 记为 GF(m) ，GF-Galois Field ，最小域 ： 一个域中最少包含加法单位元和乘法单位元两个元素，否则不能构成域。 例如：集合 0,1 在模二加法和乘法下构成一个二元有限域GF(2) 。素域：如果 p为一个素数，则正整数集合

29、 0,1,2, -1p ，在模 p 加法和乘法下为一个 阶数为 p 的域，称为素域，记为 GF(p) 。 GF(2) 为一个素域。+0123456001234561123456022345601例如： GF(7) 为一个素域，其运算如下： 模 7 加法0123456000000001012345620246135模 7 乘法5-9信息论讲义3345601244560123556012346601234534560 30 40 50 66 21 53 15 45 12 66 43 24321扩展域 ：对于任何一个正整数 m，可以将素域 GF(p) 扩展成有 pm个元素的域，称为域 GF(p)的扩

30、展域，记为： GF(pm) 。而且可以证明：任何有限域都是一个素域的扩展域。 有限域的特征 ：由于有限域 GF(q)在加法下是自闭的，因此，考虑其乘法单位元1 的加法运算， 1，1+1，1+1+1，, 1+1+1+1+1+.+1(k 个)，这些都是 GF(q)中的元素，而域 中的元素是有限个，因此必然存在两个正整数 m,n, mn ，使：mnn m1 1 or 1 0i 1i 1i 1或者说：必然存在一个最小的正整数 =n-m，我们称 为域 GF(q)的特征。二元域 GF(2)的特征 =2；素域 GF(p) 的特征 =p；有限域的特征是一个素数；循环群 ： 如果一个群存在一个元素，其各次幂构成

31、整个群，称为循环群。定理 ：有限域 GF(q)的非零元素构成一个循环群。设 a 是 GF(q) 中的一个非零元素， 由于 GF(q)的非零元素在乘法下为自闭的， 所以 a，a2， a3，也必然是 GF(q)中的非零元素，又因为 GF(q) 为有限元素，所以必然有一个最小的正 整数 n，使 an=1。这个正整数 n 称为元素 a 的阶。令 a 为有限域 GF(q) 的非零元素，则 aq-1=1 。令 a为有限域 GF(q)的非零元素，且 n 为 a的阶，则 q-1 一定能被 n 除尽。本原元 ：如果有限域 GF(q)中，非零元素 a的阶 n=q-1 ，就称 a为 GF(q)的本原元素。 本原元素

32、的各次幂构成有限域 FG(q) 的所有元素。每个有限域都有其本原元素。例如：有限域 GF(7)，域中元素为 0,1,2,3,4,5,6 ，其非零元素集合为 1,2,3,4,5,6 ，考虑 其中的非零元素 a=3，可知： 31=3，32=33=2，33=323=6，34=333=4，35=5 ，36=1 ，可 以看到 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

33、) 的多项式，因此我们重点介绍这部分的知识。域上多项式 ：如果多项式 f(x)=f 0+f 1x+f 2x2+ +fnxn 的系数取自二元有限域 GF(2) ，则称 f(x)为域 FG(2)上的多项式。 fi=0 或 fi=1;域上多项式计算 ： 加法：如果 f(x)=f 0+f1x+f 2x2+fnxn;g(x)=g0+g1x+g2x2+gnxn 则：f(x)+g(x)= (f 0+ g 0)+(f 1 +g1)x +(f 2 +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

34、)=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) 的结果可以写作：f (x) q(x) r(x)其中： q(x)=x 3+x2;g(x) g(x)3x +x+1r(x)=x 2+x+1;利用展转相除法(欧几里得除法) 32 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)除尽，

35、则称 g(x)为 f(x) 的因式； f(x) 为 g(x)的倍式。多项式的模运算 ： 如果 GF(2)上多项式， F(x),N(x),Q(x),R(x) 满足：F(x)N(x)Q(x)R(x)N(x)则称在模 N(x) 条件下， F(x)=R(x) 。不可约多项式 ：如果 f(x) 为 GF(2) 上的 m 次多项式，它不能被任何次数小于m，大于0 的多项式除尽，则称其为 GF(2) 上的不可约多项式，既约多项式。f(x)=x 3+x+1; f(x)=x 4+x+1; 均为不可约多项式。GF(2) 上的多项式若有偶数项，则一定可被 x+1 除尽。对于任意 m1,都存在 m 次不可约多项式。G

36、F(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 次本原多项式是不唯一的。22性质：对于 GF(2)上的多项式 f(x) ，有f(x) 2=f(x 2)。5-4-4 GF(2) 上的矢量空间域上矢量空间 ：令V是一个矢量集合，在其上定义一个加法运算。令F 是一个域，在域中的元素和 V 中的元素之间定义了一个乘法运算。如

37、果集合 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; 满足结合律： (a?b) ?Vi=a?(b?Vi);F 中的单位元为 1，1?Vi=Vi。V 中的单位元为 0 矢量。域上矢量空间的性质 ：0 为 F 上的零元，则 0?Vi=0;c为 F 上的任意标量，则 c?0=0;c为 F上的任意标量和 V中的任意矢量 Vi ， (-c) ?Vi=c?(

38、-Vi)=- (c?Vi);5-11信息论讲义GF(2) 上的矢量空间 ：一个有 n 个分量的序列；(a0,a1, an-1) 其中每个分量是二元域上的元素 (ai=0,1)，这个序列称为 GF(2) 上的 n-重。GF(2)上共有 2n个 n-重。令 V n表示这 2n个 n-重的集合，则可以证明 Vn是 GF(2)上的 一个矢量空间。例如： n=5, GF(2)上的 5-重矢量空间 V 5由 32 个矢量组成。(00000),(00001), (11。111)这个空间中任意两个矢量之和仍然是这个空间中的矢量。GF(2)中的元素 0，1 乘上空间中的任意矢量仍然是这个空间中的矢量。V 的子空间 ：如果 V 是 F 上的矢量空间， V 的一个子集也是 F 上的一个矢量空间，则称 S 为V 的 一个子空间。例如： V 5上的子集， (00000),(00111),(11010),(11101) 为一个子空间。线性组合 ：令 V1,V2, Vk是 F 上矢量空间 V 中的 k 个矢量。令 a1,a2ak是 F 中的 k 个标量。则 : a1V1+a2V2+ +akV k称为的线性组合。如果：除非 a1=a2= =ak=0, 否则 a1V1+a2V2+akVk0；则称 V1,V2, Vk是线性独立的。