第三章_线性分组码

1、第四章线性分组码第四章 4.1 线性分组码基本概念 4.2 生成矩阵和校验矩阵 4.3 伴随式与译码 4.4 码的纠、检错能力与MDC码 4.5 完备码与汉明码 4.6 扩展码、缩短码与删信码 4.7 分组码的性能限 （n,k）线性分组码是把信息流的每k个码元（symbol）分成一组， 通过线性变换，映射成由n个码元组成的码字（codeword）。从空间的 角度，每个码字可以看成是n维线性空间中的一个矢量，n个码元正是n 个矢量元素。码元取自字符集X= 当q=2时是二进制 码，q2时是q进制（q元）码。多进制q一般取素数或素数的幂次，实 用中多见的是q=3或q= (b是正整数)。当q= 时，每

2、码元可携带b bit 信息，长度为n的q元分组码码字可以映射成长度N=bn的二元分组码码 字。 纠错编码的任务是在n维n重矢量空间的 种组合中选择个 构成 一个子空间，或称许用码码集C，然后设法将k比特信息组一一对应的映 射到许用码码集C。不同的编码算法对应不同的码集C以及不同的映射 算法，把这样的码称为(n,k)线性分组码。不编码时，一个二进制码元可 携带1b信息（传输率为1b/符号）；编码后，n个二进制码元携带kb信 息（传输率为（k/n）b/符号）。定义k/n= 为二元分组码的码率，或 者说是效率。 011,qxxx2b2b2n2kcR4.1 线性分组码基本概念 综上所述，编码算法的核心

3、问题是： 寻找最佳的码空间，或者等效地说，寻找最佳的一组（k个）基 底，以张成一个码空间。 k维k重信息组空间 的个矢量以何种算法一一对应的映射到k维n 重码空间C。 由于上述映射是两个线性空间之间的线性交换，“线性分组码”由此 得名。又因为这些矢量在加法运算下构成交换群，所以也称之为“群 码”。返回2k4.1 线性分组码基本概念 在讨论生成矩阵之前，先看一个例题。 例4.1 （6，3）二进制分组码的输入信息组是m=( ),码组输出是c=( )。已知输入、输出码元之间的关系式 是 ，求码集 C以及编码时的映射算法。 解：将关系式列成线性方程组，然后写成矩阵形式如下：210m m m54 3 2

4、 1 0c c c c c c52412211210020,cm cm cmm cmmm cmm5 4 3 2 1 0210100111)() 010110001011c c c c c cm m mcmG 5241302211210020cmcmcmcmmcmmmcmm4.2 生成矩阵和校验矩阵 二进制码取值于GF(2),6位二进制有 =64种组合，而3位的信息组只有8种组合，一一对应到8个码字。可见，码集C包含64种组合中的8种。分别令信息组 为（000），（001），（111），带入上面的矩阵算式，不难算得各信息组对应的码字如下表所示： 62210m m m信息组 ( ) 码字（ )00

5、0000000000001011010010110011011101100100111101101100110110001111111010210m m m54 3 2 1 0c c c c c c4.2 生成矩阵和校验矩阵 在以上编码过程中，核心的因素是矩阵G，它决定了变换规则，也决定了码集C。矩阵G可以看成是由3个行矢量组成的，所有码字是这3个行矢量的线性组合： 可以验证，这里的3个行矢量线性无关，可以作为基底张成一个三维6重的码空间，该空间是六维6重空间的子空间。 从上例得到的启示是：码集其实是一个子空间，只要找到一组合适的基底，它们的线性组合就能产生整个码集。 不失一般性，C也可以扩展

6、为k维n重码空间,即： c= =mG= 式中，G称为该码的生成矩阵，是k行n列矩阵：210(100111)(010110)(001011)cmmm1,10,ncc c 110110Tkkmm mgg g4.2 生成矩阵和校验矩阵4.2 生成矩阵和校验矩阵(1)(1)(1)1(1)01101(1)11100(1)0100knkkTknngggGgg ggggggg 其中 ,i=k-1, ,0,是G中第i行的行矢量。 与任何一个（n,k）线性码的码空间C相对应，一定存在一个对偶空 间D。事实上，码空间基底数k只是n维n重空间的全部n个基底的一部 分，若能找出另外n-k个基底，也就找到了对偶空间D。

