差错控制编码第二次课课件.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=77,4)线性分组码（线性分组码（a6 a5 a4 a3 a2 a1 a0)校正子与错码位置的对应关系如表规定校正子与错码位置的对应关系如表规定(也可也可以另外规定以另外规定) S1S2S3错码位置错码位置S1S2S3错码位置错码位置001a0101a4010a1110a5100a2111a6011a3000无错无错由表可见，当一错码位置在由表可见，当一错码位置在a2,a4，a5或或a6时校时校正子正子S1为为1；否则；否则S1为为0即构成如下关系即构成如下关系由此解出由此解出给定信息位后，可直接按上式算出监督位给定信息位后，可直接按上式算出监督位监督方监督方程程信息位监督位信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a000000001000111000101110011000010101101001000111101011001010011011000010101101110101001100111110100011100011111112、 监督矩阵监督矩阵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为为0B1无错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规定规定(也可以另外规定也可以另外规定) S1S2S3错码位置错码位置S1S2S3错码位置错码位置001a0101a4010a1110a5100a2111a6011a3000无错无错由表可见，由表可见，当一错码在当一错码在a2, a4，a5或或a6时校正子时校正子S1为为1；否则；否则S1为为0. a2, a4，a5和和a6构成偶数监督关系。

构成偶数监督关系即构成如下关系即构成如下关系: 同理同理在发送端编码时，信息位在发送端编码时，信息位a6a5a4a3的值决定于输的值决定于输入信号，因此它们是随机的监督值入信号，因此它们是随机的监督值a2a1ao应应根据信息位的取值按监督关系来确定即监督根据信息位的取值按监督关系来确定即监督位应使上三式中的值为零位应使上三式中的值为零(表示编成的码组中表示编成的码组中应无错码应无错码)，由此得到方程组，由此得到方程组由此解出由此解出给定信息位后，可直接按上式算出监督位，其给定信息位后，可直接按上式算出监督位，其结果如表结果如表95所列信息位信息位监督位监督位信息位信息位监督位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111 接收端收到每个码组后，先按监督方程接收端收到每个码组后，先按监督方程计算出计算出S1、S2、 S3 ，再按表再按表94判断判断错码情况。

例：接收错码情况例：接收0000011，可得：，可得： S1S2S3=011 由表由表94可知在可知在a3位有错位有错码 (7，4)汉明码：汉明码：l最小码距最小码距d0=3l纠一个错码或检测两个错码纠一个错码或检测两个错码l编码效率编码效率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”码组外码组外)。