差错控制编码11

《差错控制编码11》由会员分享，可在线阅读，更多相关《差错控制编码11（55页珍藏版）》请在金锄头文库上搜索。

1、1,本章内容目的要求,教学要求:了解差错控制编码的基本方法和基本原理，掌握线性分组码的一般构造原理及汉明码、循环码、卷积码的概念。 内容提要:差错控制的基本方式及信道编码的概念；检错码；线性分组码；卷积码。 重点：汉明码的生成矩阵、监督矩阵的计算；循环码的生成矩阵、监督矩阵的计算。 难点：卷积码的原理。,共4学时：12.11（1、2）9.1-9.4 12.12（3、4）9.5-9.6,2,9.1 概述,信源编码和信道编码 信源编码目的：提高数字信号的有效性； 模拟信号数字化。 信道编码目的：降低误码率 提高数字通信的可靠性 信道编码方法：在信息序列上附加上一些监督码元，发现和纠正错误。,3,差

2、错控制方式,图 9-1 差错控制方式,4,1、检错重发方式： （计算机通信）,检错重发（ARQ）的优点主要表现在： （1）只需要少量的冗余码，就可以得到极低的输出误码率； （2）有一定的自适应能力； 某些不足主要表现在： （1）需要反向信道，故不能用于单向传输系统，并且实现重发控制比较复杂； （2）通信效率低，不适合严格实时传输系统。,5,2、前向纠错 发送端经信道编码后可以发出具有纠错能力的码字；接收端译码后不仅可以发现错误码，而且可以判断错误码的位置并予以自动纠正。 3、混合纠错方式 混合纠错方式是前向纠错方式和检错重发方式的结合。,6,9.2 检错与纠错原理,一、纠错编码的分类 （1）按

3、照信道编码的不同功能，可以将它分为检错码和纠错码。 （2）按照信息码元和监督码元之间的检验关系，可以将它分为线性和非线性码。 （3）按照信息码元和监督码元之间的约束方式不同，可以将它分为分组码和卷积码。 （4）按照信息码元在编码后是否保持原来的形式，可以将它分为系统码和非系统码。 （5）按照纠正错误的类型不同，可以将它分为纠正随机错误码和纠正突发错误码。,7,二、检错与纠错编码的基本原理 1、分组码 表示为（n，k）, n表示码组的长度； k信息的长度；r = n-k表示监督位长度。 几个概念： 码长n：码字中码元的数目； 码重w：码字中非0数字的数目； 码距d：两个等长码字之间对应位不同的数

4、目，有时也称作这两个码字的汉明距离。,8,例：3位二进制数构成的码组表示天气,如不要检（纠）错，传输4种不同的信息，用两位码组就够了，这两位码代表所传信息，称为信息位，多增加的称为监督位。,9,例，三位二进制码的三种编码方法。三位二进码共有8种可能的组合：000，001，010，011，100，101，110，111。,a. 若8个码组均用于表示不同的信息，任一位或一位以上的错误都会变成另一码组，所以无法检错和纠错。 b. 若将8个码组分成许用和禁用两类： 许用码组：000，011，101，110 禁用码组：111，100，010，001 因任何一位误码，都会变成禁用码组，所以可检出一位误码。

5、 c. 若只用 000，111两个码组，其余为禁用码组，则可发现两位及以下的误码，并纠正一位误码。,10,最小码距：在码字集合中全体码字之间距离的最小数值。 纠错码的抗干扰能力完全取决于许用码字之间的距离，码的最小距离越大，说明码字间的最小差别越大，抗干扰能力就越强。 分组码的最小汉明距离为d0,11,2、检错和纠错能力 （1）当码字用于检测错误时，如果要检测e个错误，则 d0 e + 1； （2）当码字用于纠正错误时，如果要纠正t个错误，则 d0 2t + 1； （3）若码字用于纠t个错误，同时检e个错误时（e t），则 d0 t + e +1。,12,三、编码效率和基本要求,编码效率R可以