7、既然用K个基底能 产生一个（n-k）线性码，那么也能用n-k个基底产生一个有 个码矢 的（n,n-k）线性码，称之为（n-k）线性码的对偶码。将D空间的n-k个 基底排列起来，可构成一个（n-k） n矩阵，称为码空间C的校验矩阵 H，它正是（n,n-k）对偶码的生成矩阵，它的每一行是对偶码的一个码 字。C和D的对偶是相互的，G和C的生成矩阵，又是D的校验矩阵；而H 是D的生成矩阵，又是C的校验矩阵。(1)10ii niiggg g2n k 由于C的基底和D的基底正交，空间C和空间D也正交，它们互为零空间。 因此，（n-k）线性码的任意码字c一定正交于其对偶码的任意一个码字，也必定正交于校验矩阵

8、H的任意一个行矢量，即 式中，0代表零阵，它是 全零矢量。 式 可以 用来检验一个n重矢量是否为码字：若等式成立（得零矢量），该n重必为码字，否则必不是码字。 由于生成矩阵的每个行矢量都是一个码字，因此必有： 这里，0代表一个尺寸为 的零矩阵。 验证H的方法是看它的行矢量是否与G的行矢量正交，即式 是否成 立。此处， 式中，两个相同的矩阵模2加后为全零矩阵。这就证明了H确实校验矩阵。0TcH 1()1 ()nnnknk 0TcH0TGH ()()knnnkknk0TGH4.2 生成矩阵和校验矩阵 0TTTkn kkn kGHIPPII PPIPP 例4.2 考虑一个（7，4）码，其生成矩阵是：

