第21讲 差错控制技术精.ppt

《第21讲 差错控制技术精.ppt》由会员分享，可在线阅读，更多相关《第21讲 差错控制技术精.ppt（46页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第21讲讲 差错控制技差错控制技术术第1页，本讲稿共46页自动请求重发自动请求重发v优点：译码设备简单，对突发错误和信道干扰较严重时比较有效。v缺点：需要反馈信道，实时性差。第2页，本讲稿共46页第3页，本讲稿共46页前向纠错前向纠错v优点：使用纠错码和单向信道，发送端无需设置缓冲器。v缺点：设备复杂、成本高。第4页，本讲稿共46页混合纠错混合纠错v特点：实时性和译码复杂性方面是前向纠错和检错重发方式的折衷，可达到较低的误码率，较适合于环路延迟大的高速数据传输系统。第5页，本讲稿共46页反馈校验反馈校验v优点：设备简单，可以纠正任何错误v缺点：会引入较大的时延。第6页，本讲稿共46页纠错编码

2、纠错编码通过通过对信息序列作某种变换对信息序列作某种变换，使原来彼此独立、互不相关的，使原来彼此独立、互不相关的信息码元信息码元产生某种规律性产生某种规律性（相关性），从而在接收端根（相关性），从而在接收端根据这种规律性来检查，进而纠正传输信号序列中的差错。据这种规律性来检查，进而纠正传输信号序列中的差错。纠错编码基本原理纠错编码基本原理变换的方法不同就构成了不同的编码。变换的方法不同就构成了不同的编码。第7页，本讲稿共46页引入差错编码控制后，实际传输的引入差错编码控制后，实际传输的 信息序列信息序列=信息码元信息码元+监督码元监督码元，称为码组。，称为码组。监督码（元）监督码（元）：为了使

3、信息码：为了使信息码元产生某种规律性，可按照元产生某种规律性，可按照某种规则在用户信息序列中某种规则在用户信息序列中插入一定数量的新码元插入一定数量的新码元，这种，这种新码元叫监督码（元）。新码元叫监督码（元）。信息码（元）信息码（元）：发送用户端：发送用户端欲发送的信息序列欲发送的信息序列，本来彼，本来彼此独立，互不相关；由用户此独立，互不相关；由用户控制，最终也交给接收用户。控制，最终也交给接收用户。差错控制编码的基本原理就是差错控制编码的基本原理就是：在保持信息位数不变（信在保持信息位数不变（信息码元）情况下，采用增加码长的方法来降低误码率。息码元）情况下，采用增加码长的方法来降低误码率

4、。第8页，本讲稿共46页例：传输例：传输A和和B两个消息。两个消息。用用一位二进制数一位二进制数表示：表示：“0”A；“1”B传输过程中出现错码，接收端无法发现，无检错和纠错能传输过程中出现错码，接收端无法发现，无检错和纠错能力。力。用用两位二进制数两位二进制数“00”A“11”B 称为称为许用码组许用码组“01”和和“10”未定义，为未定义，为禁用码组禁用码组。S：00 D：00 01 10 S:11 D：11 表示表示附加一位监督码附加一位监督码以后码组具有了以后码组具有了检测检测1位错码位错码，但因译码器不，但因译码器不能判别哪位是错码，能判别哪位是错码，不不具备纠正错码的能力；具备纠正

5、错码的能力；且无法检测错且无法检测错2位错码位错码。第9页，本讲稿共46页 用用三位二进制数三位二进制数“000”A“111”B 称为许用码组称为许用码组“001”、“010”、“011”、“100”“101”、“110”皆是禁用码组皆是禁用码组S：000 D：000 001010011100101110111表明附加两个监督码元以后码表明附加两个监督码元以后码组具备检测组具备检测1位和位和2位错码的位错码的能力；并且具备纠正一位错能力；并且具备纠正一位错码的能力，即码的能力，即3位码组中有位码组中有2个或个或3个个“0”/“1”码，则判为码，则判为“000”/“111”。但。但无法纠正两位无

