第三章线性分组码

第四章线性分组码第四章

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时是二进制码，q>2时是q进制（q元）码。多进制q一般取素数或素数的幂次，实用中多见的是q=3或q=(b是正整数)。当q=时，每码元可携带bbit

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

①寻找最佳的码空间，或者等效地说，寻找最佳的一组（k个）基底，以张成一个码空间。

②k维k重信息组空间的个矢量以何种算法一一对应的映射到k维n

重码空间C。

由于上述映射是两个线性空间之间的线性交换，“线性分组码”由此得名。又因为这些矢量在加法运算下构成交换群，所以也称之为“群码”。返回4.1线性分组码基本概念在讨论生成矩阵之前，先看一个例题。例4.1（6，3）二进制分组码的输入信息组是m=(),码组输出是c=()。已知输入、输出码元之间的关系式是，求码集

C以及编码时的映射算法。解：将关系式列成线性方程组，然后写成矩阵形式如下：4.2生成矩阵和校验矩阵二进制码取值于GF(2),6位二进制有=64种组合，而3位的信息组只有8种组合，一一对应到8个码字。可见，码集C包含64种组合中的8种。分别令信息组为（000），（001），…，（111），带入上面的矩阵算式，不难算得各信息组对应的码字如下表所示：信息组()码字（)0000000000000010110100101100110111011001001111011011001101100011111110104.2生成矩阵和校验矩阵在以上编码过程中，核心的因素是矩阵G，它决定了变换规则，也决定了码集C。矩阵G可以看成是由3个行矢量组成的，所有码字是这3个行矢量的线性组合：

可以验证，这里的3个行矢量线性无关，可以作为基底张成一个三维6重的码空间，该空间是六维6重空间的子空间。从上例得到的启示是：码集其实是一个子空间，只要找到一组合适的基底，它们的线性组合就能产生整个码集。不失一般性，C也可以扩展为k维n重码空间,即：

c=[]=mG=式中，G称为该码的生成矩阵，是k行n列矩阵：4.2生成矩阵和校验矩阵4.2生成矩阵和校验矩阵

其中,i=k-1,,0,是G中第i行的行矢量。与任何一个（n,k）线性码的码空间C相对应，一定存在一个对偶空间D。事实上，码空间基底数k只是n维n重空间的全部n个基底的一部分，若能找出另外n-k个基底，也就找到了对偶空间D。既然用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的校验矩阵。

由于C的基底和D的基底正交，空间C和空间D也正交，它们互为零空间。因此，（n-k）线性码的任意码字c一定正交于其对偶码的任意一个码字，也必定正交于校验矩阵H的任意一个行矢量，即

式中，0代表零阵，它是全零矢量。式可以用来检验一个n重矢量是否为码字：若等式成立（得零矢量），该n重必为码字，否则必不是码字。

由于生成矩阵的每个行矢量都是一个码字，因此必有：

这里，0代表一个尺寸为的零矩阵。验证H的方法是看它的行矢量是否与G的行矢量正交，即式是否成立。此处，

式中，两个相同的矩阵模2加后为全零矩阵。这就证明了H确实校验矩阵。4.2生成矩阵和校验矩阵例4.2考虑一个（7，4）码，其生成矩阵是：

①对于信息组m=(1011),编出的码字是什么？

②画一个（7，4）分组码编码器原理图。

③若接收到一个7位码r=(1001101),检验它是否码字？解：设输入信息组，编码后的码字码集C。

①由c=mG可知，将m和G的值代入，可得对应码字是（1011000）。本题由于是系统码

，，前4位不必计算，后3个校验位可以根据生成矩阵G的分块阵P列出现行方程组如下4.2生成矩阵和校验矩阵将代入方程组，得。所以码字为c=[1011000]。

②一个二进制（n,k）系统线性分组码的编码器可用k级移存器和连接到移存器适当位置（由P决定）的n-k个模2加法器组成。加法器生成校验位后按顺序暂存在另一个长度为n-k的移存器。K比特信息组移位输进k级移存器，加法器计算n-k校验比特，然后先是k位信息、紧接着是n-k位校验比特从两个移存器中移位输出。本题的编码原理图如下：

4.2生成矩阵和校验矩阵首先是信息位输入，再是，，顺序输入。编码后，开关S在输出前4位时上拨，先再~顺序输出；输出后面3

