通讯原理差错编码控制.ppt

第十一章 差错控制编码,主要内容 纠错编码的原理 线性分组码 循环码,重点 检错、纠错的概念 分组码的结构 汉明码 循环码,11.1 概述,11.2 纠错编码的原理,11.3 常用的简单编码,11.4 线性分组码,11.5 循环码,作业,11.6 卷积码,习题 11 - 1、5、7、14,作业,11.1 概述,检错重发法,11.1.2 差错控制的方法,11.1.1 编码的目的：提高信号抗加性干扰的能力,干扰种类： 加性 克服方法：差错控制编码,加性干扰的特征：,突发信道：出现错码成串集中。,混合信道：前两者中和。,乘性 克服方法：均衡器,随机信道：出现错码是随机的，相互间统计独立。,反馈校验法,前向纠错方法,定义,误码率标准,CCITT 建议的误码率标准,检错重发法：在接收端检测出错码时，通知发端重发信号，直到接收正确为止。此方法只能判断是否有错码，不能判断具体的错码位置。所以，只能检错不能纠错，且需要双向通道。,前向纠错方法：在收端检测出错码时，可以确定错码的位置，并予纠正。此方法只需要单向通道。实时性好，但设备复杂。,反馈校验法：接收端将收到的信号原封不动的发回发端，由发端将其与原发信号相比较，如果有错则重发。这种方法需双向通道，效率低，但设备简单。,在信息码序列中加监督码元（也称纠错码）,自动请求重发系统（ARQ）,11.1.3 差错控制编码的原理,不同的编码方法，有不同的检错或纠错能力，监督码元越多，检、纠错能力越强。,由于信息码元是随机序列，收端无法预知信号状态，因而无法判别接收码是否有错。增加了监督码元之后，监督码和信息码之间存在一种逻辑关系，因此，收端可以利用这种逻辑关系发现或纠正存在的错码。,自动请求重发系统（ARQ）,工作 过程：,3）重发控制器收到重发命令时，控制输入缓冲储存器重发一次当前码组，否则发送后一码组。,2）收端解码器检测出错码时由指令发生器产生重发命令传给发端，同时发出删除命令，删除输出缓冲器内容。,1）收发正常时，重发控制与指令发生器不工作。,优点：1）监督码少，占总码的( 20% ) 2）对各种信道有一定的适应能力。 3）成本及复杂性低。,缺点：1）需要双向通道 2）干扰大时系统可能处于重发循环中，效率降低 3）实时性差,11.2 纠错编码的基本原理,11.2.1 分组码的概念,11.2.2 分组码参数,例：天气预报,11.2.1 分组码的概念,特征：分组码中的监督码元仅监督本码组中的信息码元。,分组码定义：将信息码分组，为每组信息码后附加若干监督码元形成的码集合。,分组码检错、纠错能力的体现,结论：虽然接收码组有错，但接收端无法识别。,讨论,建立分组码 A,错 1 位,错 2 位,结论：只能检测出 1 位错码，但不能纠正。,禁用码组：非信息码组,许用码组：有效信息码组,建立分组码 B,错 1 位,错 2 位,k ： 码组中信息码元的数目。 n ： 码组的总位数，又称为码组长度。 r = n - k ：码组中监督码元的数目。,结构,符号( n , k ),码长 n = k + r,k 个信息位,r 个监督位,码组重量,码组中 “1 ” 的数目,11.2.2 分组码参数,码距 d ：两个码组对应位数值不同的码元个数称为码组间的汉明距离,码距与码集合检、纠错能力的关系,例：码组（a2 a1 a0）= 1 1 0 （b2 b1 b0）= 0 1 0,码距的几何概念,码距是 1,最小码距 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, 检测 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,11.3 常用的简单编码,11.3.1 奇偶监督码,11.3.2 正反码, 奇数监督码:, 偶数监督码:,监督码元 1 位,使码组中“1” 的个数为奇,监督码元 1 位,使码组中“1” 的个数为偶,只能检测奇数个错码,二维奇偶监督码（矩阵码）,能检测部分偶数个错码,生成规则： 许用码组写成一行（包括信息码和1 位监督码），设共有m 行。第 m+1 行为按列增加的监督码。（构成监督码行）,例,11.3.1 奇偶监督码,一维奇偶监督码,例,监督方程,监督方程,例 :一维偶数监督码,错 1 位,检验满足,检验不满足,只能检错，不能纠错,2）当 同时出错，则按行按列均不能检测出有错。, 能检测部分偶数个错码适用于突发信道。, 若仅一行有奇数个错码时，可通过列确定错码位置并纠正。,1）设 和 发生错码，按行无法检测出错，而按列可检测。,a2 a1 a0 0 0 0 0 1 1 1 0 1 1 1 0 0 0 0,例 ：二维偶数监督码,通式,结论： 方阵码除对构成矩形四角的错码无法检测外，其余均能检测。,特征：具有纠正 1 位错码、检测 2 位和大部分 2 位以上错码的能力,定义：信息码位数与监督码位数相同,编码 规则：,1) 当信息位中有奇数个“1”时，监督位是信息位的重复。,2) 当信息位中有偶数个“1”时，监督位是信息位的反码。,1 0 0 0 1,例：若信息码为 1 1 0 0 1,11.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”为偶 校验 =,例,例：发 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”,查表知信息码第二位错,特征：编码效率低,11.4 线性分组码,11.4.1 汉明码的编码原理,11.4.2 一般线性分组码的编码原理,11.4.3 线性码分组码的数学描述,11.4.1 汉明码的编码原理,定义：能纠正一位错码，且编码效率较高的线性分组码,问题： 在正反码中，为纠正一位错码，其监督码位数与信息码位数一样多，能否减少监督码位数但纠错能力不变？,如何实现纠错？,思路：分组码( n , k )只可能出现 n 个一位错码事件，若某种逻辑组合具有n 个状态，就能利用这种逻辑组合描述一位错码事件并予纠正。,例：分析偶数监督码，寻找逻辑组合,汉明码, 监督方程,则接收时解码是在计算,只能表示出错 不能描述错码位置,一位监督码对应一个监督方程,结论：若增加监督码元，建立多个监督方程，多个校正子就能形成逻辑组合描述错码位置,汉明码,确定监督码元位数 r,确定监督关系表,建立监督方程,建立编码方程, 分组码( n , k ) 共需 n+1 个状态描述无错及 n 个有错事件,为提高编码效率， r 取最小值,例：已知( 7 , 4 )码，r = 3, 共有3个监督方程，构成 3个校正子 S1 S2 S3,例,例：已知 ( 7 , 4 )汉明码 ，求码组集合,解：, 监督方程, 编码方程, k = 4，信息码组有 16 个, r = 3,例：汉明码的监督方程为, 矩阵表达式,11.4.2 一般线性分组码的编码原理（矩阵方程）,记为：,H ：监督矩阵,A ：码组向量,思路：确定编码矩阵方程，构造生成矩阵,又 根据监督方程确定了编码方程,两边同取转置,构造生成矩阵,称 G 为典型生成矩阵（含单位阵）, 编码矩阵方程,特点：信息位不变，监督位附加于其后。,定义系统码：由典型生成矩阵得出的码组 A,生成矩阵,G 中每行均为一个码组，且线性无关,译码运算，当,S 为校正子。说明 S 与E 间有确定的线性关系,若 E 的数目有限，能与 S 一一对应， 则 说明 S 能描述错码的位置，具有纠错能力。,11.4.3 线性码分组码的数学描述,令 发码组为 A、收码组为 B, 错码图样 E = B - A,收发码组的关系,令 B =E + A,例,发码组 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） 只有一位错码,定义：线性码中任意两个码组之和仍为这种码中的一个码组,证： 设 A1 、 A2 为线性码中两个许用码组,两式相加,是许用码组,推广：,1）两个码组间的距离必是另一码组的重量,2）除 0 码组之外，码组的最小重量是码集合的最小距离,线性分组码具有封闭性,11.5 循环码,11.5.1 码多项式,11.5.2 循环码的特性,11.5.3 循环码的编码方法,码多项式的按模运算,11.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 ）。,x 仅为码元位置的标记,例,R( x )：余式,例：( 110 0101 ) T( x ) = x 6 + x 5 + x 2 + 1,例：,解：,记为：,余式,定理：若 T ( x ) 对应一个码长为 n 的许用码组，,证： 令, T(x) 的系数是 T( x ) 中系数向左循环移位 i 次的结果,11.5.2 循环码的特性,码集合中任意一个码组，左移或右移一位得到的新码组必是该码集合中另一码组,循环码的定义,循环码的码多项式,则 x i T( x ) 按模 x n +1 运算后余式T(x) 仍为许用码组。,例,例： ( 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) 码组左移三位,循环码的生成矩阵 G,11.5.3 循环码的编码方法,思路：确定编码矩阵方程，构造生成矩阵,码生成多项式 g( x ),循环码的监督矩阵 H,码生成多项式 g( x ) 的求解,例,G 是 G( x ) 的系数矩阵,循环码的检、纠错能力,与 n、k 的值相关,循环码的编码方法,循环码生成矩阵 G 的数学描述,已知 ( 7 , 4 )汉明码,G 中每行均为一个码组，且线性无关是线性分组码的共性。,循环码是线性分组码成员之一，其 G 除满足上述特性外，每行之间必须满足循环性。, 循环码每个码组对应一个码多项式, 以最简方式寻找 k 个线性无关的码多项式就能建立 G( x ),码生成多项式 g( x ),定义： g( x )是幂次为 ( n- k ) 的码多项式。（唯一性）,分析循环码：循环码( n , k ) 的形成方法是在信息码后加监督码且保持移位循环的特征。 除全零码组外，权值最小的信息码组为 0 0 .0 0 1 ，且监督位 a0 不可能为零，否则循环数次后码组前 k 位均为零，而监督位不为零的情况，这不符合监督码的定义,结论：信息码组 0 0 .0 0 1 对应的码多项式必为( n- k ) 次幂，且常数项不等于零, 信息码组 0 0 .0 0 1 唯一, 码多项式唯一，且幂次最低，记为 g( x ), 与 g( x ) 线性无关的 k-1 个码多项式为 x g( x )、 . x k-1g( x )，可组成生成矩阵 G( x ),码生成多项式 g( x ) 的求解,定理：g( x ) 是 x n +1 的一个( n - k ) 次因子。,证： g( x ) 是幂次最低的码多项式, 任意一个码多项式 T( x ) 都是 g( x ) 倍数,令 T( x ) = h( x ) g( x ),余式为码组, x k g( x ) = x n +1 + T( x ), x n +1 = x k g( x ) + T( x ),模 2 加,= x k g( x ) + h( x ) g( x ),= x k + h( x ) g( x ),得证,例：已知 ( 7 , 3 ) 循环码，求码组集合 、监督矩阵 H 。,解： n = 7, x7 + 1 = ( x +1 )( x 6 + x 5+ x 4 + x 3 + x 2+ x + 1 ),= ( x +1 )( x 3 + x 2+ 1 )( x 3 + x + 1 ), g1( x ) = ( x +1 )( x 3 + x 2+ 1 ) = x 4 + x 2+ x + 1, g2( x ) = ( x +1 )( x 3 + x + 1 ) = x 4 + x 3+ x 2 + 1,取 g( x ) = g1( x ) = x 4 + x 2+ x + 1, A = ( a6 a5 a4 a3 a2 a1 a0 ),监督方程：, d0 = 4 t = 1,非系统码,循环码的编码方法,思路：已知信息码组多项式 m( x )，建立T( x ),编码步骤为：,1）生成 x n-k m( x ),2）生成 x n-k m( x ) /g( x )，求余式 r ( x ),3）生成循环码多项式 T ( x ),T( x ) = x n-k m( x ) + r( x ),例：m( x ) = 101 建立( 7 , 3 ) 循环码,解： x n-k m( x ) = 1010000,g( x ) = x 4 + x 2+ x + 1, r ( x ) = x 3 + x 2, T( x ) = x 6 + x 4 +x 3 + x 2,码组为 1011100 系统码,非系统码,b,c,d,a,输入,输出,开关S,S 同时上下,( 7 , 3 ) 循环码编码,11.6 卷积码,11.6.1 卷积码的图形描述,11.6.2 卷积码的解析描述,k ： 信息码元 n ： 码组长度 N ：约束长度,符号( n , k , N ),定义：线性非分组码,特点：相邻数个码组的编码相互约束,本码组编码不仅与自身的 k 位信息码有关， 还与前面 ( N-1 ) 个码组的信息段有关,11.6.1 卷积码的图形描述,输入序列 m1m2. mj.,输出序列,y1jy2jy3j y1jy2jy3j.,y1j,y2j,y3j,输入输出序列速度匹配关系,移位寄存器,树状图,网格图,状态图,( 3 , 1 , 3 ) 卷积码的编码器