通信原理电子版讲义--信道编码(3).ppt

1、1,9.2 线性分组码,信道编码：研究各种编码的方法和译码的方法。,编码器是一对一的映射，译码器是多对一的映射 图中的编码器称做码 ，编码率是 。,2,线性分组码的主要性质,线性分组码: 信息位和校验位之间的监督关系是线性的 监督位能表示成信息的线性和形式 1。封闭性。任意两个码组的和还是许用的码组。 2。码的最小距离等于非零码的最小码重。 线性分组码: 码的校验矩阵（监督矩阵） 码的生成矩阵 生成矩阵G与监督矩阵H的关系 系统码与非系统码(码的等价性） 对偶空间 校验子S （伴随式、纠错）,3,问题：为了能纠一位错，k位信息至少需要多少位的监督 信息？如何设计？,回顾： 偶校验码的监督关系：

2、 S=1，传输出错； S=0，无误传输 上式称为监督关系，S称为校验子。 对于分组码(n,k)，如希望用r=n-k个监督位构造出r个监督方程式来指示一位错码的n种可能位置，纠正错误，则要求 或 。,4,举例:说明具体如何构造线性分组码,设:分组码(7,4)中，若要能纠正一位错码，要求监督码元数。现取如果取k=4，则可以确定n=7。 用3个校验子来确定传输的7个位置是否出错 假设传输时的码字为 如果 与错码的位置对应如下:,5,传输时的码字与错码的位置关系如下,6,根据上表 发送端编码时 ,信息位 监督位 ,根据信息位的取值按监督关系来确定 即:监督位应该使上三式的取值为0 得到：,7,给出信息

3、位 根据上式可以算出监督位 从而得到（7，4）的所有码组 ：,8,写成矩阵的形式,即,9,H就称为（7，4）码的校验矩阵（或监督矩阵）。 只要监督矩阵确定，则编码时信息位与监督位的关系就确定了。 线性分组码的设计实际上是如何设计监督矩阵的问题。 写成另一种矩阵形式 变换得到,10,G称为码的生成矩阵。 如知道生成矩阵同样可以确定编码的码组。 上例中： 其中,11,生成矩阵G与监督矩阵H的关系,线性分组码全部码字： 且 对于任何线性分组码而言，上述关系总是存在的：,12,例：如果输入码组为 0011，已知分组码的监督方程如下，求编码器输出码字。,解： 监督方程的矩阵形式：,13,监督矩阵 注：H

4、矩阵称为典型形式，各行一定是线性无关的。 一个非典型形式的经过运算可以化成典型形式，通过监督矩阵可以知道监督码和信息码的监督关系。,14,生成矩阵 通过生成矩阵可以得到生成码组。 如果输入码组为 0011,15,注：由这种方式得到的生成矩阵称为典型生成矩阵 由它产生的分组码必定为系统码 就是信息码字保持不变，监督位附加其后，每行一定是线性无关的，每行都是一个生成码组。,16,系统码与非系统码,假设信息位为: 编码后的码组为: 称这种码为系统码 系统码-编码后前k个就是信息位，后n-k是监督位。 如果不存在上述关系，则称为非系统码。 上例的（7，4）码是系统码 只有系统码才有关系 系统码和非系统

5、码都有性质,17,码的等价性,设两编码器，输出的码集合是C1、C2。 如 (1) C1、C2集合相同， (2) C1、C2只是变换了比特顺序。 称这两个编码器是等价的 等价性不涉及信息映射。 系统码可同一个非系统码等价（如果是线性的则一定能）， 线性码有可能同一个非线性码等价。,零空间、对偶码,若C是n维线性空间的一个k维子空间，则必存在一个的n-k维子空间H，它与C互为零空间。即CH，或CH=。 用校验矩阵H中行矢量张成的子空间是一个(n ,n-k)线性分组码，它与码C互为对偶码,19,对偶码,在 中任意找出k个线性不相关的向量就构成了一种（n，k）码。 任意找出（nk）个线性不相关的向量就

6、够成了一种（n，nk）分组码。 对（n，k）码，给定G则会有一个H和它对应，H的各行是 中的（nk）个线性不相关的向量，所以可以用来构造一个（n，nk）码，这个码叫做原来那个码的对偶码。 如果H和G（或者其行初等变换的结果）相等，则对偶码和原来的码是一样的，称自对偶。,20,校验子S与错误图样,假设我们发送的码组为C， 接收到的码组为Y， 则YCe 错误图样 发送 ，收到y， y中可能有些位置上和c不一样（有误码）。可以表示成YCe。向量e叫错误图案，它指示哪些位置有错（e中值为1的位置），哪些位置没有错（e中值为0的位置）。 错误图案e是 中的一个向量，有 个可能的图案。,21,校验子S（伴

7、随式）,伴随式只和错误图案e有关，和发送内容c无关，故可用于译码器判断出错的位置。 伴随式s是rnk维向量，总共有2k个不同的值。 如将接收到的Y按照设计的监督关系进行运算， 可以得到上例结果。 如设计使S的不同组合与错误e一一对应，则我们可以利用错误图样得到e ，从而进行纠错译码。,22,陪集,陪集 给定e就能算出一个 ，但e和s不是一一对应的。若某个e算出的伴随式是s，则对任意 ，也算出相同的s。也就是说，有个不同的e对应着相同的s。 把所有的e按其伴随式的值排成一个标准阵列（94页表9.2.1）。排法是：所有相同s的e排成一行（这一行的所有e构成的集合叫给定s所对应的陪集），每行中码重最小的（即错误最少的图案）排在第一个（这个e叫这个陪集的陪集首）,23,译码器工作过程,(1)计算s (2)根据s查出陪集首 （3）纠正错误,24,编码器与译码器,编码器,25,汉明码,汉明码监督位为 位，因此它可以组成 个可能情况，其中一个为无错。因此可以监督码位共 要纠正一个错误，必须满足 最小码距 如果 r 位监督位所组成的校正子码组与误码图样一一对应，这种码组称为完备码（取等号时）,26,扩展汉明码,如果在汉明码基础上，再加上一位对所有码字进行校验的监督位 监督码字由 r 位增加到 r+1 位 信息位不变 码长 码结构 纠 1 位错，检测 2 位错 如 （8，4），（16，11