通信原理第11章差错控制编码.ppt

* * * * * * 11.4 线性分组码 (1) 分组码： 先将信息码分组，然后给每组信码附加若干监督码的编码称为分组码，用符号(n,k)表示，k是信息码的位数，n是编码组总位数，又称为码长，r=n-k为监督位数。 (2) 代数码： 建立在代数学基础上的编码称为代数码。例如奇偶校验码。 1、基本概念 (3) 线性码： 线性码中信息位和监督位是按一组线性方程构成的。线性码是一种代数码。 (4) 线性分组码： 信息码分组后，附加的监督码和信息码由一些线性代数方程联系着的编码称为线性分组码。 11.4 线性分组码 2、线性分组码的性质 任意两个许用码组之和（逐位模2和）仍为一许用码组，即具有封闭性。 最小码距=非零码的最小码重（1的个数）。 有零码（信息码元和监督码元均为零的码组） 11.4 线性分组码 以汉明码为例来说明编码原理。汉明码是一种设计用来纠正一位错码且编码效率较高的线性分组码，已广泛应用于数字通信和数据存储系统中，本节将以（7，4）汉明码为例进行讲述。 3、线性分组码的编码原理 11.4 线性分组码 发送端编码：将一位监督码元附加在信息码元后，使得码元中“1”码元个数为偶数。 接收端译码： 计数接收码组中“1”码元个数是否为偶数，即计算：S=an-1+ an-2+……+ a0 （模2加）（11.4-1） S=0认为没错，S=1认为有错。 （11.4-1）式称为监督方程/监督关系式，S称为校正子/校验子/伴随式 （1）回忆奇偶监督偶校验码 11.4 线性分组码 监督位增加到2位：有两个监督方程，两个伴随式； 两个伴随式组合有四种（00表示无错，01、10、11表示一位错码的三种可能位置） 监督位增加到r位：可指示一位错码的（2r-1）个可能位置 对于（n，k)分组码，若希望用r=n-k个监督位构造出的r个监督关系式来指示一位错码的n种可能位置，则要求：2r-1≥n 即2r ≥k+r+1 （11.4-2） 可以这样来考虑 11.4 线性分组码 欲纠正一位错码，由（11.4-2）式知r ≥3。取r=3，则n=k+r=7 设7位码元为：a6a5 ……a0； 三个伴随式：S1、S2、S3； 可规定S1S2S3的八种组合与一位错码的对应关系（也可规定为另一种对应关系）： 构造一（n，k)分组码，k=4并能纠正一位错码 (2) 汉明码的构造 11.4 线性分组码 表11-9 S1S2S3的八种组合与一位错码的对应关系 11.4 线性分组码 S1S2S3 错码位置 0 0 0 无错码 0 0 1 a0 0 1 0 a1 1 0 0 a2 0 1 1 a3 1 0 1 a4 1 1 0 a5 1 1 1 a6 信息码 监督码 a6 a5a4 a3 a2 a1 a0 S1= a2+a4+a5+a6 S2= a1+a3+a5+a6 S3= a0+a3+a4+a6 (11.4-3) 监督方程: （3）发端编码的原则： 信息码元a6 、a5 、a4、a3来源于待编码的信息序列； 监督码元 a2 、a1、 a0的取值应根据信息码元按监督关系式来决定，即使前面三式中的S1、 S2 、S3均为0： 11.4 线性分组码 a2 = a4+a5+a6 a1 = a3+a5+a6 a0 = a3+a4+a6 给定信息位后，根据上式算出各监督位，该编码的所有码组如表11-10： (11.4-4) a6+a5+a4+a2=0 a6+a5+a3+a1=0 a6+a4+a3+a0=0 (11.4-5) 11.4 线性分组码 表11-10 （7，4）汉明编码的许用码组 该汉明码的编码效率较高 R=k/n=4/7≈57% 该码的最小码距为3，能纠正一个错码或检测两个错码 收到码组0000011，按照（7，4）汉明码进行分析，判断是否有误，如果有，如何更正？ 按监督方程计算可得：S1=0，S2=1，S3=1；再根据校正子组合与一位错码位置的对应关系，可知错码发生在a3位，并加以纠正。0001011 11.4 线性分组码 （4）监督矩阵 沿（7，4）汉明码出发，式（11.4-4）可改写成： 1 · a6+ 1 · a5+ 1 · a4 +0 · a3+ 1 · a2 + 0 · a1+ 0 · a0=0 1 · a6+ 1 · a5+ 0 · a4 +1 · a3+ 0 · a2 + 1 · a1+ 0 · a0=0 1 · a6+ 0 · a5+ 1 · a4 +1 · a3+ 0 · a2 + 0 · a1+ 1 · a0=0 写成矩阵形式： (11.4-6) 11.4 线性分组码 H称为线性码监督矩阵 可化简为： H·AT=