第21讲差错控制技术.ppt

《第21讲差错控制技术.ppt》由会员分享，可在线阅读，更多相关《第21讲差错控制技术.ppt（46页珍藏版）》请在优知文库上搜索。

1、差错控制的常用方法差错控制的常用方法v自动请求重发（自动请求重发（ARQ）停发等待重发停发等待重发 返回重发返回重发 选择重发选择重发v前向纠错（前向纠错（FEC）v混合纠错（混合纠错（HEC）v反馈检验（反馈检验（IRQ）自动请求重发自动请求重发应答信号 信息码 能够发现错误的码 信息码 发送端 接收端 接收数据 ACK ACK NAK ACK ACK NAK ACK 1 2 3 3 4 5 5 t 发送数据 1 2 3 3 4 5 5 6 t 有错码组 有错码组 v优点：译码设备简单，对突发错误和信道干扰较严重时比较有效。v缺点：需要反馈信道，实时性差。图8-3 返回重发ARQ系统 2 1

2、 4 3 6 5 7 9 8 接收数据 有错码组 有错码组 9 10 11 10 11 12 5 7 6 ACK1 NAK5 NAK9 ACK5 5 7 6 9 5 2 1 4 3 6 7 9 8 发送数据 10 11 10 11 12 重发码组 重发码组 图8-4 选择重发ARQ系统 9 接收数据 有错码组 有错码组 2 1 4 3 6 5 7 5 9 8 10 11 13 14 12 发送数据 9 9 5 8 5 2 1 4 3 6 7 10 11 13 14 12 重发码组 重发码组 NAK9 ACK1 NAK5 ACK5 ACK9 前向纠错前向纠错v优点：使用纠错码和单向信道，发送端无

3、需设置缓冲器。v缺点：设备复杂、成本高。混合纠错混合纠错v特点：实时性和译码复杂性方面是前向纠错和检错重发方式的折衷，可达到较低的误码率，较适合于环路延迟大的高速数据传输系统。应答信号 信息码 能够发现并纠正错误的码 信息码 发送端 接收端 图 8-6 混合纠错 HEC 示意图 反馈校验反馈校验v优点：设备简单，可以纠正任何错误v缺点：会引入较大的时延。原码返回，在发送端比较 信息码 发送信息码 信息码 发送端 接收端 图 8-7 反馈检测 IRQ 示意图 纠错编码纠错编码通过通过对信息序列作某种变换对信息序列作某种变换，使原来彼此独立、互不，使原来彼此独立、互不相关的信息码元相关的信息码元产

4、生某种规律性产生某种规律性（相关性），从而在（相关性），从而在接收端根据这种规律性来检查，进而纠正传输信号序接收端根据这种规律性来检查，进而纠正传输信号序列中的差错。列中的差错。纠错编码基本原理纠错编码基本原理变换的方法不同就构成了不同的编码。变换的方法不同就构成了不同的编码。引入差错编码控制后，实际传输的引入差错编码控制后，实际传输的 信息序列信息序列=信息码元信息码元+监督码元监督码元，称为码组。，称为码组。监督码（元）监督码（元）：为了使信：为了使信息码元产生某种规律性，息码元产生某种规律性，可按照某种规则在用户信可按照某种规则在用户信息序列中息序列中插入一定数量的插入一定数量的新码元新

5、码元，这种新码元叫监，这种新码元叫监督码（元）。督码（元）。信息码（元）信息码（元）：发送用：发送用户端户端欲发送的信息序列欲发送的信息序列，本来彼此独立，互不相本来彼此独立，互不相关；由用户控制，最终关；由用户控制，最终也交给接收用户。也交给接收用户。差错控制编码的基本原理就是差错控制编码的基本原理就是：在保持信息位数在保持信息位数不变（信息码元）情况下，采用增加码长的方法来不变（信息码元）情况下，采用增加码长的方法来降低误码率。降低误码率。例：传输例：传输A和和B两个消息。两个消息。用用一位二进制数一位二进制数表示：表示：“0”A；“1”B传输过程中出现错码，接收端无法发现，无检错和传输过

6、程中出现错码，接收端无法发现，无检错和纠错能力。纠错能力。用用两位二进制数两位二进制数“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”

7、“101”、“110”皆是禁用码组皆是禁用码组S：000 D：000 001010011100101110111表明附加两个监督码元以表明附加两个监督码元以后码组具备检测后码组具备检测1位和位和2位位错码的能力；并且具备纠错码的能力；并且具备纠正一位错码的能力，即正一位错码的能力，即3位位码组中有码组中有2个或个或3个个“0”/“1”码，则判为码，则判为“000”/“111”。但但无法纠正两位出错和检无法纠正两位出错和检测测3位出错的能力位出错的能力。总结：（信息码总结：（信息码+监督码监督码=码组）构成的信息序列通过降低码组）构成的信息序列通过降低信息传输速率来提高传输的可靠性（降低误码率）

8、。信息传输速率来提高传输的可靠性（降低误码率）。11v分组码分组码 信息位信息位 监督位监督位v分组码符号：分组码符号：(n,k)其中，其中，n 码组总长度，码组总长度，k 信息码元数目。信息码元数目。r=n k 监督码元数目。监督码元数目。v分组码的一般结构：分组码的一般结构：v分组码的参数：分组码的参数：码重：码组内码重：码组内“1”的个数的个数码距：两码组中对应位取值不同的位数，又称汉明距离码距：两码组中对应位取值不同的位数，又称汉明距离 最小码距最小码距(d0)：各码组间的最小距离：各码组间的最小距离k个信息位个信息位r个监督位个监督位an-1an-2.arar-1an-2.a0t码长

