差错控制编码.ppt_第1页
差错控制编码.ppt_第2页
差错控制编码.ppt_第3页
差错控制编码.ppt_第4页
差错控制编码.ppt_第5页
已阅读5页,还剩43页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、第八章 差错控制编码,2020年7月30日,2,8.1 差错控制编码的基本概念,数字通信中,根据不同的目的,编码可分为信源编码和信道编码。 信源编码是为了提高数字通信的有效性,以及为了使模拟信号数字化而采取的编码。 信道编码是为了降低误码率,提高数字通信的可靠性而采取的编码。 数字信号在传输的过程中,加性噪声、码间串扰等都会产生误码。为了提高系统的抗干扰性能,可以加大发射功率,降低接收设备本身的噪声,以及合理选择调制、解调方法等。此外,还可以采用信道编码技术。,2020年7月30日,3,差错控制编码的基本思想:,在发送端根据要传输的数字序列(信息码元)按一定的规律加入多余码元,使原来不相关的数

2、字序列变为相关,然后把这些多余码元和有关的信息码元一起传送,接收端根据信息码元与多余码元之间的相关规则进行检验,从而发现错误。这时,或者通过反馈信道要求对方重发有错的信息,以进行纠错;或者由接收端的译码器自动把错误纠正。 这些多余码元称为校验元或监督元。它的加入不改变信息本身,也就是说,它不传送新的信息,它的作用只是使信道译码器能够检测和纠正差错,从而控制系统差错概率,提高可靠性但这是以系统的有效性为代价的。,2020年7月30日,4,8.1.1 差错控制方式,2020年7月30日,5,前向纠错方式,前向纠错方式记作FEC(Forword Error Correction) 发端编码器将数字信

3、息按一定规则附加多余码元,组成有纠错能力的码,发端发送能够纠正错误的码;收端译码器按预先规定的规则译码;若发现错误,确定其出错位置并进行纠正。 优点: 单向传输,只有正向信道;适合于只能提供单向信道的场合;一点发送多点接收的同播方式;译码延迟固定,适用于实时传输系统。 缺点: 编译码设备复杂,为了纠正较多的错误,需要附加的多余码元较多,因而传输效率较低。,2020年7月30日,6,检错重发方式,又称自动请求重传方式,记作ARQ(Automatic Repeat Request)。 发端编码器将数字信息按一定规则附加多余码元,使之具有一定的检错能力,收端译码器按一定规则对数据码元组进行错误判决,

4、并把判决结果形成应答信号,通过反馈信道回送到发端,发端根据收到的应答信号,把收端认为有错的那组数据码元再次重传,直到码元组无错为止。 优点: 只需要少量的多余码元就能获得极低的输出误码率,并且其成本和复杂性均比前向纠错低缺点。 缺点: 必须提供反向信道;不能进行同播(一点发多点收),收发端应有缓冲存储器和控制器;此外当信道干扰较大时,整个系统可能处在重传循环中,因而通信效率降低,信息传输连贯性差,不适于实时传输系统,主要在计算机通信中应用。 常用的检错重发系统有三种,即停发等候重发、返回重发和选择重发。,2020年7月30日,8,混合纠错方式,混合纠错方式记作HEC(Hybrid Error

5、Correction) 发端发送具有自动纠错同时又具有检错能力的码。收端收到码后,检查差错情况,如果错误在码的纠错能力范围以内,则自动纠错,如果超过了码的纠错能力但能检测出来,则经过反馈信道请求发端重发。 这种方式具有自动纠错和检错重发的优点,可达到较低的误码率,因此,近年来得到广泛应用。 在实际通信系统中,选择那种差错控制方式,要视具体情况而定,可以根据信源的性质,信息传输的特点信道干扰的种类和对误码率的要求而适当选择差错控制方式。,2020年7月30日,9,8.1.2 差错控制编码的分类,根据信息元和监督元的函数关系,可分为线性码和非线性码。如果函数关系是线性的,即满足一组线性方程式,则称

