线性分组码课件

6.3.1一般概念6.3.2线性分组码的监督方程和监督矩阵6.3.3线性分组码的生成矩阵6.3.4线性分组码的编码6.3.5线性分组码的译码6.3.6汉明码6.3线性分组码8/14/202316.3.1一般概念6.3线性分组码8/1/一、名词解释线性分组码：通过预定的线性运算将长为k位的信息码组变换成n长的码字(n>k)。由2k个信息码组所编成的2k个码字集合，称为线性分组码。码矢：一个n长的码字可以用矢量来表示C=(Cn－1,Cn－2,…,C1,C0)所以码字又称为码矢。(n,k)线性码：信息位长为k，码长为n的线性码。编码效率/编码速率/码率：R=k/n。它说明了信道的利用效率，R是衡量码性能的一个重要参数。6.3.1一般概念8/14/20232一、名词解释6.3.1一般概念8/1/20232线性分组码的编码：线性分组码的编码过程分为两步：把信息序列按一定长度分成若干信息码组，每组由k位组成；编码器按照预定的线性规则(可由线性方程组规定)，把信息码组变换成n长(n>k)码字，其中(n－k)个附加码元是由信息码元的线性运算产生的。信息码组长为k位，若有2k个不同的信息码组，则有2k个码字与它们一一对应。8/14/20233线性分组码的编码：线性分组码的编码过程分为两步：8/1/20线性分组码是前向纠错码，它可以在无需重发的情况下检测出有限个错码，并加以纠正。当其他改善手段（如增加发射功率或使用复杂的解调器）不切实际时，分组码可以用来改善通信系统的性能。在分组编码器中，k个信息位被编成n位，从而对k个信息位增加了n-k个冗余位，而冗余位的作用是检测和纠正错码。8/14/20234线性分组码是前向纠错码，它可以在无需重发(1)监督方程编码就是给已知信息码组按预定规则添加监督码元，以构成码字。在k个信息码元之后附加r(r=n－k)个监督码元，使每个监督元是其中某些信息元的模2和。举例：k=3,r=4，构成(7,3)线性分组码。设码字为(C6,C5,C4,C3,C2,C1,C0)C6,C5,C4为信息元，C3,C2,C1,C0为监督元，每个码元取“0”或“1”监督元可按下面方程组计算6.3.2线性分组码的监督方程和监督矩阵8/14/20235(1)监督方程6.3.2线性分组码的监督方程和监督矩监督方程的一般定义：通过已知的信息元得到监督元规则的一组方程称为监督方程。由于所有码字都按同一规则确定，又称为一致监督方程。由于监督方程是线性的，即监督元和信息元之间是线性运算关系，所以由线性监督方程所确定的分组码是线性分组码。[参见以下(7,3)分组码的例子]6.3.2线性分组码的监督方程和监督矩阵8/14/20236监督方程的一般定义：6.3.2线性分组码的监督方程和监(2)举例若已知信息码组为(101)，即C6=1,C5=0,C4=1代入方程(5.1)得：C3=0,C2=0,C1=1,C0=1由信息码组(101)编出的码字为(1010011)。其它7个码字如表5.1。6.3.2线性分组码的监督方程和监督矩阵8/14/20237(2)举例6.3.2线性分组码的监督方程和监督矩阵8(3)监督矩阵为了运算方便，将式(5.1)监督方程写成矩阵形式，得式(5.2)可写成H

CT=0T或

C

HT=0CT、HT、0T分别表示C、H、0的转置矩阵。6.3.2线性分组码的监督方程和监督矩阵8/14/20238(3)监督矩阵6.3.2线性分组码的监督方程和监督矩系数矩阵H的后四列组成一个(4×4)阶单位子阵，用I4表示，H的其余部分用P表示6.3.2线性分组码的监督方程和监督矩阵8/14/20239系数矩阵H的后四列组成一个(4×4)阶单位子阵，用推广到一般情况：对(n,k)线性分组码，每个码字中的r(r=n－k)个监督元与信息元之间的关系可由下面的线性方程组确定6.3.2线性分组码的监督方程和监督矩阵8/14/202310推广到一般情况：对(n,k)线性分组码，每个码字中的r令上式的系数矩阵为H，码字矩阵（行阵列）为C6.3.2线性分组码的监督方程和监督矩阵8/14/202311令上式的系数矩阵为H，码字矩阵（行阵列）为C6.3.2(4)监督矩阵特性对H各行实行初等变换，将后面r列化为单位子阵，于是得到下面矩阵，行变换后所得方程组与原方程组同解。监督矩阵H的标准形式：后面r列是一单位子阵的监督矩阵H。H阵的每一行都代表一个监督方程，即H阵的r行代表了r个监督方程，也表示由H所确定的码字有r个监督元。6.3.2线性分组码的监督方程和监督矩阵8/14/202312(4)监督矩阵特性6.3.2线性分组码的监督方程和监H的标准形式还说明了相应的监督元是由哪些信息元决定的。例如(7,3)码的H阵的第一行为(1011000)，说明此码的第一个监督元等于第一个和第三个信息元的模2和，依此类推。

