通信原理II第4次课课件

1、10.3 线性分组码10.3.1 线性分组码的基本概念1.线性分组码的概念(1) 分组码线性分组码中的分组是对信息序列的处理方法而言，即编码时将信息序列每位分为一组，编码器对每组的位信息按一定的规律产生个监督码，输出长度为的码组（码字）。对于分组码，每一码组的(即)个监督码仅与本码组的个信息码有关，与其他码组的信息无关。(2) 线性码 线性分组码中的线性是指码组中监督码与信息码的关系，线性码码组中任一码元都是信息码元的线性组合。 2.线性分组码的性质下面通过举例来认识和了解线性分组码及其性质。例10.3.1 (7,4)二进制线性分组码的输入信息组（又称信息段）是m,编码输出A，已知码组到信息间

2、的映射关系为求输出码组集合（这里，“+”指模二加）。 解：将由线性方程组描述的输入输出码元之间的线性变换关系改写成矩阵形式：A （模2加）= mG 码长的码组有种组合，而4位的信息组只有种组合，对应16个码组。可见，该(7,4)线性分组码仅有16个许用码组。分别令信息组为（0000），（0001），（1111），代入上面的矩阵算式，不难算得各信息组对应的码组，列于表10.3.1 。 表10.3.1 (7,4)线性分组码码组集合信息位监督位信息位监督位0000000100100011010001010110011100001110111011010101100010001001101010111

3、100110111101111111100010001001010100111表10.3.1 反映出线性分组码所具备的基本性质： (1) 一个线性分组码共有个（许用）码组；(2) 对加法满足封闭性，即线性分组码中任意两个码组之和（模2加）仍是分组码中的一个码组；(3) 全零码是线性分组码中的一个码组；(4) 线性分组码各码组之间的最小码距，等于除全零码外的码组的最小重量。10.3.2 生成矩阵及其特性在例10.3.1的编码过程中，核心的因素是矩阵G，它决定了变换规则，也决定了码组集合和性质。不失一般性，令是一组（个）二进制信息码元，它可看成是一个的矩阵m，或 m。编码后，输出码组长度增大到,通

4、常将码组写成通式A。则线性分组码的编码运算通常用矩阵形式表示为：A = mG （10.3.1）式中，G称为该码的生成矩阵，是（行列）阶矩阵： G （10.3.2）其中，系数，；表示第个信息元对第个码元的影响。 如例10.3.1中的生成矩阵G是阶矩阵；G中系数为1表示信息元对码元会产生影响，系数为0表示无影响。如G中的第5列是，表示对产生影响，而对无影响。归纳起来，生成矩阵G具有以下特性：(1) 线性分组码的每个码组都是生成矩阵G各行矢量的线性组合。因为按分块矩阵运算法则将式（10.3.2）展开，可得 A （10.3.3）或 （10.3.4）在例10.3.1中，有 A(2) 生成矩阵G的各行本身

5、就是一个码组，且它们是线性无关的。由特性(1)和(2)得到的启示是：如果已有个线性无关的码组，则它们的线性组合就能产生个码组所构成的集合。(3) 如果生成矩阵G具有的形式，其中为阶单位方阵，Q是阶矩阵，则称G为典型生成矩阵。由典型生成矩阵得出的码组称为系统码。在本章，系统码的码组中前个是信息位，后是监督位，如图10.1.3所示。如例10.3.1中，生成矩阵能分解成G (4) 非典型生成矩阵可以通过线性代数中的任何一种初等行变换和列交换，得到典型生成矩阵。10.3.3 监督矩阵及其特性若将例10.3.1中的监督位线性方程组表示成 （10.3.5）即 （10.3.6）写成矩阵形式 （模2加） （1

6、0.3.7） 令则有 或 （10.3.8）我们将H称为监督矩阵（又称校验矩阵）。推广到维一般情况，H是一个阶矩阵。监督矩阵H的特性是：(1) 线性分组码的任意码组A正交于监督矩阵H的任意一个行矢量，即 （10.3.9）(2) 监督矩阵H的各行是线性无关的。(3) 若H，其中是阶矩阵，为阶单位方阵，则称H矩阵为典型阵。(4)监督矩阵H与生成矩阵G的关系对任何线性分组码（系统码或非系统码），总是存在下列关系： 或 （10.3.10） 即监督矩阵H的行与生成矩阵G的行正交。只有系统码才有关系： 或 （10.3.11） 这时，生成矩阵G与监督矩阵H可以互相转换。10.3.4编码和译码1. 系统码编码（

