通信原理第九章培训资料.ppt

1,第九章 差错控制编码,主要内容： 纠错编码的原理 线性分组码 循环码,重点： 检错、纠错的概念 分组码的结构 汉明码 循环码,2,9.1 引言,9.2 纠错编码的原理,9.3 常用的简单编码,9.4 线性分组码,9.5 循环码,3,9.1 引 言,检错重发法,9.1.2 差错控制的方法,9.1.1 编码的目的：提高信号抗加性干扰的能力,干扰种类： 加性 克服方法：差错控制编码,加性干扰的特征：,突发信道：出现错码成串集中混合信道：前两者中和乘性 克服方法：均衡器,随机信道：出现错码是随机的，相互间统计独立白噪声）,反馈校验法,前向纠错方法,定义,误码率标准,4,CCITT 建议的误码率标准,5,检错重发法：在接收端检测出错码时，通知发端重发信号，直到接收正确为止此方法只能判断是否有错码，不能判断具体的错码位置所以，只能检错不能纠错，且需要双向通道前向纠错方法：在收端检测出错码时，可以确定错码的位置，并予纠正此方法只需要单向通道实时性好，但设备复杂反馈校验法：接收端将收到的信号原封不动的发回发端，由发端将其与原发信号相比较，如果有错则重发这种方法需双向通道，效率低，但设备简单6,在信息码序列中加监督码元（也称纠错码）,自动请求重发系统（ARQ）,9.1.3 差错控制编码的原理：,不同的编码方法，有不同的检错或纠错能力，监督码元越多，检、纠错能力越强。

由于信息码元是随机序列，收端无法预知信号状态，因而无法判别接收码是否有错增加了监督码元之后，监督码和信息码之间存在一种逻辑关系，因此，收端可以利用这种逻辑关系发现或纠正存在的错码7,自动请求重发系统（ARQ）,工作过程：,3）重发控制器收到重发命令时，控制输入缓冲储存器重发一次当前码组，否则发送后一码组2）收端解码器检测出错码时由指令发生器产生重发命令传给发端，同时发出删除命令，删除输出缓冲器内容1）收发正常时，重发控制与指令发生器不工作优点：1）监督码少，占总码的( 20% ) 2）对各种信道有一定的适应能力 3）成本及复杂性低缺点：1）需要双向通道 2）干扰大时系统可能处于重发循环中，效率降低 3）实时性差,8,9.2 纠错编码的基本原理,9.2.1 分组码的概念,9.2.2 分组码参数,9,例：天气预报,9.2.1 分组码的概念,特征：分组码中的监督码元仅监督本码组中的信息码元分组码定义：将信息码分组，为每组信息码后附加若干监督码元形成的码集合分组码检错、纠错能力的体现,结论：虽然接收码组有错，但接收端无法识别讨论,10,建立分组码 A,错 1 位,错 2 位,结论：只能检测出 1 位错码，但不能纠正。

禁用码组：非信息码组,许用码组：有效信息码组,11,结论：能纠正 1 位错码，或检测出 2 位错码建立分组码 B,错 1 位,错 2 位,12,k ： 码组中信息码元的数目 n ： 码组的总位数，又称为码组长度 r = n - k ：码组中监督码元的数目结构,符号( n , k ),,,,,码长 n = k + r,,,k 个信息位,r 个监督位,码组重量,码组中 “1 ” 的数目,9.2.2 分组码参数,,码距 d ：两个码组对应位上不同的码元个数称为码组间的汉明距离,码距与码集合检、纠错能力的关系,13,例：码组（a2 a1 a0）= 1 1 0 （b2 b1 b0）= 0 1 1,码距的几何概念,码距是 2,最小码距 d0 ：码集合中任意两两码组间距离的最小值,（ 0 1 0）,（ 1 1 0）,（ 0 0 0）,（ 1 0 0）,（ 1 0 1）,（ 0 0 1）,（ 0 1 1）,（ 1 1 1）,,选许用码组：0 0 0 0 1 1 1 1 0 1 0 1,令 n = 3 , 共有 8 个码组,沿立方体各边行走，4 个码组的距离均为 2 个边长,d0 =2,,,14,, 检测 e 个错码，要求最小码距, 纠正 t 个错码，要求最小码距, 纠正 t 个错码、同时检测 e 个错码，要求最小码距,码距与码集合检、纠错能力的关系,,,,,,,A,B,例： A = ( 00000 ) 、B = ( 11111 )， d0 = 5,,,,结论：e = 4 或 t = 2 或 e = 3、 t = 1,d = 1,d = 2,d = 3,15,9.3 常用的简单编码,9.3.1 奇偶监督码,9.3.2 正反码,16,,, 奇数监督码:, 偶数监督码:,监督码元 1 位,使码组中“1” 的个数为奇,监督码元 1 位,使码组中“1” 的个数为偶,只能检测奇数个错码,二维奇偶监督码（矩阵码）,能检测部分偶数个错码,生成规则： 许用码组写成一行（包括信息码和1 位监督码），设共有m 行。

