信息论与编码7.ppt

有关群的几个概念 交换群：如果群中定义的 * 运算满足交换律，即如果 ，则称该群为交换群。 群的阶：群所含元素的个数称为群的阶。 有限群：如果群的阶为有限值，则称该群为有限群，否则称为无限群。 7.2.2 子群 定义7.2 如果非空集合 本身也是一个群（与群G关于同一运算*），则 为G 的子群。 【例7.5】 对集合G = (1,?2,?3,?4,?5,?6,?7,?8, 9)定义模10加法运算，运算符号用 * 表示，模10加法运算结果如表7-1所示。可见，G是一个交换群，0为加法幺元。 定理7.1 有限群的子群的阶一定整除群的阶。 例7.5中生成元5在模10加法运算下构成子群G = {5,0} 。G 的阶2整除G 的阶10。 陪集分解的性质如下 （1）?完备性：可将整个群分解为若干陪集，一个元素也不剩，因为子群的阶整除群的阶。 （2）正交性：若 ，则 ， 。 7.4 线性码的纠检错能力 7.4.1 码的距离和重量 定义7.6 两个码字之间，对应位取值不同的个数，称为它们之间的汉明距 离，简称距离，用d（c1，c 2）表示。 定义7.7 码字中非零码元的个数，称为该码字的汉明重量，简称重量，用w（c）表示。 定义7.8 一个码的最小距离dmin定义为 (7－9) 定理7.2 线性分组码的最小距离等于其非零码字的最小重量。 根据定理，要得到码的最小距离，只要检查2k－1个非零码字的重量即可。 事实上，两个码字之间的距离表示了它们之间差别的大小。因此，一个线性分组码的最小距离是衡量码抗干扰能力的重要参数。码的最小距离愈大，其抗干扰能力愈强。 7.4.2 线性码的纠检错能力 以上定理是纠错码理论中最重要的基本定理之一，它说明了一个距离为d的线性分组码，既可用来纠正 个错误，又可用来检测e ? d－1个错误。 定理7.3 对于任一个（n，k）线性分组码，若要在码字内 ⑴ 检测e个错误，则要求码的最小距离d ? e＋1； ⑵ 纠正t个错误，则要求码的最小距离d ? 2t＋1； ⑶ 纠正t个错误同时检测e（? t）个错误，则要求d ? t＋e＋1。 * * 第七章 线性分组码 第七章 线性分组码 内容提要 线性分组码同时具有信息位分组和校验位与信息位呈线性关系两种特性。目前，几乎所有得到实际应用的纠错码都是线性的。本章首先介绍有关纠错码的基本概念，然后介绍抽象代数中与编码直接相关的基础知识，包括群及群的陪集分解，重点论述线性分组码的定义及其编译码理论，并介绍线性分组码的纠检错能力。最后介绍一种典型的线性分组码——汉明码。 7.1 纠错码的基本概念 l信源编码的目的是压缩冗余度，提高信息的传输速率。 l信道编码的目的是提高信息传输时的抗干扰能力以增加信息传输的可靠性。 香农第二定理指出，当信息传输速率低于信道容量时，通过某种编译码方法，就能使错误概率为任意小。目前已有了许多有效的编译码方法，并形成了一门新的技术——纠错编码技术。 这里所讲的纠错编码即信道编码，与信源编码一样都是一种编码，但两者的作用是完全不同的。 7.1.1 信道纠错编码 讨论码字序列c通过离散信道时发生的情况，信道分为无记忆信道和有记忆信道。 l在无记忆信道中，噪声对传输码元的影响是相互独立的，即每一个差错的出现与其前后是否有错无关,如图8.1。在无记忆信道中，错误是随机产生的，因此被称作随机错误，无记忆信道也被称为随机信道（random channel）。 图8.1 二进制对称信道 7.1.2 差错类型 有记忆信道中，各种干扰所造成的错误往往不是单个地，而是成群、成串地出现，表现出错误之间有相关性。图8.2就是这种信道的一个模型。 图8.2 有记忆信道模型 就实际信道而言，由于其干扰的复杂性，往往是两种错误并存。随机错误与突发错误并存的信道，称为组合信道或复合信道。 为了方便研究，将信息传输系统模型简化成图7.3所示的简化模型 图7.3 简化的信息传输系统模型 模型突出了以控制差错为目的的纠错码编码器和译码器，因此也称为差错控制系统。 7.1.3 差错控制系统模型及分类 在差错控制系统中使用的码按其纠错能力的不同可分为两种：检错码和纠错码。 能发现错误但不能纠正错误的