线性分组码ppt课件.ppt

《线性分组码ppt课件.ppt》由会员分享，可在线阅读，更多相关《线性分组码ppt课件.ppt（48页珍藏版）》请在三一办公上搜索。

1、2022/11/13,1,6.3.1 一般概念6.3.2 线性分组码的监督方程和监督矩阵6.3.3 线性分组码的生成矩阵6.3.4 线性分组码的编码6.3.5 线性分组码的译码6.3.6 汉明码,6. 3 线性分组码,2022/11/13,2,一、名词解释线性分组码：通过预定的线性运算将长为 k 位的信息码组变换成 n 长的码字 ( nk )。由 2k 个信息码组所编成的 2k个码字集合，称为线性分组码。码矢：一个 n 长的码字可以用矢量来表示C = (Cn1,Cn2,C1,C0 ) 所以码字又称为码矢。( n, k ) 线性码：信息位长为 k，码长为 n 的线性码。编码效率/编码速率/码率：

2、R=k /n。它说明了信道的利用效率，R是衡量码性能的一个重要参数。,6.3.1 一般概念,2022/11/13,3,线性分组码的编码：线性分组码的编码过程分为两步：把信息序列按一定长度分成若干信息码组，每组由 k 位组成；编码器按照预定的线性规则(可由线性方程组规定)，把信息码组变换成 n 长 (nk) 码字，其中 (nk) 个附加码元是由信息码元的线性运算产生的。信息码组长为 k 位，若有 2k 个不同的信息码组，则有 2k 个码字与它们一一对应。,2022/11/13,4,线性分组码是前向纠错码，它可以在无需重发的情况下检测出有限个错码，并加以纠正。当其他改善手段（如增加发射功率或使用复

3、杂的解调器）不切实际时，分组码可以用来改善通信系统的性能。 在分组编码器中，k个信息位被编成n位，从而对k个信息位增加了n-k个冗余位，而冗余位的作用是检测和纠正错码。,2022/11/13,5,(1) 监督方程编码就是给已知信息码组按预定规则添加监督码元，以构成码字。在 k 个信息码元之后附加 r(r=nk) 个监督码元，使每个监督元是其中某些信息元的模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 线性分组码

4、的监督方程和监督矩阵,2022/11/13,6,监督方程的一般定义：通过已知的信息元得到监督元规则的一组方程称为监督方程。由于所有码字都按同一规则确定，又称为一致监督方程。由于监督方程是线性的，即监督元和信息元之间是线性运算关系，所以由线性监督方程所确定的分组码是线性分组码。参见以下( 7,3 )分组码的例子,6.3.2 线性分组码的监督方程和监督矩阵,2022/11/13,7,(2) 举例若已知信息码组为 (101)，即C6=1, C5=0, C4=1代入 方程(5.1) 得： C3=0, C2=0, C1=1, C0=1由信息码组 (101) 编出的码字为 (1010011)。其它7个码字

5、如表5.1。,6.3.2 线性分组码的监督方程和监督矩阵,2022/11/13,8,(3) 监督矩阵为了运算方便，将式(5.1)监督方程写成矩阵形式，得式(5.2)可写成 H CT=0T或 C HT=0 CT、HT、0T分别表示C、H、0的转置矩阵。,6.3.2 线性分组码的监督方程和监督矩阵,2022/11/13,9,系数矩阵 H 的后四列组成一个 (44) 阶单位子阵，用 I4 表示，H 的其余部分用 P 表示,6.3.2 线性分组码的监督方程和监督矩阵,2022/11/13,10,推广到一般情况：对 (n,k) 线性分组码，每个码字中的 r(r=nk) 个监督元与信息元之间的关系可由下面

6、的线性方程组确定,6.3.2 线性分组码的监督方程和监督矩阵,2022/11/13,11,令上式的系数矩阵为 H，码字矩阵（行阵列）为 C,6.3.2 线性分组码的监督方程和监督矩阵,2022/11/13,12,(4) 监督矩阵特性对H 各行实行初等变换，将后面 r 列化为单位子阵，于是得到下面矩阵，行变换后所得方程组与原方程组同解。监督矩阵H 的标准形式：后面 r 列是一单位子阵的监督矩阵H。H 阵的每一行都代表一个监督方程，即 H 阵的 r 行代表了 r 个监督方程，也表示由H 所确定的码字有 r 个监督元。,6.3.2 线性分组码的监督方程和监督矩阵,2022/11/13,13,H 的标

7、准形式还说明了相应的监督元是由哪些信息元决定的。 例如 (7,3) 码的H 阵的第一行为 (1011000)，说明此码的第一个监督元等于第一个和第三个信息元的模2和，依此类推。,6.3.2 线性分组码的监督方程和监督矩阵,2022/11/13,14,(1) 线性码的封闭性线性码的封闭性：线性码任意两个码字之和仍是一个码字。定理：设二元线性分组码 CI (CI表示码字集合) 是由监督矩阵H所定义的，若 U 和 V 为其中的任意两个码字，则 U+V 也是 CI中的一个码字。证明：由于 U 和 V 是码 CI 中的两个码字，故有HUT=0T，HVT=0T 那么 H(U+V)T=H(UT+VT)=HU