6、为线性码,否则为非线性码。 根据上述关系涉及的范围,可分为分组码和卷积码。分组码的各码元仅与本组的信息元有关;卷积码中的码元不仅与本组的信息元有关,而且还与前面若干组的信息元有关。 根据码的用途,可分为检错码和纠错码。检错码以检错为目的,不一定能纠错;而纠错码以纠错为目的,一定能检错。,2020年7月30日,10,8.1.3 几种简单的检错码(1),奇偶监督码,设码字A=an-1,an-2,a1,a0,对偶监督码有: an-1 an-2 a1 a0 = 0,奇监督码情况相似, 只是码组中“1”的数目为奇数, 即 满足条件: an-1 an-2 a1 a0 = 1,而检错能力与偶监督码相同。,2

7、020年7月30日,11,奇偶监督码,编码方法:把信息码元分组,在每组信息码元 的后面附加一位监督码元,使得 码组中1的数目为奇数或偶数即可 编码规则:码组长度n;信息位n-1 特点:是一种能发现奇数个差错的分组码;n 较大,即编码码组较长时,编码效率 接近于1;(n-1)/n 信息码元比 码组码元 适用于检测随机的零星错码加性白噪声造 成的,2020年7月30日,12,8.1.3 几种简单的检错码(2),二维奇偶监督码,(6,11)行列监督码,2020年7月30日,13,二维奇偶监督码,编码方法:把码元排成方阵,按行列进行奇偶校验 分别附加一位监督码元 特点:不仅可检测每行(每列)中奇数个错

8、误,而且 可通过水平监督和垂直监督来确定错码的位置 纠正仅一行(一列)出现的奇数个错误 通过水平监督和垂直监督的关系可以发现单行中出现 的偶数个错误;但不能发现构成矩形的4个错误码元 适用于突发差错由突发干扰(突发脉冲,如: 闪电,电火花等)在短时间内错码成串出现,在某 一行中出现多个错码,2020年7月30日,14,8.1.3 几种简单的检错码(3),重复码 在每位信息码元之后,用简单重复多次的方法编码。 例:重复两次时,用111传输1码,用000传输0码 编码方法:每位信息码元简单重复多次; 收端 译码采用多数表决法; 例:重复2次 特点:纠正1个错,检出2个错,2020年7月30日,15

9、,8.1.3 几种简单的检错码(4),恒比码,码字中 1 的数目与 0 的数目保持恒定比例的码称为恒比码。 这种码在检测时,只要计算接收码元中 1 的数目是否正确, 就知道有无错误。,2020年7月30日,16,恒比码,例:5中取3恒比码用于电报电码 每个码组长度为5,共有25=32种不同的码组, 其中有3个1的码组为可用码组,共有10种 表示10个阿拉伯数字,用它拼成汉字(每4阿拉 伯数字组成1个汉字电码);其余的22个为禁用 码组。 特点:简单;除了1错为0与0错为1成对出现(对换 性)差错不能检测外,其它任何奇数个或偶数 个错码都可以被检测出来。 只适用于传输种类较少且有固定代码的字符,

10、而不适用于表示由信源来的二进制随机,数字序列。,2020年7月30日,17,8.1.3 几种简单的检错码(4),ISBN国际统一图书编号 例 ISBN 0471029777,2020年7月30日,18,8.1.4 检错和纠错的基本原理,如用三位二进制编码来代表八个字母 000 A100E 001 B101F 010C110G 011D111H 不管哪一位发生错误,都会使传输字母错误 如用三位字母传四个字母 000 A011B101 C110D 发生一位错误,准用码字将变成禁用码字,接收端就能知道出错,但是不能纠错。 如果进一步将许用码组限制为两种 000 A 111 B,检错和纠错能力是用信息