9、 对于信息组m=(1011),编出的码字是什么？ 画一个（7，4）分组码编码器原理图。 若接收到一个7位码r=(1001101),检验它是否码字？ 解：设输入信息组 ，编码后的码字 码集C。 由c=mG可知，将m和G的值代入，可得对应码字是 （1011000）。本题由于是系统码 ， ，前4位不必计 算，后3个校验位可以根据生成矩阵G的分块阵P列出现行方程组如下 41000101010011100101100001011GIP3210mm m m m6543210cc c c c c c c32102 1 0()cm m m m c c c232112100320 ( cmmmcmmmcmmm式

10、式中中“”指指模模2 2加加）4.2 生成矩阵和校验矩阵 将 代入方程组，得 。所以码 字为c=1011000。 一个二进制（n,k）系统线性分组码的编码器可用k级移存器和连接 到移存器适当位置（由P决定）的n-k个模2加法器组成。加法器生成校验 位后按顺序暂存在另一个长度为n-k的移存器。K比特信息组移位输进k级 移存器，加法器计算n-k校验比特，然后先是k位信息、紧接着是n-k位校 验比特从两个移存器中移位输出。本题的编码原理图如下： 0m1m2m3m0c1c2cS2100,0,0ccc32101,0,1,1mmmm4.2 生成矩阵和校验矩阵 首先是信息位 输入，再是 ， ， 顺序输入。编

11、码后， 开关S在输出前4位时上拨，先 再 顺序输出；输出后面3 位时，开关S下拨，将 顺序输出。 H矩阵如下： 根据式 ，如果接受到的r是属于码集C的某码字，必 有 ；反之，如 ，说明r必定不是码字。将H和 r=1001101代入式 ，得： 说明 r与H不正交，接收的r=(1001101)不是码字。返回 4.2 生成矩阵和校验矩阵3m2m1m0m2c0c3m2m0m1 1 1 0 1 0 00 1 1 1 0 1 01 1 0 1 0 0 1Tn kHP I0TcH0TrH0TrH0TcH1 (101)0 (111)0 (110) 1 (011) 1 (100)0 (010) 1 (001)(

12、011)(000)TrH 由于信道干扰的缘故，使得接收端的接受码R= 不一定等 于发送码C= ,定义差错图案E为： E= =R-C 差错图案是信道干扰图案的反应。对二进制码，模2加与模2减等同，因此 有： E=R+C 及 R=C+E 利用式 所示码字与校验矩阵的正交性 ,可通过下列运算 来判断接受码R是否有错： 如果接受码无误，必有R=C即E=0及 =0,此时上式满足 =0。 如果信道产生差错，必有 = 0。保持 不变，则 仅与差错图案E有关，而与发送什么码C无关。为此定义伴随式S为： 110(, ,)nrr r110(,)ncc c110111100(,)(,)nnnee ercrc rc0

13、TCH()0TTTTTTRHCE HCHEHEHEHTEHTRHTRHTEHTHTRH110(,)TTnkSsssRHEH0TCH4.3 伴随式与译码 从物理意义看，伴随式S并不反映发送的码字是什么，而只反应信道 对码字造成怎样的干扰。 可以看到：伴随式S是一个n-k重矢量，只有 种可能的组合；而差 错图案E是n重矢量，共有 个可能的组合。因此，同一伴随式可能对应 若干个不同的差错图案。 在接受端，并不知道发送码C究竟是什么，但可以知道 和接受码 R，从而算出S。译码最重要的任务是从伴随式S找出C的估值 ，具体方 法是：先算出S，再由S算出E，最后令 =R+E而求出： =S E =R+E 最关

14、键的是从S找出E,只要E正确，译出的码也就是正确的。 展开成线性方程组形式后：2n k2nTHCCTRHC(1)(1)(1)1(1)01101101(1)11100(1)0100(,)(,)n knn kn kTn knnnhhhSss sEHee ehhhhhh 4.3 伴随式与译码 会发现很难解，所以这里提供了在一般情况下构造标准阵列译码表的方法。 （1）第一步：用概率译码确定各伴随式对应的差错图案 （2）第二步：确定标准阵列译码表的第一列和第一行 （3）第三步：在码表的第j行第i列填入 11(1)(1)1(1)10(1)011 1(1)1 110 10010(1)101000n knn

15、knn kn knnnnsehe he hsehe he hsehe he h ijCE4.3 伴随式与译码 例4.3 某一个（5，2）系统线性码的生成矩阵 ,设接收码R=(10101),请先构造该码的标准阵列译码表，然后译出发送码 的估值 。 解：分别以信息组m=（00），（01），（11）及已知的G代入式： ，求得4个许 用码字为 。 由式 求得校验矩阵为：4.3 伴随式与译码C1011101101G110110110,TnkkccccmGmm mgg g1234(00000),(10111),(01101),(11010)CCCCTn kHPI 242322212031413121110

16、04030201001 1100100 101 100 1ThhhhhHPIhhhhhhhhhh 展开后得： 伴随式有8种组合；而差错图案除了代表无差错的全零图案外，代 表一个差错的图案有5种，代表两个差错的图案有10种。要把8个伴随式 对应到8个最轻的差错图案，无疑先应选择全零差错图案和5种一个差错 的图案。剩下的两个伴随式不得不在10种两个差错的图案中选取两个。 先将 代入上面的线 性方程组，解得对应的 分别是（000），（111），（101）， （100），（010），（001）。剩下的两个伴随式是（011）和 （110），每个有 种解，对应有 个差错图案。本例中，伴随式 （011）的4

17、个解（差错图案）是（00011），（10100），（01110）， （11001），其中（00011）和（10100）并列最小重量，只能选择其中之一作为解。24243232221210204321414313212111010410404303202101000430se he he he he heeese he he he he heese he he he he heee(00000),(10000),(01000),(00100),(00010),(00001)jE jS2k2k4.3 伴随式与译码 至此，根据4个码字和8个差错图案，画出标准阵列译码表如下所示： =000 =00000

18、 =10111 =01101 =11010 =111 =10000001111110101010 =101 =01000111110010110010 =100 =00100100110100111110 =010 =00010101010111111000 =001 =00001101100110011011 =011 =00011101000111011001 =110 =001101000101011111000S1S2S3S4S5S6S7S00EC2C4C3C1E2E3E4E5E6E7E4.3 伴随式与译码 若接收码R=(10101)，可用以下三种方法之一译码。 直接搜索码表，查得（1

19、0101)所在列的子集头是（10111），因此 取译码输出为（10111）。 可以先求伴随式，找到伴随式所在行数， 再搜索码表的第5行找到（10101），最后顺着该列向上找出码字 （10111） 先求出伴随式 ，在表中查出对应的陪首集（差 错图案） =（00010），再将陪集首与接收码相加，得到码字C=R+ =(10101)+(00010)=(10111)。返回 4(010)TRHS4E5E4.3 伴随式与译码4(10101)(010)TTRHHS4.4 码的纠、检错能力与MDC码 例4.3的（5，2）分组码中，如果码字有一位误码，译码后该差错能被纠正；如果有两位误码，可以检测出差错的存在，但

