第六章线性分组码.ppt

2020/6/5,1,第六章：线性分组码,6.1分组码的概念(与主教材标题不同)6.2线性分组码6.3线性分组码的校验矩阵(与主教材标题不同)6.5译码方法和纠错能力(与主教材标题不同)6.4、6.6、6.7、6.8一些特殊的线性分组码,2020/6/5,2,6.1分组码的概念,设信道是一个D元字母输入/D元字母输出的DMC信道，字母表为0,1,D-1。其信道转移概率矩阵为DD矩阵传输错误的概率为p。信道容量为C=logD-H(p)-plog(D-1)。,2020/6/5,3,6.1分组码的概念,对随机变量序列X1X2进行的信道编码为(N,L)码：(X1X2XL)(U1U2UN)=C(X1X2XL)。这个(N,L)码又称为(N,L)分组码。已经有结论：当设备所确定的编码速率R(dmin-1)/2；d(c,u)=d(c,y)+d(y,u)。（三角不等式变为等式）（请注意，这样的向量y存在！）此时d(c,y)=d(c,u)-d(y,u)=dmin-(dmin-1)/2+1=dmin-1-(dmin-1)/2。,2020/6/5,39,d(y,u)=(dmin-1)/2+1；d(c,y)=dmin-1-(dmin-1)/2。,当dmin是奇数时，d(y,u)=(dmin-1)/2+1，d(c,y)=(dmin-1)/2，故d(c,y)(dmin-1)/2，则未必e(s)=e，因而未必c=u。换句话说，如果w(e)(dmin-1)/2，则e一定是s=eHT的陪集首；如果w(e)(dmin-1)/2，则e未必是s=eHT的陪集首。,2020/6/5,41,6.5译码方法和纠错能力,定理6.5.4记真正的差错向量为e。记t是一个非负整数。如果（1）当w(e)t时总是能够正确译码，（2）当w(e)t时并不总是能够正确译码，则t=(dmin-1)/2。推论记真正的差错向量为e。事件“总是能够正确译码”定义为“w(e)(dmin-1)/2”。则“总是能够正确译码”的概率为,2020/6/5,42,6.5译码方法和纠错能力,定理6.5.4说明，dmin是线性分组码纠错能力的一个指标。dmin越大，(dmin-1)/2就越大，“总是能够正确译码”的概率也越大。当N比L大得越多，码字在所有N维向量中占的比例越小，越容易使得dmin大。问题是，当N和L都确定时，如何设计码使得dmin大。纠正一种误解：dmin越大，“总是能够正确译码”的概率越大。决不能说：dmin越大，正确译码的概率越大。（？）,2020/6/5,43,6.5译码方法和纠错能力,例二元（6，3）线性分组码，生成矩阵G已经给出。求一致校验矩阵H；码字集合；译码预计算（简化计算量）。显然是系统码。,2020/6/5,44,6.5译码方法和纠错能力,信息向量码字000000000100011100010101010001110001110110110101101101011011011111000111,2020/6/5,45,6.5译码方法和纠错能力,伴随式s对应的所有“可能的差错向量”e000000000，011100，101010，110001，110110，101101，011011，000111100100000，111100，001010，010001，010110，001101，111011，100111010010000，001100，111010，100001，100110，111101，001011，010111001001000，010100，100010，111001，111110，100101，010011，001111110000100，011000，101110，110101，110010，101001，011111，000011101000010，011110，101000，110011，110100，101111，011001，000101011000001，011101，101011，110000，110111，101100，011010，000110111100100，111000，001110，010101，010010，001001，111111，100011,伴随式s陪集首e(s)000000000100100000010010000001001000110000100101000010011000001111100100,2020/6/5,46,6.5译码方法和纠错能力,dmin=3；(dmin-1)/2=1。当真正的差错向量的Hamming重量不超过1时，总是能够正确译码；当真正的差错向量的Hamming重量超过1时，未必总是能够正确译码。总是能够正确译码的概率为(1-p)6+6(1-p)5p。正确译码的概率为(1-p)6+6(1-p)5p+(1-p)4p2。若p=10-2，则(1-p)6=0.9415；(1-p)6+6(1-p)5p=0.9986；(1-p)6+6(1-p)5p+(1-p)4p2=0.9987。,2020/6/5,47,6.5译码方法和纠错能力,设信道的输出向量为y=(111111)。计算伴随式s=yHT=(111)。以s为地址查找e(s)=(100100)。计算c=y-e(s)=(111111)-(100100)=(011011)。信息向量为(011)。,2020/6/5,48,6.4、6.6、6.7、6.8一些特殊的线性分组码,二元Hamming码N=2m-1，L=2m-1-m，即二元(2m-1，2m-1-m)线性分组码。其校验矩阵是如下的m(2m-1)阶矩阵H：H的(2m-1)列恰好是(2m-1)个非全0的m维向量。因此：校验矩阵H的任意一列不是全0的m维向量；校验矩阵H的任意两列互不相同；校验矩阵H的某三列的和为全0的m维向量。换句话说，重量为1、重量为2的2m-1维向量都不是码字，而某些重量为3的2m-1维向量是码字。再换句话说，Hamming码的dmin=3。再换句话说，当差错向量的重量不超过1时，肯定能够正确译码。编码效率为R=(2m-1-m)/(2m-1)。（编码效率大）,2020/6/5,49,6.4、6.6、6.7、6.8一些特殊的线性分组码,定义如果存在一个t，使得任一个接收向量y，都有唯一的码字u满足d(y,u)t，则称该码为t阶完备码。命题当一个(N，L)线性分组码是t阶完备码时，所有不同伴随式所对应的陪集首恰好是所有重量不超过t的N维向量。注意：不同伴随式的个数为2N-L，重量不超过t的N维向量的个数为定理二元Hamming码（它是二元(2m-1，2m-1-m)线性分组码）是1阶完备码。（2m=1+2m-1）,2020/6/5,50,6.4、6.6、6.7、6.8一些特殊的线性分组码,Hadamard码从Hadmard矩阵的行中选择码字可以构造出Hadamad码。Hadmard矩阵Mn是一个nn阶矩阵，其中n=2m。该矩阵满足有一行为全0行，其余的行有2m-1个0，2m-1个1。任意两行有2m-1个位置不同，2m-1个位置相同。如何构造Hadmard矩阵？看如下的递归方法。,2020/6/5,51,6.4、6.6、6.7、6.8一些特殊的线性分组码,以Hadmard矩阵Mn的所有行作为所有的码字，得到的码就是Hadamad码。Hadamad码的参数如下：共有n个码字，因此共有n个信息，因此信息长为logn=m。码长为n。编码效率为R=m/n=m/2m。（编码效率小）任何两个码字的Hamming距离都等于2m-1=n/2。因此dmin=2m-1=n/2。Mn的任意m个非全0行都是线性无关的，因此生成矩阵可能是Mn的任意m个非全0行构成的mn阶矩阵。（？）,2020/6/5,52,6.4、6.6、6.7、6.8一些特殊的线性分组码,Golay码Golay码是线性(23,12)码，最小距离为7。将其增加一个全校验位扩展为二元线性（24,12）码，最小距离为8，称为扩展Golay码。表6.4.1给出了Golay码和扩展Golay码的重量分布。循环码定义6.6.1(p188)一个二元(N,L)线性分组码C，若对任意c=(c0,c1,c2,cN-1)C，恒有c=(cN-1,c0,c1,cN-2)C，则称C为二元循环码。,2020/6/5,53,6.4、6.6、6.7、6.8一些特殊的线性分组码,二元循环码的产生过程取二元域GF(2)=(0,1,(mod2)加法,(mod2)乘法)。取GF(2)上的N次多项式1+xN。取多项式1+xN的（在GF(2)上的）一个N-L次因式g(x)：g(x)=g0+g1x1+g2x2+gN-LxN-L。取以下的LN矩阵G作为二元(N,L)线性分组码C的生成矩阵，则该码一定就是一个二元循环码。（主教材中有证明）,2020/6/5,54,6.4、6.6、6.7、6.8一些特殊的线性分组码,例6.6.1(p190)例6.6.2(p192)取N=7。则（在GF(2)上）：1+x7=(1+x)(1+x+x3)(1+x2+x3)。若取g(x)=1+x+x3，则产生的二元(7,4)线性分组码C一定就是一个二元循环码，生成矩阵为,2020/6/5,55,6.4、6.6、6.7、6.8一些特殊的线性分组码,如此产生的二元循环码的译码设接收向量为y=(y0,y1,y2,yN-1)。记y(x)=y0+y1x1+y2x2+yN-1xN-1。用g(x)除y(x)，得余式s(x)=s0+s1x1+s2x2+sN-L-1xN-L-1。则此时：除式y(x)=q(x)g(x)+s(x)也可以表示成y(x)s(x)(modg(x)。余式s(x)的次数一定不超过N-L-1。N-L维向量s=(s0,s1,s2,sN-L-1)就是接收向量y的伴随式。（因而不需要校验矩阵）,2020/6/5,56,习题课,6.1设有4个消息al，a2，a3和a4被编成为长为5的二元码的00000，01101，10111，l1010。(a)试给出码的一致校验关系。(b)若通过转移概率为p1/2的BSC传送，试给出最佳译码表及相应的译码错误概率表示式。(c)若码通过BEC信道传送，试问可恢复几个删除?其最佳译码表应如何配置？(d)一般，最小距离为dmin的线性码，可恢复几个删除?,2020/6/5,57,习题课,(a)首先需要验证该码是线性码：01101+10111=l1010。其次需要给出该码的生成矩阵和校验矩阵：最后该码的一致校验关系为：对任意码字(x0 x1x2x3x4)，恒有x0+x1+x2=0，x0+x3=0，x0+x1+x4=0。,2020/6/5,58,习题课,(b)通过转移概率为p1/2的BSC传送。如果直接按照“最小距离准则”来求最佳译码表，则最佳译码表为,2020/6/5,59,习题课,求“译码错误概率表示式”，可以有多种含义。本题应该理解为以下的含义，而不应该理解为别的含义：,2020/6/5,60,求最佳译码表，当然也可以采用标准方法，先求可能的差错向量、伴随式、陪集首的关系：,2020/6/5,61,习题课,根据公式：“接收向量”-“陪集首”=“所要译为的码字”，得到的最佳译码表仍然是,2020/6/5,62,习题课,求“译码错误概率表示式”，第一种的理解是：,2020/6/5,63,习题课,求“译码错误概率表示式”，第二种的理解是：,2020/6/5,64,(c)若码通过BEC信道传送，则至少可恢复dmin-1=2个删除。因此，当接收向量中有不超过2个删除时，对应译码值是显然的。当接收向量中有大于2个删除时，对应译码值比较复杂。(d)一般，最小距离为dmin的线性码，可恢复dmin-1个删除。理由很简单：一个码字，它的dmin-1个分量“模糊不清”，根据该码字的其它N-(dmin-1)个分量来唯一确定码字。如果竟然确定了两个码字满足条件，则这两个码字的距离dmin-1。矛盾。,2020/6/5,65,习题课,6.2设证件号码由7位10进制数x7x6x1构成。今附加一位校验位x0，其中若(x7x6x1)(8245123)，试求x0。若其中数字x6模糊不清时，能否恢复出原来的数字？6.2的解答x0=33+29+127+581+4243+2729+82187(mod10)=5。若其中数字x6模糊不清时，5=33+29+127+581+4243+x6729+82187(mod10)。7=x69(mod10)。x6=79(mod10)=3。,2020/6/5,66,习题课,更深入的解释：10元(8,7)线性分组码，即所用的加法和乘法是模10加法和乘法。信息向量为(x7x6x1)，对应的码字为(x7x6x1x0)，生成矩阵为,2020/6/5,67,习题课,一个校验矩阵为H=3,1,7,9,3,1,7,1。即：8维向量(x7x6x1x0)是一个码字，当且仅当3x7+x6+7x5+9x4+3x3+x2+7x1+x0(mod10)=0。若码字其中有个别数字模糊不清，说明将码字输入了“纯删除信道”。当只有一个位置模糊不清时，根据其它7个位置的值可以恢复模糊不清的数字。严重的问题：10不是素数！因此，0,1,9关于模10加法和模10乘法不构成有限域！不过只要生成矩阵G关于模10是满行秩的，仍然可以得到10元(8,7)线性分组码。,2020/6/5,68,习题课,6.4设二元(6,3)码的生成矩阵为试给出它的校验矩阵。6.4的解答,2020/6/5,69,习题课,6.5令x(x1x2x3x4)是GF(3)上的