线性分组码.ppt

第三章 线性分组码,一、线性分组码的一般性定义,定义：通过预定的线性运算将k维q元（q为素数幂）信息数组变换成n维（nk)码数组（称码字），由qk个码字所成的集合，称为n,k线性分组码，简称分组码。码字用（cn-1,cn-2,cn-k,cn-k-1,c1,c0)表示。码率（传信率，信道利用率）R=k/n表示信息位所占的比重。最简单的情况：在后面添加n-k个监督元，叫系统码（定义3.2.2)。,cn-k-1=h1,n-1cn-1+h1,n-2cn-2+h1,n-kcn-1cn-k-2=h2,n-1cn-1+h2,n-2cn-2+h2,n-kcn-1.c0=hn-k,n-1cn-1+hn-k,n-2cn-2+hn-k,n-kcn-1,h1,n-1 h1,n-2 h1,n-k 10 0 cn-1h2,n-1 h2,n-2 h2,n-k 01 0 cn-2=0.hn-k,n-1hn-k,n-2 hn-k,n-k001 c0,HcT=0T,二、线性分组码的严格数学定义,1.定义GF(q)中的元素（q为素数幂）组成的(n-k)n矩阵，其秩为n-k。满足方程HcT=0T的矢量c=(cn-1,cn-2,ci,c0)（ciGF(q)的集合称为n,k线性分组码。H称为监督（检验)矩阵。HcT=0T称为（一致）监督矩阵。,为什么秩为n-k？,一致：同一规则,对H进行初等变换，化为,h1,n-1 h1,n-2 h1,n-k 10 0 h2,n-1 h2,n-2 h2,n-k 01 0.hn-k,n-1hn-k,n-2 hn-k,n-k001,=Q In-k的形式，称为,H的标准形式。H称为典型监督矩阵。,二、线性分组码的严格数学定义2,2.定理1(码的封闭性）,设CH为由监督矩阵H定义的分组码，则c1,c2CH:c1+c2CH,证明：由c1CH，得Hc1T=0T;由c2CH，得Hc2T=0T;所以 H(c1+c2)T=H(c1T+c2T)=Hc1T+Hc2T=0Tc1+c2满足HcT=0T，所以c1+c2 CH,3.定理2,n,k线性分组码对矢量相加构成阿贝尔群。封闭性（定理1），结合律，有恒等元和逆元。,二、线性分组码的严格数学定义3,3.定理3,n,k线性分组码是GF(q)上的n维线性空间Vn中的一个k维子空间。证：设CH是由监督矩阵H定义的n,k线性码。1.先证CH为子空间。(1)CH是阿贝尔群(定理2);(2)aGF(q),cCH:a c CH;(3)分配律:c1,c2 CH,a,bGF(q):a(c1+c2)=ac1+ac2且(a+b)c1=ac1+bc1;(4)结合律成立:a1,a2 GF(q),cCH:(a1a2)c=a1(a2c).2.再证维数为k设cCH,则HcT=0T.c与H的每一行矢量正交,故c在由H的行矢量张成的n-k维线性子空间Vn,n-k的零空间中(第2章定理17,定理2.6.9),CH中每个码字和H张成的子空间的矢量正交,所以CH为H张成的子空间的零空间(第2章定理16,定理2.6.8),维数为k(第2章定理18,定理2.6.10)。,二、线性分组码的严格数学定义4,由第2章定理3可知，必存在k个线性独立的码字g1,g2,gk,使cCH:c=mn-1g1+mn-2g2+mn-kgk=m G,g1,n-1 g1,n-2 g1,0 g2,n-1 g2,n-2 g2,0.gk,n-1 gk,n-2 gk,0,G=,G称为n,k码的生成矩阵。G的标准形式IkP,称为典型生成矩阵。,基不同，G不同，但生成的空间是一样的，不同的G的意义是什么？,秩是多少？,三、G与H的关系,G的行矢量是码字，HgiT=0T,有HGT=0T,H与G所张成的空间互为零空间。CH:H校验，G生成。CG:G校验，H生成。,互为对偶码，若CH=CG,则称为自对偶码（P62),Q In-k IkPT=QIn-k IkT PTT=Q+PT=0所以 P=-QT 或 Q=-PT由此得 G=Ik P=Ik QTH=Q In-k=-PT In-k,三、G与H的关系2,例：已知7，3码（p52,例3.1),1 0 1|1 0 0 01 1 1|0 1 0 01 1 0|0 0 1 00 1 1|0 0 0 1,H=,c=(c6c5c4c3c2c1c0)由HcT=0T得c3=c6+c4c2=c6+c5+c4c1=c6+c5c0=c5+c4,1 1 1 00 1 1 11 1 0 1,P=-QT=,G=Ik P=,1 0 0|1 1 1 0 0 1 0|0 1 1 10 0 1|1 1 0 1,三、G与H的关系3,设信息组m=(m6m5m4)c6=m6c5=m5c4=m4c3=m6+m4=c6+c4c2=m6+m5+m4=c6+c5+c4c1=m6+m5=c6+c5c0=m5+m4=c5+c4,考虑如何用串行方式？,三、G与H的关系4,m4m5m6,m4m5,m5m6,m6,m6+m5,m6,m6,m4,m4m5m6,m6,m6,m6+m5,m6+m5+m6=m5,m6+m5,m6,m5+m4,m5+m4,m6+m5,m6+m5+m4,m6+m4,设信息组m=(m6m5m4)c6=m6c5=m5c4=m4c3=m6+m4=c6+c4c2=m6+m5+m4=c6+c5+c4c1=m6+m5=c6+c5c0=m5+m4=c5+c4,三、G与H的关系5,G=,1 0 0|1 1 1 0 0 1 0|0 1 1 10 0 1|1 1 0 1,写成多项式,g1(x)=x6+x3+x2+x=x(x5+x2+x+1)=x(x+1)(x4+x3+x2+1)g2(x)=x5+x2+x+1=(x+1)(x4+x3+x2+1)g3(x)=x4+x3+x2+1,g1(x)=x6+x3+x2+x=x(x+1)(x4+x3+x2+1)=x(x+1)g3(x)g2(x)=x5+x2+x+1=(x+1)(x4+x3+x2+1)=(x+1)g3(x)c(x)=m6g1(x)+m5g2(x)+m4g3(x)=m6g1(x)+m5g2(x)+m4g3(x)=m6x(x+1)g3(x)+m5(x+1)g3+m4g3(x)=(m6x2+m6x+m5x+m5+m4)g3(x)=m(x)g3(x)所有码字多项式都是g3(x)的倍式又因为是系统码c(x)=m(x)xn-k+r(x)0(mod g3(x)(信息位左移n-k位 加上监督位）r(x)-m(x)xn-k(mod g3(x)除法电路（见168页）,x6 x5x4 x3 x2x,四、线性分组码的最小距离、检错和纠错能力,检、纠错的必要条件：码字在一些码元发生错误后，还没有变成其它码字。为使码具有强的检错、纠错能力，各码字的距离差别（汉明距离）足够大。线性分组码的最小距离d(最小汉明距离）若n,k线性分组码的最小距离为d,记为n,k,d定理4：n,k分组码的最小距离d满足,d(c1,c2)=w(c1+c2)=w(c3),定理5：GF(2)上的n,k,d分组码中任何码字c1,c2满足:w(c1+c2)=w(c1)+w(c2)-2(c1c2)内积 或 d(c1,c2)w(c1)+w(c2)推论1：GF(2)上的n,k分组码满足:c1,c2,c3n,k:d(c1,c2)+d(c2,c3)d(c1,c3),c1,c2,c3,d(c1,c2),d(c1,c3),d(c2,c3),四、线性分组码的最小距离、检错和纠错能力2,定理6：(p12定理1.3.1)任一n,k,d，若要:(1)检测e个错误，则要求de+1(2)纠正t个错误，则要求d2t+1(3)纠正t个错误，或检测e(t)个错误，则要求d t+e+1(4)纠正t个错误和个删除，则要求d 2t+1,e,e,1,t,t,1,t,t,t,t,1,e,e,t,t,t,t,五、线性分组码的译码,1.伴随式,+,c,r=c+e,e,HcT=0THrT=H(c+e)T=HcT+HeT=HeT定义s rHT 称为接收字r 的伴随式（校正子）,h1,n-1 h1,n-2 h1,0h2,n-1 h2,n-2 h2,0.hn-k,n-1hn-k,n-2 hn-k,0,H=,=(hn-1,hn-2,h1,h0),设e=(en-1,en-2,e1,e0)=(0,ei1,ei2,eit,0),s=eHT=0,ei1,ei2,eit,0,hn-1Thn-2T.h1Th0T,=ei1 hi1T+ei2 hi2T+eit hi tT,发生错误的位所对应的列向量的线性组合,五、线性分组码的译码2,例：7，3码，H=,101|1000111|0100110|0010011|0001,s=r HT=(r6 r5 r4 r3 r2 r1 r0),101|1000111|0100110|0010011|0001,T,r6+r4+r3r6+r5+r4+r2r6+r5+r1r5+r4+r0,=,T,=（s3 s2 s1 s0),五、线性分组码的译码3,c=(1010011)e=(0100000)r=(1110011),s=r HT=e HT=(0100000),101|1000111|0100110|0010011|0001,T,=,0111,T,c=(1010011)e=(1001000)r=(0011011),s=r HT=e HT=(1001000),101|1000111|0100110|0010011|0001,T,=,1110,T,+,T,1000,=,(0110),五、线性分组码的译码4,若e=(0,0,ei,0,0)s=eihiT 若为二进制，则s=hiT 若要各列彼此区分，各列互不相同，即任意两列线性无关H(n-k)n最多可构成2n-k-1个互不相同的非零列，即必须保证 2n-k-1 n取下限，得2n-k-1=n，即为汉明码。,2.汉明码,定义（定义3.3.1)：GF(2)上的线性分组码n,k,d称为汉明码，若满足下列条件：(1)n=2m-1(mN,且m3)；(2)k=2m-m-1(3)n-k=m;(4)d=3。,五、线性分组码的译码5,构造办法：a.按H的二进制数的顺序排列。例GF(2)上的7,4,3的汉明码，m=3，23-1=7个非零列，3维矢量按07的二进制数排列,1 1 1 1 0 0 0 1 1 0 0 1 1 01 0 1 0 1 0 1,H=,b.系统码,1 1 1 0 1 0 0 1 1 0 1 0 1 01 0 1 1 0 0 1,H=,五、线性分组码的译码6,定理7：若n,k线性码的监督矩阵H任意s列线性无关，而存在s+1列线性相关，则d=s+1。反之，若d=s+1,则H的任意s列线性无关，而必存在有相关的s+1列。,e1s1=e1 HTe2s2=e2 HT若e1e2，希望s1s2.即保证e与s有一一对应关系。设e1=(0ei1.ei2eit)e2=(0ej1.ej2ejt)s1=ei1hi1T+ei2hi2T+eithitT s2=ej1hi1T+ej2hj2T+ejthjtT 若要s1s2，则s1-s2=ei1hi1T+ei2hi2T+eithitT-ej1hi1T-ej2hj2T-ejthjtT 0任2t列线性无关。d2t+1,3.线性分组码的最小距离与H的关系,问题：d=2t+1越大越好，能大到什么程度？,五、线性分组码的译码6,问题：d=2t+1越大越好，能大到什么程度？H的秩为n-k,有n-k列线性无关，但任n-k+1列线性相关。所以dn-k+1(推论3.3.1)取上限，得d=n-k+1,称为Singleton限。达到Singleton限的码称为极大最小距离可分码（MDS)。RS码达到此限。,五、线性分组码的译码7,由于线性分组码n,k,d是方程 HcT=0T的解空间,任一码字c满足cTH=0.若c经过信道到达终端变为r=c+e.如没有发生错误(e=0),则rTH=0;如果发生错误即e 0,这时有两种情况:e n,k,d,这时r n,k,d,也就是r变成了另外一个码字,rTH仍等于0;e n,k,d,这时rTH=cTH+eTH=eTH 0,只与e有关.由此可见,如果码字间的距离足够大以至发生了错误也不会变成另一个码字,则可从S=rTH判断码字在传输中是否有错,错误的图样是什么.s 称为伴随式.通过伴随式与错误的图样的一一对应关系来译码叫伴随式译码。,4.伴随式译码,s计算电路,se组合逻辑电路,r-e电路,r,s,五、线性分组码的译码8,5、标准阵列译码,c1=0c2.ci.cj.c2ke2c2+e2.ci+e2.cj+e2.c2k+e2e3c2+e3.ci+e3.cj+e3.c2k+e3.emc2+em.ci+em.cj+em.c2k+em.e2n-kc2+e2n-k.ci+e2n-k.cj+e2n-k.c2k+e2n-k,最佳码：使w=w(e2)+w(e3)+w(em)+w(e2n-k)为最小的码不是唯一，p64表3-3，p15表1-2。,由于Fq上线性码C=n,k是n维矢量线性空间V的qk阶加法子群,故V可划分为qn/qk=qn-k个C的不同陪集(包括C).如果第一个陪集C+e2的陪集首e2取V-C中重量最小者,第二个陪集C+e3的陪集首e3取V-C-(C+e2)中重量最小者,依次类推可得C的各个陪集,由它们排列成译码的标准阵列.,群码 C,译为cj,错误图样,em的陪集,以剩余矢量中重量最小者为陪集首,五、线性分组码的译码9,c1=0c2.ci.cj.c2ke2c2+e2.ci+e2.cj+e2.c2k+e2e3c2+e3.ci+e3.cj+e3.c2k+e3.emc2+em.ci+em.cj+em.c2k+em.e2n-kc2+e2n-k.ci+e2n-k.cj+e2n-k.c2k+e2n-k,证明标准阵列译码符合最小距离译码准则,即证：d(ci+em,ci)d(ci+em,cj),证明：d(ci+em,ci)=w(em)d(ci+em,cj)=w(ci+cj+em)=w(cq+em)由标准阵列的生成规则，得w(em)w(cq+em)下证不相等。由d(cq,em)+d(cq+em,cq)d(cq+em,em),得w(cq+em)+w(em)w(cq)w(cq+em)w(cq)-w(em)又若 d(cq,0)2 w(em)+1，则 w(cq)2 w(em)+1,所以w(cq+em)2w(em)+1-w(em)=w(em)+1w(em)w(cq+em),cq+em,cq,em,五、线性分组码的译码10,最佳码：使w=w(e0)+w(e1)+.+w(e2n-k)为最小的码。不是唯一，表3-3，表1-2。5.完备码,定理8：GF(2)上的(n,k)线性码能纠2n-k个错误图样,错误图样数,所以 2n-k,n-k:监督元数目,t:纠错能力,取下限，得2n-k=,满足这个条件的叫完备码（定义3.3.2)。可见，完备码的纠错能力达到极限。,问题：如果是多元码，情况会怎样？,五、线性分组码的译码11,汉明码2m-1,2m-1-m,3是能纠一个错的2元完备码(=1+2m-1=2m).,定义（定义3.3.1)：GF(2)上的线性分组码n,k,d称为汉明码，若满足下列条件：(1)n=2m-1(mN,且m3)；(2)k=2m-m-1(3)n-k=m;(4)d=3。,戈莱(Golay)码23,12,7（P202-203)是目前唯一已知能纠多个错误的2元完备码,六、由一个已知码构造新码的简单方法,扩展码：增加一个检验位n,k n+1,k加奇偶校验位，一般为偶校验。,H=,对于汉明码2m-1,2m-1-m,3,由于d=3,H任两列线性无关同时存在线性相关的3列,而在H中,任三列线性无关(最后一位3个1相加不为0),但存在线性相关的4列(原在H中线性相关的3列加上H的最后一列),所以H确定了扩展汉明码2m,2m-1-m,4.,2.删除码：删去一个检验位（和扩展码相反）n,k n-1,k,六、由一个已知码构造新码的简单方法2,3.增广码：（增信删余码）增加一个信息元，删去一个校验元n,k n,k+1,4.增余删信码删去一个信息元，增加一个校验元 n,k n,k-1,5.延长码先增广，后扩展n,k n,k+1 n+1,k+1,扩展,原码,增余删信,扩展,删除,缩短,n,k,n+1,k,n,k-1,延长,增余删信,增信删余,6.缩短码删去一个信息元 缩短循环码（p157,5.4节）n,k n-1,k-1,七、线性码的不可检测错误概率Pu(e),当错误图样是一个非零码字时，s=0，这时无法检测错误。共有2k-1个非零码字,1.根据n和d求Pu(e),01,01,1-p,p,p,对于2进制对称信道(BSC),1-p,2.由(n,k)的重量分布A0,A1,Ai,An求Pu(e),Ai表示重量为i的码字的个数,七、线性码的不可检测错误概率Pu(e)（2）,3.由(n,k)的对偶码的重量分布B0,B1,Bi,Bn求Pu(e),（1）,（2）,七、线性码的不可检测错误概率Pu(e)（3）,4.GF(2)上Pu(e)的上限,当n,k很大时，计算A0,A1,Ai,An和 B0,B1,Bi,Bn 比较困难，一般可取Pu(e)平均值的上限定理9：二进制n,k线性分组码集合中，Pu(e)的平均值满足,Pu(e)随着监督位的上升而下降,八、线性码的码距限,即d的上下限,1.普洛特金（Plotkin)限（P限）,定理10.GF(q)上的线性分组码n,k,d满足(定理3.8.1),H的秩为n-k,有n-k列线性无关，但任n-k+1列线性相关。所以dn-k+1(推论3.3.1)取上限，得d=n-k+1,称为Singleton限。达到Singleton限的码称为极大最小距离可分码（MDS)。RS码达到此限。,八、线性码的码距限2,3.沃尔沙莫夫-吉尔伯特限（V-G限）,普洛特金限和汉明限为构造码的必要条件，而码限为充分条件,定理12.设q为素数幂，若r=n-k是满足,的最小整数，则一定可以构造一个n,k,d线性码,(定理3.8.3),汉明限,2.汉明限（球包限、H限）,定理11.若GF(q)上的线性分组码n,k,dd2t+1,则(定理3.8.2),二元汉明限,取等号为完备码,