6、法纠正两位出错和检测出错和检测3位出错的能力位出错的能力。总结：（信息码总结：（信息码+监督码监督码=码组）构成的信息序列通过降低信息码组）构成的信息序列通过降低信息传输速率来提高传输的可靠性（降低误码率）。传输速率来提高传输的可靠性（降低误码率）。第10页，本讲稿共46页11v分组码分组码 信息位信息位 监督位监督位v分组码符号：分组码符号：(n,k)其中，其中，n 码组总长度，码组总长度，k 信息码元数目。信息码元数目。r=n k 监督码元数目。监督码元数目。v分组码的一般结构：分组码的一般结构：v分组码的参数：分组码的参数：码重：码组内码重：码组内“1”的个数的个数码距：两码组中对应位取

7、值不同的位数，又称汉明距离码距：两码组中对应位取值不同的位数，又称汉明距离 最小码距最小码距(d0)：各码组间的最小距离：各码组间的最小距离k个信息位r个监督位an-1an-2.arar-1an-2.a0t码长 n=k+r分组码的结构纠错能力与码距关系纠错能力与码距关系第11页，本讲稿共46页v码距的几何意义：以n=3的编码为例 v一般而言，码距是 n 维空间中单位正多面体顶点之间的汉明距离。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a1第12页，本讲稿共46页v为了检测e个随机错误，则要求码组的最小距离距为 第13

8、页，本讲稿共46页v为了纠正t个随机错误，则要求码组的最小距离为第14页，本讲稿共46页v纠正t个随机错码，同时检测e个随机错误，则要求码组的最小距离为(e t)第15页，本讲稿共46页常用的简单编码v奇偶校验码奇偶校验码:增加一位监督码来使得码组中增加一位监督码来使得码组中“1”的个数保持奇数的个数保持奇数（奇校验）或偶数（偶校验）。分为：垂直奇偶校验；水平奇偶校（奇校验）或偶数（偶校验）。分为：垂直奇偶校验；水平奇偶校验；水平垂直奇偶校验。验；水平垂直奇偶校验。v群计数码群计数码：监督码元附加在信息码元之后，每一个监督码元在数值监督码元附加在信息码元之后，每一个监督码元在数值上表示其对应的

9、信息码元中上表示其对应的信息码元中“1”的个数。的个数。第16页，本讲稿共46页v恒比码恒比码：每个码组中均包含相同数目的：每个码组中均包含相同数目的“1”和和“0”，即数目，即数目之比是一定的，所以也叫定比码。之比是一定的，所以也叫定比码。v正反码：正反码：监督码元与信息码元位数相同，但根据信息码元中监督码元与信息码元位数相同，但根据信息码元中“1”的数目不同，监督码元与信息码元完全相同或相反。的数目不同，监督码元与信息码元完全相同或相反。第17页，本讲稿共46页v代数码代数码 利用代数关系式产生监督位的编码利用代数关系式产生监督位的编码v线性分组码线性分组码 代数码的一种，其监督位和信息位

10、的代数码的一种，其监督位和信息位的关系由线性代数方程决定关系由线性代数方程决定v汉明码汉明码 一种能够纠正一个错码的线性分组码一种能够纠正一个错码的线性分组码v校正子：校正子：在偶数监督码中，计算在偶数监督码中，计算实际上就是计算实际上就是计算并检验并检验S是否等于是否等于0。S称为校正子称为校正子v监督关系式：监督关系式：线性分组码第18页，本讲稿共46页纠错基本原理v 中，S只有两种取值，故只能表示有错和无错，而不能进一步指明错码的位置。v若此码组长度增加一位，则能增加一个监督关系式。这样，就能得到两个校正子。两个校正子的可能取值有4种组合，即00，01，10，11，故能表示4种不同的信息

11、。若用其中一种组合表示无错码，则还有其他3种组合可以用于指明一个错码的3种不同位置。从而可以有纠错能力。v一般而言，若有 r 个监督关系式，则 r 个校正子可以指明一个错码的(2r 1)个不同位置。v当校正子可以指明的错码位置数目等于或大于码组长度n时，才能够纠正码组中任何一个位置上的错码，即要求第19页，本讲稿共46页汉明码v例：要求设计一个能够纠正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