位时，开关S下拨，将~顺序输出。

③H矩阵如下：根据式，如果接受到的r是属于码集C的某码字，必有；反之，如，说明r必定不是码字。将H和

r=[1001101]代入式，得：

说明r与H不正交，接收的r=(1001101)不是码字。返回

4.2生成矩阵和校验矩阵由于信道干扰的缘故，使得接收端的接受码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为：

4.3伴随式与译码从物理意义看，伴随式S并不反映发送的码字是什么，而只反应信道对码字造成怎样的干扰。可以看到：伴随式S是一个n-k重矢量，只有种可能的组合；而差错图案E是n重矢量，共有个可能的组合。因此，同一伴随式可能对应若干个不同的差错图案。在接受端，并不知道发送码C究竟是什么，但可以知道和接受码

R，从而算出S。译码最重要的任务是从伴随式S找出C的估值，具体方法是：先算出S，再由S算出E，最后令=R+E而求出：

=SE=R+E

最关键的是从S找出E,只要E正确，译出的码也就是正确的。展开成线性方程组形式后：4.3伴随式与译码

会发现很难解，所以这里提供了在一般情况下构造标准阵列译码表的方法。（1）第一步：用概率译码确定各伴随式对应的差错图案（2）第二步：确定标准阵列译码表的第一列和第一行（3）第三步：在码表的第j行第i列填入

4.3伴随式与译码例4.3某一个（5，2）系统线性码的生成矩阵

,设接收码R=(10101),请先构造该码的标准阵列译码表，然后译出发送码的估值。解：分别以信息组m=（00），（01），（11）及已知的G代入式：，求得4个许用码字为。由式求得校验矩阵为：4.3伴随式与译码展开后得：

伴随式有8种组合；而差错图案除了代表无差错的全零图案外，代表一个差错的图案有5种，代表两个差错的图案有10种。要把8个伴随式对应到8个最轻的差错图案，无疑先应选择全零差错图案和5种一个差错的图案。剩下的两个伴随式不得不在10种两个差错的图案中选取两个。先将

代入上面的线性方程组，解得对应的分别是（000），（111），（101），（100），（010），（001）。剩下的两个伴随式是（011）和（110），每个有

种解，对应有个差错图案。本例中，伴随式（011）的4个解（差错图案）是（00011），（10100），（01110），（11001），其中（00011）和（10100）并列最小重量，只能选择其中之一作为解。4.3伴随式与译码

至此，根据4个码字和8个差错图案，画出标准阵列译码表如下所示：

=000=00000=10111=01101=11010

=111=10000001111110101010=101=01000111110010110010=100=00100100110100111110=010=00010101010111111000=001=00001101100110011011=011=00011101000111011001=110=001101000101011111004.3伴随式与译码若接收码R=(10101)，可用以下三种方法之一译码。

①直接搜索码表，查得（10101)所在列的子集头是（10111），因此取译码输出为（10111）。

②可以先求伴随式，找到伴随式所在行数，再搜索码表的第5行找到（10101），最后顺着该列向上找出码字（10111）③先求出伴随式，在表中查出对应的陪首集（差错图案）=（00010），再将陪集首与接收码相加，得到码字C=R+=(10101)+(00010)=(10111)。返回

4.3伴随式与译码4.4码的纠、检错能力与MDC码例4.3的（5，2）分组码中，如果码字有一位误码，译码后该差错能被纠正；如果有两位误码，可以检测出差错的存在，但不一定能纠正它。显然，任何一种信道编码的纠、检错能力都有一定的限度，这种限度与码距有关的。为此，有必要引入相关的定义和定理，适用于GF(2)域。

①汉明重量：n重矢量R中。非零元素的个数称为n重的汉明重量，简称重量，用w(R)表示。②汉明距离：逐位比较两个n重矢量和的对应各位，其中取值不同的元素的个数为与德汉明距离，用表示。③最小距离：分组码码集中，每两两码字之间都存在一定距离，其中最小者称为该分组码的最小距离，用符号表示。如直接计算最小距离，含个码字的码集需计算个距离后才能找出。由于分组码是群码，利用群的封闭性，即两个码字之和仍是码字，可得：于是得以下定理。