6、用下式表示： 基本要求： 检错和纠错能力强 编码效率高 编码规律简单,13,9.3 简单分组码,1 奇偶监督码 可以表示成为（n，n-1）。如果是奇监督码，在附加上一个监督元以后，码长为n的码字中“1”的个数为奇数个；如果是偶监督码，在附加上一个监督元以后，码长为n的码字中“1”的个数为偶数个。,偶监督码有,奇监督码,奇偶效验码码组间最小距离dmin2,14,奇偶监督码的编码可以用软件实现，也可用硬件电路实现。 如果码组B无错，BA，则M0；如果码组B有单个（或奇数个）错误，则M1。 编码效率 : R=(n-1)/n,15,2、水平奇偶监督码,表91 水平奇偶监督码,m个码组分别以各自码组为单

7、位作奇效验或偶效验，然后以各码组的最高位、次高位， 依次发送。 当突发的错误数小于m个时，每个码组中的误码个数小于2个，通过奇偶效验可以检出。,16,3 行列监督码 行列监督码又称水平垂直一致监督码或二维奇偶监督码，有时还被称为矩阵码。,二维奇偶监督码适于检测突发错码。二维奇偶监督码不仅可用来检错，还可用来纠正一些错码。,图 9-2 (66,50)行列监督码,17,4、群计数码,计算码组中信息位“1”的个数，将计算值作为监督位，可检出除“0”变“1”，“1”变“0”成对出现之外的所有错误。,5、恒比码,恒比码又称等重码，该码的码字中1和0的位数保持恒定的比例。具体情况见表9-3,18,表 9-

8、3 32 恒比码,目前我国电传通信中普遍采用3：2码，国际上通用的ARQ电报通信系统中，采用3：4码即7中取3码。,19,9.4 线性分组码,一、 基本概念 分组码是一组固定长度的码组，可表示为（n , k），通常它用于前向纠错。在编码时，k个信息位被编为n 位码组长度，而n-k 个监督位的作用就是实现检错与纠错。 这样，一个k 比特信息的线性分组码可以映射到一个长度为n 码组上。,20,二、汉明码（Hamming）,具有下列特点的线性分组码称之为汉明码： 码长：n2r1，信息位：k2r1r，监督位：rnk 最小码距 dmin3，纠错能力 t1 记为： （n，k）（ 2r1，2r1r ） 汉明

9、码的编码效率：,若S0，则无错；若S1就认为有错。,监督方程,21,二、汉明码（Hamming）,现以(7,4)分组码为例来说明线性分组码的特点。设其码字为A=a6 a5 a4 a3 a2 a1 a0，其中前 4 位是信息元，后 3 位是监督元， 可用下列线性方程组来描述该分组码，产生监督元。,22,表95 校正子与错码位置的关系,23,表 9-6 (7,4)码的码字表,汉明码的编码效率,24,设信息码组a6a5a4a30101 a2a6a5a4 0101 a1a6a5a3 0110 a0 a6a5a4 = 0011 发送： a6a5a4a3 a2a1a0 0101101 若接收时有一位，a5

10、，位出错： a6a5a4a3 a2a1a00001101 S1a6a5a4a2 0001=1 S2a6a5a3a1 0010=1 S3a6a5a3a0 0000=0 根据效验子 S1 S2 S3110，可判断误码发生在a5。,25,三、监督距阵,监督矩阵H 将（7，4）码的三个监督方程式可以重新改写为如下形式： 上式可以记作：HA T=0 T或AH T=0 ，其中,26,监督矩阵的性质： （1）H由码元间的监督关系唯一确定； （2）H的行向量相互独立，当采用系统码结构时，具有形式 其中Ir是rr单位阵。 （3）若发A，收到R， 则有误码。,27,若把监督方程补充为下列方程,四、生成距阵,28,

11、可改写为矩阵形式,29,这里G称为生成矩阵，利用它可以产生整个码组：,这时Q = PT，如果在Q矩阵的左边在加上一个kk的单位矩阵，就形成了一个新矩阵G：,30,设发送码组A=an-1,an-2,a1,a0，在传输过程中可能发生误码。接收码组B=bn-1,bn-2,b1,b0，则收发码组之差定义为错误图样E， 也称为误差矢量， 即,其中E=en-1,en-2,e1,e0，且,(9 - 23),五、伴随式(校正子)S 和检错,31,表 9-7 (7,4)码S与E的对应关系,则接收端利用接收到的码组B计算校正子： S=BHT=(A+E)HT= AHT + EHT = EHT 因此，校正子仅与E有关

