数字通信原理第8次课课件(2015)

110.3线性分组码10.3.1线性分组码的基本概念1.线性分组码的概念(1)分组码kn,线性分组码中的分组是对信息序列的处理方法而言，即编码时将信息序列每k位分为一组，编码器对每组的k位信息按一定的规律产生r个监督码，输出长度为nkr的码组（码字）。对于分组码，每一码组的r(即nk)个监督码仅与本码组的k个信息码有关，与其他码组的信息无关。(2)线性码线性分组码中的线性是指码组中监督码与信息码的关系，线性码码组中任一码元都是信息码元的线性组合。2.线性分组码的性质下面通过举例来认识和了解线性分组码及其性质。例10.3.1(7,4)二进制线性分组码的输入信息组（又称信息段）是m0123mmmm,编码输出A0123456aaaaaaa，已知码组到信息间的映射关系为oooommmammmammmamamamama1323112323142536监督位信息位求输出码组集合（这里，“+”指模二加）。解：将由线性方程组描述的输入输出码元之间的线性变换关系改写成矩阵形式：A00010110010101010011010001110123mmmm（模2加）=mG码长7n的码组有12827种组合，而4位的信息组只有1624种组合，对应16个码组。可见，该(7,4)线性分组码仅有16个许用码组。分别令信息组20123mmmm为（0000），（0001），…，（1111），代入上面的矩阵算式，不难算得各信息组对应的码组，列于表10.3.1。表10.3.1(7,4)线性分组码码组集合信息位监督位信息位监督位3456aaaa00000001001000110100010101100111012aaa0000111011101101010110003456aaaa10001001101010111100110111101111012aaa111100010001001010100111表10.3.1反映出线性分组码所具备的基本性质：(1)一个kn,线性分组码共有k2个（许用）码组；(2)对加法满足封闭性，即线性分组码中任意两个码组之和（模2加）仍是分组码中的一个码组；(3)全零码是线性分组码中的一个码组；(4)线性分组码各码组之间的最小码距，等于除全零码外的码组的最小重量。10.3.2生成矩阵及其特性在例10.3.1的编码过程中，核心的因素是矩阵G，它决定了变换规则，也决定了码组集合和性质。不失一般性，令011,,mmmk是一组（k个）二进制信息码元，它可看成是一个k1的矩阵m011mmmk，或m011mmmk。编码后，输出码组长度增大到n,通常将码组写成通式A01,1aaan。则线性分组码的编码运算可以用矩阵形式表示为：A011,,,aaan000110101111011111011gggggggggmmmnnkknkk=mG（10.3.1）3式中，G称为该码的生成矩阵，是nk（k行n列）阶矩阵：G000110101111011111011ggggggggggggnnkknkTk（10.3.2）其中，系数0,1ijg，1,,1,0ik（；1,,1,0)jn表示第i个信息元im对第j个码元的影响。如例10.3.1中的生成矩阵G是47阶矩阵；G中系数为1表示信息元对码元会产生影响，系数为0表示无影响。如G中的第5列是1110T，表示321mmm对2a产生影响，而0m对2a无影响。归纳起来，生成矩阵G具有以下特性：(1)线性分组码的每个码组都是生成矩阵G各行矢量的线性组合。因为按分块矩阵运算法则将式（10.3.2）展开，可得A001111gmgmgmkk（10.3.3）或0,1,,1,0011,11njgmgmgmajjjkkj（10.3.4）在例10.3.1中，有A00010110010101010011010001110123mmmm(2)生成矩阵G的各行本身就是一个码组，且它们是线性无关的。由特性(1)和(2)得到的启示是：如果已有k个线性无关的码组，则它们的线性组合就能产生k2个码组所构成的集合。(3)如果生成矩阵G具有QIk的形式，其中kI为k阶单位方阵，Q是knk阶矩阵，则称G为典型生成矩阵。由典型生成矩阵得出的码组称为系统码。在本章，系统码的码组中前k个是信息位，后kn是监督位，如图10.1.3所示。如例10.3.1中，生成矩阵能分解成G01110111011100010010010010004(4)非典型生成矩阵可以通过线性代数中的任何一种初等行变换和列交换，得到典型生成矩阵。10.3.3监督矩阵及其特性若将例10.3.1中的监督位线性方程组表示成346035614562aaaaaaaaaaaa（10.3.5）即000034613562456aaaaaaaaaaaa（10.3.6）写成矩阵形式0001011001110101011101000123456aaaaaaa（模2加）（10.3.7）令101100111010101110100H则有0THA或0TAH（10.3.8）我们将H称为监督矩阵（又称校验矩阵）。推广到n维一般情况，H是一个nkn阶矩阵。监督矩阵H的特性是：(1)线性分组码的任意码组A正交于监督矩阵H的任意一个行矢量，即0TAH（10.3.9）(2)监督矩阵H的各行是线性无关的。(3)若HrIP，其中P是nr阶矩阵，rI为r阶单位方阵，则称H矩阵为典型阵。(4)监督矩阵H与生成矩阵G的关系5·对任何线性分组码（系统码或非系统码），总是存在下列关系：0THG或0TGH（10.3.10）即监督矩阵H的行与生成矩阵G的行正交。·只有系统码才有关系：TPQ或TQP（10.3.11）这时，生成矩阵G与监督矩阵H可以互相转换。10.3.4编码和译码1.系统码编码（略）2.译码线性分组码的译码是以码组为单位、通过检测收发码组之间的差异来发现或纠正错误的。(1)错误图样设编码器输出码组A011,,,aaan，接收端的接收码组B011,,,bbbn，则由信道干扰引起的收、发码组之间的差异可表示成B=A+E（10.3.12）式中，E011,,,eeen，当0ie时，表示该位接收码元无错；若1ie，则表示该位接收码元有错。我们把这个错码矢量称为错误图样。错误图样表征了收发码组之间的差异，因此，虽然事先并不知道发送码组A，但是，如果译码器能推测出错误图样是E，那就可以给出译码结果为A=B+E（10.3.13）(2)校正子与译码为找出E，定义校正子（又称伴随式）S为TknBHsssS011,,,（10.3.14）将式（10.3.13）代入式（10.3.14）中可得TTTEHAHHEAS（10.3.15）利用式（10.3.9）所示码组与监督矩阵的正交性，所以TEHS（10.3.16）上式表明，校正子S的值只取决于错误图样E，而与发送什么码组A无关。如果想要推测出错误图样是什么，可以从校正子入手，并且，当给定S时，可能的错误图样一定是方程（10.3.16）的解。6(3)译码过程图10.3.1译码过程示意图译码过程可描述为：①利用式TSBH，计算校正子。·如果0S，则表明接收码组与监督矩阵正交，即0TBH，可断定接收码组就是发送码组；·如果0S，转入步骤②。②由校正子S求错误图样E。·若S与E之间一一对应，则可能的错误图样一定是方程TEHS的解。此时，校正子的组合数目不少于可纠正错误图样的数目（参见例10.3.2）；·若方程TEHS有多解（解E是不唯一），则可以运用概率译码的处理方法选择错误图样的估值。③利用关系式EBA，由错误图样估值ˆE求发送码组估值ˆA。上述译码过程的框图如图10.3.2所示。(4)概率译码注意，方程组（10.3.16）中有n个未知数011,,,eeen，却只有kn个方程，可知它有多解（解E是不唯一）。式（10.3.16）的解一共有k2个，记其为1210,,,KEEE，由此带来的后果是，由TBH确定S后，可能的译码结果也是k2个，它们是00EBA，11EBA，1212,KKEBA。那么究竟取哪一个作为错误图样E的解呢？这里，介绍一种叫做概率译码的处理方法，它是把所有k2个解的重量（错误图样E中1的个数）做比较，选择最轻者作为E的估值。这种算法的理论根据是：若二进制对称信道（BSC）的差错概率是p，则长度为n的码中错1位（对应于E中有一个1或E的重量为1）7的概率是11npp，错2位的概率是,,122npp以此类推。由于1p，必有nnnppppp22111（10.3.17）所以，在E的k2个解中取重量最小的E时，译码正确的概率最大。由于E=B+A即收、发码之间的汉明距离，E重量最小，就是B和A的距离最小，所以概率译码实际上体现了最小距离译码法则。10.3.5汉明码汉明码是一类能纠正单个随机错误的线性分组码。汉明码具有如下特性：(1)二进制汉明码应满足条件：nkn12（10.3.18）式（10.3.18）的左边为校正子的组合数目，右边是无错传输（毫无疑问仅一种情形）与可纠正错误图样数目（因汉明码纠错能力1t，所以nCCntn1）之和。因此，汉明码的校正子和可纠正错误图样是一一对应的，即式TEHS中的S与E之间一一对应。(2)令knm，汉明码n和k服从关系式：码长12mn，信息位mkm12，最小码距3mind。当,8,7,6,5,4,3m时，分别有（7，4），（15，11），（31，26），（63，57），（127，120），（255，247），…是汉明码。(3)汉明码的编码效率nmnk1，当码长n很大时，接近于1，所以汉明码是一类高效率的纠错码。(4)n个单个错误的校正子就是监督矩阵H矩阵的每一列。H矩阵所具有的这种特殊性质，使得能以相对简单的方法来构造汉明码。例10.3.2已知(7,4)汉明码的监督矩阵为H=1110100110101010110011)试求校正子的组合数目、可纠正错误图样数目。2)验证该(7,4)码符合由校正子来指示一位错码位置的要求，并列出校正子与可纠正错误图样的对应关系。3)若接收码组是(1100100)，写出校正子，同时指出发生一位错码的位置。8解：1)7n，4k。校正子的组合数目是3228nk，可纠正错误图样数目为7n。2)一般来说，如果希望用nk维校正子矢量来指示一位错码的n种可能位置，则要求：21nkn或21nkn本例中28nk、7n，显然符合由校正子来指示一位错码位置的要求。利用关系式TEHS，不难求得校正子与可纠正错误图样的对应关系，列表如下：校正子S可纠正错误图样E1111101010111000100011000000010000000100000001000000010000000100000001不难看出，将除全零外的其余校正子组合T001T010…T111排列起来就是监督矩阵。且排列顺序不同，所得矩阵也就不同，说明H矩阵不是唯一的，也不一定是典型的。3)TSBH=1111101011100100011=101100010001