线性分组码.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-1 cn-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-1 h2,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=0T c1+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 QT H=Q In-k= -PT In-k,三、G与H的关系2,例： 已知7，3码（p52, 例3.1),1 0 1 | 1 0 0 0 1 1 1 | 0 1 0 0 1 1 0 | 0 0 1 0 0 1 1 | 0 0 0 1,H=,c=(c6c5c4c3c2c1c0) 由HcT=0T得 c3=c6+c4 c2=c6+c5+c4 c1=c6+c5 c0=c5+c4,1 1 1 0 0 1 1 1 1 1 0 1,P= -QT=,G=Ik P =,1 0 0 | 1 1 1 0 0 1 0 | 0 1 1 1 0 0 1 | 1 1 0 1,三、G与H的关系3,设信息组m = (m6m5m4) c6=m6 c5=m5 c4=m4 c3=m6+m4=c6+c4 c2=m6+m5+m4=c6+c5+c4 c1=m6+m5=c6+c5 c0=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=m6 c5=m5 c4=m4 c3=m6+m4=c6+c4 c2=m6+m5+m4=c6+c5+c4 c1=m6+m5=c6+c5 c0=m5+m4=c5+c4,三、G与H的关系5,G=,1 0 0 | 1 1 1 0 0 1 0 | 0 1 1 1 0 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=0T HrT= H(c+e)T= HcT+HeT= HeT 定义s rHT 称为接收字r 的伴随式（校正子）,h1,n-1 h1,n-2 h1,0 h2,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-1T hn-2T . h1T h0T,= ei1 hi1T+ +ei2 hi2T+ eit hi tT,发生错误的位所对应的列向量的线性组合,五、线性分组码的译码2,例：7，3码， H=,101 | 1000 111 | 0100 110 | 0010 011 | 0001,s = r HT= ( r6 r5 r4 r3 r2 r1 r0 ),101 | 1000 111 | 0100 110 | 0010 011 | 0001,T,r6 + r4 + r3 r6 + r5 + r4 + r2 r6 + r5 + r1 r5 + r4 + r0,=,T,= （s3 s2 s1 s0),五、线性分组码的译码3,c =(1010011) e =(0100000) r =(1110011),s = r HT = e HT = (0100000),101 | 1000 111 | 0100 110 | 0010 011 | 0001,T,=,0 1 1 1,T,c =(1010011) e =(1001000) r = (0011011),s = r HT = e HT = (1001000),101 | 1000 111 | 0100 110 | 0010 011 | 0001,T,=,1 1 1 0,T,+,T,1 0 0 0,=,(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 0 1 0 1 0 1 0 1,H=,b. 系统码,1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 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 HT e2s2=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=0 c2 ci cj c2k e2 c2+e2 ci+e2 cj +e2 c2k+e2 e3 c2+e3 ci+e3 cj +e3 c2k+e3 em c2+em ci+em cj +em c2k+em e2n-k c2+ 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=0 c2 ci cj c2k e2 c2+e2 ci+e2 cj +e2 c2k+e2 e3 c2+e3 ci+e3 cj +e3 c2k+e3 em c2+em ci+em cj +em c2k+em e2n-k c2+ 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) +1 w(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),0 1,0 1,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),二元汉明限,取等号为完备码,