20、不一定能纠正它。显然，任何一种信道编码的纠、检错能力都有一定的限度，这种限度与码距有关的。为此，有必要引入相关的定义和定理，适用于GF(2)域。 汉明重量：n重矢量R中。非零元素的个数称为n重的汉明重量，简称重量，用w(R)表示。 汉明距离：逐位比较两个n重矢量 和 的对应各位，其中取值不同的元素的个数为 与 德汉明距离，用 表示 。 最小距离：分组码码集中，每两两码字之间都存在一定距离，其中最小者称为该分组码的最小距离，用符号 表示。1R2R2R1R12(,)d RRm ind 如直接计算最小距离，含 个码字的码集需计算 个距离后才能找出 。由于分组码是群码，利用群的封闭性，即两个码字之和仍

21、是码字 ，可得： 于是得以下定理。 定理4.1 线性分组码的最小距离等于码集中非零码字的最小重量，即 及 距离和重量除了上述关系外，还满足以下两个不等式： 这里采用符号R，是强调上面两式适用于一切n重矢量，而不限于码字。4.4 码的纠、检错能力与MDC码2k2 (21) / 2kkmind123()CCCC12123(,)()()d CCw CCw Cminmin() iidw CCC0iC 1312321212(,)(,)(,)()()()d R Rd R Rd R Rw RRw Rw R 定理4.2 对于任何最小距离为 的线性分组码，其检测随机差 错的能力为 。 定理4.3 对于任何最小距

22、离等于 的线性分组码，其纠正随机 差错的能力t为： 式中，INT.表示取整。 定理4.4 （n,k）线性分组码的最小距离等于 充要条件是：校 验矩阵H中有 列线性无关。 定理4.5 （n,k）线性分组码的最小距离必定小于等于n-k+1,即 返回mindmin1dmindmin12dtINTmin1dnkmindmin1d4.4 码的纠、检错能力与MDC码4.5 完备码与汉明码 4.5.1 完备码 4.5.2 汉明码 4.5.3 高莱码 返回4.5.1 完备码 二元（n,k)线性分组码的伴随式是一个n-k重矢量，有 个可能的组合。如该码的纠错能力是t，则对于任何一个重量小于等于t的差错图案，都应

23、有惟一的伴随式组合与之对应，才有可能实行纠错译码。也就是说，伴随式组合的数目必须满足条件： 这个条件称为汉明眼。任何一个纠t码都应满足汉明眼。 2n k02012tn kinnnnnti 如果某二元（n,k）线性分组码能使上式的等号成立，即该码的伴 随式组合数目恰好和不大于t个差错的图案数目相等，相当于在标准阵 列中能将所有重量不大于t的差错图案实现一一对应，娇艳位得到最充 分的利用。把满足方程： 的二元（n,k）线性分组码成为完备码（Perfect Code）。 迄今发现的二进制完备码有t=1的汉明码 、t=2德（23，12，7） 高莱（Golay）码，以及长度n为奇数、由两个码字组成且满足

24、 =n的任何二进制（n,1）码。已发现三进制完备码有t=2的 （11，6，5）高莱码。返回02tnkini4.5.1 完备码mind 纠错能力t=1的完备码称为汉明码（Hamming Code）。汉明码的校验矩阵H具有特殊的性质，使得能以相对简单的方法来构造码。 例4.4 构造一个m=3的二元（7，4）汉明码。 解：由题知，就是求出它的生成矩阵或它的校验矩阵。由于（7，4）汉明码的校验矩阵是3*7矩阵，而校验矩阵的行矢量不能为全零（零与任何码元的乘积为零，失去校验功能），因此H的7个行矢量正好是除全零矢量外3重矢量的全部可能组合。H不是惟一的，由于交换列不会影响最小距离，所以可通过列置换将最初

25、的H变为系统形式的H，称为系统汉明码： 得系统汉明码的生成矩阵G为：30 0 0 1 1 1 11 1 1010 00 1 10 0 1 10 1 1 10 1010 10 10 11 1 0 10 0 1THPI4.5.2 汉明码 得系统汉明码的生成矩阵G为： 上列中校验矩阵的构成方法具有一般性。由于H是（n-k）*n矩阵，可以看成由n个n-k重矢量构成。这样的行矢量除去全零后有 -1中可能的组合，由 =1+n知正好等于码长n。返回 2n k2n k41000101010011100101100001011GIP4.5.2 汉明码4.5.3 高莱码 高莱码（Golay）是二进制（23，12）

