1、第11章 差错控制编码,11.1引 言 11.2 纠错编码的基本原理 11.3 常用的简单编码 11.4 线性分组码 11.5循环码, 11.1 引言,设计数字通信系统时,应首先合理选择调制、解调方法及发送功率。若不满足要求,则考虑差错控制。 从差错控制角度看,信道可以分为三类:即随机信道、突发信道和混合信道。 随机信道在随机信道中、错码的出现是随机的,且错码之间是统计独立的。 突发信道错码是成串集中出现的。 混合信道存在随机和突发两种错码。,常用的差错控制方法有以下几种: 检错重发法接收端在收到的信码中检测出(发现)错码时,即设法通知发送端重发,直到正确收到为止。 前向纠错法接收端不仅能发现错码,还能够确定错码的位置,能够纠正它。 反馈校验法接收端将收到的信码原封不动地转发回发送端与原信码比较。若发现错误则发端重发。 三种差错控制方法可以结合使用。,接收端根据什么来识别有无错码由发送端的信道编码器在信息码元序列中增加一些监督码元。这些监督码和信码之间有确定的关系,使接收端可以利用这种关系由信道译码器来发现或纠正可能存在的错码。 在信息码元序列中加入监督码元就称为差错控制编码,有时也称
2、为纠错编码。 差错控制编码原则上是以降低信息传输速率为代价来换取传输可靠性的提高。,ARQ系统组成,ARQ优点:冗余码元少、对信道有自适应能力、成本和复杂性低; ARQ缺点:需要反向信道、重发控制较复杂、干扰大通信效率低、实时性差。,例:3位二进制数字构成的码组,共有8种不同的组合。若将其全部利用来表示天气,则可以表示8种不同的天气。 000(晴),001(多云),010(阴),011(雨),100(雪), 101(霜), 110(雾), 111(雹)。 任一码组在传输中若发生一个或多个措码则将变成另一信息码组。这时接收端将无法发现错误。, 11. 2 纠错编码的基本原理,若:,000=晴 001 =不可用 010 =不可用 011=云 100 =不可用 101=阴 110=雨 111 =不可用,则: 虽然只能传送4种不同的天气但是接收消却有可能发现码组中的一个错码。 例如,若000(晴)中错了一位,则接收码组将变成100或010或001,这三种码组都是不准许使用的,称为禁用码组,故接收端在收到禁用码组时,就认为发现了错码。,但是这种码不能发现两个措码,因为发生两个错码后产生的是许用码
3、组。 上述码只能检测错误,不能纠正错误。例如,当收到的码组为禁用码组100时,无法判断是哪一位码发生了错误因为晴、阴、雨三者错了一位都可以变成100。 要想能纠正错误,还要增加多余度。例如,苦规定许用码组只有两个:000(晴)、111(雨)、其余都是禁用码组。这时,接收场能检测两个以下错码,或能纠正一个错码。,分组码的一般概念。 为了传输4种不同的信息,用两位二进制码组就够了,它们是:00、01、10、11。代表所传信息的这些两位码,称为信息位。前面使用3位码,多出的一位称为监督位。 信息码分组,每组信码附加若干监督码的编码集合,称为分组码。 例如,分组码的结构,符号 (n,k)表示分组码 k信息码元数 n码组长度(码长) n-k监督码元数,码重、码距与码的纠检错能力,码重“1”的数量称为码组的重量 码距两个码组对应位上数字不同的位数称为码组的距离,简称码距。又称汉明(Hamming)距离。 最小码距某种编码中各个码组间距离的最小值称为最小码距(d0)。 若记: d0 最小码距; e检错位数; t纠错位数; 则有:,(1) e +1 d0,即码的检错能力e比最小码距d0小1位; (2)
4、2t+1 d0,即码的纠错能力t的2倍比最小码距d0小1位; (3) e +t+1 d0 ,即若码同时纠t个错并检出e个错误,则e +t比最小码距d0小1位。 以下说明:,(1) e +1 d0,(2) 2t +1 d0,(3) t +e+1 d0,差错控制编码的效用,假设:发送“0”的错误概率和发送“1”的错误概率相等,都等于P,且P1,则在码长为n的码组中恰好发生r个错码的概率为,例如,当码长n7时,p=10-3则有 P7(1) 7p= 710-3 ;P7(2) 21p2=2.110-5 ;,P7(3) 35p3=3.510-8。 可见,采用差错控制编码,即使仅能纠正(或检测)这种码组中12个错误,也可以使误码率下降几个数量级。这就表明,即使是较简单的差错控制编码也具有较大实际应用价值。, 11. 3 常用的简单编码,1奇偶监督码奇偶监督码包括奇数监督码和偶数监督码。只有一位监督位。 在偶监督码中,监督位使码组中“l”的个数为偶数,即满足下式条件 在奇监督码中,监督位使码组中“l”的个数为奇数,即满足下式条件,2二维奇偶监督码又称方阵码。每一行是奇偶监督码的一个码组,若干码组再按列
5、排列成矩阵,每列增加一位监督位。,二维奇偶监督码特点: 可检测偶数个错误 适于检测突发错码。 不仅可检错,还可纠一些错。 检错能力强。,3恒比码每个码组均含有相同数目的“1”(和“0”)。 应用:电传机传输汉字,每个汉字用4位阿拉伯数字表示。每个阿拉伯数字又用5位二进制符号构成的码组表示。每个码组的长度为5位,其中恒有3个1,称为5中取3恒比码。可能编成的不同码组数等于从5中取3组合数30。30种许用码组恰好可用来表示10个阿拉伯数字。,4正反码一种简单的能够纠正错码的编码。其中的监督位数与信息位数相同,监督码元与信息码元相同(是信息码的重复)或者相反(是信息码的反码)。 由信息码中“1”的个数而定。 解码方法:先将接收码组中信息位和监督值按位模2相加,产生校验码组。最后,观察校验码组中“1”的个数,按表93进行判决及纠正可能发现的错码。, 11. 4 线性分组码,从上节介绍的一些简单编码可以看出,每种编码所依据的原理各不相同,而且是大不相同,其中奇偶监督码的编码原理利用了代数关系式。我们把这类建立在代数学基础上的编码称为代数码。在代数码中,常见的是线性码。线性码中信息位和监督位是由一
6、些线性代数方程联系着的,或者说,线性码是按一组线性方程构成的。本节将以汉明(Hamming)码为例引入线性分组码的一般原理。,回顾奇偶监督码 在接收端解码时,实际上就是在计算 若S0,认为无错;若S1,认为有错。上式称为监督关系式,S称为校正子。S只有两种取值,只能代表有、无错两种信息,不能指出错码位置。如果监督位增加一位,则增加一个监督关系式。由于两个校正子的可能值有4种组合:00,01,10,11,故能表示4种不同状态。,若用其一种表示无错,则其余3种就可能用来指示一位错码的3种不同位置。同理r个监督关系式能指示一位错码的(2r-1)个可能位置。 一般地,若码长为n,信息位数为k,则监督位数r=n-k。如果希望用r个监督位构造出r个监督关系式来指示一位错码的n种可能位置,则要求 2r-1 n,或者 2r r+k+1,举例说明如何构造监督关系式: 设(n,k)分组码中r=4。为了纠正一位错码,要求监督拉数r 3。若取r=3,则n=k+r=7。校正子与错码位置的对应关系如表94规定(也可以另外规定) 。,由表可见,当一错码在a2,a4,a5或a6时校正子S为1;否则S为0即构成如下关系
7、 同理,在发送端编码时,信息位a6a5a4a3的值决定于稳入信号,因此它们是随机的。监督值a2a1ao应根据信息位的取值按监督关系来确定即监督位应使上三式中的值为零(表示编成的码组中应无错码),由此得到方程组,由此解出,给定信息位后,可直接按上式算出监督位,其结果如表95所列。,接收端收到每个码组后,先按监督方程计算出S1、S2、 S3 ,再按表94判断错码情况。例,接收0000011,可得: S1S2S3=011 。由表94可知在a3位有错码。 (7,4)汉明码: 最小码距d0=3 纠一个错码或检测两个错码。 编码效率k/n=(2r-1-r)(2r-1)=I-rn。当n很大时,则编码效率接近1。,线性分组码的般原理。线性分组码是指信息位和监督位满足一组线性方程的编码。 改写为,(模2),简记为 或,称为监督矩阵,H矩阵的各个行是线性无关的 行数=监督位数,列数=码字长度,典型阵,转置得,称为生成矩阵,生成矩阵G的每一行都是一个码组。 例如,(参照前页矩阵G)。 利用生成矩阵,码字,再由 得,,译码,若发送码组为 接收码组为 二者之差为 其中E称为错误图样。,表示该位接收码元无错; 表
8、示该位接收码元有错。,接收端译码时计算 当接收码组无错时S等于零 有错但不超过检错能力时, S不等于零。 在错码超过检错能力时,B变为另一许用码组,仍能成立S等于零。这样的错码是不可检测的。 S称为校正子(伴随式) 。S只与E有关,而与A无关,意味着S与E有的线性变换关系,能与E一一对应,可指示错码位置。,线性码重要性质之一,是它具有封闭性。 若:A1和A2是线性码中的两个许用码组,则:(A1+A2)仍为其中的一个码组。 由封闭性,两个码组之间的距离必是另一码组的重量。故码的最小距离即是码的最小重量(除全“0”码组外)。 线性码又称群码,这是由于线性码的各许用码组构成代数学中的群。, 11. 5 循环码,11. 5 . 1 循环码原理: 在线性分组码中,有一种重要的码称为循环码。循环码除了具有线性码的一般性质外还具有循环性,即任一码组循环一位(将最右端的码元移至左端,或反之)以后,仍为该码中的一个码组。即若 是许用码组,则 也是许用码组。,循环码举例(7,3)循环码,码组的多项式表示码多项式。 例如 A=1100101 A(x)=1x6+1x5+0x4+0x3+1x2+0x1+1x0
9、=x6+x5+x2+1 码多项式表示具有线性的性质,码多项式的按模运算 循环移位 对应的码多项式 如果规定xn=x0,即规定xn+1=0,则有,这种xn+1=0的规定,实质上是一xn+1为模的运算。对于整数m,若可以表示为 则称m=p(模n) ,或称m与p是同余的。 码多项式也有类似的运算。多项式F(x)被n次多项式N(x)除,得到商式q(x)和一个次数小于n的余式R(x),即 F(x)q(x)N(x)+R(x) 则写为F(x)R(x) ( 模N(x) ),码多项式系数仍按模2运算,即只取值0和1。例如 于是,可以有 由此可见为了使xn=1,只需做模xn+1的运算即可。 例如:x4+x2+1=x2+x+1 模x3+1,由前面的分析可知,若T(x)是码多项式,则在模xn+1的运算条件下, xiT(x)仍然是码多项式。,2循环码的生成矩阵G 若能找到k个线性无关的码组,就能构成矩阵G。在循环码中,一个(n,k)码有2k个不同码组,若用g(x)表示其中前(k-1)位皆为0的码组,即 g(x)=0 1x x k位 n-k位 则g(x) 、xg(x),x2g(x) ,xk-1g(x)都是码组,而且这k个码组是线性无关的。因此可以用来构成循环码的生成矩阵G。,例 表96的循环码, 唯一的一个(n-k)次码多项式代表的码组是0010111,相对应的码多项式为,一旦确定了g(x),则整个(nk)循环码就被确定了。因此,循环码的生成矩阵G可以写成,这个生成矩阵不是系统码的生成矩阵,可以通过行变换,变换成系统码的生成矩阵。,g(x)x4+x2+x+1 将此g(x)代入上式,得到,g(x)的性质: g(x)必须是一个常数项a0=1; 次数为(n-k)次; 唯一的(n-k)次多项式; 我们称这唯一的g(x)为码的生成多项式。 g(x)是xn+1的因式(见后面分析)。,说明g(x)是xn+1的因式。 因为任码多项式T(x)都是g(x)的倍式,所以有 T(x)=h(x)g(x) g(x)本身也是一个码
《通信原理讲稿第11章课件》由会员F****n分享,可在线阅读,更多相关《通信原理讲稿第11章课件》请在金锄头文库上搜索。