差错控制编码第二次课课件.ppt
11.5 线性分组码,1 基本概念 分组码 将信息码分组，每组由信码附加若干监督码组成。分组码一般用符号（n,k）表示，k为每组信码位数；n为每组编码总位数，又称为码长；r= n-k为每组中监督码元数。 代数码 建立在代数学基础上的编码称为代数码。 线性码 码组的信息码和监督码间约束关系按一组线性代数方程组构成。线性码是一种代数码。 由此可见，将分组码和线性码的概念结合一起，即为线性分组码。,回顾奇偶监督码,在接收端解码时，实际上就是在计算,若S0，认为无错,若S1，认为有错,S只有两种取值，只能代表有、无错两种信息，不能指出错码位置。,监督关系式,校正子,在（n,k）码中，为能纠正一位错误要求,在（n,k）码中，k=4。为能纠正一位错码，则r至少应为多少？,举例说明如何构造监督关系式：上例中，若取r=3，则n=k+r=7。(7,4)线性分组码（a6 a5 a4 a3 a2 a1 a0)校正子与错码位置的对应关系如表规定(也可以另外规定) 。,由表可见，当一错码位置在a2,a4，a5或a6时校正子S1为1；否则S1为0即构成如下关系,由此解出,给定信息位后，可直接按上式算出监督位,监督方程,2、 监督矩阵H和生成矩阵G,改写为,(模2),简记为 或,称为监督矩阵,H矩阵的各个行是线性无关的行数=监督位数，列数=码字长度,典型阵,r 行n列,转置得,K行r列,Q = PT，在Q矩阵的左边在加上一个kk的单位矩阵，就形成了一个新矩阵G：,典型形式生成矩阵,K行n列,称为生成矩阵,生成矩阵G的每一行都是一个码组,G为典型生成矩阵，则得到的码为系统码否则得到的码为非系统码,例【1】 已知线性（6，3）码的生成矩阵为,求（1）信息码组为101对应的编码码组 （2）所有许用码组、各码组的码重、最小码距和该码的差错控制能力。,例2已知（7，4）码的生成矩阵为：,列出所有许用码组并求监督矩阵,例3课后习题9-61、写出监督方程2、由监督方程求出所有许用码组3、求生成矩阵4、最小码距？只用于检错，能检出几位错码？只用于纠错？同时用于检错和纠错？,若发送码组为,表示该位接收码元无错；表示该位接收码元有错。,3、译码,接收码组为,二者之差为,E称为错误图样,接收端译码时计算,错误图样与校正子之间有确定的关系,无错时，S等于零有错，S不等于零。,校正子(伴随式),纠错-只纠一位错误时,例4 设,验证3个接收码组是否发生差错？若在某码组中有错码，错码的校正子是什么？然后再指出发生错码的码字中，哪位有错？,且有3个接收码组,解：1）若无错，则错误图样为0，S为0,B1无错,B2错,B3错,2） ,S2=H 第1列 E=1 0 0 0 0 0 第1位错同理 S3=H 第3列 E=0 0 1 0 0 0 第3位错,例5、已知一（7，4），监督码元和信息码元之间的关系为：,求（1）信息码字I=0 0 1 1时的编码码组 （2） 如果接收的码字B=1000101，确定收到的码组是否有错，并纠正。,4、汉明码,（1）码长满足,（2）最小码距d0=3,（3）编码效率, 9. 4 线性分组码,我们把建立在代数学基础上的编码称为代数码。在代数码中，常见的是线性码。线性码中信息位和监督位是由一些线性代数方程联系着的，或者说，线性码是按一组线性方程构成的。 本节将以汉明(Hamming)码为例引入线性分组码的一般原理。,回顾奇偶监督码在接收端解码时，实际上就是在计算若S0，认为无错；若S1，认为有错。上式称为监督关系式，S称为校正子。S只有两种取值，只能代表有、无错两种信息，不能指出错码位置。如果监督位增加一位，则增加一个监督关系式。两个校正子的可能值有4种组合：00，01，10，11，故能表示4种不同状态。,若用其一种表示无错，则其余3种就可能用来指示一位错码的3种不同位置。同理r个监督关系式能指示一位错码的(2r-1)个可能位置。 一般地，若码长为n，信息位数为k，则监督位数r=n-k。如果希望用r个监督位构造出r个监督关系式来指示一位错码的n种可能位置，则要求 2r-1 n，或者 2r r+k+1,举例说明如何构造监督关系式：设(n，k)分组码中k=4。为了纠正一位错码，要求监督位数r 3。若取r=3，则n=k+r=7。校正子与错码位置的对应关系如表94规定(也可以另外规定) 。,由表可见，当一错码在a2, a4，a5或a6时校正子S1为1；否则S1为0. a2, a4，a5和a6构成偶数监督关系。即构成如下关系: 同理,在发送端编码时，信息位a6a5a4a3的值决定于输入信号，因此它们是随机的。监督值a2a1ao应根据信息位的取值按监督关系来确定即监督位应使上三式中的值为零(表示编成的码组中应无错码)，由此得到方程组,由此解出,给定信息位后，可直接按上式算出监督位，其结果如表95所列。,接收端收到每个码组后，先按监督方程计算出S1、S2、 S3 ，再按表94判断错码情况。例：接收0000011，可得： S1S2S3=011 。由表94可知在a3位有错码。 (7，4)汉明码：最小码距d0=3纠一个错码或检测两个错码。编码效率k/n=(2r-1-r)(2r-1)=I-rn。当n很大时，则编码效率接近1。,线性分组码的般原理。线性分组码是指信息位和监督位满足一组线性方程的编码。改写为,(模2),简记为 或,称为监督矩阵,H矩阵的各个行是线性无关的行数=监督位数，列数=码字长度,典型阵,转置得,其中：,矩阵P,称为典型生成矩阵,生成矩阵G的每一行都是一个码组。例如，（参照前页矩阵G）。利用生成矩阵，码字,再由 得，,H和G互为正交关系,译码,若发送码组为接收码组为二者之差为其中E称为错误图样。,表示该位接收码元无错；表示该位接收码元有错。,接收端译码时计算当接收码组无错时S等于零有错但不超过检错能力时， S不等于零。在错码超过检错能力时，B变为另一许用码组，仍能成立S等于零。这样的错码是不可检测的。S称为校正子(伴随式) 。S只与E有关，而与A无关，意味着S与E有的线性变换关系，能与E一一对应，可指示错码位置。,线性码重要性质之一，是它具有封闭性。 若：A1和A2是线性码中的两个许用码组，则：(A1+A2)仍为其中的一个码组。由封闭性，两个码组之间的距离必是另一码组的重量。故码的最小距离即是码的最小重量(除全“0”码组外)。 线性码又称群码，这是由于线性码的各许用码组构成代数学中的群。,9.3.4 线性分组码的译码 码字Ci 接收字R Ci的估值 干扰 1.差错图案 线性分组码 C 的任一码字Ci =(ci 1 , ci 2 , , cin) 经信道传输后，接收到字 R = (r 1 , r 2 , , rn)；令 E = R- Ci = ( r 1- ci1 , r2- ci2 , , rn - cin ) ; 这里称 E 为差错图案。 根据模2运算的性质，E=R+Ci E = 0 则R是码C 的码字；否则， R不是码C 的码字。 对于二元(n , k)码 ，差错图案E 的分量中“1”的个数即为接收码字R 差错的个数 。 差错图案出现 t 个差错的图案数量为Cnt 。,2.伴随式 根据 Ci H T= 0 1(n-k) 及 R = Ci + E， R H T = ( Ci + E ) H T= Ci H T + E H T = E H T 令 S= R H T 或 S = E H T ; 这里 S = (s1 , s2 , , sn-k) 这里称 S 为伴随式 。 伴随式 S 仅与接收字R 或差错图案E 有关，与码字Ci 无关。 由于伴随式S是n-k 维矢量，故不同S的个数只有2n-k 个；而接收字R 或差错图案 E 有 2 n 个，因此，不同的接收字R 或差错图案E 有相同的伴随式 S .,例 ( 5 , 2 ) 线性分组码 1生成矩阵G 2 校验矩阵H3编码码字: 00000 01101 10111 11010 dmin=34差错图案E出现 0 个差错的 1个: 00000 出现 1 个差错的 5个: 00001 00010 00100 01000 10000出现 2 个差错的10个: 00011 00110 01100 11000 00101 01010 10100 01001 10010 10001,5伴随式S = R HT = E HT 00000000 00001001 00011011 00010010 00110110 00100100 01100001 01000101 11000010 10000111 00101101 01010111 10100011 01001100 10010101 10001110,E S,E S,E S,3.线性分组码的译码原理 生成矩阵G 或校验矩阵H确定后，就可以解决编码问题。码字经过信道传输后，接收端获得的只有R，而 Ci 未知的，因此E也是未知的. 如何根据H和R进行译码， 1如果接收字无差错，则 R = Ci ，则S= R H T = 0； 2如果接收字有差错，当差错dmin时，则S=RH T0； 3当码字Ci 错为另一个码字时 , 则 S = RH T = 0。结论： 如果S0，则接收字有差错；如果 S=0，不能肯定接收字无差错。 在有扰信道情况下，找到一个绝对无错的译码方案是不可能的， 只能选择一种译码错误概率最小的译码方案。 无论S0 或 S = 0，均按最小距离原理译码。,4.伴随式译码 1根据H计算出与各种差错图案E 对应的伴随式S ； 2接收到码字R，计算 S= RH T； 3根据 S , 查找与对应的差错图案或陪集头E； 4计算 C= R+E , 则 C 被认为是发送的码字。前例 根据H计算差错图案对应的伴随式S 若接收字 R = (10101)，则 S = RHT= (010) 查表得 S =(010) E = (00010) 译码 C = R + E = (10101) + (00010) = (10111) (n, k)线性分组码，当 n , k 较大时译码表，译码器变得很复杂。,9.3.6 完备码 二元(n , k)线性分组码能纠正 2n-k个差错图案，包括无错的差错图案. 二元(n , k) 码的接收字R 有 2n 个 , 码字Ci 的个数为2k 个，伴随式S 最多有 2n-k 个，差错图案 E 有 2n 个 , 但只能纠检错 2n-k 个。 差错为0图案Cn0，差错为1图案Cn1, ,差错为t图案Cnt 。 若二元(n , k)线性分组码纠错能力为 t , 则对差错数小于等于 t 的差错图案均应有一个伴随式与之对应 。因此， 若 则称二元(n , k)线性分组码为完备码,1. Hamming码 若二元(n , k)线性分组码纠错能力为1，试求是否有完备码 。 因为 Cn01，Cn1n ，所以 2n k =1+n 令 n = 2nk -1 , k =2nk -1-(n-k) 再令 m = n -k 则 n = 2m1 , k = 2m 1 m , m=3 , 4 , 5 , 这种形式二元(n, k)线性分组码称为Hamming码 , 它是一类完备码 , 其 最小距离 dmin=3 , 纠错能力 t=1 ； 编码效率 R= ( 2m 1 m)/ ( 2m1) 。 当 m = 3 , 4 , 5 , 6 , 7 , 8 , 时 , 有 (7 , 4) , (15 , 11) , (31 , 26) , (63 , 57) , (127, 120) , ,例 ( 7 , 4 ) 线性分组码 1生成矩阵G 2 校验矩阵H3码字: 0000000 0001011 0010110 0011101 11111114差错图案E 与伴随式S,