定理4.1线性分组码的最小距离等于码集中非零码字的最小重量，即及距离和重量除了上述关系外，还满足以下两个不等式：这里采用符号R，是强调上面两式适用于一切n重矢量，而不限于码字。4.4码的纠、检错能力与MDC码定理4.2对于任何最小距离为的线性分组码，其检测随机差错的能力为。定理4.3对于任何最小距离等于的线性分组码，其纠正随机差错的能力t为：式中，INT[.]表示取整。定理4.4（n,k）线性分组码的最小距离等于充要条件是：校验矩阵H中有列线性无关。定理4.5（n,k）线性分组码的最小距离必定小于等于n-k+1,即

返回4.4码的纠、检错能力与MDC码4.5完备码与汉明码

4.5.1完备码

4.5.2汉明码

4.5.3高莱码

返回4.5.1完备码

二元（n,k)线性分组码的伴随式是一个n-k重矢量，有个可能的组合。如该码的纠错能力是t，则对于任何一个重量小于等于t的差错图案，都应有惟一的伴随式组合与之对应，才有可能实行纠错译码。也就是说，伴随式组合的数目必须满足条件：

这个条件称为汉明眼。任何一个纠t码都应满足汉明眼。

如果某二元（n,k）线性分组码能使上式的等号成立，即该码的伴随式组合数目恰好和不大于t个差错的图案数目相等，相当于在标准阵列中能将所有重量不大于t的差错图案实现一一对应，娇艳位得到最充分的利用。把满足方程：

的二元（n,k）线性分组码成为完备码（PerfectCode）。迄今发现的二进制完备码有t=1的汉明码、t=2德（23，12，7）高莱（Golay）码，以及长度n为奇数、由两个码字组成且满足

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

上列中校验矩阵的构成方法具有一般性。由于H是（n-k）*n矩阵，可以看成由n个n-k重矢量构成。这样的行矢量除去全零后有-1中可能的组合，由=1+n知正好等于码长n。返回

4.5.2汉明码4.5.3高莱码高莱码（Golay）是二进制（23，12）线性码，其最小距离

=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,这才达到了极限纠错能力。

返回

4.6扩展码、缩短码与删信码4.6.1扩展码4.6.2缩短码4.6.3删信码

返回4.6.1扩展码如果给（n,k）分组码添加一个奇偶校验位，可得一个（n+1,k）扩展码。由于信息位k没变，码集包含的码字总数也不会变，只不过每个码字的长度增加1。对于码字，扩展后变为若采用偶校验，校验位的选择应满足校验方程：

从校验矩阵的角度看，扩展前校验矩阵是（n-k）*n矩阵H，扩展后的校验矩阵为（n-k+1）*（n+1）矩阵，多出了1行1列。

从最小距离角度看，若扩展前原码的最小距离是奇数，即最轻码字中包含奇数个1，则扩展后最轻码字的码重加1，扩展码的最小距离因此比原来增加1，变成

+1；若原码的最小距离是偶数，则偶校验不改变其最小距离。返回4.6.2缩短码码字中的每个码元都是信息元的线性组合。在生成矩阵一定的条件下，由于信息组中0与1结构对称、奇偶性对称，因此在二进制

(n,k,)分组码的个码字中总有一半码字(个)的第一位为0，而另一半码字的第一位为1。在第一位为0的码字中，又有一半码字(个)得下一位为0，而另一半为1，以此类推。于是，若把第一位为0的

个码字拿出来，去掉第一位的0，就缩短为长度为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，缩短码的码率总是比原码小。返回4.6.3删信码

在二进制(n,k)分组码的个码字中，挑出码重为偶数的那一半码字，共个，组成一个新的码集，这就是(n,k-1)删信码。取名删信码，是因为码长n不变而信息位少1，相当于将一个信息位转变为偶校验位使用了，所以又称之为增余删信码。从校验矩阵的角度看，若原校验矩阵是(n-k)*n矩阵H，则删信码的校验矩阵为(n-k+1)*n矩阵，比原校验矩阵多出了1行，形式是：

如果原码的最小距离是奇数d，则删信加上偶校验后最小距离为1，成为偶数d+1。另一种情况，如果原码的最小距离是偶数d，则删信并加偶校验后最小距离不变。返回

4.7分组码的性能限