103线性分组码

《103线性分组码》由会员分享，可在线阅读，更多相关《103线性分组码（11页珍藏版）》请在金锄头文库上搜索。

1、k个码元（Symbol）分成一组，通过线性变换,10.3线性分组码10.3.1线性分组码的基本概念1. 线性分组码及其描述方法n, k线性分组码是把信息码元序列的每映射成由 n个码元组成的码组,且每一码组仅与本码组的k个信息位有关，与其他码组的 信息无关。对于线性分组码，码组中任一码元都是信息码元的线性组合。例10. 3.1设某（7, 4）二进制线性分组码编码器的输入信息组（又称信息段）是 m3m2m1m0 ,编码输出是 A = ：ia6a5a4a3a2a1a0 ,已知输入、输出码元之间的关系式 是 a m3 ,a = m2 ,a4=叶,a m0 ,a?= m3m?叶,a= m3m?m ,a0

2、 m3 m1| m0 ,这里，“ +”指模二加。求编码时“码组到信息”间的映射关系以及 输出码组集合。解 将题中所给输入、输出码元之间的线性变换关系用线性方程组描述如下:a6 = m3+ + 匕 2m m+ + 叫卩罷m3 - Cfa4a3a a 位 位 息 督 B监(10. 3. 1)=叫+卩还可以将式（10.3. 1）改写成矩阵形式:10001111rT0100110十丄A= m3m2m|m0（模 2 加）3210 0010101卫001011一=mG（ 10. 3. 2）分别令信息组（吨口2日口0为（0000）, （0001）,，（1111）,代入上面的矩阵算式,不难算得各信息组对应的码

3、组，列于表10. 3. 1表10.3. 1（7, 4）线性分组码的许用码组集合信息位监督位信息位监督位a6 a5 a4a3a? 414oa6a5a4a342414o00000001000111000101110011000010101101001000111101011001010011011000010101101110101001100111110100011100011111112. 线性分组码性质表10. 3. 1反映出线性分组码所具备的基本性质：(1) 一个n, k线性分组码共有2k个许用码组；(2) 对加法满足封闭性，即线性分组码中任意两个码组之和(模二加)仍是分组码 中的一个码组