12、=7个错码的位置。若规定校正子和错码位置的关系如下表，则仅当在a6 a5 a4 a2位置上有错码时，校正子S1的值才等于1；否则S1的值为零。这就意味着a6 a5 a4 a2四个码元构成偶数监督关系：同理，有第20页，本讲稿共46页21在编码时，信息位a6 a5 a4 a3的值决定于输入信号，它们是随机的。监督位a2 a1 a0是按监督关系确定的，应该保证上列3式中的校正子等于0，即有给定信息位后，为了计算监督位，上式可以改写为按照上式计算结果为第21页，本讲稿共46页22在接收端解码时，对于每个接收码组，先按式计算出校正子S1，S2和S3，然后按照表判断错码的位置。例：若接收码组为00000

13、11，则按上三式计算得到：S1=0，S2=1，S3=1。这样，由上表可知，错码位置在a3。第22页，本讲稿共46页上例中的汉明码是(7,4)码，其最小码距d0=3。由式可知，此码能够检测2个错码，或纠正1个错码。v汉明码的码率：当r(或n)很大时，上式趋近于1。所以汉明码是一种高效编码。第23页，本讲稿共46页分组码的一般原理v线性分组码的监督位和信息位的关系 可以改写为上式中，已经将“”简写成“+”。第24页，本讲稿共46页v监督矩阵上式可以写成矩阵形式：（模2）将上式简写为HAT=0T 或AHT=0第25页，本讲稿共46页26 HAT=0T 式中，称为监督矩阵 v监督矩阵的性质监督矩阵H确