26、线性码，其最小距离 =7，纠错能力t=3。 由于满足 它也是完备码。在（23，12）码上添加一位奇偶位即得二进制（24， 12）扩展高莱码，其最小距离 =8。 必须指出，从伴随式与差错图案关系的角度来看，完备码是“好码”， 是标准阵列最规则，因而译码最简单的码，但它并不一定是纠错能力最强 的码。完备码强调了n,k和t的关系，保证 至少等于3（即t-1），但并 未强调 最大化，即达到极大最小局里码MDC中 的程度。换言 之，完备码未必是MDC码。比如，（63，57）汉明码可保证t=1,而按 MDC码的要求应有t=INT(63-57+1)/2=3,这才达到了极限纠错能力。 返回 mind23 12

27、232323220481123 mindmindmindmind4.6 扩展码、缩短码与删信码u4.6.1 扩展码u4.6.2 缩短码u4.6.3 删信码u u返回4.6.1 扩展码 如果给（n,k）分组码添加一个奇偶校验位，可得一个（n+1,k）扩展码。由于信息位k没变，码集包含的码字总数也不会变，只不过每个码字的长度增加1。对于码字 ，扩展后变为 若采用偶校验，校验位 的选择应满足校验方程： 从校验矩阵的角度看，扩展前校验矩阵是（n-k）*n矩阵H，扩展后的校验矩阵为（n-k+1）*（n+1）矩阵，多出了1行1列。 从最小距离角度看，若扩展前原码的最小距离 是奇数，即最轻码字中包含奇数个1

28、，则扩展后最轻码字的码重加1，扩展码的最小距离因此比原来增加1，变成 +1；若原码的最小距离是偶数，则偶校验不改变其最小距离。返回110, , ncc c110, ,ncc c c校校c校校1100ncccc校校mindmind4.6.2 缩短码 码字中的每个码元都是信息元 的线性组合。在生成矩阵一定的条件下，由于信息组中0与1结构对称、奇偶性对称，因此在二进制 (n,k, )分组码的 个码字中总有一半码字( 个)的第一位为0，而另一半码字的第一位为1。在第一位为0的码字中，又有一半码字( 个)得下一位为0，而另一半为1，以此类推。于是，若把第一位为0的 个码字拿出来，去掉第一位的0，就缩短为

29、长度为n-1的矢量。由于缩短时去掉的码字第一位的0，对码重没有影响，因此这个(n-1,k-1)缩短码的最小距离仍然是 ，称为(n-1,k-1, )缩短码。同样，可得缩短码为 从生成的角度看，去掉信息组和码组的第一位，相当于去掉生成矩阵的第1行和第1列。若缩短前的生成矩阵是k*n矩阵，则去掉最上边i行和最左边后剩下的(k-i)*(n-i)矩阵就是 缩短码的生成矩阵 校验矩阵与原校验矩阵H相比，行数不变，只是去掉了H矩阵左边i列，由(n-k)*n矩阵变为(n-k)*(n-i)矩阵。 由于(k-i)/(n-i)k/n，缩短码的码率总是比原码小。返回10,kmmmind2k12k22k12k mind

30、mind, (,)ni kim m i i n nm m i i n n( ( n n - - 2 2 , , k k - - 1 1 , , d d) ) , ,d d(,)ni kiminmind dsG4.6.3 删信码 在二进制(n,k)分组码的 个码字中，挑出码重为偶数的那一半码 字，共 个，组成一个新的码集，这就是(n,k-1)删信码。取名删信 码，是因为码长n不变而信息位少1，相当于将一个信息位转变为偶校验位 使用了，所以又称之为增余删信码。 从校验矩阵的角度看，若原校验矩阵是(n-k)*n矩阵H，则删信码的校 验矩阵为(n-k+1)*n矩阵 ，比原校验矩阵多出了1行，形式是： 如果原码的最小距离是奇数d，则删信加上偶校验后最小距离为1，成 为偶数d+1。另一种情况，如果原码的最小距离是偶数d，则删信并加偶校验后最小距离不变。返回 2k12keH1 11 1eHH4.7 分组码的性能限 t, 和n-k三者间的关系可用极限值、渐近线或解析公式来描述，但极限描述过于粗糙，解析公式又难以寻找，因此以