第十章-线性分组码

WuhanUniversity第10章线性分组码10.1线性分组码10.2生成矩阵和校验矩阵10.3特殊的线性分组码10.4伴随式和最小距离译码WuhanUniversity2线性分组码分组码：将长为k位的信息码组变换成n重的码字(nk)。由2k个信息码组所编成的码字集合，称为(n,k)分组码。码矢：一个n长的码字可以用矢量来表示C=(Cn－1,Cn－2,…,C1,C0)所以码字又称为码矢。编码速率/编码效率/码率/传信率：R=k/n。它说明了信道的利用效率，R是衡量码性能的一个重要参数。WuhanUniversity3线性分组码码字重量：码字中非0码元符号的个数，汉明重量。在二元线性码中，码字重量是码字中含“1”的个数。等重码:所有码字具有相同的重量.汉明距离：在(n,k)分组码中，两个码字U、V之间对应码元位上符号取值不同的个数。最小距离dmin：任意两个码字间距离最小值.例如：(7,3)码的两个码字U=0011101,V=0100111，它们之间第2、3、4和6位不同。因此，码字U和V的距离为4。WuhanUniversity4线性分组码汉明球：以码字C为中心，半径为t的汉明球是与C的汉明距离≤t的向量全体SC(t)任意两个汉明球不相交最大程度取决于任意两个码字之间的最小汉明距离dmin。tRCdRSt),()(CWuhanUniversity5线性分组码线性分组码：ci,cj是GF(q)上(n,k)分组码中的两个码字,a,bGF(q)上两个元素,如果aci+bcj也是一个码字,称码为线性分组码。(包含全0码字，取a=-b)码的最小距离是衡量码的抗干扰能力（检、纠错能力）的重要参数。码的最小距离越大，码的抗干扰能力就越强。WuhanUniversity6线性分组码有限域上的分组码当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为此码的生成矩阵。WuhanUniversity7线性分组码线性分组码的代数结构命题1不同的信息向量对应不同的码字。（变换u=xG是单射）命题2生成矩阵G的第1行是信息向量(1,0,0,…,0)的码字；生成矩阵G的第2行是信息向量(0,1,0,…,0)的码字；…生成矩阵G的第K行是信息向量(0,…,0,0,1)的码字。WuhanUniversity8线性分组码命题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))的码字。WuhanUniversity9线性分组码（命题3和命题4告诉我们，一个N维向量是一个码字，当且仅当它是生成矩阵G的第1行~第L行的线性组合。还告诉我们，线性分组码的码字集合构成一个线性空间。这个线性空间是几维的？L维的，因为生成矩阵G的第1行~第L行恰好是该线性空间的一组基底）WuhanUniversity10线性分组码命题5设一个D元(N,K)线性分组码的生成矩阵为G。设另一个D元(N,K)线性分组码的生成矩阵为G’=MG，其中M是K阶可逆方阵。则两个码的码字集合完全重合，只是信息向量与码字的对应关系不同。换句话说，如果把线性分组码的生成矩阵G做可逆行变换变成另一个生成矩阵，则不改变码字集合，只改变信息向量与码字的对应关系。WuhanUniversity11线性分组码证明（要证明，第一个码中任一个码字也是第二个码中的码字；第二个码中任一个码字也是第一个码中的码字）设在第一个码中，u是信息向量x的码字：u=xG；则在第二个码中，u是信息向量xM-1的码字：u=xM-1MG=xM-1G’。设在第二个码中，u是信息向量x的码字：u=xG’；则在第一个码中，u是信息向量xM的码字：u=xMM-1G’=xMG。WuhanUniversity12线性分组码线性分组码的特例：系统码定义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位为码字的一致校验位。WuhanUniversity13线性分组码例二元(7,4)码是线性分组码，生成矩阵G是由信息向量(1000)、(0100)、(0010)、(0001)的码字组成的4行1000101010011100101100001011G该码是系统码WuhanUniversity14线性分组码例二元(5,3)线性分组码的生成矩阵是111110110000111G100110101100111100110110000111111110110000111该码不是系统码，但是将生成矩阵经过可逆变换后，变成了一个系统码的生成矩阵因此，该码的码字集合与一个系统码的码字集合相同WuhanUniversity第10章线性分组码10.1线性分组码10.2生成矩阵和校验矩阵10.3特殊的线性分组码10.4伴随式和最小距离译码10.5循环码WuhanUniversity16生成矩阵和校验矩阵设ui是码字ci的k个信息位,{ci}构成一个K维子空间sC,选k个线性独立的码字gi构成sC的基底,则码字CC=u0g0+u1g1+…+uk-1gk-1生成矩阵：由于矩阵G生成了(n,k)线性码，称矩阵G为(n,k)线性码的生成矩阵。WuhanUniversity17生成矩阵线性系统分组码:通过行初等变换，将G化为前k列是单位子阵的标准形式线性系统分组码：用标准生成矩阵Gk×n编成的码字，这种信息数字(k位)在前,校验数字(r=n－k位)在后的线性分组码称为线性系统分组码。kbit信息位(n-k)bit校验位WuhanUniversity18生成矩阵例(7,4)线性码的生成矩阵为WuhanUniversity19一致监督方程/一致校验方程：确定由信息元得到监督元规则的一组方程称为监督方程/校验方程。由于所有码字都按同一规则确定，又称为一致监督方程/一致校验方程。由于一致监督方程是线性的，即监督元和新信源之间是线性运算关系，所以由线性监督方程所确定的分组码是线性分组码。校验矩阵WuhanUniversity20将监督方程写成矩阵形式，得可写成HCT=0T或CHT=0校验矩阵校验矩阵WuhanUniversity21校验矩阵H的后三列组成一个(3×3)阶单位子阵，用I3表示，H的其余部分用P表示校验矩阵WuhanUniversity22推广到一般情况：对(n,k)线性分组码，每个码字中的r(r=n－k)个监督元与信息元之间的关系可由下面的线性方程组确定校验矩阵WuhanUniversity23校验矩阵从另一个角度来看检验矩阵：每个(n,k)分组码都有一个维数为n-k的对偶码,参数(n,n-k),记为空间V，V的维数是n-k。G的校验矩阵H作为V的生成矩阵,有WuhanUniversity24生成矩阵和校验矩阵的关系例(7,4)线性码的生成矩阵为其对应的校验矩阵为校验方程WuhanUniversity25最小重量/Wmin：线性分组码CI中，非0码字重量最小值，叫做码CI的最小重量：Wmin=min{W(V),V∈CI,V≠0}最小距离与最小重量的关系：线性分组码的最小距离等于它的最小重量。[证明]：设线性码CI，且U∈CI,V∈CI，又设U－V=Z，由线性码的封闭性知，Z∈CI。因此，d(U,V)=W(Z)，由此可推知，线性分组码的最小距离必等于非0码字的最小重量。校验矩阵的特性WuhanUniversity26校验矩阵的特性由ciHT=0,所以H的列矢量线性相关.又最小距离dmin等于最小重量,所以H中存在dmin个列线性相关.H中小于或等于dmin-1个列肯定是线性独立的.(不存在重量为dmin-1的码，使其与H的内积为0)所以WuhanUniversity第10章线性分组码10.1线性分组码10.2生成矩阵和校验矩阵10.3特殊的线性分组码10.4伴随式和最小距离译码WuhanUniversity28伴随式和最小距离译码对于离散无记忆对称信道，最大似然译码就是从所有可能码字中选择一个与接收字的汉明距离最小,即最小汉明距离译码设发送码矢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位有错WuhanUniversity29伴随式用监督矩阵译码：接收到一个接收字R后，校验RHT=0是否成立?若关系成立，则认为R是一个码字；否则判为码字在传输中发生了错误；伴随式：S=RHT=(C+E)HT=CHT+EHT由于CHT=0，所以S=EHT伴随式仅与错误图样有关，而与发送的具体码字无关；WuhanUniversity30伴随式伴随式仅与错误图样有关，与发送的具体码字无关；若S≠0，有错误出现。若S=0，可能是E=0没有出错，接收字是一个码字；也可能是E≠0,但E为一个码字,这时有错误不能发现.这类错误称为不可检验错误图样。对于BSC其概率为：Ai码中重量为i的码字数目WuhanUniversity31伴随式译码举例：(7,3)码接收矢量R的伴随式计算.设发送码矢C=1010011，接收码字R＝1010011，R与C相同。WuhanUniversity32伴随式译码若接收字中有一位错误,设发送码矢C=1010011，接收码字R＝1110011，伴随式WuhanUniversity33伴随式译码当码元错误多于1个时,设发送码矢C=1010011，接收码字R＝0011011，伴随式WuhanUniversity34伴随式译码将2n个可能的向量分为2n-k个集合，集合中每个向量的伴随式相同，这样的集合称为陪集选择陪集中重量最轻的向量作为陪集代表，称陪集首。1.s=0的陪集，即码C中的元素排第一行，c=(00…0)排最左边，计e0.2.从其余的元素中选重量最轻的元素e1,并与码C中的元素相加，得到的元素分别列于相应的码字下面。3.从剩下的元素中任取一个重量最轻的，按相同方式构成第三行，依此类推…WuhanUniversity35伴随式译码伴随式陪集首陪集WuhanUniversity36伴随式译码(6,3)码的标准阵陪集首伴随式WuhanUniversity37伴随式译码第l个陪集首的重量重量为i的陪集首的数量BSC下，二元线性码正确译码的概率：WuhanUniversity38伴随式译码译码步骤：计算接收矢量的伴随式由伴随式确定陪集首将陪集首作为错误图样e将v译为c=v-eWuhanUniversity39最小距离和纠错能力Th.v属于码字集合的充要条件是v的非零码元与H相应列的乘积之和为0。推论：若矩阵H中任意d-1列线性无关，相应码的最小距离至