14、定码组中的信息位和监督位的关系。H 的行数就是监督关系式的数目，即监督位数 r。H 的每行中“1”的位置表示相应的码元参与监督关系。H 可以分成两部分，例如 典型监督矩阵 式中，P 为r k阶矩阵，Ir为 r r 阶单位方阵。A=a6 a5 a4 a3 a2 a1 a0 0=000第26页，本讲稿共46页循环码循环码 循环性是指任一码组循环一位后仍然是该编码中的一个码组。例：一种(7,3)循环码的全部码组如下 表中第2码组向右移一位即得到第5码组；第5码组向右移一位即得到第7码组。第27页，本讲稿共46页28 若(an-1 an-2 a0)是循环码的一个码组，则循环移位后的码组：(an-2 a

15、n-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可以表示为 第28页，本讲稿共46页循环码的运算 整数的按模运算在整数运算中，有模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除得的余数。第2

16、9页，本讲稿共46页码多项式的按模运算 若任意一个多项式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运算中加法和减法一样。第30页，本讲稿共46页 在循环码中，设T(x)是一个长度为n的码组，若则T(x)也是该编码中的一个码组。证 设一循环码为 则有 上式中的T(x)正是码组T(x)向左循环移位 i 次的结果。例：一循环码为1100101，即 若给定 i=3，则有 上式对应的码组为0

17、101110，它正是T(x)向左移3位的结果。结论：一个长为n的循环码必定为按模(xn+1)运算的一个余式。第31页，本讲稿共46页循环码的生成循环码的生成 v有了生成矩阵G，就可以由k个信息位得出整个码组：例：式中，生成矩阵G的每一行都是一个码组。v因此，若能找到 k 个已知的码组，就能构成矩阵G。如前所述，这k个已知码组必须是线性不相关的。v在循环码中，一个(n,k)码有2k个不同的码组。若用g(x)表示其中前(k-1)位皆为“0”的码组，则g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是码组，而且这k个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵G。第32页，本

18、讲稿共46页v在循环码中除全在循环码中除全“0”码组外，再没有连续码组外，再没有连续k位均为位均为“0”的码组。否则，在经过若干次循环移位后将得到的码组。否则，在经过若干次循环移位后将得到k位信息位位信息位全为全为“0”，但监督位不全为，但监督位不全为“0”的一个码组。这在线性的一个码组。这在线性码中显然是不可能的。码中显然是不可能的。v因此，因此，g(x)必须是一个常数项不为必须是一个常数项不为“0”的的(n-k)次多项式，次多项式，而且这个而且这个g(x)还是这种还是这种(n,k)码中次数为码中次数为(n k)的唯一一个的唯一一个多项式。因为如果有两个，则由码的封闭性，把这两个相多项式。因

19、为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码组多项式的次数将小于加也应该是一个码组，且此码组多项式的次数将小于(n k)，即连续，即连续“0”的个数多于的个数多于(k 1)。显然，这是与前面的。显然，这是与前面的结论矛盾的。结论矛盾的。v称这唯一的称这唯一的(n k)次多项式次多项式g(x)为码的生成多项式。一旦为码的生成多项式。一旦确定了确定了g(x)，则整个，则整个(n,k)循环码就被确定了。循环码就被确定了。第33页，本讲稿共46页v因此，循环码的生成矩阵G可以写成v例：上表中的编码为(7,3)循环码，n=7,k=3,n k=4，其中唯一的一个(n k)=4次码多项

20、式代表的码组是第二码组0010111，与它对应的码多项式，即生成多项式，为g(x)=x4+x2+x+1。第34页，本讲稿共46页 g(x)=x4+x2+x+1 即 “1 0 1 1 1”将此g(x)代入上矩阵，得到 或上式不符合G=IkQ形式，所以它不是典型生成矩阵。但它经过线性变换后，不难化成典型阵。此循环码组的多项式表示式T(x)：上式表明，所有码多项式T(x)都能够被g(x)整除，而且任意一个次数不大于(k 1)的多项式乘g(x)都是码多项式。第35页，本讲稿共46页寻求码生成多项式 因为任意一个循环码T(x)都是g(x)的倍式，故它可以写成T(x)=h(x)g(x)而生成多项式g(x)

21、本身也是一个码组，即有 T(x)=g(x)由于码组T(x)是一个(n k)次多项式，故xk T(x)是一个n次多项式。由可知，xk T(x)在模(xn+1)运算下也是一个码组，所以有上式左端分子和分母都是n次多项式，故相除的商式Q(x)=1。因此，上式可以写成第36页，本讲稿共46页将 T(x)=h(x)g(x)和 T(x)=g(x)代入化简后，得到上式表明，生成多项式g(x)应该是(xn+1)的一个因子。例：(x7+1)可以分解为为了求出(7,3)循环码的生成多项式 g(x)，需要从上式中找到一个(n k)=4次的因子。这样的因子有两个，即以上两式都可以作为生成多项式。选用的生成多项式不同，

22、产生出的循环码码组也不同。第37页，本讲稿共46页 循环码的编码方法用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，则有 上式是用码多项式表示的运算。它和下式等效：编出的码组T(x)为：T(x)=xn-k m(x)+r(x)在上例中，T(x)=1100000+101=1100101 第38页，本讲稿共46页 循

23、环码的解码方法在检错时：当接收码组没有错码时，接收码组R(x)必定能被g(x)整除，即下式中余项r(x)应为零；否则，有误码。v当接收码组中的错码数量过多，超出了编码的检错能力时，有错码的接收码组也可能被g(x)整除。这时，错码就不能检出了。在纠错时：v用生成多项式g(x)除接收码组R(x)，得出余式r(x)。v按照余式r(x)，用查表的方法或计算方法得出错误图样E(x)。v从R(x)中减去E(x)，便得到已经纠正错码的原发送码组T(x)。第39页，本讲稿共46页截短循环码截短目的：在设计时，通常信息位数k、码长n和纠错能力都是预先给定的。但是，并不一定有恰好满足这些条件的循环码存在。故采用截

24、短码长截短，得出满足要求的编码。截短方法：设给定一个(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)截短循环码。第40页，本讲

25、稿共46页 卷积码卷积码的特点：v监督码元不仅和当前的k比特信息段有关，而且还同前面m=(N 1)个信息段有关。v将N称为码组的约束长度。v将卷积码记作(n,k,m)，其码率为k/n。第41页，本讲稿共46页m m序列序列vm序列是最长线性反馈移位寄存器序列的简序列是最长线性反馈移位寄存器序列的简称称第42页，本讲稿共46页第43页，本讲稿共46页n级线性反馈移位寄存器级线性反馈移位寄存器特征多项式第44页，本讲稿共46页扰码与解扰扰码与解扰第45页，本讲稿共46页v例例8-5 设设m序列发生器的本原多项式为：序列发生器的本原多项式为：，由该，由该m序列发生器序列发生器构成的扰码和解扰器。构成的扰码和解扰器。1、画出扰码器和解扰器的方框图、画出扰码器和解扰器的方框图 2、若输入信号为、若输入信号为“11101001010”，求扰码器的输出序列。，求扰码器的输出序列。第46页，本讲稿共46页