第三章_线性分组码

第四章线性分组码第四章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=时，每码元可携带bbit信息，长度为n的q元分组码码字可以映射成长度N=bn的二元分组码码字。纠错编码的任务是在n维n重矢量空间的种组合中选择个构成一个子空间，或称许用码码集C，然后设法将k比特信息组一一对应的映射到许用码码集C。不同的编码算法对应不同的码集C以及不同的映射算法，把这样的码称为(n,k)线性分组码。不编码时，一个二进制码元可携带1b信息（传输率为1b/符号）；编码后，n个二进制码元携带kb信息（传输率为（k/n）b/符号）。定义k/n=为二元分组码的码率，或者说是效率。011,,,},qxxx2b2b2n2kcR4.1线性分组码基本概念综上所述，编码算法的核心问题是：①寻找最佳的码空间，或者等效地说，寻找最佳的一组（k个）基底，以张成一个码空间。②k维k重信息组空间的个矢量以何种算法一一对应的映射到k维n重码空间C。由于上述映射是两个线性空间之间的线性交换，“线性分组码”由此得名。又因为这些矢量在加法运算下构成交换群，所以也称之为“群码”。返回2k4.1线性分组码基本概念在讨论生成矩阵之前，先看一个例题。例4.1（6，3）二进制分组码的输入信息组是m=(),码组输出是c=()。已知输入、输出码元之间的关系式是，求码集C以及编码时的映射算法。解：将关系式列成线性方程组，然后写成矩阵形式如下：210mmm543210cccccc52412211210020,,,,cmcmcmmcmmmcmm543210210100111)()010110001011ccccccmmmcmG5241302211210020cmcmcmcmmcmmmcmm4.2生成矩阵和校验矩阵二进制码取值于GF(2),6位二进制有=64种组合，而3位的信息组只有8种组合，一一对应到8个码字。可见，码集C包含64种组合中的8种。分别令信息组为（000），（001），…，（111），带入上面的矩阵算式，不难算得各信息组对应的码字如下表所示：62210mmm信息组()码字（)000000000000001011010010110011011101100100111101101100110110001111111010210mmm543210cccccc4.2生成矩阵和校验矩阵在以上编码过程中，核心的因素是矩阵G，它决定了变换规则，也决定了码集C。矩阵G可以看成是由3个行矢量组成的，所有码字是这3个行矢量的线性组合：可以验证，这里的3个行矢量线性无关，可以作为基底张成一个三维6重的码空间，该空间是六维6重空间的子空间。从上例得到的启示是：码集其实是一个子空间，只要找到一组合适的基底，它们的线性组合就能产生整个码集。不失一般性，C也可以扩展为k维n重码空间,即：c=[]=mG=式中，G称为该码的生成矩阵，是k行n列矩阵：210(100111)(010110)(001011)cmmm1,10,,nccc110110Tkkmmmggg4.2生成矩阵和校验矩阵4.2生成矩阵和校验矩阵(1)(1)(1)1(1)01101(1)11100(1)0100[]knkkTknngggGggggggggg其中,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的校验矩阵。(1)10[]iiniigggg2nk由于C的基底和D的基底正交，空间C和空间D也正交，它们互为零空间。因此，（n-k）线性码的任意码字c一定正交于其对偶码的任意一个码字，也必定正交于校验矩阵H的任意一个行矢量，即式中，0代表零阵，它是全零矢量。式可以用来检验一个n重矢量是否为码字：若等式成立（得零矢量），该n重必为码字，否则必不是码字。由于生成矩阵的每个行矢量都是一个码字，因此必有：这里，0代表一个尺寸为的零矩阵。验证H的方法是看它的行矢量是否与G的行矢量正交，即式是否成立。此处，式中，两个相同的矩阵模2加后为全零矩阵。这就证明了H确实校验矩阵。0TcH1()1()nnnknk0TcH0TGH[][()]()knnnkknk0TGH4.2生成矩阵和校验矩阵[][][][][][]0TTTknkknkGHIPPIIPPIPP例4.2考虑一个（7，4）码，其生成矩阵是：①对于信息组m=(1011),编出的码字是什么？②画一个（7，4）分组码编码器原理图。③若接收到一个7位码r=(1001101),检验它是否码字？解：设输入信息组，编码后的码字码集C。①由c=mG可知，将m和G的值代入，可得对应码字是（1011000）。本题由于是系统码，，前4位不必计算，后3个校验位可以根据生成矩阵G的分块阵P列出现行方程组如下41000101010011100101100001011GIP3210[]mmmmm6543210[]cccccccc3210210()cmmmmccc232112100320(cmmmcmmmcmmm式中“”指模2加）4.2生成矩阵和校验矩阵将代入方程组，得。所以码字为c=[1011000]。②一个二进制（n,k）系统线性分组码的编码器可用k级移存器和连接到移存器适当位置（由P决定）的n-k个模2加法器组成。加法器生成校验位后按顺序暂存在另一个长度为n-k的移存器。K比特信息组移位输进k级移存器，加法器计算n-k校验比特，然后先是k位信息、紧接着是n-k位校验比特从两个移存器中移位输出。本题的编码原理图如下：0m1m2m3m0c1c2cS2100,0,0ccc32101,0,1,1mmmm4.2生成矩阵和校验矩阵首先是信息位输入，再是，，顺序输入。编码后，开关S在输出前4位时上拨，先再~顺序输出；输出后面3位时，开关S下拨，将~顺序输出。③H矩阵如下：根据式，如果接受到的r是属于码集C的某码字，必有；反之，如，说明r必定不是码字。将H和r=[1001101]代入式，得：说明r与H不正交，接收的r=(1001101)不是码字。返回4.2生成矩阵和校验矩阵3m2m1m0m2c0c3m2m0m1110100[]01110101101001TnkHPI0TcH0TrH0TrH0TcH1(101)0(111)0(110)1(011)1(100)0(010)1(001)(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(,,,)nrrr110(,,,)nccc110111100(,,,)(,,,)nnneeercrcrc0TCH()0TTTTTTRHCEHCHEHEHEHTEHTRHTRHTEHTHTRH110(,,,)TTnkSsssRHEH0TCH4.3伴随式与译码从物理意义看，伴随式S并不反映发送的码字是什么，而只反应信道对码字造成怎样的干扰。可以看到：伴随式S是一个n-k重矢量，只有种可能的组合；而差错图案E是n重矢量，共有个可能的组合。因此，同一伴随式可能对应若干个不同的差错图案。在接受端，并不知道发送码C究竟是什么，但可以知道和接受码R，从而算出S。译码最重要的任务是从伴随式S找出C的估值，具体方法是：先算出S，再由S算出E，最后令=R+E而求出：=SE=R+E最关键的是从S找出E,只要E正确，译出的码也就是正确的。展开成线性方程组形式后：2nk2nTHˆCˆCTRHˆC(1)(1)(1)1(1)01101101(1)11100(1)0100(,,,)(,,,)nknnknkTnknnnhhhSsssEHeeehhhhhh4.3伴随式与译码会发现很难解，所以这里提供了在一般情况下构造标准阵列译码表的方法。（1）第一步：用概率译码确定各伴随式对应的差错图案（2）第二步：确定标准阵列译码表的第一列和第一行（3）第三步：在码表的第j行第i列填入11(1)(1)1(1)10(1)0111(1)111010010(1)101000nknnknnknknnnnsehehehsehehehsehehehijCE4.3伴随式与译码例4.3某一个（5，2）系统线性码的生成矩阵,设接收码R=(10101),请先构造该码的标准阵列译码表，然后译出发送码的估值。解：分别以信息组m=（00），（01），（11）及已知的G代入式：，求得4个许用码字为。由式求得校验矩阵为：4.3伴随式与译码C1011101101G110110110[,,,][][]TnkkccccmGmmmggg1234(00000),(10111),(01101),(11010)CCCC[]TnkHPI242322212031413121110040302010011100[]1001011001ThhhhhHPIhhhhhhhhhh展开后得：伴随式有8种组合；而差错图案除了代表无差错的全零图案外，代表一个差错的图案有5种，代表两个差错的图案有10种。要把8个伴随式对应到8个最轻的差错图案，无疑先应选择全零差错图案和5种一个差错的图案。剩下的两个伴随式不得不在10种两个差错的图案中选取两个。先将代入上面的线性方程组，解得对应的分别是（000），（111），（101），（100），（010），（001）。剩下的两个伴随式是（011）和（110），每个有种解，对应有个差错图案。本例中，伴随式（011）的4个解（差错图案）是（00011），（10100），（01110），（11001），其中（00011）和（10100）并列最小重量，只能选择其中之一作为解。24243232221210204321414313212111010410404303202101000430seheheheheheeeseheheheheheeseh