8、T+HVT=0T 即 U+V 满足监督方程，所以 U+V 一定是码字集合CI中的一个码字。,6.3.3 线性分组码的生成矩阵,2022/11/13,15,(2) 线性分组码的生成矩阵的由来： 在由 (n,k) 线性码构成的线性空间 Vn 的 k 维子空间中，一定存在 k 个线性独立的码字：g1,g2, gk,。 码字集合CI 中，其它任何码字C都可以用这 k 个码字的某种线性组合来表示，即,6.3.3 线性分组码的生成矩阵,2022/11/13,16,G 中每一行 gi = ( gi 1, gi 2, , gi n ) 都是一个码字；对每一个信息码元m来说，都可以通过矩阵G求得其对应的码字。生

9、成矩阵的定义：由于矩阵 G 生成了 (n,k) 线性码中的任何一个码字，称矩阵 G 为 (n,k) 线性码的生成矩阵。(n,k) 线性码的每一个码字都是生成矩阵 G 的行的线性组合。,6.3.3 线性分组码的生成矩阵,2022/11/13,17,标准生成矩阵： 通过行初等变换，将 G 化为前 k 行和k 列是单位子阵的标准形式,6.3.3 线性分组码的生成矩阵,2022/11/13,18,线性系统分组码：用标准生成矩阵 Gkn 编成的码字，前面 k 位为信息数字，后面 r=nk 位为校验字，这种信息数字在前校验数字在后的线性分组码称为线性系统分组码。当生成矩阵 G 确定之后，(n,k) 线性码

10、也就完全被确定了，只要找到码的生成矩阵，编码问题也同样被解决了。 参见下面有关（7，4）线性码例子 ,6.3.3 线性分组码的生成矩阵,2022/11/13,19,(3) 举例： 已知一个 (7,4) 线性码的生成矩阵G如下图示，当输入信息码元为1010时，试求输出的码字。,6.3.3 线性分组码的生成矩阵,由矩阵乘法规则可知： C = m G 的结果，就是矩阵 G 中，与 m 中为“1”的元素相对应的行按位模 2 加的结果。,2022/11/13,20,6.3.3 线性分组码的生成矩阵,练习： 已知某线性分组码的生成矩阵为,试问：（1）n = ? k = ? , 该码组集合中的码字有多少？（

11、2）若信息码元 m 分别是 1100 和1111时 , 写出其对应的输出码字。,2022/11/13,21,6.3.3 线性分组码的生成矩阵,（1）n = 7 , k = 4 , 共有16个码字。,2022/11/13,22,(4) 生成矩阵与监督矩阵的关系由于生成矩阵G的每一行都是一个码字，所以G 的每行都满足HCT=0T，则有HGT=0T 或 GHT=0结论：线性系统码的监督矩阵 H 和生成矩阵 G 之间可以直接转换。,6.3.3 线性分组码的生成矩阵,2022/11/13,23,举例： 1、已知线性系统码的监督矩阵，写出其生成矩阵。,6.3.3 线性分组码的生成矩阵,2022/11/13

12、,24,6.3.3 线性分组码的生成矩阵,举例： 2、已知线性系统码的生成矩阵，写出其监督矩阵。,2022/11/13,25,6.3.3 线性分组码的生成矩阵,练习题： 已知 ( 7,3 ) 线性分组码,其码字表示为: C = (C6,C5,C4,C3,C2,C1,C0) C6,C5,C4为三位信息元，C3,C2,C1,C0为四位监督元，可由下列方法产生:,试求：（1）生成矩阵G和监督矩阵H；（2）写出其全部的码字，码字间的最小距离 dmin是多少？,2022/11/13,26,码字最小距离为: 4,根据产生监督码的方法，写出监督方程为：,6.3.3 线性分组码的生成矩阵,2022/11/13

13、,27,1：已知 (8,4) 系统线性码的监督方程为,课堂作业,式中：C7, C6, C5, C4为信息码元， C3, C2, C1, C0为监督码元， 求该码的监督矩阵和生成矩阵。,2022/11/13,28,2、某（n,k）系统线性分组码的全部码字如下：00000 01011 10110 11101求：（1）n = ? , k = ?（2）码的生成矩阵G和监督矩阵H。,2022/11/13,29,2、解：（1）已知 M = 2K = 4 ，故 k = 2 ；又知码长n = 5 ，那么r = n - k = 3 该码是（5，2）线性码。 （2）,2022/11/13,30,3、某（5，2）线

14、性分组码的H矩阵为：求：（1）该码的G矩阵；（2）写出该码的全部码字。,2022/11/13,31,(n,k) 线性码的编码就是根据线性码的监督矩阵或生成矩阵将长为 k 的信息组变换成长为 n(nk) 的码字。举例：用监督矩阵构造 (7,3) 线性分组码的编码电路：设码字矢量为C = (C6 C5C4C3C2C1C0)码的监督矩阵为,6.3.4 线性分组码的编码,2022/11/13,32,根据方程组可直接画出 (7,3) 码的并行编码电路和串行编码电路，如图。,6.3.4 线性分组码的编码,2022/11/13,33,举例：一个( 6 , 3 )线性分组码，其生成矩阵是 求：（1）将生成矩阵