4、；(3) 全零码是线性分组码中的一个码组；(4) 线性分组码各码组之间的最小码距，等于除全零码外的码组的最小重量。10.3.2生成矩阵及其特性在例10.3.1的编码过程中，核心的因素是矩阵 G，它决定了变换规则，也决定了码 组集合和线性分组码所具有的性质。不失一般性，令mk_!，m,m0是一组(k个)二进制信息码元，它可看成是一个1 k 的矩阵m二mkm1m0 1，或 m = mk_ m1m0。编码后，输出码组长度增大到 n,通常将码组写成通式 A = (anao )。则线性分组码的编码运算可以用矩阵形式表示为：X -1jjn -1 )g(k1 19g(k10g1(n-1 )g11g10g0

5、(n -A )g01g00 _二 mm1 m0(10. 3.3)式中,G称为该码的生成矩阵，是k ng(kG = bk -1 g1g0 卩-(k行n列)一1 jn 7 )g (k 1 g(k -1 0a-aa矩阵:g1(nT ) ,g0(n T )g11 g10g01 g00(10. 3.4)系数gq S,1， ( i = k -1,卄1,1,0 ； j = n -1l,1,0)表示第i个信息元m对第j个码其中， 元的影响。归纳起来，生成矩阵 G具有以下特性(1) 线性分组码的每个码组是生成矩阵G各行矢量的线性组合。即A 二 口一廿mgo( 10.3.5)aq = mk-g(kv ,j + +

6、口2“ +mgoj , j = n 1,1,0(10. 3.6)在例10.3.1中，有A = m3(1000111)+ m2(0100110)+m1(0010101)+ m0(OOO1O11)表明，生成矩阵G可以产生整个码组。(2) 生成矩阵G的各行本身就是一个码组，且它们是线性无关的。因此，如果已有k个线性无关的码组，则可以用其作为生成矩阵G,并由它生成其余的码组。(3) 如果生成矩阵G具有4k Q】的形式，其中Ik为k阶单位方阵，Q是kn-k )阶矩阵，如例10.3.1中，生成矩阵能分解成rooo dii0100110G =10010-101000仁 011则称G为典型生成矩阵。由典型生成

7、矩阵得出的码组称为系统码。在本章，系统码 的码组中前k个是信息位，后nk是监督位，如图10. 1.2所示。(4) 非典型生成矩阵可以通过线性代数中的任何一种初等行变换和列交换，得到典 型生成矩阵。10.3. 3监督矩阵及其特性若将例10. 3.1中的监督位线性方程组表示成：2=：6+ ：5 十：4：1=：6+ ：5 +：3(10. 3.7)00=：6+ ：4 +：3：6十：5+ a4 +a2 =0：6+ ：5+ a3 +a =0(10. 3.8 )1：6+ ：4p +ao =0写成矩阵形式111010011010101011001一a5:4a3:2：1$0 一0(模 2 加)0J(10. 3.

8、9)hat =0 或 AHT =0我们将H称为监督矩阵(又称校验矩阵) 定，编码时监督位和信息位的关系就完全确定了。推广到n维一般情况，H是一个n-k n阶矩阵。 监督矩阵H的特性是：(1)译码时，(2)(3)阵。(10.3.10)。式(10. 3.10 )表明，只要监督矩阵H给线性分组码的任意码组A正交于监督矩阵H的任意一个行矢量，即AH0( 10. 3.11)可以利用这种正交性来判断接收码组是否有错。监督矩阵H的各行是线性无关的。若H = Plr ，其中P是r n阶矩阵，Ir为r阶单位方阵，则称H矩阵为典型(4) 监督矩阵H与生成矩阵G的关系对任何线性分组码(系统码或非系统码)，总是存在下

9、列关系:(10. 3.12 )HG =0或 GH =0即监督矩阵H的行与生成矩阵G的行正交只有系统码才有关系：Q 二 pT 或 P 二 qT（ 10. 3.13）这时，生成矩阵G与监督矩阵H可以互相转换。10.3. 4系统码的编码与概率译码1. 系统码编码 下面举例说明系统码的编码原理。例10. 3. 2 一个（7, 4）码的生成矩阵是10001110100110G =0010101-0001 011 一（1）对于信息组m = 1011，编出的码组是什么？（2）画出该（7, 4）分组码编码器原理图。解：（1）利用式（10. 3.3 ）A=m G,将m 和G的值代入，便得到对应码组是（10110

10、01）。本题由于是系统码，所以码组 A的前4位不必计算，后3个监督位可以根据矩阵 G 的分块阵Q列出线性方程组如下：a2 = m3 二 m2 二 m1a= m3 二 二 ma 二 m3 二 m1 二 m。将 m3=1，m2= 0，m1=1，m= 1 代入方程组，得a= 0，a=0， a=1，所以码组为 A=1011001。（2） 一个二进制n,k系统线性分组码的编码器，可用 k级移存器和连接到移存器适 当位置（由分块矩阵 Q决定）的r（ r二n - k）个模2加法器组成。加法器生成监督位 后按顺序暂存在另一个长度为r的移存器中。k比特信息组移位输进k级移存器，加法器 计算r监督比特，然后先是k

11、位信息，紧接着是r位监督比特从两个移存器中移位输出。 本题的编码器原理图如图10. 3. 1所示。2. 纠错译码设编码器输出码组A= an_i,，ai，a，接收端的接收码组B=垢_1,，b),bo，则 由信道干扰引起的收、发码组之间的差异可表示成B = A + E( 10.3.14)式中，e =(勺/，6!,e0)，当e =0时，表示该位接收码元无错；若e =1，则表示该位 接收码元有错。我们把这个错码矢量称为错误图样。将式(10. 3.14 )改写成A = B + E( 10.3.15)可见，虽然事先并不知道发送码组 A，但是，如果译码器能推测出错误图样是 上， 那就可以给出译码结果为 A

12、= B E( 10.3.16)为找出E，定义校正子(又称伴随式)S为S=Sn_k/,，SiSohBHT( 10.3.17 )将式(10. 3. 14)代入式( 10.3. 17)中可得S NA E Ht =AHt EHt( 10. 3.18)利用式(10. 3. 13)所示码组与监督矩阵的正交性，所以S = EHt( 10.3.19)上式表明，校正子S的值只取决于错误图样E,而与发送什么码组 A无关。如果想 要推测出错误图样是什么，可以从校正子入手，并且，当给定S时，可能的错误图样一定是方程(10. 3. 19)的解。A.因此，译码过程可描述为：首先由式(10. 3.17)算出S,再由S算出E

13、，最后求出A的估值A二B E，如图10. 3. 2所示。E图10. 3. 2译码过程框图注意，方程组（10.3.19）中有n个未知数enj,，级（0，却只有nk个方程，可知 式（10. 3.19 ）有多解（解 E是不唯一）。式（10. 3.19 ）的解一共有2k个，记其为 E0,目，E2k /，由此带来的后果是，由BHt确定S后，可能的译码结果也是2k个，、AA.A它们是 A（）二 BE，A|二 BE1，, A2K_1二 BE?K _1。那么究竟取哪一个作为错误图样 E的解呢？这里，介绍一种叫做概率译码的处理方 法，它是把所有2k个解的重量（错误图样E中1的个数）做比较，选择最轻者作为E的 估

14、值。这种算法的理论根据是：若二进制对称信道（BSC）的差错概率是p，则长度为n 的码中错1位（对应于E中有一个1或E的重量为1）的概率是p 1 - p门一1，错2位的 概率是p2（1 - p 2,，以此类推。由于p1，必有p1_p 门/八卩“一卩 n-2, pn所以，在E的2k个解中取重量最小的E时，译码正确的概率最大。由于 E=B+A即 收、发码之间的汉明距离，E重量最小，就是B和A的距离最小，所以概率译码实际上 体现了最小距离译码法则。10. 3.5汉明码汉明码是一类能纠正单个随机错误的线性分组码。汉明码具有如下特性：（1）二进制汉明码应满足条件：2* =1 n（10. 3.21）式（10.3.21）的左边为校正子的组合数目，右边是无错传输（毫无疑问仅一种情形） 与可纠正错误图样数目（因汉明码纠错能力 t =1，所以c二c二n ）之和。因此，汉明 码的校正子和可纠正错误图样是一一对应的， 即式（10. 3.20 ）中的S与E之间一一对应。（2）令m二n -k，汉明码n和k服从关系式：码长n