6.3.2线性分组码的监督方程和监督矩阵8/14/202313H的标准形式还说明了相应的监督元是由哪些信息元决定的。6.(1)线性码的封闭性线性码的封闭性：线性码任意两个码字之和仍是一个码字。定理：设二元线性分组码CI(CI表示码字集合)是由监督矩阵H所定义的，若U和V为其中的任意两个码字，则U+V也是CI中的一个码字。[证明]：由于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线性分组码的生成矩阵8/14/202314(1)线性码的封闭性6.3.3线性分组码的生成矩阵8/1(2)线性分组码的生成矩阵的由来：在由(n,k)线性码构成的线性空间Vn的k维子空间中，一定存在k个线性独立的码字：g1,g2,…,gk,。码字集合CI中，其它任何码字C都可以用这k个码字的某种线性组合来表示，即6.3.3线性分组码的生成矩阵8/14/202315(2)线性分组码的生成矩阵的由来：6.3.3线性分组码G中每一行gi=(gi1,gi2,…,gin)都是一个码字；对每一个信息码元m来说，都可以通过矩阵G求得其对应的码字。生成矩阵的定义：由于矩阵G

生成了(n,k)线性码中的任何一个码字，称矩阵G为(n,k)线性码的生成矩阵。(n,k)线性码的每一个码字都是生成矩阵G的行的线性组合。6.3.3线性分组码的生成矩阵8/14/202316G中每一行gi=(gi1,gi2,…标准生成矩阵：通过行初等变换，将G化为前k行和k列是单位子阵的标准形式6.3.3线性分组码的生成矩阵8/14/202317标准生成矩阵：6.3.3线性分组码的生成矩阵8/1/202线性系统分组码：用标准生成矩阵Gk×n

编成的码字，前面k位为信息数字，后面r=n－k位为校验字，这种信息数字在前校验数字在后的线性分组码称为线性系统分组码。当生成矩阵G确定之后，(n,k)线性码也就完全被确定了，只要找到码的生成矩阵，编码问题也同样被解决了。[参见下面有关（7，4）线性码例子]6.3.3线性分组码的生成矩阵8/14/202318线性系统分组码：用标准生成矩阵Gk×n编成的码字，前面(3)举例：

已知一个(7,4)线性码的生成矩阵G如下图示，当输入信息码元为1010时，试求输出的码字。6.3.3线性分组码的生成矩阵由矩阵乘法规则可知：

C

=

m

G的结果，就是矩阵G中，与m中为“1”的元素相对应的行按位模2加的结果。8/14/202319(3)举例：6.3.3线性分组码的生成矩阵由矩阵乘法规则6.3.3线性分组码的生成矩阵练习：已知某线性分组码的生成矩阵为试问：（1）n=?k=?,该码组集合中的码字有多少？（2）若信息码元m分别是1100和1111时,写出其对应的输出码字。8/14/2023206.3.3线性分组码的生成矩阵练习：试问：8/1/20236.3.3线性分组码的生成矩阵（1）n=7,k=4,共有16个码字。8/14/2023216.3.3线性分组码的生成矩阵（1）n=7,k(4)生成矩阵与监督矩阵的关系由于生成矩阵G的每一行都是一个码字，所以G的每行都满足HCT=0T，则有HGT=0T

或GHT=0结论：线性系统码的监督矩阵H和生成矩阵G之间可以直接转换。6.3.3线性分组码的生成矩阵8/14/202322(4)生成矩阵与监督矩阵的关系6.3.3线性分组码的生举例：1、已知线性系统码的监督矩阵，写出其生成矩阵。6.3.3线性分组码的生成矩阵8/14/202323举例：6.3.3线性分组码的生成矩阵8/1/2023236.3.3线性分组码的生成矩阵举例：2、已知线性系统码的生成矩阵，写出其监督矩阵。8/14/2023246.3.3线性分组码的生成矩阵举例：8/1/2023246.3.3线性分组码的生成矩阵练习题：

已知(7,3)线性分组码,其码字表示为:

C

=

(C6,C5,C4,C3,C2,C1,C0)C6,C5,C4为三位信息元，C3,C2,C1,C0为四位监督元，可由下列方法产生:试求：（1）生成矩阵G和监督矩阵H；（2）写出其全部的码字，码字间的最小距离dmin是多少？8/14/2023256.3.3线性分组码的生成矩阵练习题：试求：8/1码字最小距离为:4根据产生监督码的方法，写出监督方程为：6.3.3线性分组码的生成矩阵8/14/202326码字最小距离为:4根据产生监督码的方法，写出监督方程为：1：已知(8,4)系统线性码的监督方程为课堂作业式中：C7,C6,C5,C4为信息码元，

C3,C2,C1,C0为监督码元，求该码的监督矩阵和生成矩阵。8/14/2023271：已知(8,4)系统线性码的监督方程为课堂作业式中：2、某（n,k）系统线性分组码的全部码字如下：00000010111011011101求：（1）n=?,k=?（2）码的生成矩阵G和监督矩阵H。8/14/2023282、某（n,k）系统线性分组码的全部码字如下：8/1/2022、解：（1）已知M=2K

=4，故k=2；又知码长n=5，那么r=n-k=3该码是（5，2）线性码。

（2）8/14/2023292、解：8/1/2023293、某（5，2）线性分组码的H矩阵为：求：（1）该码的G矩阵；（2）写出该码的全部码字。8/14/2023303、某（5，2）线性分组码的H矩阵为：8/1/202330(n,k)线性码的编码就是根据线性码的监督矩阵或生成矩阵将长为k的信息组变换成长为n(n>k)的码字。举例：用监督矩阵构造(7,3)线性分组码的编码电路：设码字矢量为C=(C6C5C4C3C2C1C0)码的监督矩阵为6.3.4线性分组码的编码8/14/202331(n,k)线性码的编码就是根据线性码的监督矩阵或生成矩阵将根据方程组可直接画出(7,3)码的并行编码电路和串行编码电路，如图。6.3.4线性分组码的编码8/14/202332根据方程组可直接画出(7,3)码的并行编码电路和串行编码举例：一个(6,3)线性分组码，其生成矩阵是

求：（1）将生成矩阵G转化为标准生成矩阵GS后，计算系统码码集，列出映射关系。（2）写出监督矩阵HS，画出编码器原理图。6.3.4线性分组码的编码8/14/202333举例：一个(6,3)线性分组码，其生成矩阵是6.3解：（1）根据矩阵的初等变换规则，对G作行运算：原第1行+第3行作为第一行，原第1行+第2行+第3行作为第二行，原第1行+第2行作为第三行；得到系统化后的生成矩阵GS，于是系统码C=m2[100111]+m1[010110]+m0[001011],得码集和映射关系如下表。8/14/202334解：8/1/202334（2）根据标准监督矩阵与生成矩阵之间的关系，可得：根据监督矩阵可得到监督方程组：8/14/202335（2）根据标准监督矩阵与生成矩阵之间的关系，可得：8/1/2一、接收码字的伴随式和错误检测的概念：①用监督矩阵编码，也用监督矩阵译码：当接收到一个码字R后，校验H

RT=0T是否成立：若关系成立，则认为R是一个码字；否则判为码字在传输中发生了错误；H

RT的值是否为0是校验码字出错与否的依据。②伴随式/监督子/校验子：S=R

HT或ST=H

RT。③如何纠错？设发送码矢C=(Cn－1,Cn－2,…,C0)信道错误图样为E=(En－1,En－2,…,E0)，其中Ei=0，表示第i位无错；Ei=1，表示第i位有错。i=n－1,n－2,…,0。6.6线性分组码的译码8/14/202336一、接收码字的伴随式和错误检测的概念：6.6线性分组码的译④伴随式与错误图样之间的关系：伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图样决定；伴随式是错误的判别式：若S=0，则判为没有出错，接收字是一个码字；若S≠0，则判为有错。不同的错误图样具有不同的伴随式，它们是一一对应的。对二元码，伴随式是H阵中与错误码元对应列之和；特别地，当只发生一个错误时，求出的伴随式一定对应于H阵中的某一列，那么，与接收码字对应的某一位就发生了错误。也就是说：伴随式的二进制数值就是错误位置号。6.6线性分组码的译码8/14/202337④伴随式与错误图样之间的关系：6.6线性分组码的译码8/⑤伴随式译码举例：某(7,3)线性系统码设发送码字C=1010011，接收码字R＝1010011，R与C相同。6.6线性分组码的译码8/14/202338⑤伴随式译码举例：6.6线性分组码的译码8/1/20233若接收码字中有一位错误6.6线性分组码的译码8/14/202339若接收码字中有一位错误6.6线性分组码的译码8/1/202当码元错误多于1个时6.6线性分组码的译码8/14/202340当码元错误多于1个时6.6线性分组码的译码8/1/2023练习：已知(7,4)线性分组码的生成矩阵如下。求：(1)该码集的全部码字16个码字以及监督矩阵H。(2)若接收码字R分别为1101101和1001001时，根据伴随式来判断收的码字有无错误。若有错，写出纠错后的码字。6.6线性分组码的译码8/14/202341练习：6.6线性分组码的译码8/1/202341当R=（1101101）时，说明：第7位发生错误。E

=0000001纠正：C’=R+E=1101101+0000001=1101100S=0，接收码字正确。8/14/202342当R=（1101101）时，说明：第7位发生错误。E=⑥伴随式计算电路：伴随式的计算可用电路来实现。以(7,3)码为例：设接收字为R=(R6R5R4R3R2R1R0)，伴随式为6.6线性分组码的译码8/14/202343⑥伴随式计算电路：6.6线性分组码的译码8/1/2023根据上式可画出伴随式计算电路，如图所示。6.6线性分组码的译码8/14/202344根据上式可画出伴随式计算电路，如图所示。6.6线性分组码的二、结论：由于码的可