第 m+1 行为按列增加的监督码构成监督码行）,例,9.3.1 奇偶监督码,一维奇偶监督码,例,监督方程,监督方程,17,例 :,一维偶数监督码,错 1 位,满足：,检验不满足,只能检错，不能纠错,18,2）当 同时出错，则按行按列均不能检测出有错 能检测部分偶数个错码适用于突发信道 若仅一行有奇数个错码时，可通过列确定错码位置并纠正1）设 和 发生错码，按行无法检测出有错，而按列可检测a2 a1 a0 0 0 0 0 1 1 1 0 1 1 1 0 0 0 0,例 ：二维偶数监督码,通式,结论： 方阵码除对构成矩形四角的错码无法检测外，其余均能检测19,特征：具有纠正 1 位错码、检测 2 位和大部分 2 位以上错码的能力,定义：信息码位数与监督码位数相同,编码 规则：,1）当信息位中有奇数个“1”时，监督位是信息位的重复2）当信息位中有偶数个“1”时，监督位是信息位的反码1 0 0 0 1,例：若信息码为 1 1 0 0 1,9.3.2 正反码,则正反码为 1 1 0 0 1 1 1 0 0 1,1 0 0 0 1 0 1 1 1 0,1）将接收码组中信息码和监督码对应按位模2 加，得合成码组,2）根据接收码组中信息码含 “1” 的奇偶情况，由合成码组生成校验码组,3）根据校验码组的组成，依表判断错码情况，并予检错与纠错,译码 规则：,“1”为奇 校验 = 合成 “1”为偶 校验 =,例,20,例：发 1 1 0 0 1 1 1 0 0 1,1）收无错, 信息码中含奇数个“1”,2）收有错、为 1 0 0 0 1 1 1 0 0 1,合成码组=,1 1 0 0 1 1 1 0 0 1,,0 0 0 0 0,译码判决：, 校验码组 = 合成码组 = 00000,判断接收无错码,合成码组=,1 0 0 0 1 1 1 0 0 1,,0 1 0 0 0, 信息码中含偶数个“1”,,查表知信息码第二位错,特征：编码效率低,21,9.4 线性分组码,9.4.1 汉明码的编码原理,9.4.2 一般线性分组码的编码原理,9.4.3 线性码分组码的数学描述,22,,9.4.1 汉明码的编码原理,定义：能纠正一位错码，且编码效率较高的线性分组码,问题： 在正反码中，为纠正一位错码，其监督码位数与信息码位数一样多，能否减少监督码位数但纠错能力不变？,如何实现纠错？,思路：分组码( n , k )只可能出现 n 个一位错码事件，若某种逻辑组合具有n 个状态，就能利用这种逻辑组合描述一位错码事件并予纠正。

