《《差错控制技术》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《差错控制技术》PPT课件.ppt（46页珍藏版）》请在三一办公上搜索。
1、差错控制的常用方法,自动请求重发（ARQ）停发等待重发 返回重发 选择重发前向纠错（FEC）混合纠错（HEC）反馈检验（IRQ）,自动请求重发,优点：译码设备简单，对突发错误和信道干扰较严重时比较有效。缺点：需要反馈信道，实时性差。,前向纠错,优点：使用纠错码和单向信道，发送端无需设置缓冲器。缺点：设备复杂、成本高。,混合纠错,特点：实时性和译码复杂性方面是前向纠错和检错重发方式的折衷，可达到较低的误码率，较适合于环路延迟大的高速数据传输系统。,反馈校验,优点：设备简单，可以纠正任何错误缺点：会引入较大的时延。,纠错编码,通过对信息序列作某种变换，使原来彼此独立、互不相关的信息码元产生某种规律
2、性（相关性），从而在接收端根据这种规律性来检查，进而纠正传输信号序列中的差错。,纠错编码基本原理,变换的方法不同就构成了不同的编码。,引入差错编码控制后，实际传输的 信息序列=信息码元+监督码元，称为码组。,监督码（元）：为了使信息码元产生某种规律性，可按照某种规则在用户信息序列中插入一定数量的新码元，这种新码元叫监督码（元）。,信息码（元）：发送用户端欲发送的信息序列，本来彼此独立，互不相关；由用户控制，最终也交给接收用户。,差错控制编码的基本原理就是：在保持信息位数不变（信息码元）情况下，采用增加码长的方法来降低误码率。,例：传输A和B两个消息。,用一位二进制数表示：“0”A；“1”B传输
3、过程中出现错码，接收端无法发现，无检错和纠错能力。,用两位二进制数“00”A“11”B 称为许用码组“01”和“10”未定义，为禁用码组。S：00 D：00 01 10 S:11 D：11,表示附加一位监督码以后码组具有了检测1位错码，但因译码器不能判别哪位是错码，不具备纠正错码的能力；且无法检测错2位错码。,用三位二进制数“000”A“111”B 称为许用码组“001”、“010”、“011”、“100”“101”、“110”皆是禁用码组,S：000 D：000 001010011100101110111,表明附加两个监督码元以后码组具备检测1位和2位错码的能力；并且具备纠正一位错码的能力，
4、即3位码组中有2个或3个“0”/“1”码，则判为“000”/“111”。但无法纠正两位出错和检测3位出错的能力。,总结：（信息码+监督码=码组）构成的信息序列通过降低信息传输速率来提高传输的可靠性（降低误码率）。,11,分组码 信息位 监督位分组码符号：(n,k)其中，n 码组总长度，k 信息码元数目。r=n k 监督码元数目。分组码的一般结构：分组码的参数：码重：码组内“1”的个数码距：两码组中对应位取值不同的位数，又称汉明距离 最小码距(d0)：各码组间的最小距离,纠错能力与码距关系,码距的几何意义：以n=3的编码为例 一般而言，码距是 n 维空间中单位正多面体顶点之间的汉明距离。,为了检
5、测e个随机错误，则要求码组的最小距离距为,为了纠正t个随机错误，则要求码组的最小距离为,纠正t个随机错码，同时检测e个随机错误，则要求码组的最小距离为,(e t),常用的简单编码,奇偶校验码:增加一位监督码来使得码组中“1”的个数保持奇数（奇校验）或偶数（偶校验）。分为：垂直奇偶校验；水平奇偶校验；水平垂直奇偶校验。群计数码：监督码元附加在信息码元之后，每一个监督码元在数值上表示其对应的信息码元中“1”的个数。,恒比码：每个码组中均包含相同数目的“1”和“0”，即数目之比是一定的，所以也叫定比码。正反码：监督码元与信息码元位数相同，但根据信息码元中“1”的数目不同，监督码元与信息码元完全相同或
6、相反。,代数码 利用代数关系式产生监督位的编码线性分组码 代数码的一种，其监督位和信息位的关系由线性代数方程决定汉明码 一种能够纠正一个错码的线性分组码校正子：在偶数监督码中，计算实际上就是计算并检验S是否等于0。S称为校正子监督关系式：,线性分组码,纠错基本原理 中，S只有两种取值，故只能表示有错和无错，而不能进一步指明错码的位置。若此码组长度增加一位，则能增加一个监督关系式。这样，就能得到两个校正子。两个校正子的可能取值有4种组合，即00，01，10，11，故能表示4种不同的信息。若用其中一种组合表示无错码，则还有其他3种组合可以用于指明一个错码的3种不同位置。从而可以有纠错能力。一般而言
7、，若有 r 个监督关系式，则 r 个校正子可以指明一个错码的(2r 1)个不同位置。当校正子可以指明的错码位置数目等于或大于码组长度n时，才能够纠正码组中任何一个位置上的错码，即要求,汉明码例：要求设计一个能够纠正1个错码的分组码(n,k)，给定的码组中有4个信息位，即k=4。由这时要求监督位数r 3。若取r=3，则n=k+r=7。现在用a6 a5 a4 a3 a2 a1 a0表示这7个码元，用S1 S2 S3表示校正子，则这3个校正子恰好能够指明23 1=7个错码的位置。若规定校正子和错码位置的关系如下表，则仅当在a6 a5 a4 a2位置上有错码时，校正子S1的值才等于1；否则S1的值为零
8、。这就意味着a6 a5 a4 a2四个码元构成偶数监督关系：同理，有,21,在编码时，信息位a6 a5 a4 a3的值决定于输入信号，它们是随机的。监督位a2 a1 a0是按监督关系确定的，应该保证上列3式中的校正子等于0，即有给定信息位后，为了计算监督位，上式可以改写为按照上式计算结果为,22,在接收端解码时，对于每个接收码组，先按式计算出校正子S1，S2和S3，然后按照表判断错码的位置。例：若接收码组为0000011，则按上三式计算得到：S1=0，S2=1，S3=1。这样，由上表可知，错码位置在a3。,上例中的汉明码是(7,4)码，其最小码距d0=3。由式可知，此码能够检测2个错码，或纠正
9、1个错码。汉明码的码率：当r(或n)很大时，上式趋近于1。所以汉明码是一种高效编码。,分组码的一般原理线性分组码的监督位和信息位的关系 可以改写为上式中，已经将“”简写成“+”。,监督矩阵上式可以写成矩阵形式：（模2）将上式简写为HAT=0T 或AHT=0,26,HAT=0T 式中，称为监督矩阵 监督矩阵的性质监督矩阵H确定码组中的信息位和监督位的关系。H 的行数就是监督关系式的数目，即监督位数 r。H 的每行中“1”的位置表示相应的码元参与监督关系。H 可以分成两部分，例如 典型监督矩阵 式中，P 为r k阶矩阵，Ir为 r r 阶单位方阵。,A=a6 a5 a4 a3 a2 a1 a0 0
10、=000,循环码 循环性是指任一码组循环一位后仍然是该编码中的一个码组。例：一种(7,3)循环码的全部码组如下 表中第2码组向右移一位即得到第5码组；第5码组向右移一位即得到第7码组。,28,若(an-1 an-2 a0)是循环码的一个码组，则循环移位后的码组：(an-2 an-3 a0 an-1)(an-3 an-4 an-1 an-2)(a0 an-1 a2 a1)仍然是该编码中的码组。多项式表示法一个长度为n的码组(an-1 an-2 a0)可以表示成 上式中x 的值没有任何意义，仅用它的幂代表码元的位置。例：码组1 1 0 0 1 0 1可以表示为,循环码的运算 整数的按模运算在整数运
11、算中，有模n运算。例如，在模2运算中，有 1+1=2 0(模2)，1+2=3 1(模2)，2 3=6 0(模2)一般说来，若一个整数m可以表示为 式中，Q为整数，则在模n运算下，有m p(模n)所以，在模n运算下，一个整数m等于它被n除得的余数。,码多项式的按模运算 若任意一个多项式F(x)被一个n次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即则在按模N(x)运算下，有这时，码多项式系数仍按模2运算。例1：x3被(x3+1)除，得到余项1，即 例2：因为 xx3+1 x4+x2+1 x4+x x2+x+1 在模2运算中加法和减法一样。,在循环码中，设T(x)是一个长度为
12、n的码组，若则T(x)也是该编码中的一个码组。证 设一循环码为 则有 上式中的T(x)正是码组T(x)向左循环移位 i 次的结果。例：一循环码为1100101，即 若给定 i=3，则有 上式对应的码组为0101110，它正是T(x)向左移3位的结果。结论：一个长为n的循环码必定为按模(xn+1)运算的一个余式。,循环码的生成 有了生成矩阵G，就可以由k个信息位得出整个码组：例：式中，生成矩阵G的每一行都是一个码组。因此，若能找到 k 个已知的码组，就能构成矩阵G。如前所述，这k个已知码组必须是线性不相关的。在循环码中，一个(n,k)码有2k个不同的码组。若用g(x)表示其中前(k-1)位皆为“
13、0”的码组，则g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是码组，而且这k个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵G。,在循环码中除全“0”码组外，再没有连续k位均为“0”的码组。否则，在经过若干次循环移位后将得到k位信息位全为“0”，但监督位不全为“0”的一个码组。这在线性码中显然是不可能的。因此，g(x)必须是一个常数项不为“0”的(n-k)次多项式，而且这个g(x)还是这种(n,k)码中次数为(n k)的唯一一个多项式。因为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码组多项式的次数将小于(n k)，即连续“0”的个数多于(k 1)。显
14、然，这是与前面的结论矛盾的。称这唯一的(n k)次多项式g(x)为码的生成多项式。一旦确定了g(x)，则整个(n,k)循环码就被确定了。,因此，循环码的生成矩阵G可以写成例：上表中的编码为(7,3)循环码，n=7,k=3,n k=4，其中唯一的一个(n k)=4次码多项式代表的码组是第二码组0010111，与它对应的码多项式，即生成多项式，为g(x)=x4+x2+x+1。,g(x)=x4+x2+x+1 即“1 0 1 1 1”将此g(x)代入上矩阵，得到 或上式不符合G=IkQ形式，所以它不是典型生成矩阵。但它经过线性变换后，不难化成典型阵。此循环码组的多项式表示式T(x)：上式表明，所有码多
15、项式T(x)都能够被g(x)整除，而且任意一个次数不大于(k 1)的多项式乘g(x)都是码多项式。,寻求码生成多项式 因为任意一个循环码T(x)都是g(x)的倍式，故它可以写成T(x)=h(x)g(x)而生成多项式g(x)本身也是一个码组，即有 T(x)=g(x)由于码组T(x)是一个(n k)次多项式，故xk T(x)是一个n次多项式。由可知，xk T(x)在模(xn+1)运算下也是一个码组，所以有上式左端分子和分母都是n次多项式，故相除的商式Q(x)=1。因此，上式可以写成,将 T(x)=h(x)g(x)和 T(x)=g(x)代入化简后，得到上式表明，生成多项式g(x)应该是(xn+1)的
16、一个因子。例：(x7+1)可以分解为为了求出(7,3)循环码的生成多项式 g(x)，需要从上式中找到一个(n k)=4次的因子。这样的因子有两个，即以上两式都可以作为生成多项式。选用的生成多项式不同，产生出的循环码码组也不同。,循环码的编码方法用xn-k乘m(x)。这一运算实际上是在信息码后附加上(n k)个“0”。例如，信息码为110，它写成多项式为m(x)=x2+x。当n k=7 3=4时，xn-k m(x)=x4(x2+x)=x6+x5，它表示码组1100000。用g(x)除xn-k m(x)，得到商Q(x)和余式r(x)，即有例：若选定g(x)=x4+x2+x+1，则有 上式是用码多项
17、式表示的运算。它和下式等效：编出的码组T(x)为：T(x)=xn-k m(x)+r(x)在上例中，T(x)=1100000+101=1100101,循环码的解码方法在检错时：当接收码组没有错码时，接收码组R(x)必定能被g(x)整除，即下式中余项r(x)应为零；否则，有误码。当接收码组中的错码数量过多，超出了编码的检错能力时，有错码的接收码组也可能被g(x)整除。这时，错码就不能检出了。在纠错时：用生成多项式g(x)除接收码组R(x)，得出余式r(x)。按照余式r(x)，用查表的方法或计算方法得出错误图样E(x)。从R(x)中减去E(x)，便得到已经纠正错码的原发送码组T(x)。,截短循环码截
18、短目的：在设计时，通常信息位数k、码长n和纠错能力都是预先给定的。但是，并不一定有恰好满足这些条件的循环码存在。故采用截短码长截短，得出满足要求的编码。截短方法：设给定一个(n,k)循环码，它共有2k种码组，现使其前i(0 i k)个信息位全为“0”，于是它变成仅有2k-i种码组。然后从中删去这 i 位全“0”的信息位，最终得到一个(n i，k i)的线性码。将这种码称为截短循环码。截短循环码与截短前的循环码至少具有相同的纠错能力，并且截短循环码的编解码方法仍和截短前的方法一样。例：要求构造一个能够纠正1位错码的(13,9)码。这时可以由(15,11)循环码的11种码组中选出前两信息位均为“0”的码组，构成一个新的码组集合。然后在发送时不发送这两位“0”。于是发送码组成为(13,9)截短循环码。,卷积码卷积码的特点：监督码元不仅和当前的k比特信息段有关，而且还同前面m=(N 1)个信息段有关。将N称为码组的约束长度。将卷积码记作(n,k,m)，其码率为k/n。,m序列,m序列是最长线性反馈移位寄存器序列的简称,n级线性反馈移位寄存器,特征多项式,扰码与解扰,例8-5 设m序列发生器的本原多项式为：，由该m序列发生器构成的扰码和解扰器。1、画出扰码器和解扰器的方框图 2、若输入信号为“11101001010”，求扰码器的输出序列。,