12、，即错误图样与校正子之间有确定的关系。,32,六、线性分组码的性质,线性分组码的主要性质如下： 具有封闭性：也就是说，任意两许用码之和仍为一许用码， 有零码、有负元 满足结合律和交换律 码组间的最小码距等于非零码的最小码重。,33,9.5 循环码,循环码是线性分组码的一个重要子集，是目前研究得最成熟的一类码，它有许多特殊的代数性质。 特点：循环码中任一许用码组经过循环移位后，所得到的码组仍然是许用码组。 描述：许用循环码A=(an-1 an-2 a1 a0)，可以将它的码多项式表示为：,一、循环特性,34,表 9-8 (7,3)循环码,如果一种码的所有码多项式都是多项式g(x)的倍式，则称g(

13、x)为该码的生成多项式。在(n,k)循环码中任意码多项式A(x)都是最低次码多项式的倍式。如表 9-8 的(7,3)循环码中.,35,二、生成多项式及生成矩阵,其它码多项式都是g(x)的倍式， 即,36,循环码的生成矩阵常用多项式的形式来表示,37,例如(7,3)循环码，n=7, k=3, r=4, 其生成多项式及生成矩阵分别为,38,进行矩阵行运算：r1+r3mod2 得到:,39,可以证明生成多项式g(x)具有以下特性： （1） g(x)是一个常数项为1的 次多项式； （2） g(x)是 的一个因式； （3）该循环码中其它码多项式都是g(x)的倍式。,40,为了便于对循环码编译码，通常还定

14、义监督多项式， 令,其中g(x)是常数项为 1 的r次多项式，是生成多项式；h(x)是常数项为 1 的k次多项式，称为监督多项式。同理，可得监督矩阵H,9.5.3 监督多项式及监督矩阵,41,是h(x)的逆多项式。例如(7，3)循环码，g(x)=x4+x3+x2+1，则,其中,42,9.5.4 编码方法,在编码时，首先要根据给定的(n,k)值选定生成多项式g(x)，即应在xn+1的因式中选一个r=n-k次多项式作为g(x)。设编码前的信息多项式m(x)为,循环码的码多项式可表示为,图9-2（7-3）循环码的编码电路P321,43,9.5.5 译码方法和电路,图 9-4 单个错误出现在接收码组首

15、位的(7,3)循环码译码电路,循环码的译码可以分三步进行： （1）由接收到的码多项式B(x)计算校正子（伴随式）多项式S(x)； （2）由校正子S(x)确定错误图样E(x)； （3）将错误图样E(x)与B(x)相加，纠正错误。,44,9.6.1 基本概念,9.6 卷 积 码,卷积码中编码后的n个码元不仅与当前段的k个信息有关，而且也与前面（N-1）段的信息有关，编码过程中相互关联的码元为nN个。因此，这N段时间内的码元数目nN通常被称为这种码的约束长度。 由于与前面m段规定时间内的信息位有关，这里的mN-1通常用（n，k，m）表示卷积码 。,45,图 9-5 卷积码(2,1,2)编码器,例如：

16、卷积码的n = 2，k = 1，m = 2，因此，它的约束长度nN = n(m+1) = 23 = 6。,46,假如输入的信息为D = 11010，为了使信息D全部通过移位寄存器，还必须在信息位后面加3个零。表列出了对信息D进行卷积编码时的状态。 描述卷积码的方法：图解表示和解析表示。 卷积码的译码方法可分为代数译码和概率译码两大类。,47,起始状态，各级移位寄存器清零，即S1S2S3为000。S1等于当前输入数据，而移位寄存器状态S2S3存储以前的数据，输出码字C由下式确定,表 9-6 (2,1,2)编码器的工作过程,48,1. 树图,图 10-9 (2,1,2)码的树图,9.6.2 卷积码的图解表示,49,2. 状态图,图 9 -10 (2,1,2)码的状态图,5