7、略）2. 译码线性分组码的译码是以码组为单位、通过检测收发码组之间的差异来发现或纠正错误的。(1) 错误图样设编码器输出码组A，接收端的接收码组B，则由信道干扰引起的收、发码组之间的差异可表示成B = A + E （10.3.12）式中，E，当时，表示该位接收码元无错；若，则表示该位接收码元有错。我们把这个错码矢量称为错误图样。错误图样表征了收发码组之间的差异，因此，虽然事先并不知道发送码组A，但是，如果译码器能推测出错误图样是，那就可以给出译码结果为 （10.3.13）(2) 校正子与译码为找出，定义校正子（又称伴随式）S为 （10.3.14）将式（10.3.13）代入式（10.3.14）中

8、可得 （10.3.15）利用式（10.3.9）所示码组与监督矩阵的正交性，所以 （10.3.16）上式表明，校正子S的值只取决于错误图样E，而与发送什么码组A无关。如果想要推测出错误图样是什么，可以从校正子入手，并且，当给定S时，可能的错误图样一定是方程（10.3.16）的解。(3) 译码过程译码过程可描述为： 利用式，计算校正子。如果，则表明接收码组与监督矩阵正交，即，可断定接收码组就是发送码组；如果，转入步骤。 由校正子S求错误图样E若S与E之间一一对应，则可能的错误图样一定是方程的解。此时，校正子的组合数目不少于可纠正错误图样的数目（参见例10.3.2）；若方程有多解，则可以运用概率译码

9、的处理方法选择错误图样的估值。 利用关系式，由错误图样估值求发送码组估值。上述译码过程的框图如图10.3.2所示。图10.3.1 译码过程示意图(4) 概率译码注意，方程组（10.3.16）中有个未知数，却只有个方程，可知方程的解E是不唯一。式（10.3.16）的解一共有个，记其为，由此带来的后果是，由确定S后，可能的译码结果也是个，它们是，。那么究竟取哪一个作为错误图样E的解呢？这里，介绍一种叫做概率译码的处理方法，它是把所有个解的重量（错误图样E中1的个数）做比较，选择最轻者作为E的估值。这种算法的理论根据是：若二进制对称信道（BSC）的差错概率是，则长度为的码中错1位（对应于E中有一个1

10、或E的重量为1）的概率是，错2位的概率是以此类推。由于，必有 （10.3.17） 所以，在E的个解中取重量最小的E时，译码正确的概率最大。由于E=B+A即收、发码之间的汉明距离，E重量最小，就是B和A的距离最小，所以概率译码实际上体现了最小距离译码法则。10.3.5 汉明码汉明码是一类能纠正单个随机错误的线性分组码，其最小码距。汉明码具有如下特性：(1) 二进制汉明码应满足条件： （10.3.18）式（10.3.18）的左边为校正子的组合数目，右边是无错传输（毫无疑问仅一种情形）与可纠正错误图样数目（因汉明码纠错能力，所以）之和。因此，汉明码的校正子和可纠正错误图样是一一对应的，即式中的S与E

11、之间一一对应。(2) 令，则利用关系式（10.3.18），汉明码码长和信息位可表示成：，于是当时，分别有（7，4），（15，11），（31，26），（63，57），（127，120），（255，247），是汉明码。(3) 汉明码的编码效率，当码长很大时，接近于1，所以汉明码是一类高效率的纠错码。(4) 个单个错误的校正子就是监督矩阵H矩阵的每一列。H矩阵所具有的这种特殊性质，使得能以相对简单的方法来构造汉明码。例10.3.2 已知(7,4)汉明码的监督矩阵为H=1) 试求校正子的组合数目、可纠正错误图样数目。2) 验证该(7,4)码符合由校正子来指示一位错码位置的要求，并列出校正子与可纠正错误

12、图样的对应关系。3) 若接收码组是(1100100)，写出校正子，同时指出发生一位错码的位置。解：1) ，。校正子的组合数目是，可纠正错误图样数目为。2) 一般来说，如果希望用维校正子矢量来指示一位错码的种可能位置，则要求：或对于码长的编码，为了纠正一位错码，则；或者若取值为3，则，显然本例符合由校正子来指示一位错码位置的要求。利用关系式，不难求得校正子与可纠正错误图样的对应关系，列表如下：校正子S可纠正错误图样E111110101011100010001 1000000 0100000 0010000 0001000 0000100 0000010 0000001不难看出，将除全零外的其余校正子组合排列起来就是监督矩阵。且排列顺序不同，所得矩阵也就不同，说明H矩阵不是唯一的，也不一定是