第3章 线性分组码.ppt

《第3章 线性分组码.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3章线性分组码3.1线性分组码的基本概念3.2码的一致校验矩阵与生成矩阵3.3伴随式与标准阵列及其它译码3.4线性码的覆盖半径3.5由一个已知码构造新码的简单方法3.6用多个已知码构造新码的方法3.7线性码的重量分布与译码错误概率3.8线性码的纠错能力习题3.1线性分组码的基本概念第一章第三节已叙述了分组码的某些重要概念，如分组码的表示、码率、距离、重量等。如果我们把每一码字看成是一个n维数组或n维线性空间中的一个矢量，则可以从线性空间的角度，比较深入地讨论线性分组码。一个［n，k］线性分组码，是把信息划成k个码元为一段(称为信息组)，通过编码器变成长为n个码元的一组，作为［n，k］

2、线性分组码的一个码字。若每位码元的取值有q种(q为素数幂)，则共有qk个码字。n长的数组共有qn组，在二进制情况下，有2n个数组。显然，qn个n维数组(n重)组成一个GF(q)上的n维线性空间。如果qk(或2k)个码字集合构成了一个k维线性子空间，则称它是一个［n，k］线性分组码。定义3.1.1［n，k］线性分组码是GF(q)上的n维线性空间Vn中的一个k维子空间Vn,k。由于该线性子空间在加法运算下构成阿贝尔群，所以线性分组码又称为群码。为简单起见，今后若没有特别说明，所说的分组码均指线性分组而言，且用(cn-1，cn-2，…，c1，c0)表示［n，k］码的一码字，其中每一分量ci∈

3、GF(q)。例3.1n=7，k=3的［7，3］线性分组码的8个码字和信息组如表3-1所示。这8个码字在模2加法运算下构成一个阿贝尔加群。信息组码字00000101001110010111011100000000011101010011101110101001110101001111010011110100由于线性分组码是分组码的一类，因此第一章中有关分组码的参数，如码率R=k／n、码字的距离与码的最小距离、码字的重量等定义，以及说明最小距离与纠错能力之间关系的定理1.3.1，对线性分组码均适用，这里不再赘述。显然，R和d是分组码的两个最重要的参数，因此今后我们

4、用［n，k，d］(或［n，k］)表示线性分组码。而用(n，M，d)表示码字数目为M的任何码，此时码率R=n–1logqM。［n，k，d］分组码是一个群码，因此若码字C1∈［n，k，d］、C2∈［n，k，d］，则由群的封闭性可知，码字C1与C2之和C1+C2∈［n，k，d］，即C1+C2也必是［n，k，d］分组码的一个码字。所以，两码字C1和C2之间的距离d(C1，C2)必等于第三个码字C1+C2的汉明重量。如例3.1中的两个码字：(1010011)，(1101001)，它们之间的距离是4，它就是(0111010)码字的重量，即d(C1，C2)=w(C1+C2)因此，一个［n，k

5、，d］分组码的最小距离必等于码中非零码字的最小重量，由此可得如下定理。定理3.1.1［n，k，d］线性分组码的最小距离等于非零码字的最小重量。定理3.1.2GF(2)上［n，k，d］线性分组码中，任何两个码字C1，C2之间有如下关系：w(C1+C2)=w(C1)+w(C2)-2w(C1·C2)(3.1.1)或d(C1，C2)≤w(C1)+w(C2)(3.1.2)式中，C1·C2是两个码字的内积。请同学自己证明。推论3.1.1GF(2)上线性分组码任3个码字C1，C2，C3之间的汉明距离，满足以下三角不等式d(C1，C2)+d(C2，C3)≥d(C1，C3)(3.1.

6、3)证明设码字Ca=C1+C2，Cb=C2+C3，由式(3.1.2)可知：w(Ca+Cb)=w(C1+C2+C2+C3)=w(C1+C3)=d(C1，C3)≤w(Ca)+w(Cb)=w(C1+C2)+w(C2+C3)。所以d(C1，C3)≤d(C1，C2)+d(C2，C3)定理3.1.3任何［n，k，d］线性分组码，码字的重量或全部为偶数，或者奇数重量的码字数等于偶数重量的码字数。证明略。§3.2码的一致校验矩阵与生成矩阵一、码的校验矩阵与生成矩阵［n，k，d］分组码的编码问题就是在n维线性空间Vn中，如何找出满足一定要求的，有2k个矢量组成的k维线性子空间Vn，k。或者说，在

7、满足给定条件(码的最小距离d或码率R)下，如何从已知的k个信息元求得r=n-k个校验元。这相当于建立一组线性方程组，已知k个系数，要求n-k个未知数，使得到的码恰好有所要求的最小距离d。上例中的［7，3，4］码，若c6，c5，c4代表3个信息元，则c3，c2，c1，c0这4个校验元，可由以下线性方程组求得：1·c3=1·c6+0·c5+1·c41·c2=1·c6+1·c5+1·c41·c1=1·c6+1·c5+0·c41·c0=0·c6+