《线性分组码》PPT课件.ppt

第10章 线性分组码,10.1 线性分组码10.2生成矩阵和校验矩阵10.3特殊的线性分组码10.4伴随式和最小距离译码,2,线性分组码,分组码：将长为 k 位的信息码组变换成 n 重的码字(nk)。由 2k 个信息码组所编成的 码字集合，称为(n,k)分组码。码矢：一个 n 长的码字可以用矢量来表示C=(Cn1,Cn2,C1,C0)所以码字又称为码矢。编码速率/编码效率/码率/传信率：R=k/n。它说明了信道的利用效率，R是衡量码性能的一个重要参数。,3,线性分组码,码字重量：码字中非0码元符号的个数，汉明重量。在二元线性码中，码字重量是码字中含“1”的个数。等重码:所有码字具有相同的重量.汉明距离：在(n,k)分组码中，两个码字 U、V 之间对应码元位上符号取值不同的个数。最小距离dmin：任意两个码字间距离最小值.,例如：(7,3)码的两个码字 U=0011101,V=0100111，它们之间第2、3、4和6位不同。因此，码字 U 和 V 的距离为4。,4,线性分组码,汉明球：以码字C为中心，半径为 t 的汉明球是与 C 的汉明距离 t 的向量全体 SC(t)任意两个汉明球不相交最大程度取决于任意两个码字之间的最小汉明距离dmin。,5,线性分组码,线性分组码：ci,cj是GF(q)上(n,k)分组码中的两个码字,a,b GF(q)上两个元素,如果aci+bcj也是一个码字,称码为线性分组码。(包含全0码字，取a=-b),码的最小距离是衡量码的抗干扰能力（检、纠错能力）的重要参数。码的最小距离越大，码的抗干扰能力就越强。,6,线性分组码,有限域上的分组码当D是素数时，分组码可以充分利用有限域GF(D)的代数运算，使得编码和译码更加简便。,定义 取GF(D)上的一个K行N列的矩阵G，它是满行秩的。(N,K)分组码定义为(u1,u2,uN)=(x1,x2,xK)G其中(x1,x2,xK)是信息向量，(u1,u2,uN)是对应的码字。（1）称此码为D元(N,K)线性分组码。（2）称矩阵G为此码的生成矩阵。,7,线性分组码,线性分组码的代数结构命题1 不同的信息向量对应不同的码字。（变换u=xG是单射）命题2 生成矩阵G的第1行是信息向量(1,0,0,0)的码字；生成矩阵G的第2行是信息向量(0,1,0,0)的码字；生成矩阵G的第K行是信息向量(0,0,0,1)的码字。,8,线性分组码,命题3 信息向量(x1,x2,xK)的码字是：x1数乘G的第1行，加x2数乘G的第2行，加，加xK数乘G的第k行。即任何一个码字都是生成矩阵G的线性组合。命题4 当u(1)和u(2)都是码字，u(1)+u(2)也是码字。（线性分组码的码字关于线性运算封闭）证明 设u(1)是信息向量x(1)的码字：u(1)=x(1)G；u(2)是信息向量x(2)的码字：u(2)=x(2)G。则u(1)+u(2)=x(1)G+x(2)G=(x(1)+x(2)G，即u(1)+u(2)是信息向量(x(1)+x(2)的码字。,9,线性分组码,（命题3和命题4告诉我们，一个N维向量是一个码字，当且仅当它是生成矩阵G的第1行第L行的线性组合。还告诉我们，线性分组码的码字集合构成一个线性空间。这个线性空间是几维的？L维的，因为生成矩阵G的第1行第L行恰好是该线性空间的一组基底）,10,线性分组码,命题5 设一个D元(N,K)线性分组码的生成矩阵为G。设另一个D元(N,K)线性分组码的生成矩阵为G=MG，其中M是K阶可逆方阵。则两个码的码字集合完全重合，只是信息向量与码字的对应关系不同。,换句话说，如果把线性分组码的生成矩阵G做可逆行变换变成另一个生成矩阵，则不改变码字集合，只改变信息向量与码字的对应关系。,11,线性分组码,证明（要证明，第一个码中任一个码字也是第二个码中的码字；第二个码中任一个码字也是第一个码中的码字）设在第一个码中，u是信息向量x的码字：u=xG；则在第二个码中，u是信息向量xM-1的码字：u=xM-1MG=xM-1G。设在第二个码中，u是信息向量x的码字：u=xG；则在第一个码中，u是信息向量xM的码字：u=xMM-1G=xMG。,12,线性分组码,线性分组码的特例：系统码定义 D元(N,K)线性分组码的生成矩阵为G=PK(N-K),IK，其中IK是K阶单位阵，PK(N-K)是(N-K)K阶矩阵。则称此码为系统码。此时信息向量(x1,x2,xK)的码字是(u1,u2,uN)=(x1,x2,xK)G=(x1,x2,xK)PK(N-K),x1,x2,xK)。码字的后K位恰好是信息向量(x1,x2,xK)，称为码字的信息位。称码字的前N-K位为码字的一致校验位。,13,线性分组码,例 二元(7,4)码是线性分组码，生成矩阵G是由信息向量(1000)、(0100)、(0010)、(0001)的码字组成的4行,该码是系统码,14,线性分组码,例 二元(5,3)线性分组码的生成矩阵是,该码不是系统码，但是将生成矩阵经过可逆变换后，变成了一个系统码的生成矩阵,因此，该码的码字集合与一个系统码的码字集合相同,第10章 线性分组码,10.1 线性分组码10.2生成矩阵和校验矩阵10.3特殊的线性分组码10.4伴随式和最小距离译码10.5循环码,16,生成矩阵和校验矩阵,设ui是码字ci的k个信息位,ci构成一个K维子空间sC,选k个线性独立的码字gi构成sC的基底,则码字CC=u0g0+u1g1+uk-1gk-1,生成矩阵：由于矩阵 G 生成了(n,k)线性码，称矩阵 G 为(n,k)线性码的生成矩阵。,17,生成矩阵,线性系统分组码:通过行初等变换，将 G 化为前 k 列是单位子阵的标准形式,线性系统分组码：用标准生成矩阵Gkn 编成的码字，这种信息数字(k位)在前,校验数字(r=nk位)在后的线性分组码称为线性系统分组码。,kbit信息位,(n-k)bit校验位,18,生成矩阵,例(7,4)线性码的生成矩阵为,19,一致监督方程/一致校验方程：确定由信息元得到监督元规则的一组方程称为监督方程/校验方程。由于所有码字都按同一规则确定，又称为一致监督方程/一致校验方程。由于一致监督方程是线性的，即监督元和新信源之间是线性运算关系，所以由线性监督方程所确定的分组码是线性分组码。,校验矩阵,20,将监督方程写成矩阵形式，得可写成 H CT=0T或C HT=0校验矩阵,校验矩阵,21,校验矩阵 H 的后三列组成一个(33)阶单位子阵，用 I3 表示，H 的其余部分用 P 表示,校验矩阵,22,推广到一般情况：对(n,k)线性分组码，每个码字中的 r(r=nk)个监督元与信息元之间的关系可由下面的线性方程组确定,校验矩阵,23,校验矩阵,从另一个角度来看检验矩阵：每个(n,k)分组码都有一个维数为n-k的对偶码,参数(n,n-k),记为空间V，V的维数是n-k。G的校验矩阵H作为V的生成矩阵,有,24,生成矩阵和校验矩阵的关系,例(7,4)线性码的生成矩阵为,其对应的校验矩阵为,校验方程,25,最小重量/Wmin：线性分组码CI中，非0码字重量最小值，叫做码CI的最小重量：Wmin=minW(V),VCI,V0最小距离与最小重量的关系：线性分组码的最小距离等于它的最小重量。证明：设线性码CI，且UCI,VCI，又设UV=Z，由线性码的封闭性知，ZCI。因此，d(U,V)=W(Z)，由此可推知，线性分组码的最小距离必等于非0码字的最小重量。,校验矩阵的特性,26,校验矩阵的特性,由ciHT=0,所以H的列矢量线性相关.又最小距离dmin等于最小重量,所以H中存在dmin个列线性相关.H中小于或等于dmin-1个列肯定是线性独立的.(不存在重量为dmin-1的码，使其与H的内积为0)所以,第10章 线性分组码,10.1 线性分组码10.2生成矩阵和校验矩阵10.3特殊的线性分组码10.4伴随式和最小距离译码,28,伴随式和最小距离译码,对于离散无记忆对称信道，最大似然译码就是从所有可能码字中选择一个与接收字的汉明距离最小,即最小汉明距离译码,设发送码矢 Cm=(Cm0,Cm1,Cm,n-1),接收字为 R=(R0,R1,Rn-1)信道错误图样为 E=(E0,E1,En-1)=R-Cm=(R0-Cm0,R1-Cm1,Rn-1-Cm,n-1)，其中Ei=0，表示第i位无错；Ei=1，表示第i位有错,29,伴随式,用监督矩阵译码：接收到一个接收字 R 后，校验 RHT=0 是否成立?若关系成立，则认为 R 是一个码字；否则判为码字在传输中发生了错误；,伴随式：S=RHT=(C+E)HT=CHT+EHT由于CHT=0，所以 S=EHT伴随式仅与错误图样有关，而与发送的具体码字无关；,30,伴随式,伴随式仅与错误图样有关，与发送的具体码字无关；若S0，有错误出现。若S=0，可能是E=0 没有出错，接收字是一个码字；也可能是E0,但E为一个码字,这时有错误不能发现.这类错误称为不可检验错误图样。对于BSC其概率为：,Ai码中重量为i的码字数目,31,伴随式译码,举例：(7,3)码接收矢量 R 的伴随式计算.设发送码矢C=1010011，接收码字R1010011，R与C相同。,32,伴随式译码,若接收字中有一位错误,设发送码矢C=1010011，接收码字R1110011，伴随式,33,伴随式译码,当码元错误多于1个时,设发送码矢C=1010011，接收码字R0011011，伴随式,34,伴随式译码,将2n个可能的向量分为2n-k个集合，集合中每个向量的伴随式相同，这样的集合称为陪集选择陪集中重量最轻的向量作为陪集代表，称陪集首。,1.s=0的陪集，即码C中的元素排第一行，c=(000)排最左边，计e0.2.从其余的元素中选重量最轻的元素e1,并与码C中的元素相加，得到的元素分别列于相应的码字下面。3.从剩下的元素中任取一个重量最轻的，按相同方式构成第三行，依此类推,35,伴随式译码,伴随式,陪集首,陪集,36,伴随式译码,(6,3)码的标准阵,陪集首,伴随式,37,伴随式译码,第l个陪集首的重量,重量为i的陪集首的数量,BSC下，二元线性码正确译码的概率：,38,伴随式译码,译码步骤：计算接收矢量的伴随式由伴随式确定陪集首将陪集首作为错误图样e将v译为c=v-e,39,最小距离和纠错能力,Th.v属于码字集合的充要条件是v的非零码元与H相应列的乘积之和为0。推论：若矩阵H中任意d-1列线性无关，相应码的最小距离至少为d。,40,最小距离和纠错能力,1.最小距离与纠错能力：(n,k)线性码能纠t个错误的充要条件是码的最小距离为,证明：设码C的最小距离为dmin,以码字为中心，以t为半径的球应不相交。反证若相交，设V为其中元素，C1,C2为两相交球的码字，有三角不等式。d(C1,C2)d(C1,V)+d(V,C2)2tdmin-1与码的最小距离为dmin矛盾，固能纠正t个错误。,41,最小距离和纠错能力,如图：如果接收字R中错误个数tt，那么接收字R和发送字V间距离t，而与其它任何码字间距离都大于t，按最小距离译码把R译为V。此时译码正确，码字中的错误被纠正。几何意义：译码错误概率：,42,最小距离和纠错能力,2.最小距离与检、纠错能力：(n,k)线性码能纠 t 个错误，并能发现 l 个错误(l t)的充要条件是码的最小距离为 dmint+l+1,几何意义：,43,最小距离和纠错能力,当(n,k)线性码的最小距离 dmin 给定后，可按实际需要灵活安排纠错的数目。例如，对 dmin=8 的码，可用来纠3检4错，或纠2检5错，或纠1检6错，或者只用于检7个错误。,