9、码长 n=k+r分组码的结构分组码的结构纠错能力与码距关系纠错能力与码距关系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)a2a0a1v为了检测e个随机错误，则要求码组的最小距离距为 01dev为了纠正t个随机错误，则要求码组的最小距离为021dt B t A 汉明距离 0 1 2 3 4 5 t d0 8-10 码距等于5的两个码组 v纠正t个随机错码，同时检测e个随机错误，则要求码组的最小距离为01dte(e t)A B 1

10、 t t 汉明距离 e 图8-11 码距等于(e+t+1)的两个码组 常用的简单编码常用的简单编码v奇偶校验码奇偶校验码:增加一位监督码来使得码组中增加一位监督码来使得码组中“1”的个数的个数保持奇数（奇校验）或偶数（偶校验）。分为：垂直奇保持奇数（奇校验）或偶数（偶校验）。分为：垂直奇偶校验；水平奇偶校验；水平垂直奇偶校验。偶校验；水平奇偶校验；水平垂直奇偶校验。v群计数码群计数码：监督码元附加在信息码元之后，每一个监督监督码元附加在信息码元之后，每一个监督码元在数值上表示其对应的信息码元中码元在数值上表示其对应的信息码元中“1”的个数。的个数。v恒比码恒比码：每个码组中均包含相同数目的：每

11、个码组中均包含相同数目的“1”和和“0”，即，即数目之比是一定的，所以也叫定比码。数目之比是一定的，所以也叫定比码。v正反码：正反码：监督码元与信息码元位数相同，但根据信息码监督码元与信息码元位数相同，但根据信息码元中元中“1”的数目不同，监督码元与信息码元完全相同或的数目不同，监督码元与信息码元完全相同或相反。相反。代数码代数码 利用代数关系式产生监督位的编码利用代数关系式产生监督位的编码 线性分组码线性分组码 代数码的一种，其监督位和信息位的代数码的一种，其监督位和信息位的关系由线性代数方程决定关系由线性代数方程决定 汉明码汉明码 一种能够纠正一个错码的线性分组码一种能够纠正一个错码的线性

12、分组码 校正子：校正子：在偶数监督码中，计算在偶数监督码中，计算实际上就是计算实际上就是计算并检验并检验S是否等于是否等于0。S称为校正子称为校正子 监督关系式：监督关系式：1200nnaaa120nnSaaa120nnSaaa线性分组码线性分组码纠错基本原理v 中，S只有两种取值，故只能表示有错和无错，而不能进一步指明错码的位置。v若此码组长度增加一位，则能增加一个监督关系式。这样，就能得到两个校正子。两个校正子的可能取值有4种组合，即00，01，10，11，故能表示4种不同的信息。若用其中一种组合表示无错码，则还有其他3种组合可以用于指明一个错码的3种不同位置。从而可以有纠错能力。v一般而

13、言，若有 r 个监督关系式，则 r 个校正子可以指明一个错码的(2r 1)个不同位置。v当校正子可以指明的错码位置数目等于或大于码组长度n时，才能够纠正码组中任何一个位置上的错码，即要求021aaaSnn1212rknrr或汉明码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=7个错码的位置。若规定校正子和错码位置的关系如下表，则仅当在a6 a5 a4 a2位置上有错码时

14、，校正子S1的值才等于1；否则S1的值为零。这就意味着a6 a5 a4 a2四个码元构成偶数监督关系：同理，有1212rknrr或24561aaaaS13562aaaaS03463aaaaS21在编码时，信息位a6 a5 a4 a3的值决定于输入信号，它们是随机的。监督位a2 a1 a0是按监督关系确定的，应该保证上列3式中的校正子等于0，即有给定信息位后，为了计算监督位，上式可以改写为按照上式计算结果为000034613562456aaaaaaaaaaaa346035614562aaaaaaaaaaaa22在接收端解码时，对于每个接收码组，先按式计算出校正子S1，S2和S3，然后按照表判断错

15、码的位置。例：若接收码组为0000011，则按上三式计算得到：S1=0，S2=1，S3=1。这样，由上表可知，错码位置在a3。24561aaaaS13562aaaaS03463aaaaS上例中的汉明码是(7,4)码，其最小码距d0=3。由式可知，此码能够检测2个错码，或纠正1个错码。v汉明码的码率：当r(或n)很大时，上式趋近于1。所以汉明码是一种高效编码。10 ed120 td1212rrrnk分组码的一般原理v线性分组码的监督位和信息位的关系 可以改写为上式中，已经将“”简写成“+”。000034613562456aaaaaaaaaaaa01001101001010110001011101

16、2345601234560123456aaaaaaaaaaaaaaaaaaaaav监督矩阵上式可以写成矩阵形式：（模2）将上式简写为HAT=0T 或AHT=0010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa0001011001110101011101000123456aaaaaaa26 HAT=0T 式中，称为监督矩阵 v监督矩阵的性质监督矩阵H确定码组中的信息位和监督位的关系。H 的行数就是监督关系式的数目，即监督位数 r。H 的每行中“1”的位置表示相应的码元参与监督关系。H 可以分成两部分，例如 典型监督矩阵 式中，P 为r k阶矩阵，Ir为 r r 阶单位方阵。101100111010101110100HrPIH001101101011011001110A=a6 a5 a4 a3 a2 a1 a0 0=000循环码循环码 循环性是指任一码组循环一位后仍然是该编码中的一个码组。例：一种(7,3)循环码的全部码组如下 表中第2码组向右移一位即得到第5码组；第5码组向右移一位即得到第7码组。28 若(