[理学]第3章 线性分组码.ppt

第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］线性分组码的一个码字。 若每位码元的取值有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∈GF(q)。 例3.1 n =7， k =3的［7， 3］线性分组码的8个码字和信息组如表 3 - 1所示。 这8个码字在模2加法运算下构成一个阿贝尔加群。 由于线性分组码是分组码的一类， 因此第一章中有关分组码的参数， 如码率R=k ／n 、 码字的距离与码的最小距离、 码字的重量等定义， 以及说明最小距离与纠错能力之间关系的定理1.3.1， 对线性分组码均适用， 这里不再赘述。 显然， R和d是分组码的两个最重要的参数， 因此今后我们用［n ， k ， d］(或［n ， k ］)表示线性分组码。 而用(n ， M， d)表示码字数目为M的任何码， 此时码率R=n –1 logqM。 ［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 ， d］分组码的最小距离必等于码中非零码字的最小重量， 由此可得如下定理。 定理3.1.2 GF(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.1 GF(2)上线性分组码任3个码字C1， C2， C3之间的汉明距离， 满足以下三角不等式 d(C1， C2)+d(C2， C3)≥d(C1， C3) (3.1.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］线性分组码， 码字的重量或全部为偶数，