讲义61线性分组码

信息论课程讲义（第六章）第六章 线性分组码纠错编码（FEC）主要分为分组码和卷积码两大类，这一章主要介绍 分组码。6-1 汉明码（Hamming Code）汉明码是一种基本的线性分组码。6-1-1线性分组码的定义分组码是一种代数编码，它的基本关系一个码字包括独立的信息元和监督元，其监督元与信息元之间是一种代数关系，如果这种代数关系为线性的则称为线性分组码。分组码的编码器的模型为：m= 3 kM |-EnCoderC=（cn-1 ,cn-2, c）m为编码器的输入，称为信息码元（信息位），它由k位码元组 成。C为编码器的输出，称为码字矢量，它由 n位码元组成，其中 有k位信息元，r=n-k位监督元。对于二元编码来说，k位信息码元 共有2k个不同组合，根据编码器为一一对应关系，输出的码字矢量 也应当有2k种码字。对于长度为n的二元序列来（n-重）说，共有2n 个可能的码字矢量，编码器只是在这2n个可能码矢中选择2k个码字， 被选中的2k个n-重称为许用码字，其余的2n-2k个码字称为禁用码字， 称这2k个码字矢量的集合为（n,k）分组码。信息元监督元线性分组码定义:长度为n,有2k个码字的分组码，当且仅当 这2k个码字是GF(2)上n维矢量空间(所有n重)的一个k维子空 间时，称为(n,k)线性分组码，简称(n,k)码。二元分组码为线性分组码的充要条件为两个码字的模二加也 是一个码字。由于k维子空间是在模2加法下运算的，构成了一个加法交换 群(阿贝尔群)，所以线性分组码也称为群码。线性分组码的一个重要参数为码率(Code rate): R=k/n;它实际 上也就是编码效率或传输效率。如果(n,k)码位信息位没有变化，与信息码元排列相同，并且与 监督位分开，称为系统码，否则称为非系统码。6-1-2 基本监督矩阵(Parity check matrix)线性分组码可以用GF(2)上的矢量空间的矩阵和GF(2)上多项式来 描述，对于汉明码这一类分组码用矩阵描述更为方便。汉明码定义:对于任意正整数A3,存在有下列参数的线性分 组码，码长：n=2r-1信息位：k=2r-1-r=n-r监督位：r=n-k最小码距：dmin=3这种码称为狭义汉明码，也称为完备汉明码。这种码的码字矢量为：C=c n-i,cn-2, Ci,co如果对于系统码，其前k位为信息位，后r位位监督位。信息位=m k-1,mk-2,，闸二cn-1,cn-2, ,rCk监督位二cn-k-i , Cl,Co由于线性分组码的监督元与信息元之间的线性关系，可以用二元域上的线性方程组描述。记为：cn-k-1=h1,n-1 cn-1 + h1,n-2cn-2 + +h,n-kcn-kcn-k-2= h2,n-icn-i + h2,n-2cn-2 + +方介曲co = hr,n-1cn-1+hr,n-2cn-2 + +hr,n-kcn-k在二元域上,hj：0,1整理这个方程组可得：hl,n-hl,n-hl,n-k1012h2,n-h2,n-h2,n-k0112hr,n-1hr,n-2hr,n-k00记为：=0HC T=0C为C的转置，称矩阵H为分组码的基本监督矩阵（一致校验矩阵，一致监督矩阵）。可见系统码的基本监督矩阵为：H=P I rP h1,n h1,nh1,n-1-2-k6-3信息论课程讲义(第六章)h2,nh2,nh2,n-1-2-khr,nhr,nhr,n-1-2-k100Ir 010一 一001巳为rxk矩阵,Ir为rx r单位阵。举例:(7,4)系统汉明码，n=7, k=4, r=3C = c 6,C5,C4,C3,C2,C1,C0；其中C6,C5,C4,C3为信息位，。为监督位。0111100H1011010一1101001由HC T=0可知：监督方程为:C2F5+C4+C3C1=C6+C4+C3Co=C6+C5+C3根据这个方程组可以进行编码。例如信息码元m=1011,则有C2=C5+C4+C3=0+1+1=0C1 =C6+C4+C3=1+1+1=1Co=C6+C5+C3=1+0+1=0则汉明码字C=1011010。6-1-3 生成矩阵(Generator matrix)(1)生成矩阵的基本形式:由上面(7,4)汉明码的例子；可以将基本监督方程扩展写为：C6=C6C5=C5C4=C4C3=C3C2=C5+C4+C3Cl=C6+C4+C3C0=C6+C5+C3用矩阵表示:C6,C5,C4,C3,C2,Cl,Co1 C6,C5,C4, 0 C3. 0 0000011100101010110001111C6,C5,C4,C3,C2,C1,C m3,m2,m1,0= m。.可以写为：1000011010010100101100001111C=m3,m2,m1,m0.G汉明码字尸信息码字生成矩阵G称为(7,4)汉明码的生成矩阵。例如：m=1100, C=1100G=1100110(n,k)码的生成矩阵的基本形式为：g1,n g1,1 g1,0 -2 g2,ng2,1g2,0-2 gk,ngk,1gk,0-2同样，利用生成矩阵的编码关系为C=mG而系统(n,k)码的生成矩阵的基本形式应当为gi,og2,0gk,0g1,n-1Gg2,n-=1可以看出:gk,n-.0g1,n-k-1G.0g2,n-k-1gk,n-k-1这种系统码的生成矩阵也称为典型生成矩阵，其基本形式为；G=Ik,Q, Q为kx r矩阵，鼠为kxk单位阵。(2)系统码基本监督矩阵与典型生成矩阵的关系:从生成矩阵与码字矢量的关系可以看出：G矩阵的每一行都是一个码字矢量，分别对应信息码字10 - 0,010 030030伸分组码 的码字。由于每一行都是码字，把每一行作为一个码字矢量，都应当满足监督矩阵所规定的监督关系，即应当有：HGT=0,同时有：GHT=0称H与G为正交矩阵，由P Ir Ik Q T=06-5信息论课程讲义(第六章)P+QT=P=Q T Q=巳 TP矩阵与Q矩阵互为转置矩阵。对于系统码，已知监督矩阵H就可以确定典型生成矩阵G,反 之，已知生成矩阵也就可以确定监督矩阵。（3）生成矩阵的一般性质:根据线性分组码的定义，（n,k）线性分组码C是二元n重矢量空间 中的一个k维子空间，因此，在码字C的集合中（2k个码元的码组 中），可以找到k个线性独立的码字，gi,g2,乐；使C中的所有码字 都是这k个码字的线性组合。g1=g1,n-1,g1,n-2,闻0g2 = g2,n-1,g2,n-2, 国0gk = gk,n-1,gk,n-2, ,g0C=mn-igi+mn-2g2+mn-kgk其中系数就是信息码字矢量的元素：mn-i,mn-2m n-k=mk-i,mk-2m 0根据线性矢量空间的知识，这k个码字矢量就可以张成（生成） 这个k维子空间，将这k个矢量组成的矩阵就是（n,k）分组码的 生成矩阵。所以生成矩阵是一个 k行n列的矩阵。确定（n,k）码的生成矩阵的问题实际上就是确定n-重矢量空间中k维子空间的k个线性无关的码字矢量的问题。也就是寻找 基底的问题。(n,k)码的n-重矢量空间中的一个 k维子空间的基底可以有多 个，因此可以有不同的生成矩阵G,但都产生相同的码组。(n,k)码的n-重矢量空间中可以有多个k维子空间，产生不同的 码组。(？)(4)非系统汉明码:可以证明非系统汉明码的一致监督矩阵可以用一种简单方法得至上例如：(7,4)非系统汉明码的H为0 0 0 1111H 0 11 0 0 1110 10 10 1其每一例都是二进制数的1,2, 3 。利用HC T=0的基本关系， 可以得到非系统形式的汉明码。通过H矩阵的列换位，可以将H变 为系统码的形式。6-1-4 校验子与译码(Syndrome Matrix and Decoding)设发送码字为：C=(C n-1 ,Cn-2,，0)；由于信道干扰产生差错，反映到接收码字上可以用一个二元矢量E表示，称为错误图样(errorpatterns), E=(en-1,en-2, ,0)其中：e=1表明相应位有错，e=0表明相应位无错。这时接收码字可以表示为，R=C+E=(C n-1+en-1,Cn-2+en-2, .，)译码器的作用就是从接收码字R中得到发送码字的估计值，或者6-#信息论课程讲义（第六章）说从接收码字中确定错误图样E,然后由C=R-E得到发送码字的估计值，如果估计正确则译码正确，否则译码错误。定义 S为校验子（伴随式）：S=RH T=CH T+EH T=EH T 或ST=HR T=HC T+HE T=HE T （本教材的表示方法）S=Sr,S-1, Si= Sn-k,Sn-k-i, 1可以看出：如果校验子矢量S?0,接收码字一定有错误，如果校验子矢量S=0,译码器认为接收码字无错误。下面通过例子说明校验子的作用。（7,4）汉明码的基本监督矩阵H为已知,H01111001011010110 1001由其得到的汉明码字如下表:000 00000 00010010 0011000 0001 1110010 1100011 001010 00101 011 0 01110100101 0101 010 0110 011 011110010001001101010111000 0111001 1001010 1011011 010110 0110 1111011111100 1101101 0011110 0001111 111假如接收码字为R=0100101可以看到:ST=HR T=0这时表明无差错;如果接收码字有一位差错，R=0110101;即错误图样E=0010000;接收码字的第三位错。这时校验子矢量为:0 11110 010 110 10相当于:11 01 01110 10 0 16-150 01 0 0 0 00 011 0 0 0可见这时，校验子矢量不为0,但是如果这时接收机按原来的译0 11110 010 110 10110 10 0 1可见这时校验子ST不为0,译码器认为有错，且正好等于H的 第三列，表明接收码字的第三位码元错了。这时判断发送码字位0100101,译码正确。如果接收码字由两位差错，R=011_1101;即错误图样E=0011000;接收码字的第三、四位错。这时校验子矢量为:0 11110 010 110 10110 10 0 1码方法，将认为第7位出错。但如果接收机设计为检错系统，当校验 子不为0,就认为有错。因为（7,4）汉明码的最小码距为3,其纠错检 错能力是正确的。注意：这里告诉我们一个问题，纠错码的选用要小心，要根据信道条件来确定，如果信道较差，而使用的纠错码能力不够，可能使译 码错误反而增加，不仅错误的码元没有纠正，原来正确的码元还被错 误的改变。错上加错。这种纠检错能力是由码组的最小码距决定的。可以验证：下面的（7,3）线性分组码的最小码距为 4,可以纠一位 错，同时检两位错，其基本监督矩阵为：1 0 11 0 0 0H 111 0 1 0 0=1 1 0 0 0 0 00 1 1 0 0 0 16-1-5分组码的纠检错能力已知（n,k）分组码的最小码距，就可以知道其纠检错能力，例如， 当最小码距为4时，可以纠一位错，同时检两位错，也可以用于检三 位错，这与上一章介绍的结论是一样的。这里将进一步介绍有关性质。定理1:任一个（n,k）线性分组码，若要纠正t位错误，其充要条 件是一致监督矩阵H中的任何2t个列向量线性无关。或者说：若使一个（n,k）线性分组码的最小码距为 d,其一致监督 矩阵H中的任何d-1个列向量线性无关。或者说：若使一个（n,k）线性分组码的最小码距 d,等于一致监督矩阵H中和为0的最小列数。推理1:改变一致监督矩阵的列的位置，不会影响列的相关性， 也就不会影响其最小码距。但可能产生不同的码组，其纠错检错能力 是相同的。根据这个推理，非系统汉明码的一致监督矩阵，经过列换位，可 以得到系统汉明码的一致监督矩阵。例如：（7,4）非系统汉明码的监督矩阵位,0 0 0 1H 0 11010 1011H110 1将其进行列换位，可以得到:0 110010 0 10110 01由于前面4列的位置可以任意放置，编出的码字可以不同，但纠 错能力是相同的推理2： （n,k）线性分组码的最小码距dmin的最大值为n-k+1=r+1c dmin & r+1这说明，要想提高纠检错能力，只能增加监督元的位数。例如：110 0H1 0 1 010 0 1这个监督矩阵的最小码距位 dmin=4,因为，它由d-1=3个列向量线性无关，任何两个列或三个列相加都不为0。这时最小码距达到其最大值实际上这是一个n=4, k=1, r=3的简单重复码,0-00001 1111它可以纠一位，同时检两位，或检 4位。定理2:线性分组码的最小码距等于非 0码字的最小码重分组码的检错能力:最小码距为dmin的分组码，能检出所有dmin-1位或更少位错误 的错误图样。它不能检测出所有的dmin位错误，但可以检出一些（大部分） dmin位或更多位的码元错误。事实上，（n,k）码能检出长度为n的2n-2k个错误图样。因为为禁 用码字的个数，收到禁用码字就等于检出错码。令一个（n,k）线性分组码，Ai为码组中重量为i的码字的个数，码 字集合（码组）的重量分布为 Ao,Ai, -Ano这时码字在误码率（转移 概率）为Pe的BSC信道上的漏检概率为： nin _LPU = Ai Pe（1 - Pe） i 1其中Peid-Pe）”“为错误图样（en-i, 中出现i个1, n-i个0的概率, Ai为此错误图样分布正好错成许用码字的数量。 也就是错误图样等于 许用码字的可能性就是漏检概率。例如：（7,4）汉明码的重量分布为：A0=1,A1=A2=0,A3=A4=7,A5=A6=0,A7=1 。Pu=7p3（1-p）4+7p4（1-p）3+p7（根据公式 A0 一项没用，所以只有三项）当Pe=10-2时，漏检概率为7X10-60可见其实际检错能力远远高于 最低检错能力。如果按照最小码距与检错能力的分析，其漏检概率为： n7Pu = c cnpe（i - Pe）-=1 c7pe（i - Pe）7i ：e 1i =3但是对于短码可以这样计算，对于长码，这样计算是很困难的。分组码的纠错能力:当（n,k）分组码的最小码距为d=2t+1,它可以纠正t个或更少的错 误。但实际上，纠错能力为t的分组码还可以纠正一些t+1位或更多位 错误的错误图样（在后面的译码原理分析中可以看出）,但较难精确 计算，其错误译码概率的上限为：n?e 三、cn pe（i - pe）n i 4 16-1-6标准阵与校验子译码（n,k）分组码的译码步骤为：由接收码字R计算校验子ST=HRT。若S=0,则译码器认为接收码字没错，否则有错，并由 S计 算错误图样E。由错误图样进行译码，估计发送的码字C=R-E=R+E（模 2减法等于加法）。其中最困难的是第二步，确定错误图样，即错误定位。这里介绍一个基本的译码方法，标准阵译码，即查表法译码。（n,k）分组码的2k个码字，是n维矢量空间Vn中的一个k维子空 间，它在GF（2）上是一个子群。利用分元陪集的方法，可以利用该子 空间的所有2k元素，生成n为空间中的所有2n个元素。产生的方法 如图。码字（子陪集首群）C0CiC2C2k-i禁用码 字EiE2 E2r-1Ci+ EiCi+ E2 Ci+E2r-1C2+ EiC2+ E2 C2 +E2r-iC2k-i + Ei C2k-i +E2 C2k-i + E2r-i将2k个码字放在表中的第一行（第一陪集），该子群的加法单位元Co=（00 放在第一列，作为第一个陪集的陪集首。在所有禁用码字中，挑出一个汉明重量最小的作为第二行的第 一列，作为第二个陪集的陪集首。将第一行的相应元素与其陪 集首相加，构成第二个陪集。依次进行，构成第2r个陪集。这个表称为标准译码表，简称标准阵。译码器按以下规则进行：收到码字R必然在这个表中，如果落在表中某一列，译码器就译成第一行的相应码字，由此可以看出：译码表的第一列 （陪集首）相当 于错误图样，如果实际错误图样完全包含在表中的第一列中， 译码器 就不会产生错误译码，否则就可能产生错误译码。因此问题的关键是如何选择译码表的陪集首。我们知道，在随机 信道中，错一个码元的概率大于错两个码元的概率， 错两个码元的概 率会大于错三个码元的概率。错误图样的汉明重量越小，其产生的可能性越大，应用译码表正 确译码的可能性越大，错误译码概率越小。所以在设计译码表是应选 择重量最轻的禁用码字作为陪集首。这一译码设计满足最小汉明距离译码准则， 可以证明在BSC信道 条件下，最小汉明距离译码等价于最大似然译码。例题:设一个(5,2)线性分组码，该码的最小汉明距离为dmin=3, 可以纠正一个码元的错误。其一致监督矩阵为:H110 00 01010 01其码字为C =(C4,C3,C2,C1,C0),其信息元为(C4,C3),监督元为(C2,C1,C0)。编码后得到的四个码字分别为:C0=(00000)C1=(01101)C2=(10111)C4=(11010)这时的标准译码表为许用码 字00000011011011111010禁用码 字10000 01000 00100 0001000001 000110011011101 00101 01001 0111101100 01110 010110011111111100111010110110101001000101010100101111011000110111100111100例如接收码字 R=(10101),则由译码表可知，按最大似然译码准则译码器输出为(10111),在译码表中的第一列中可以看到，在禁用码字部分，前五行为只错一位的错误图样，即汉明重量为最小 (dmin=1) 的码字矢量。但由这五个汉明距离最小的码矢作为陪集首， 并没有构 成全部n维空间的码字矢量，所以这个译码表又选择了两个汉明距离信息论课程讲义（第六章）较小的禁用码字作为陪集首。所以按这种译码表译码，不仅可以纠正 所有单个错误，而且可以纠正两种类型的两位错误。可以得到错误译码概率为：Pe=1-5Pe(1-Pe)4-2pe2(1-Pe)3利用标准译码表，需要把2n个码字矢量存在译码器中，译码器的 复杂性会随n指数增加。当n较大时，这种方法不可能实现。解决的方法之一，错误图样与校验子矢量有一一对应的关系，根据这种关系，可以将译码表简化。例如(5,2)线性码的简化译码表为错误图样校验子000000001000 01000011110100100100000100100000 00011100101100110110当接收码字R=(10101)时，可以计算出校验子S=(010),查表的错误图样的估计值为E=(00010),由C=R+E可得译码器输出为C=(10111)。当n-k=r较小时(小于30)这种利用校验子表的方法是简单实用的 方法。但n进一步大时查表方法就不太实用了，需要找到更简化的译码方法，或者是具有简单译码方法的编码方法。6-1-7分组码的其它概念(1)完备译码:从上面介绍的译码方法可以看出，汉明码的译码器接收到一个错 误码字(禁用码字)后是利用比较这个错误码字与所有许用码字之间 的汉明距离来实现译码的。判断与这个错误码字汉明距离最小的许用 码字为发送码字。这种方法称为 最小汉明距离译码。定义:（n,k）线性分组码的所有2n-k=2个校验子（伴随式），在译 码过程中都用来纠正所有t=（d-1）/2个随机错误，及大部分大于t个码 元错误，则称这种译码方法为完备译码，否则称为非完备译码。如果译码器对于每个接收码字，都必须明确判决发送的对应码字， 称为完备译码。相应的译码器称为 完备译码器。例如：（3,1）重复码译 码，可以实现完备译码。如果译码器对于一些接收码字作出译码判决，而对于另外一些接 收码字不能明确作出译码判决，称为不完备译码。例如：（4,1）重复码， 当一个码字错两位时，译码器不能明确判决，无论怎样判决都会是很 大的错判概率，只能是不完备译码。（2）限定距离译码:如果一个（n,k）线性分组码，能纠正t小于等于（d-1）/2个码元错误。 在译码时只纠正t 3,码长和信息位长度分别为 n=2r-1和k=n-r。码长必须为奇数， 信息位是受到限制的。因此人们通过进一步研究，发现了一些由汉明 码引出的线性分组码，它们不属于狭义汉明码，但有时也称为汉明码， 可以理解为广义汉明码。例如（7,3）汉明码，不是狭义汉明码，因为这 时r=4,如果按照狭义汉明码的定义，码长应当为n=2r-1=15。下面我们看一下引出码的例子。（4）对偶码:从线性空间的零化空间的概念可以知道，如果一个矢量空间的有 两个子空间，其中一个子空间的每一个矢量都与另一个子空间的每一 个矢量正交，则称这两个子空间互为正交空间，或互为零化空间，也 叫作对偶空间。由线性分组码的一致监督矩阵H和生成矩阵G的基本定义可知，生成矩阵的每一个行向量均为一个码字，因此有 HGT=0,这 说明H与G互为零化空间，而且分别为n维线性空间Vn的维和k 维子空间。如果H和G分别是码字C的监督矩阵和生成矩阵，则将H d=G 作为监督矩阵，Gd=H作为生成矩阵，则可以产生一个（n,n-k）线性 分组码Cd ,称C和Cd互为对偶码。例如：（7,4）分组码的对偶码为一种（7,3）分组码。如果一种码的对偶码是它本身，则称此码为自对偶码。例如 （2,1） 重复码就是自对偶码。（5）缩短码:在实际使用中，为了得到希望的码长和信息位长度，有时将 （n,k） 汉明码的信息位减少若干个 码元，这时构成一种（n-i,k-i）分组码，这 种码称为原码的缩短码。例如：（7,4）汉明码的缩短码为（6,3）码，其一致监督矩阵由原来的H将第一列去掉而得到1111 0 0吧 S 0 11 0 1 0 =1 0 1 0 0 1（6）增余汉明码:在汉明码的基础上，再增加一位监督元，它取为所有码元的模2加，这样使汉明码的最小码距 dmin=4,可以在纠一位错的同时检两 位错，这种线性分组码称为增余汉明码，也称为扩展汉明码。（其它线性分组码同样有扩展码。）例如：由（7,4）汉明码可以构成（8,4）增余汉明码，其一致监督矩阵 为：1 1 1 1 0 0 00 1 1 0 1 0 0吧 S 1 0 1 0 0 1 0 =1 1 1 1 1 1 1可以验证这种（8,4）增余汉明码可以纠一位错同时检两位错。（作业）（7）完备码:任何一个二元（n,k）线性分组码，有2k个码字，2n-k=2个校验子矢 量。若要纠正所有小于等于t个错误，就必须有大于等于t+1个校验 子矢量与之对应。分别指出无错和哪t位错。即校验子的个数必须满 足：t2n* 1； +cn+.+c： =z cn i -0这个关系式称为汉明界。它是构造纠正t位错的（n,k）码的必要条件。如果一个（n,k）线性分组码使汉明界的等号成立，校验子的个数与所有可纠正的错误图样数正好相等，说明校验位得到了充分的利用， 这种码称为完备码。（对于汉明码来说即称为狭义汉明码，否则称为 广义汉明码）完备码的标准阵译码表中，能将重量小于等于t的所有错误图样选作陪集首，而且不用大于t的禁用码字作为陪集首。完备码是较少的，可以证明：狭义汉明码是完备码，（23,12）Golay 码是完备码。如果译码表中除了使用重量小于等于 t的所有错误图样选作陪集 首外，还使用了一些重量等于t+1的错误图样作为陪集首，称为准完 备码，这种码字是比较多的。如果将一个（n,k）分组码的全部纠错能力都用于纠错，称为完备译 码。如果只用一部分用于纠错，另一部分用于检错或不使用，则称为 非完备译码。6-21