11、量的冗余度来换取的。,2020年7月30日,19,检错和纠错的基本原理,检错和纠错能力是用信息量的冗余度换取的与码组之间的差别有关;不同的编码方法和形式,检错和纠错能力不同。 例: n = 3,共有8种组合,都用于传输消息,在传输过程中若发生一个误码,则一种码组就会错误地变成另一种码组,但接收端却不能发现错误,因为任何一个码组都是许用码组。,在差错控制编码中,定义码组中非零码元的数目为码字的汉明(Hamming)重量, 简称码重。例如,码字 10110,码重w=3。 定义两个等长码组之间相应位取值不同的数目为这两个码组的汉明(Hamming)距离, 简称码距。例如 11000 与 10011之

12、间的距离d=3。 码组集中任意两个码字之间距离的最小值称为码的最小距离,用dmin表示。最小码距是码的一个重要参数, 它是衡量码检错、纠错能力的依据。,2020年7月30日,21,最小码距与检错纠错能力的关系,码组内的距离反映了码组之间的差别,最小距离越大,说明两个码组间的最小差别越大,或者说其中一个码组错为另一个码组的可能性就越小,那么其检错和纠错能力也就越强,因此可以说最小码距是衡量一种纠错编码的检错,纠错能力大小的标准。,码的最小距离直接关系着码的检错和纠错能力;任一(n,k)分组码,若要在码字内: (1) 检测e个随机错误,则要求码的最小距离dmine+1; (2) 纠正t个随机错误,

13、 则要求码的最小距离dmin2t+1; (3) 纠正t个同时检测e(t)个随机错误,则要求码的最小距离dmint+e+1。,t,1,e,A,B,2020年7月30日,23,用差错控制编码提高通信系统的可靠性, 是以降低有效性为代价换来的。我们定义编码效率R来衡量有效性: Rc=k/n 其中, k是信息元的个数,n为码长。 对纠错码的基本要求是: 检错和纠错能力尽量强; 编码效率尽量高;编码规律尽量简单。实际中要根据具体指标要求,保证有一定纠、检错能力和编码效率,并且易于实现。,编码效率,2020年7月30日,24,8.2 线性分组码,线性分组码的构成 将信息序列划分为等长(k位)的序列段 共有

14、2k个不同的序列段,在每一信息 段之后,附加m位监督元,构成长度 n = k + m的分组码(n ,k) 监督元与信息码元为线性关系,2020年7月30日,25,例,信息元长度k = 3共有2k = 8个不同的信息组 每组信息组加4个监督元,构成一个长度为7 的(7,3)线性分组码。 设: 每组信息元为C1C2C3监督元为C4 C5 C6C7 根据下列线性方程组求监督元 C4 = C1 + C3 C5 = C1 + C2 + C3 C6 = C1 + C2 C7 = C2 + C3,2020年7月30日,26,例,(7,3)码有8个信息组,信息组按上方程组求得每个 信息组的4个监督元,得到(7

15、,3)码的所有8个码字 信息组 码元 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 0 0 1 1 1 1 0 1 1 0 1 0 0 1 1 1 1 1 1 1 0 1 0 0 重要特性,线性码有封闭性,2020年7月30日,27,8.2 线性分组码,设分组码由n位码组构成,记为c1,c2,cn,信息码组由k位码组成,记为d1,d2,dk。则该分组码记为(n,k)码。 码组和信息码组可用行矩阵C和D表示 若为线性分组

16、码,C中的n个元素都是由D中的k个元素经线性组合形成的。可用一联立方程表示为,将码组C写成矩阵形式,矩阵G称为生成矩阵,它是一个kn的矩阵,2020年7月30日,29,生成矩阵G,2020年7月30日,30,生成矩阵G,Ik 单位矩阵,k行k列(k x k阶) P矩阵,k行m列(k x m阶) 编码前k位,编码后有n位,2n 2k; 选择P矩阵,可得到有较强检错纠错能力,实现 方法尽可能简单,编码效率又高的线性分组码 由于线性码具有封闭性,故任何二个码组之间的距离必须与某一个码组中“1”的个数相等,而码组中非零码元的数目“1”的个数为码组的重量(码重)所以线性码任意二个码字之间的距离必须等于码

