线性分组码ppt课件

2022-11-516.3.1 一般概念6.3.2 线性分组码的监督方程和监督矩阵6.3.3 线性分组码的生成矩阵6.3.4 线性分组码的编码6.3.5 线性分组码的译码6.3.6 汉明码6.3 线性分组码2022-11-52n一、名词解释n线性分组码：通过预定的线性运算将长为 k 位的信息码组变换成 n 长的码字(nk)。由 2k 个信息码组所编成的 2k个码字集合，称为线性分组码。n码矢码矢：一个 n 长的码字可以用矢量来表示C=(Cn1,Cn2,C1,C0)所以码字又称为码矢。n(n,k)线性码线性码：信息位长为 k，码长为 n 的线性码。n编码效率编码效率/编码速率/码率：R=k/n。它说明了信道的利用效率，R是衡量码性能的一个重要参数是衡量码性能的一个重要参数。6.3.1 一般概念2022-11-53n线性分组码的编码线性分组码的编码：线性分组码的编码过程分为两步：n把信息序列按一定长度分成若干信息码组，每组由 k 位组成；n编码器按照预定的线性规则(可由线性方程组规定)，把信息码组变换成 n 长(nk)码字，其中(nk)个附加码元是由信息码元的线性运算产生的。n信息码组长为 k 位，若有 2k 个不同的信息码组，则有 2k 个码字与它们一一对应。2022-11-54 线性分组码是前向纠错码，它可以在无需重发的情况下检测出有限个错码，并加以纠正。当其他改善手段（如增加发射功率或使用复杂的解调器）不切实际时，分组码可以用来改善通信系统的性能。在分组编码器中，k个信息位被编成n位，从而对k个信息位增加了n-k个冗余位，而冗余位的作用是检测和纠正错码。2022-11-55(1)监督方程n编码就是给已知信息码组按预定规则添加监督码元，以构成码字。n在 k 个信息码元之后附加 r(r=nk)个监督码元，使每个监督元是其中某些信息元的模2和。n举例：k=3,r=4，构成(7,3)线性分组码。设码字为n(C6,C5,C4,C3,C2,C1,C0)nC6,C5,C4为信息元，C3,C2,C1,C0为监督元，每个码元取“0”或“1”n监督元可按下面方程组计算6.3.2 线性分组码的监督方程和监督矩阵)1.5(4505614562463CCCCCCCCCCCCC2022-11-56n监督方程的一般定义监督方程的一般定义：n通过已知的信息元得到监督元规则的一组方程称为监督方程。由于所有码字都按同一规则确定，又称为一致监督方程。n由于监督方程是线性线性的，即监督元和信息元之间是线性运算关系，所以由线性监督方程所确定的分组码是线性线性分组码分组码。n参见以下(7,3)分组码的例子6.3.2 线性分组码的监督方程和监督矩阵2022-11-57(2)举例n若已知信息码组为(101)，即C6=1,C5=0,C4=1n代入 方程(5.1)得：C3=0,C2=0,C1=1,C0=1n由信息码组(101)编出的码字为 (1010011)。其它7个码字如表5.1。)1.5(4505614562463CCCCCCCCCCCCC00000000000000000000451562456346CCCCCCCCCCCCC6.3.2 线性分组码的监督方程和监督矩阵2022-11-58)3.5(1000110010001100101110001101H00000C)2.5(0000100011001000110010111000110101234560123456CCCCCCCCCCCCCC令(3)监督矩阵n为了运算方便，将式(5.1)监督方程写成矩阵形式，得n式(5.2)可写成 H CT=0T或 C HT=0 CT、HT、0T分别表示C、H、0的转置矩阵。6.3.2 线性分组码的监督方程和监督矩阵2022-11-59n系数矩阵 H 的后四列组成一个(44)阶单位子阵，用 I4 表示，H 的其余部分用 P 表示)5.5(IPH1000010000100001I110011111101P43437434),(所以6.3.2 线性分组码的监督方程和监督矩阵2022-11-510n推广到一般情况：对(n,k)线性分组码，每个码字中的 r(r=nk)个监督元与信息元之间的关系可由下面的线性方程组确定)6.5(000022110222212101212111ChChChChChChChChChrnnrnrnnnnnn6.3.2 线性分组码的监督方程和监督矩阵2022-11-511n令上式的系数矩阵为 H，码字矩阵（行阵列）为 C矩阵，简称监督矩阵。线性分组码的一致监督为称或可写成式),(H)8.5(0HC0CH)6.5(C)7.5(H11110211212222111211knCCChhhhhhhhhrTrnnTrTnnrnnnrnrrnnnr6.3.2 线性分组码的监督方程和监督矩阵2022-11-512(4)监督矩阵特性n对H 各行实行初等变换，将后面 r 列化为单位子阵，于是得到下面矩阵，行变换后所得方程组与原方程组同解。n监督矩阵监督矩阵H H 的标准形式的标准形式：后面 r 列是一单位子阵的监督矩阵H。nH 阵的每一行都代表一个监督方程，即 H 阵的 r 行代表了 r 个监督方程，也表示由由H H 所确定的码字有所确定的码字有 r 个监督元个监督元。)9.5(100010001H212222111211rnrrkknrppppppppp6.3.2 线性分组码的监督方程和监督矩阵2022-11-513nH 的标准形式还说明了相应的监督元是由哪些信息元决定的。例如(7,3)码的H 阵的第一行为(1011000)，说明此码的第一个监督元等于第一个和第三个信息元的模2和，依此类推。6.3.2 线性分组码的监督方程和监督矩阵2022-11-514(1)线性码的封闭性n线性码的封闭性线性码的封闭性：线性码任意两个码字之和仍是一个码字。n定理定理：设二元线性分组码 CI(CI表示码字集合)是由监督矩阵H所定义的，若 U 和 V 为其中的任意两个码字，则 U+V 也是 CI中的一个码字。n证明证明：由于 U 和 V 是码 CI 中的两个码字，故有HUT=0T，HVT=0T 那么 H(U+V)T=H(UT+VT)=HUT+HVT=0T 即 U+V 满足监督方程，所以 U+V 一定是码字集合CI中的一个码字。6.3.3 线性分组码的生成矩阵2022-11-515(2)线性分组码的生成矩阵的由来：在由(n,k)线性码构成的线性空间 Vn 的 k 维子空间中，一定存在 k 个线性独立的码字：g1,g2,gk,。码字集合CI 中，其它任何码字C都可以用这 k 个码字的某种线性组合来表示，即6.3.3 线性分组码的生成矩阵阶矩阵。是一个是待编码的信息组。写成矩阵形式得）（nkmmmmmmkimmmmkknkkkkknikkkGm)11.5(GmgggC1,1,0),2(GF10.5gggC0211210211022112022-11-516 G 中每一行 gi=(gi 1,gi 2,gi n )都是一个码字；n对每一个信息码元m来说，都可以通过矩阵G求得其对应的码字。n生成矩阵的定义生成矩阵的定义：由于矩阵 G 生成了(n,k)线性码中的任何一个码字，称矩阵 G 为(n,k)线性码的生成矩阵。n(n,k)线性码的每一个码字都是生成矩阵 G 的行的线性组合。)11.5(gggG21222211121121knkknnknkggggggggg6.3.3 线性分组码的生成矩阵2022-11-517n标准生成矩阵：通过行初等变换，将 G 化为前 k 行和k 列是单位子阵的标准形式标准形式6.3.3 线性分组码的生成矩阵11121()21222()12()100010GIQ(5.12)001n kn kk nkk rkkk n kqqqqqqqqq 2022-11-518n线性系统分组码线性系统分组码：用标准生成矩阵 Gkn 编成的码字，前面 k 位为信息数字，后面 r=nk 位为校验字，这种信息数字在前校验数字在后的线性分组码称为线性系统分组码。n当生成矩阵 G 确定之后，(n,k)线性码也就完全被确定了，只要找到码的生成矩阵，编码问题也同样被解决了。n 参见下面有关（7，4）线性码例子 6.3.3 线性分组码的生成矩阵2022-11-519(3)举例：已知一个(7,4)线性码的生成矩阵G如下图示，当输入信息码元为1010时，试求输出的码字。6.3.3 线性分组码的生成矩阵)1010011(11010000110100111001010100010101)1010(11010000110100111001010100017441714174GmCmG，则若n由矩阵乘法规则可知：C=m G 的结果，就是矩阵 G 中，与 m 中为“1”的元素相对应的行按位模 2 加的结果。2022-11-5206.3.3 线性分组码的生成矩阵练习：已知某线性分组码的生成矩阵为l试问：l（1）n=?k=?,该码组集合中的码字有多少？l（2）若信息码元 m 分别是 1100 和1111时,写出其对应的输出码字。10000110100101G001011000011112022-11-5216.3.3 线性分组码的生成矩阵1 41 71 44 7m(1100)10000110100101CmG1 100(1100110)00101100001111若，1 41 71 44 7m(1111)10000110100101CmG1 1 1 1(1111111)00101100001111若，l（1）n=7,k=4,共有16个码字。2022-11-522(4)生成矩阵与监督矩阵的关系n由于生成矩阵G的每一行都是一个码字，所以G 的每行都满足HCT=0T，则有HGT=0T 或 GHT=0n结论：结论：线性系统码的监督矩阵线性系统码的监督矩阵 H H 和生成矩阵和生成矩阵 G G 之间可以直接转换之间可以直接转换。6.3.3 线性分组码的生成矩阵)14.5(I)Q(HQIGP)Q()P(Q0Q)P(I)P(QIIPQIHGIPHQIGrTrkSrkkSkrTrkTkrrkrkrkTkrrTkrrkkTrkrrkkTSSrkrSrkkS或所以，2022-11-523n举例：1、已知线性系统码的监督矩阵，写出其生成矩阵。6.3.3 线性分组码的生成矩阵(7,4)(7,4)1110100H0111010110100110001010100111G00101100001011可 直 接 出：2022-11-5246.3.3 线性分组码的生成矩阵(7,4)(7,4)10001010011G001011000011111100H110101101001n举例：2、已知线性系统码的生成矩阵，写出其监督矩阵。2022-11-5256.3.3 线性分组码的生成矩阵线性分组码的生成矩阵 练习题：练习题：已知已知(7,3)线性分组码线性分组码,其码字表示为其码字表示为:C C=(C6,C5,C4,C3,C2,C1,C0)C6,C5,C4为三位信息元，为三位信息元，C3,C2,C1,C0为四位监督元，可为四位监督元，可由下列方法产生由下列方法产生:试求：试求：（1）生成矩阵）生成矩阵G和和监督监督矩阵矩阵H；（2）写出其全部的码字，码字间的最小距离）写出其全部的码字，码字间的最小距离 dmin是多少？是多少？3642654165054CCCCCCCCCCCCC2022-11-526 1000110010001100101110001101H H 101110011100100111001G G码字最小距离为码字最小距离为:4根据产生监督码的方法，写出监督方程为：根据产生监督码的方法，写出监督方程为：00000000000000000000451562456346CCCCCCCCCCCCC6.3.3 线性分组码的生成矩阵线性分组码的生成矩阵2022-11-5271：已知：已知(8,4)系统线性码的监督方程为系统线性码的监督方程为课堂作业课堂作业3467245714560567CCCCCCCCCCCCCCCC式中：式中：C7,C6,C5,C4为信息码元，为信息码元，C3,C2,C1,C0为监督码元，为监督码元，求该码的监督矩阵和生成矩阵。求该码的监督矩阵和生成矩阵。2022-11-528n2、某（、某（n,k）系统线性分组码的全部码字如下：）系统线性分组码的全部码字如下：n00000 01011 10110 11101n求求：n（1）n=?,k=?n（2）码的生成矩阵）码的生成矩阵G和监督矩阵和监督矩阵H。2022-11-529n2、解、解：n（1）已知已知 M=2K=4，故，故 k=2；n又知码长又知码长n=5，那么那么r=n-k=3 n该码是（该码是（5，2）线性码。）线性码。（2）1 0 1 1 00 1 0 1 1G101001101001001H2022-11-530n3、某（、某（5，2）线性分组码的）线性分组码的H矩阵为：矩阵为：n求求：n（1）该码的）该码的G矩阵；矩阵；n（2）写出该码的全部码字。）写出该码的全部码字。111001001011001H2022-11-531n(n,k)线性码的编码就是根据线性码的线性码的编码就是根据线性码的监督矩阵监督矩阵或或生成生成矩阵矩阵将长为将长为 k 的信息组变换成长为的信息组变换成长为 n(nk)的码字的码字。n举例：用举例：用监督矩阵监督矩阵构造构造(7,3)线性分组码的编码电路：线性分组码的编码电路：n设码字矢量为设码字矢量为C C=(C6 C5C4C3C2C1C0)n码的监督矩阵为码的监督矩阵为6.3.4 线性分组码的编码线性分组码的编码4505614562463)3,7(1000110010001100101110001101CCCCCCCCCCCCCTT得由0HCH2022-11-532n根据方程组可直接画出根据方程组可直接画出(7,3)码的并行编码电路和串行编码码的并行编码电路和串行编码电路，如图。电路，如图。6.3.4 线性分组码的编码m0m1m2C6C5C4C3C2C1C0mC(a)并行编码电路 （b）串行编码电路图6.2.2 (7,3)线性系统编码电路2022-11-533举例：一个举例：一个(6,3)线性分组码，其生成矩阵是线性分组码，其生成矩阵是求：求：（1）将生成矩阵）将生成矩阵G转化为标准生成矩阵转化为标准生成矩阵GS后，计算系统码码集，列后，计算系统码码集，列出映射关系。出映射关系。（2）写出监督矩阵）写出监督矩阵 HS，画出编码器原理图。，画出编码器原理图。6.3.4 线性分组码的编码线性分组码的编码101110100011010111G2022-11-534n解解：（1）根据矩阵的初等变换规则，对）根据矩阵的初等变换规则，对G作行运算：原第作行运算：原第1行行+第第3行作行作为第一行，原第为第一行，原第1行行+第第2行行+第第3行作为第二行，原第行作为第二行，原第1行行+第第2行作为第三行；得到系统化后的生成矩阵行作为第三行；得到系统化后的生成矩阵GS，于是系统码于是系统码C=m2100111+m1010110+m0001011,得得码集和映射关系如下表。码集和映射关系如下表。S100111G010110001011表 5.1 (7,3)分 组 码 编 码 表 信 息 组 系 统 码 字 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 1 1 0 1 1 0 0 1 0 0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0 1 1 0 0 0 1 1 1 1 1 1 1 0 1 0 2022-11-535（2）根据标准监督矩阵与生成矩阵之间的关系，可得：）根据标准监督矩阵与生成矩阵之间的关系，可得：根据监督矩阵可得到监督方程组：根据监督矩阵可得到监督方程组：S110100H1110101010012541543053CCCCCCCCCC2022-11-536一、接收码字的伴随式和错误检测的概念：一、接收码字的伴随式和错误检测的概念：用监督矩阵编码，也用监督矩阵编码，也用监督矩阵译码用监督矩阵译码：当接收到一个码字当接收到一个码字 R R 后，校后，校验验 HH R RT=0 0T 是否成立：是否成立：n若关系成立，则认为若关系成立，则认为 R R 是一个码字；是一个码字；n否则判为码字在传输中发生了错误；否则判为码字在传输中发生了错误；nHH R RT的值是否为的值是否为0 0是校验码字出错与否的依据。是校验码字出错与否的依据。伴随式伴随式/监督子监督子/校验子校验子：S S=R R HHT或或S ST=HH R RT。如何纠错？如何纠错？n设发送码矢设发送码矢 C C=(Cn1,Cn2,C0)n信道错误图样为信道错误图样为 E E=(En1,En2,E0)，n其中其中E i =0，表示第，表示第 i 位无错；位无错；nE i =1，表示第，表示第 i 位有错。位有错。i=n1,n2,0。6.6 线性分组码的译码线性分组码的译码2022-11-537 伴随式与错误图样之间的关系：伴随式与错误图样之间的关系：n伴随式仅与错误图样有关，而与发送的具体码字无关，即伴伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图样决定；随式仅由错误图样决定；n伴随式是错误的判别式：伴随式是错误的判别式：n若若S S=0 0，则判为没有出错，接收字是一个码字；，则判为没有出错，接收字是一个码字；n若若S S 0 0，则判为有错。，则判为有错。n不同的错误图样具有不同的伴随式，它们是一一对应的。不同的错误图样具有不同的伴随式，它们是一一对应的。n对二元码，伴随式是对二元码，伴随式是H H 阵中与错误码元对应列之和；阵中与错误码元对应列之和；n特别地，当只发生一个错误时，求出的伴随式一定对应于特别地，当只发生一个错误时，求出的伴随式一定对应于H H 阵中的某一列，那么，与接收码字对应的某一位就发生了错阵中的某一列，那么，与接收码字对应的某一位就发生了错误误。也就是说：也就是说：伴随式的二进制数值就是错误位置号。伴随式的二进制数值就是错误位置号。6.6 线性分组码的译码线性分组码的译码2022-11-538伴随式译码举例：伴随式译码举例：某某(7,3)线性系统码线性系统码n设发送码字设发送码字C C=1010011，接收码字，接收码字R R 1010011，R R与与C C相同。相同。6.6 线性分组码的译码无错。因此，译码器判接收字代入得和计算伴随式，把根据接收字道就是发送的码字，但接收端译码器并不知TTT0HRSRHRH10001100100011001011100011012022-11-539n若接收码字中有一位错误若接收码字中有一位错误6.6 线性分组码的译码线性分组码的译码正确。错能力相符，所以译码中错误码元数与码的纠由于接收字的第二位是错的。因此判定接收字的第二列，等于且码是纠单个错误的码，译码器判为有错。由于伴随式为接收码字发送码矢RRHS0SRHSRCTTTT)3,7(,111011001111000110010001100101110001101111001110100112022-11-540n当码元错误多于1个时6.6 线性分组码的译码位上，只是发现有错。无法判定错误出在哪些同，阵中的任何一列都不相但与，不等于是第一列和第四列之和由于伴随式为接收码字发送码矢H0SRHSRCTTT011011011001000110010001100101110001101001101110100112022-11-5410111000110010010100101110001G练习：练习：已知已知(7,4)线性分组码的生成矩阵如下。线性分组码的生成矩阵如下。求：求：(1)该码集的全部码字该码集的全部码字16个码字以及监督矩阵个码字以及监督矩阵 H。(2)若接收码字若接收码字 R分别为分别为1101101和和1001001时，根据伴随式来判断时，根据伴随式来判断收的码字有无错误。若有错，写出纠错后的码字。收的码字有无错误。若有错，写出纠错后的码字。6.6 线性分组码的译码线性分组码的译码2022-11-542当当 R=R=（11011011101101）时，）时，111 10110000SH R1 011010011 1100011101TT 说明：说明：第第7 7位发生错误位发生错误。E E=0000001=0000001纠正：纠正：C C=R+E=R+E=1101101+0000001=11011001101101+0000001=110110010110110000SHR10110100111100010001TT S=0，接收码字接收码字正确。正确。2022-11-543 伴随式计算电路：伴随式计算电路：n伴随式的计算可用电路来实现。伴随式的计算可用电路来实现。n以以(7,3)码为例：设接收字为码为例：设接收字为R R=(R6R5R4R3R2R1R0)，伴随，伴随式为式为0123045156345634601234561000110010001100101110001101SSSSRRRRRRRRRRRRRRRRRRRRTTRHS6.6 线性分组码的译码线性分组码的译码2022-11-544n根据上式可画出伴随式计算电路，如图所示。6.6 线性分组码的译码2022-11-545二、结论：二、结论：n由于码的可纠错误图样和伴随式是一一对应的，利用此对应关系由于码的可纠错误图样和伴随式是一一对应的，利用此对应关系可以得到可以得到(n,k)线性码的一般译码步骤。线性码的一般译码步骤。n(n,k)线性码的一般译码步骤如下：线性码的一般译码步骤如下：n计算接收码字计算接收码字 R R 的伴随式的伴随式 S ST=HRHRT；n根据伴随式和错误图样一一对应的关系，由伴随式计算出根据伴随式和错误图样一一对应的关系，由伴随式计算出 R R 的错误图样的错误图样 E E；n将接收码字加上错误图样，得到发送码字的估值将接收码字加上错误图样，得到发送码字的估值 C C=R+ER+E。n 上述译码法称为伴随式译码法。这种译码法具有最小的译码上述译码法称为伴随式译码法。这种译码法具有最小的译码错误概率，原则上可用于任何错误概率，原则上可用于任何(n,k)线性码。（见下页一般线性码。（见下页一般线性分组码译码器原理图）线性分组码译码器原理图）6.6 线性分组码的译码线性分组码的译码2022-11-5466.6 线性分组码的译码2022-11-547n汉明码是汉明于汉明码是汉明于1950年提出的纠一个错误的线性码，也是第一个纠错年提出的纠一个错误的线性码，也是第一个纠错码。由于它编码简单，因而是在通信系统和数据存储系统中得到广泛应码。由于它编码简单，因而是在通信系统和数据存储系统中得到广泛应用的一类线性码。用的一类线性码。n汉明码的结构特点：汉明码的结构特点：n纠一个错误的线性码，其最小距离纠一个错误的线性码，其最小距离 dmin=3；n监督矩阵任意两列线性无关监督矩阵任意两列线性无关/即即H H 中任两列互不相同中任两列互不相同；n没有全没有全0 0的列，监督元个数的列，监督元个数 nk=r，即即H H 阵中每列有阵中每列有 r 个元素，个元素，至多可构成至多可构成 2r1种互不相同的非种互不相同的非0 0列。列。n汉明码的结构参数汉明码的结构参数：（对于任意正整数（对于任意正整数 m3）n监督位数：监督位数：nk=mn码长：码长：n=2m1n信息位数：信息位数：k=2mm1n码的最小距离：码的最小距离：dmin=3 (t=1)6.7 汉明码汉明码2022-11-548n汉明码的种类：汉明码的种类：n当当 m=3,4,5,6,7,8,m=3,4,5,6,7,8,时时,有有(7,4),(15,11),(31,26),(63,57),(127,120),(155,247),(7,4),(15,11),(31,26),(63,57),(127,120),(155,247),汉明汉明码码