例：分析偶数监督码，寻找逻辑组合,汉明码, 监督方程,则接收时解码是在计算,只能表示出错 不能描述错码位置,一位监督码对应一个监督方程,结论：若增加监督码元，建立多个监督方程，多个校正子就能形成逻辑组合描述错码位置,23,汉明码,确定监督码元位数 r,确定监督关系表,建立监督方程,建立编码方程, 分组码( n , k ) 共需 n+1 个状态描述无错及 n 个有错事件,,为提高编码效率， r 取最小值,例：已知( 7 , 4 )码，r = 3, 共有3个监督方程，构成 3个校正子 S1 S2 S3,例,24,例：已知 ( 7 , 4 )汉明码 ，求码组集合,解：, 监督方程, 编码方程, k = 4，信息码组有 16 个, r = 3,25,例： 汉明码的监督方程为, 矩阵表达式,9.4.2 一般线性分组码的编码原理（矩阵方程）,记为：,H ：监督矩阵,A ：码组向量,,,思路：确定编码矩阵方程，构造生成矩阵,26,又 根据监督方程确定了编码方程,,两边同取转置,构造生成矩阵,称 G 为典型生成矩阵（含单位阵）,, 编码矩阵方程,特点：信息位不变，监督位附加于其后定义系统码：由典型生成矩阵得出的码组 A,27,生成矩阵,,G 中每行均为一个码组，且线性无关,28,译码运算，当,S 为校正子。

说明 S 与E 间有确定的线性关系,若 E 的数目有限，能与 S 一一对应， 则 说明 S 能描述错码的位置，具有纠错能力9.4.3 线性码分组码的数学描述,令 发码组为 A、收码组为 B,错码图样 E = B- A,收发码组的关系,令 B =E + A,,,例,29,发码组 A = 1 1 0 0 0 1 0,收码组 B = 1 0 0 0 0 1 0, 译码运算,例： ( 7 , 4 )汉明码,, a5 错,含义：错码图样 E =（0 1 0 0 0 0 0） 只有一位错码,30,定义：线性码中任意两个码组之和仍为这种码中的一个码组,证： 设 A1 、 A2 为线性码中两个许用码组,两式相加,,是许用码组,推广：,1）两个码组间的距离必是另一码组的重量,2）除 0 码组之外，码组的最小重量是码集合的最小距离线性分组码具有封闭性,31,9.5 循环码,9.5.1 码多项式,9.5.2 循环码的特性,9.5.3 循环码的编码方法,32,码多项式的按模运算：,9.5.1 码多项式,码多项式,定义：以码组中各码元为系数的多项式,T( x ) = an-1 x n-1 + an-2 x n-2 + ... + a1 x + a0,设 多项式 F( x ) 、除数为 N( x ),记：模 N( x ),注：多项式按模 N( x ) 运算过程中，其系数按模2 加运算（系数为二进制，只能取 0 或 1 ，系数的相减均为模2 加）。

x 仅为码元位置的标记,例,R( x )：余式,例：( 110 0101 ) T( x ) = x 6 + x 5 + x 2 + 1,33,例：,解：,记为：,余式,34,定理：若 T ( x ) 对应一个码长为 n 的许用码组，,证： 令, T(x) 的系数是 T( x ) 中系数向左循环移位 i 次的结果,9.5.2 循环码的特性,码集合中任意一个码组，左移或右移一位得到的新码组必是该码集合中另一码组,循环码的定义,循环码的码多项式,则 x i T( x ) 按模 x n +1 运算后余式T(x) 仍为许用码组例,35,例： ( 7 , 3 )循环码, 码组为( 110 0101 )，求码多项式T( x )验证 x 3 T( x ) 按模 x 7 +1 运算后余式仍是一个许用码组解： T( x ) = an-1 x n-1 + an-2 x n-2 + ... + a1 x + a0, T( x ) = x 6 + x 5 + x 2 + 1, x 3 T( x ) = x 9 + x 8 + x 5 + x 3,, 余式T(x) 对应码组为 ( 0101110 ),是T (x) 码组左移三位,36,循环码的生成矩阵 G,9.5.3 循环码的编码方法,思路：确定编码矩阵方程，构造生成矩阵,码生成多项式 g( x ) 的定义,循环码的监督矩阵 H,码生成多项式 g( x ) 的求解,例,G 是 G( x ) 的系数矩阵,循环码的检、纠错能力,与 n、k 的值相关,37,循环码生成矩阵 G 的数学描述,已知 ( 7 , 4 )汉明码,G 中每行均为一个码组，且线性无关是线性分组码。