17、中某一个码字的重量线性码最小码距正好等于非零码的最小码重 估算线性码的差错控制能力: 求最小码距最小码重,2020年7月30日,31,例,已知(6,3)码的生成距阵,求:编码码组,2020年7月30日,32,监督矩阵H,校验矩阵或监督矩阵 H: m x n 阶 PT: m行k列 k + m = n列,2020年7月30日,33,伴随式(校正子)S,设发送码组C=cn-1,cn-2,c1,c0,在传输过程中可能 发生误码。接收码组R =rn-1,rn-2,r1,r0,则收发码组之差定义为错误图样E, 也称为误差矢量, 即,E =RC =en-1,en-2,e1,e0,且,当ri=ci,当rici

18、,令 S = RHT,称为伴随式或校正子 S = RHT = CHT EHT = EHT S只与错误图形有关,与发送的码组C无关 HT :n x m 阶;E:1x n 阶;S:1x m 阶;S = s1 s2 sm ,解得误差矢量E,求得纠错后的码组 C = R E,2020年7月30日,34,检错与纠错,检错:当码组出现错误S为非零矢量 纠错: S = RHT = CHT EHT = EHT S与E之间有着确定的线性关系由H矩阵 确定(也就是与G(P)矩阵有关) S=s1 s2 sm 共有2m种不同的形式,除全 0外,可代表2m -1种有错误的图形 信息码组有2k个错误图形,有多种不同的形式

19、可能有2k种解答;为了选择正确的结果,要使用最大似然比准则,选择与R最相似的C(与R距离最小的码组E是1码最小的矢量)。,2020年7月30日,35,例:(6,3)码,2020年7月30日,36,S与E对照表,E S 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 1 1 1 (6,3)码具有纠1位错的能力 发生1个错误的情况: S是HT的第i行,说明R中第i位 产生了

20、错误,可以把它纠正 发生2个错误的情况: 除S=111对应第1,5位有错 其它的双错不能得到纠正 例: 接收码组R111011,2020年7月30日,37,查表法译码器的原理,S = RHT = CHT EHT = EHT 算出伴随式S与最小码重的差错 矢量E的对照表,提供译码使用,2020年7月30日,38,汉明码,按上述方法构造的能纠正单个错误的线性分组码称为 汉明码。 对于线性分组码,为了指示所有单错位置和无错的情况,必须满足不等式 汉明码具有以下特点: 汉明码的编码效率,2020年7月30日,39,汉明界,如果码组有纠t个差错的能力,则应能指出无错、单错到t个差错所有可能的情况,校验位

21、数m应满足不等式:,汉明界,是纠正t个差错的一个必要条件,2020年7月30日,40,8.3 循环码,特点 线性分组码 循环性任一许用码字经过循环移位后,得到的码组仍为一个许用码组 如 是循环码的一许用码组 则 也是一许用码组 移位i次得到 也是许用码组,2020年7月30日,41,8.3.1 循环码的特点及表达,码多项式表示 以此类推,码组C移位i次,相应的码多项式c(i)(x)是xic(x)除以(xn+1)后的余式。 在模(xn+1)意义下,若c(x)是码多项式,则xic(x)都是码多项式。,2020年7月30日,42,循环码的编码过程,一个k位的信息码组 可用信息多项式表示 假设码组多项

22、式可表示为,如果(n +1)是g()的倍式 C(1)()=d()g()+ aC1g() =d()+ aC1g()= d1()g() d1()对应某个信息码组,2020年7月30日,43,生成多项式g(),(n +1)是g()的倍式,且g()为n-k次多项式,所以对(n +1)进行因式分解,便可得到相应的g()。对(n +1)进行因式分解可由计算机完成,有表格给出。 由信息多项式求解码多项式 C() = d() g() n-1次 k-1次 n-k次,2020年7月30日,44,例,(7,4) n=7k=4 m=n-k=3 g()应为(7 + 1 )的3次因式 + 1 = (+ 1 ) ( + + 1 ) ( + + 1 ) g1() = ( + + 1 ) g2() = ( + + 1 ) D = 1010 d() = ( + ) C1() = d()g1() = ( + ) ( + + 1 ) = + + + C1 = 1001110

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论