《通讯原理差错编码控制.ppt》由会员分享，可在线阅读，更多相关《通讯原理差错编码控制.ppt（53页珍藏版）》请在三一办公上搜索。
1、第十一章 差错控制编码,主要内容纠错编码的原理线性分组码循环码,重点检错、纠错的概念分组码的结构汉明码循环码,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 编码的目的：提高信号抗加性干扰的能力,干扰种类：加性 克服方法：差错控制编码,加性干扰的特征：,突发信道：出现错码成串集中。,混合信道：前两者中和。,乘性 克服方法：均衡器,随机信道：出现错码是随机的，相互间统计独立。,反馈校验法,前向纠错方法,定义
2、,误码率标准,CCITT 建议的误码率标准,检错重发法：在接收端检测出错码时，通知发端重发信号，直到接收正确为止。此方法只能判断是否有错码，不能判断具体的错码位置。所以，只能检错不能纠错，且需要双向通道。,前向纠错方法：在收端检测出错码时，可以确定错码的位置，并予纠正。此方法只需要单向通道。实时性好，但设备复杂。,反馈校验法：接收端将收到的信号原封不动的发回发端，由发端将其与原发信号相比较，如果有错则重发。这种方法需双向通道，效率低，但设备简单。,在信息码序列中加监督码元（也称纠错码）,自动请求重发系统（ARQ）,11.1.3 差错控制编码的原理,不同的编码方法，有不同的检错或纠错能力，监督码
3、元越多，检、纠错能力越强。,由于信息码元是随机序列，收端无法预知信号状态，因而无法判别接收码是否有错。增加了监督码元之后，监督码和信息码之间存在一种逻辑关系，因此，收端可以利用这种逻辑关系发现或纠正存在的错码。,自动请求重发系统（ARQ）,工作过程：,3）重发控制器收到重发命令时，控制输入缓冲储存器重发一次当前码组，否则发送后一码组。,2）收端解码器检测出错码时由指令发生器产生重发命令传给发端，同时发出删除命令，删除输出缓冲器内容。,1）收发正常时，重发控制与指令发生器不工作。,优点：1）监督码少，占总码的(20%)2）对各种信道有一定的适应能力。3）成本及复杂性低。,缺点：1）需要双向通道
4、2）干扰大时系统可能处于重发循环中，效率降低 3）实时性差,11.2 纠错编码的基本原理,11.2.1 分组码的概念,11.2.2 分组码参数,例：天气预报,11.2.1 分组码的概念,特征：分组码中的监督码元仅监督本码组中的信息码元。,分组码定义：将信息码分组，为每组信息码后附加若干监督码元形成的码集合。,分组码检错、纠错能力的体现,结论：虽然接收码组有错，但接收端无法识别。,讨论,建立分组码 A,错 1 位,错 2 位,结论：只能检测出 1 位错码，但不能纠正。,禁用码组：非信息码组,许用码组：有效信息码组,结论：能纠正 1 位错码，或检测出 2 位错码。,建立分组码 B,错 1 位,错
5、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
6、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
7、位,使码组中“1”的个数为偶,只能检测奇数个错码,二维奇偶监督码（矩阵码）,能检测部分偶数个错码,生成规则：许用码组写成一行（包括信息码和1 位监督码），设共有m 行。第 m+1 行为按列增加的监督码。（构成监督码行）,例,11.3.1 奇偶监督码,一维奇偶监督码,例,监督方程,监督方程,例:一维偶数监督码,错 1 位,检验满足,检验不满足,只能检错，不能纠错,2）当 同时出错，则按行按列均不能检测出有错。,能检测部分偶数个错码适用于突发信道。,若仅一行有奇数个错码时，可通过列确定错码位置并纠正。,1）设 和 发生错码，按行无法检测出错，而按列可检测。,a2 a1 a00 0 00 1 11
8、0 11 1 00 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）根据接收码组中信息码
9、含“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 汉
10、明码的编码原理,11.4.2 一般线性分组码的编码原理,11.4.3 线性码分组码的数学描述,11.4.1 汉明码的编码原理,定义：能纠正一位错码，且编码效率较高的线性分组码,问题：在正反码中，为纠正一位错码，其监督码位数与信息码位数一样多，能否减少监督码位数但纠错能力不变？,如何实现纠错？,思路：分组码(n,k)只可能出现 n 个一位错码事件，若某种逻辑组合具有n 个状态，就能利用这种逻辑组合描述一位错码事件并予纠正。,例：分析偶数监督码，寻找逻辑组合,汉明码,监督方程,则接收时解码是在计算,只能表示出错不能描述错码位置,一位监督码对应一个监督方程,结论：若增加监督码元，建立多个监督方程，多
11、个校正子就能形成逻辑组合描述错码位置,汉明码,确定监督码元位数 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：码组向量,思路：确定编码矩阵方程，构造生成矩阵,又 根据监督方程确定了编码方程,两边同取转
12、置,构造生成矩阵,称 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 错,含义
13、：错码图样 E=（0 1 0 0 0 0 0）只有一位错码,定义：线性码中任意两个码组之和仍为这种码中的一个码组,证：设 A1、A2 为线性码中两个许用码组,两式相加,是许用码组,推广：,1）两个码组间的距离必是另一码组的重量,2）除 0 码组之外，码组的最小重量是码集合的最小距离,线性分组码具有封闭性,11.5 循环码,11.5.1 码多项式,11.5.2 循环码的特性,11.5.3 循环码的编码方法,码多项式的按模运算,码多项式,码多项式,定义：以码组中各码元为系数的多项式,T(x)=an-1 x n-1+an-2 x n-2+.+a1 x+a0,设 多项式 F(x)、除数为 N(x),模
14、 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 次的结果,循环码的特性,码集合中任意一个码组，左移或右移一位得到的新码组必是该码集合中另一码组,循环码的定义,循环码的码多项式,则 x i T(x)按模 x n+1 运算后余式T(x)仍为许用码组。,例,例：(7,3)循环码,码组为(110
15、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 的值相关,循环码的编码方法,循
16、环码生成矩阵 G 的数学描述,已知(7,4)汉明码,G 中每行均为一个码组，且线性无关是线性分组码的共性。,循环码是线性分组码成员之一，其 G 除满足上述特性外，每行之间必须满足循环性。,循环码每个码组对应一个码多项式,以最简方式寻找 k 个线性无关的码多项式就能建立 G(x),码生成多项式 g(x),定义：g(x)是幂次为(n-k)的码多项式。（唯一性）,分析循环码：循环码(n,k)的形成方法是在信息码后加监督码且保持移位循环的特征。除全零码组外，权值最小的信息码组为 0 0.0 0 1，且监督位 a0 不可能为零，否则循环数次后码组前 k 位均为零，而监督位不为零的情况，这不符合监督码的定
17、义,结论：信息码组 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)+
18、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),编码步骤
19、为：,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：约束长度,符
20、号(n,k,N),定义：线性非分组码,特点：相邻数个码组的编码相互约束,本码组编码不仅与自身的 k 位信息码有关，还与前面(N-1)个码组的信息段有关,11.6.1 卷积码的图形描述,输入序列 m1m2.mj.,输出序列,y1jy2jy3j y1jy2jy3j.,y1j,y2j,y3j,输入输出序列速度匹配关系,移位寄存器,树状图,网格图,状态图,(3,1,3)卷积码的编码器,输出序列的变化规律,树状图,0,001,011,010,100,1,110,1,000,000,000,111,111,001,011,010,100,101,110,000,111,001,110,0,1,0,111,
21、0,1,a,a,b,a,b,c,101,d,b,a,c,d,a,b,c,d,a：m1m2=00,b：m1m2=01,c：m1m2=10,d：m1m2=11,寄存器初态,m3,m3,m3,m3,00,11,01,10,11,00,10,01,m1m2 0 0,网格图,000,b,c,d,a,010,110,111,101,000,111,001,特点：相同状态的节点合并,100,011,(3,1,3)卷积码,初态,上支路实线下支路虚线,从第 N 个节点开始图形重复出现,2N-1 种,状态图,特点：状态稳定后的转移图,例,010,110,111,100,001,100,110,101,例：输入序列为 11010111，初始状态为 a，,求(3,1,3)卷积码。,1,b,c,d,a,1,0,1,0,1,1,1,000,111,110,001,100,011,010,101,解：利用网格图求输出序列,输出,11.6.2 卷积码的解析描述,生成矩阵 G,矩阵形式,当初态全为零时，第一、第二比特输入时存在过渡过程,系数矩阵,定义：输入序列矩阵 M、输出序列矩阵 Y、生成矩阵 G,半无限矩阵,监督矩阵 H,监督矩阵 H,输出序列 m1 y21 y31 m2 y22 y32 m3 y23 y33,监督关系,前 3 列下移 2 行,前 6 列决定，分析截短矩阵,
