《西电纠错码课件---第三章线性分组码》课件.ppt

第三章 线性分组码 要求掌握的内容 线性分组码的定义及性质 码的一致校验矩阵和生成矩阵 码的伴随式、标准阵列及译码 汉明码及译码 RM码的基本原理 格雷码的基本编译码原理 3.1 线性分组码基本概念 线性空间 线性分组码定义 线性分组码的生成矩阵 线性分组码的校验矩阵 对偶码、系统码和缩短码 汉明码 一、线性空间(p38) 定义1(线性空间)：如果域F上的n重元素集合V满足下述条件，称V是域F上的一个n维线性空间： 1) V 关于加法构成阿贝尔群 2) 对于V中的任意元素v和F中任意元素c(纯量或标量)，cv一定属于集合V(数乘运算) 3) 分配律成立 c(u+v)=cu+cv,(c+d)v=cv+dv 4) 结合律成立 (cd)v=c(dv) 定义2(域F上的线性组合) 定义3(线性相关和线性无关) 定义4(张成)：给定线性空间V和V中的一个子集S，若V中的任意一个矢量均可用S中的矢量线性组合生成，则称S张成了矢量空间V。 定义5(基底和维数)：给定线性空间V，能张成该空间的线性独立矢量的集合称为V的基底，而线性独立矢量的数目称为V的维数 零空间(P48)：若V1是n维空间V的子空间，则和V1中每一个n维矢量均正交的所有矢量，构成V的另一个子空间V2，称V2为V1的零空间。 若n维空间V的子空间V1的维数为k，则V1的零空间的维数为n-k。 二、线性分组码的定义（p52） 定义3.1.1 ［n， k］线性分组码是GF(q )上的n维线性空间Vn中的一个k维子空间Vn,k。 由于该线性子空间在加法运算下构成阿贝尔群， 所以线性分组码又称为群码。 用(cn-1， cn-2， …， c1， c0)表示［n， k］码的一码字， 其中每一分量ci∈GF(q)。 二、线性分组码的定义（p52） 如果一个线性分组码的码字可分成消息部分和冗余部分，其中消息部分是k个未经处理的原始消息，冗余部分是产生的校验位，则该类码称为线性系统分组码 注： 生成矩阵G中的每一行都是一个码字 任意k个线性独立的码字都可以作为生成矩阵 给定一个[n,k,d]线性分组码，其生成矩阵可有多个 四、线性分组码的一致校验矩阵 ［n ， k ， d］分组码的编码问题就是在n 维线性空间Vn 中， 如何找出满足一定要求的， 有2k 个矢量组成的k 维线性子空间Vn， k 。 或者说， 在满足给定条件(码的最小距离d或码率R)下， 如何从已知的k 个信息元求得r=n -k 个校验元。 若用矩阵形式，这些线性方程组可表示为： 称上式中的4行7列矩阵为［7， 3， 4］码的一致校验矩阵， 通常用H 表示， 该码的 线性分组码的校验矩阵是一个(n -k )×n 阶矩阵。 由校验矩阵可以很快地建立码的线性方程组： 或 注： 1)校验矩阵是一个(n -k )×n阶的矩阵，各行之间是线性无关的，即 校验矩阵的行秩为n-k 2) 校验矩阵的n-k行为基底，可张成一个n-k维线性子空间 3) 任意一个合法码字C均满足 HCT=0T 4) 交换校验矩阵的各列并不影响其纠错能力 假设 c6=1， c5=0， c4=1， 求c3， c2， c1， c0。 由上述线性方程组可知：  c3=c6+c4=1+1=0 c2=c6+c5+c4=1+0+1=0 c1=c6+c5=1+0=1 c0=c5+c4=0+1=1 由此得到的码字为： (1010011)。 1)对于任一个[n,k]线性分组码，存在一个k)×n阶的生成矩阵G，其行空间为码C，即该线性分组码的所有的码字都可由生成矩阵获得。 2) 同时，该分组码还存在一个(n -k )×n阶的校验矩阵，使得当且仅当 时，n维向量v是线性分组码的一个码字。任意一个合法码字C均满足 HCT=0T 。 校验矩阵与生成矩阵之间的关系 校验矩阵H与任意一个码字之积为零，因此有 五、线性分组码的最小汉明距离 定理3.1.1 ［n ， k ， d］线性分组码的最小距离等于非零码字的最小重量。 定理3.1.2 GF(2)上［n ， k ， d］线性分组码中， 任何两个码字C1， C2之间有如下关系： w(C1+C2)=w(C1)+w(C2)-2w(C1·C2) 或 