新第章差错控制编码.ppt

第5章 差错控制编码 按功能分：检错码和纠错码 按监督码元与信息码元关系分：线性码与非线性码 按信息码元与监督码元之间的约束关系不同分：分组码与卷积码 按信息码元在编码后是否保持原来的信号形式分：系统码与非系统码 按纠正差错的类型分：纠正随机错误的码与纠正突发错误的码 按码元的取值分：二进制码与多进制码 5.2 差错控制编码的基本原理 5.2 差错控制编码的基本原理 5.2 差错控制编码的基本原理 码长：码字中码元的数目。 码距：两个码组之间对应位上码元取值不同的个数，定义为两码字的距离，简称码距（d）。 对于二进制称作这两个码字的汉明距离。如两码字“10011”与“11010”间码距为2。 5.2 差错控制编码的基本原理 一个码能检测e个错码，则要求其最小码dmin≥e+1 一个码能纠正t个错码，则要求其最小dmin≥2t+1 一个码能纠正t个错码，同时能检测e个错码，则要求其最小码距 dmin≥e+t+1 (et) 5.2 差错控制编码的基本原理 5.2 差错控制编码的基本原理 5.2 差错控制编码的基本原理 5.2 差错控制编码的基本原理 当码长n=7, P=10-3时，则有 5.2 差错控制编码的基本原理 设n=k+r 指一个码组中信息位所占比重，用η 表示 η=k/n=k/(k+r)，其中k为信息码元的数目，n为码长 编码效率是衡量纠错性能的一个重要指标，一般情况下，监督位越多，检纠错能力越强，但相应的编码效率也越低 5.3 常用的简单编码 奇偶监督码 二维奇偶监督码 恒比码 正反码 1、奇偶监督码 2、水平奇偶监督码 将经过奇偶监督编码的码元序列按行排成方阵，每行为一组奇偶监督码，但发送时按列的顺序传输 接收端将码元排成发送时的方阵形式，再按行进行奇偶校验 能够发现某行上所有奇数个错误以及突发长度不大于方阵行数的突发错误 编码效率 3、水平垂直奇偶监督码 又称为方阵码、行列监督码、二维奇偶监督码。 将水平奇偶监督码推广到二维。即在水平监督基础上再对方阵中每一列进行奇偶校验，发送时按列的顺序传输 接收端将码元排成发送时的方阵形式，再分别按行、按列进行奇偶校验 5.4 线性分组码 （重点） (1) 分组码： 先将信息码分组，然后给每组信码附加若干监督码的编码称为分组码，用符号(n,k)表示，k是信息码的位数，n是编码组总位数，又称为码长，r=n-k为监督位数。 (2) 代数码： 建立在代数学基础上的编码，称为代数码。例如奇偶校验码。 5.4 线性分组码 (3) 线性码： 线性码中信息位和监督位是按一组线性方程构成的。线性码是一种代数码。奇偶监督码是最简单的线性码。 (4) 线性分组码： 信息码分组后，附加的监督码和信息码由一些线性代数方程联系着的编码称为线性分组码。 3、线性分组码的编码原理 以汉明码为例来说明编码原理。汉明码是一种设计用来纠正一位错码且编码效率较高的线性分组码。（7，4）汉明码的编码效率为： （1）回忆奇偶监督偶校验码 发送端编码：将一位监督码元附加在信息码元后，使得码元中“1”码元个数为偶数。 接收端译码： 计数接收码组中“1”码元个数是否为偶数，即计算：S=an-1+ an-2+……+ a0 （模2加）（5.4-1） S=0认为没错，S=1认为有错。 （5.4-1）式称为监督方程/监督关系式，S称为校正子/校验子/伴随式 监督位增加到2位：有两个监督方程，两个校验子； 两个校验子组合有四种（如00表示无错，01、10、11则可表示一位错码的三种可能位置） 监督位增加到r位：可指示一位错码的（2r-1）个可能位置 对于（n，k)分组码，若希望用r=n-k个监督位构造出的r个监督关系式来指示一位错码的n种可能位置，则要求： 欲纠正一位错码，由（5.4-2）式知r ≥3。取r=3，则n=k+r=7 设7位码元为：a6a5 ……a0； 三个校正子：S1、S2、S3； 可规定S1S2S3的八种组合与一位错码的对应关系（也可规定为另一种对应关系）： 该汉明码的编码效率较高 R=k/n=4/7≈57% 该码的最小码距为3，能纠正一个错码或检测两个错码 设收到码组0000011，按监督方程计算可得：S1=0，S2=1，S3=1；再根据校正子组合与一位错码位置的对应关系，可知错码发生在a3位，并加以纠正。0001011 （4）监督矩阵 沿（7，4）汉明码出发，式（5.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 · a