15、G转化为标准生成矩阵GS后，计算系统码码集，列出映射关系。（2）写出监督矩阵 HS，画出编码器原理图。,6.3.4 线性分组码的编码,2022/11/13,34,解：（1）根据矩阵的初等变换规则，对G作行运算：原第1行+第3行作为第一行，原第1行+第2行+第3行作为第二行，原第1行+第2行作为第三行；得到系统化后的生成矩阵GS ，于是系统码C = m2100111 + m1010110 + m0001011 ,得码集和映射关系如下表。,2022/11/13,35,（2）根据标准监督矩阵与生成矩阵之间的关系，可得：根据监督矩阵可得到监督方程组：,2022/11/13,36,一、接收码字的伴随式和

16、错误检测的概念： 用监督矩阵编码，也用监督矩阵译码：当接收到一个码字 R 后，校验 HRT=0T 是否成立：若关系成立，则认为 R 是一个码字；否则判为码字在传输中发生了错误；HRT的值是否为0是校验码字出错与否的依据。 伴随式/监督子/校验子：S=RHT或ST=HRT。 如何纠错？设发送码矢 C=(Cn1,Cn2,C0)信道错误图样为 E=(En1,En2,E0) ，其中E i = 0，表示第 i 位无错；E i = 1，表示第 i 位有错。i =n1,n2,0。,6.6 线性分组码的译码,2022/11/13,37, 伴随式与错误图样之间的关系：伴随式仅与错误图样有关，而与发送的具体码字无

17、关，即伴随式仅由错误图样决定；伴随式是错误的判别式：若S = 0，则判为没有出错，接收字是一个码字；若S 0，则判为有错。不同的错误图样具有不同的伴随式，它们是一一对应的。对二元码，伴随式是H 阵中与错误码元对应列之和；特别地，当只发生一个错误时，求出的伴随式一定对应于H 阵中的某一列，那么，与接收码字对应的某一位就发生了错误。 也就是说：伴随式的二进制数值就是错误位置号。,6.6 线性分组码的译码,2022/11/13,38,伴随式译码举例： 某(7,3) 线性系统码设发送码字C = 1010011，接收码字R 1010011，R与C相同。,6.6 线性分组码的译码,2022/11/13,3

18、9,若接收码字中有一位错误,6.6 线性分组码的译码,2022/11/13,40,当码元错误多于1个时,6.6 线性分组码的译码,2022/11/13,41,练习：已知(7,4)线性分组码的生成矩阵如下。求：(1) 该码集的全部码字16个码字以及监督矩阵 H 。 (2) 若接收码字 R分别为1101101和1001001时，根据伴随式来判断收的码字有无错误。若有错，写出纠错后的码字。,6.6 线性分组码的译码,2022/11/13,42,当 R =（1101101）时，,说明：第7位发生错误。E = 0000001纠正： C=R+E= 1101101 + 0000001 = 1101100,S

19、=0，接收码字正确。,2022/11/13,43, 伴随式计算电路：伴随式的计算可用电路来实现。以(7,3)码为例：设接收字为R=(R6R5R4R3R2R1R0)，伴随式为,6.6 线性分组码的译码,2022/11/13,44,根据上式可画出伴随式计算电路，如图所示。,6.6 线性分组码的译码,2022/11/13,45,二、结论：由于码的可纠错误图样和伴随式是一一对应的，利用此对应关系可以得到 (n,k) 线性码的一般译码步骤。(n,k) 线性码的一般译码步骤如下：计算接收码字 R 的伴随式 ST=HRT ；根据伴随式和错误图样一一对应的关系，由伴随式计算出 R 的错误图样 E；将接收码字加

20、上错误图样，得到发送码字的估值 C=R+E 。 上述译码法称为伴随式译码法。这种译码法具有最小的译码错误概率，原则上可用于任何 (n,k) 线性码。（见下页一般线性分组码译码器原理图）,6.6 线性分组码的译码,2022/11/13,46,6.6 线性分组码的译码,2022/11/13,47,汉明码是汉明于1950年提出的纠一个错误的线性码，也是第一个纠错码。由于它编码简单，因而是在通信系统和数据存储系统中得到广泛应用的一类线性码。汉明码的结构特点：纠一个错误的线性码，其最小距离 dmin=3 ；监督矩阵任意两列线性无关/ 即H 中任两列互不相同；没有全0的列，监督元个数 nk=r ，即H 阵中每列有 r 个元素，至多可构成 2r1种互不相同的非0列。汉明码的结构参数： （对于任意正整数 m3）监督位数： nk=m码长： n=2m1信息位数： k=2mm1码的最小距离：dmin= 3 ( t =1 ),6.7 汉明码,2022/11/13,48,汉明码的种类：当 m = 3, 4 ,5 ,6,7, 8, 时,有(7,4),(15,11),(31,26),(63,57),(127,120),(155,247),汉明码,