数字通信原理 纠错编码课件.ppt

《数字通信原理 纠错编码课件.ppt》由会员分享，可在线阅读，更多相关《数字通信原理 纠错编码课件.ppt（87页珍藏版）》请在三一办公上搜索。

1、差错控制编码,10.1 概述 10.2 常用的几种简单分组码 10.3 线性分组码 10.4 循环码 10.5 卷积码,本章内容在数字通信系统中所处的位置：,差错控制编码，又称信道编码、可靠性编码、抗干扰编码或纠错码，它是提高数字信号传输可靠性的有效方法之一。它产生于20世纪50年代初，发展到70年代趋向成熟。本章将主要分析信道编码的基本原理、介绍常用的检错码、线性分组码及卷积码的构造原理及其应用。,10.1 概 述,一、信源编码和信道编码 在数字通信中，根据不同的目的，编码可分为信源编码和信道编码。信源编码是为了提高数字通信的有效性以及使模拟信号数字化而采取的编码技术。信道编码是为了降低误码

2、率，提高数字通信的可靠性而采取的编码。,10.1 概 述,数字信号在传输过程中受到干扰的影响，使信号波形变坏，发生误码，可以采用一些方法解决。,差错出现原因 外界噪声 传输中码间串扰,解决方法 合理地设计基带信号，选择调制、解调方式，采用均衡技术，提高发送功率等因素，使误比特率降低。差错控制编码。,差错控制的基本原理 在信息码上附加一定位数的监督码元，使其与信息位按某种规则相互关联；若数据在传输过程中发生差错，关联关系被破坏，从而可 检出和/或纠正错误。,差错控制编码的分类 线性码：信息码与监督码之间的关系为线性关系；非线性码：信息码与监督码之间的关系为非线性关系。分组码：监督码只与本组信息码

3、有系；卷积码：监督码与本组和前面码组中的信息码有关。系统码：编码后码组中信息码保持原图样顺序不变；非系统码：编码后码组中原信息码原图样发生变化。,误码的主要形式 随机错误：误码的位置随机（误码间无关联），随机误码 主要由白噪声引起。突发错误：误码成串出现，主要由强脉冲及雷电等突发的 强干扰引起。混合错误：以上两种误码及产生原因的组合。,10.1.2 差错控制类型,1、检错重发（ARQ Automatic Repeat Request）:在发送端采用具有检错功能的编码，接收端发现出错后自动请求重发.有以下三种方式：停止-等待ARQ,具有回拉功能的连续ARQ 具有选择性重发功能的连续ARQ,特点：

4、设备较简单；传输序列中冗余量较小；需要有反向信道支持；出错后重传造成延时较大。,2、前向纠错方式（FECForward ErrorCorrection)发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误特点：无需反馈信道，无需重传，延时小；传输序列中冗余量较大。运用在移动通信系统、军事系统通信中。,3、混合纠错方式 HEC(Hybrid ErrorCorrection)混合纠错方式记作是FEC和ARQ方式的结合。出错较少时FEC起作用；出错较多时ARQ起作用,图 10-1 差错控制方式,总结：,信道编码的核心问题,发现错误 纠正错误,码长：码字中码元的个数，通常用n表示。码重：码字

5、中非零码元的个数定义为该码字的重量，简称码重。如“10011”码字的码重为3。码距：两个等长码字之间对应码元不同的数目，通常用d表示。两个码字对应位模2相加得到的新码组的重量就是这两个码字之间的距离。,（1）几个概念,编码效率：信息码元数与码长之比，通常用 表示，其中k为信息码元的数目，n为码长。最小码距：在一个码字集合中，任意两个码字间距离的最小值，即码字集合中任意两元素间的最小距离，记为dmin或d0,纠错码的抗干扰能力完全取决于许用码字之间的距离，码的最小距离越大，说明码字间的最小差别越大，抗干扰能力就越强。,举例说明：假如要传送A、B两个消息,编码一：消息A-“0”；消息B-“1”最小

6、码距1若传输中产生错码（“0”错成“1”或“1”错成“0”）收端无法发现，该编码无检错纠错能力。,编码二：消息A-“00”；消息B-“11”最小码距2若传输中产生一位错码，则变成“01”或“10”，收端判决为有错（因“01”“10”为禁用码组），但无法确定错码位置，不能纠正，该编码具有检出一位错码的能力。这表明增加一位冗余码元后码具有检出一位错码的能力,编码三：消息A-“000”；消息B-“111”最小码距3传输中产生一位即使两位错码，都将变成禁用码组，收端判决传输有错。该编码具有检出两位错码的能力。在产生一位错码情况下，收端可根据“大数”法则进行正确判决，能够纠正这一位错码。例如收到110，

7、认为是111。这表明增加两位冗余码元后码具有检出两位错码及纠正一位错码的能力。,一个码能检测e个错码，则要求其最小码dmine+1一个码能纠正t个错码，则要求其最小dmin2t+1一个码能纠正t个错码，同时能检测e个错码，则要求其最小码距 dmine+t+1(et),（2）最小码距与检错和纠错能力的关系,奇偶监督码 二维奇偶监督码（略，见附录）恒比码,10.2 常用的几种简单分组码,10.2.1 奇偶监督码,奇偶监督码：在信息码元后附加一位监督位，使得码组中奇偶监督码“1”的个数为偶数或奇数。,表：码长为4的奇、偶监督码,只能检测出单个或奇数个错误，不能检测偶数个错误不能纠错。应用：以随机错误

8、为主的计算机通信系统，难于对付突发错误 编码效率=k/n=k/(k+1)，是一种高效率码。,10.2.2二维奇偶监督码见附录,表 10-1 32 恒比码,（是一种五中取三码）,10.2.3 恒比码,码字中1的数目与0的数目保持恒定比例的码称为恒比码。又称等重码，定1码。这种码在检测时，通过计算接收码元中1的数目是否正确，就知道有无错误。,线性分组码：先将信息码分组，然后给每组信码附加若干监督码的编码称为分组码。若附加的监督码和信息码由一些线性代数方程相则称为线性分组码。用符号(n,k)表示，k是信息码的位数，n是编码组总位数，又称为码长，r=n-k为监督位数。,1、基本概念,10.3 线性分组

9、码（重点）,现以(7,4)分组码为例来说明线性分组码的特点。设其码字为A=a6 a5 a4 a3 a2 a1 a0，其中前 4 位是信息元，后 3 位是监督元，可用下列线性方程组来描述该分组码，产生监督元。,表 10-2(7,4)码的码字表,2、线性分组码的性质,任意两个许用码组之和（逐位模2和）仍为一许用码组，即具有封闭性。最小码距=非零码的最小码重（1的个数）。,10.3.2 监督矩阵H和生成矩阵G,其中,P为rk阶矩阵，Ir为rr阶单位矩阵。可以写成H=P Ir形式的矩阵称为典型监督矩阵。HAT=0T，说明H矩阵与码字的转置乘积必为零，可以用来作为判断接收码字A是否出错的依据。,并简记为

10、,rn阶矩阵 监督矩阵H确定了编码时监督码元与信息码元的关系 把具有PIr形式的H矩阵称为典型形式的监督矩阵，其中P为r k阶矩阵,Ir为r r阶单位方阵 H矩阵的各行应线性无关。矩阵若能写成典型形式，则其各行一定线性无关,监督矩阵H特点,若把监督方程补充为下列方程,可改写为矩阵形式,k n阶矩阵把具有IkQ形式的G矩阵称为典型形式的生成矩阵，其中，Ik为kk阶单位方阵，Q为k r阶矩阵由典型生成矩阵产生的分组码一定是系统码G矩阵的各行应线性无关，每行均为许用码组,生成矩阵G特点,已知（6，3）汉明码(能纠正单个错误的线性分组码)的生成矩阵如下，(1)列出所有许用码组;(2)最小码距d0;(3

11、)检错纠错能力(4)编码效率,（1）,（3）,（4）,（2）,设（7,4）线性码的生成矩阵G为：,当信息位为0001时，（1）试求其后的监督位。（2）监督矩阵H,解：（1）,（2）监督矩阵H根据生成矩阵和监督矩阵的关系：G=IkQ，H=PIr其中P=QT，可得监督矩阵H为：,错误矩阵/错误图样E：设发送码组为A，接收码组为B，,则错误矩阵,10.3.3 伴随式(校正子)S,接收端计算校正子S，即S=BHT=(A+E)HT=AHT+EHT=0+EHT=EHT 校正子只与E有关，即错误图样与校正子之间有确定的关系.确定错误图样与校正子的关系表。可从表中找得错码位置，加以纠正。,表 10-3(7,4

12、)码S与E的对应关系,以（7，4）汉明码为例设发送码组A=（0001011）接收码组 B=（0000011）则收端译码过程如下：计算校正子,查表得b3为错误位置，即可纠正（0001011）,10.4 循 环 码,循环码是一种重要的线性分组码。这种码的编码和解码设备都不太复杂，且有较强的检（纠）错能力。共n位，通常前k位为信息位，后r位为监督位。,10.4.1 循环码的编码原理,循环码的特点：封闭性；循环性；即码中任一码组循环一位(将最右端的码元移到左端或反之）以后，仍为该码中的一个码组。,若(an-1,an-2,a1,a0)是一(n,k)循环码的码组，则(an-2,an-3,a1,a0,an-

13、1)(an-3,an-4,a0,an-1,an-2)(a0,an-1,an-2,an-3,a2,a1)也都是该循环码的码组。,表一种（7，3）循环码的全部码字,把码长为n的码组中的各码元当作n-1次多项式的系数若码组A=（an-1，an-2，a1，a0)，则其相应的码多项式为(以降幂顺序排列)：A(x)=an-1xn-1+an-1xn-2+a1x+a0对于（7，3）循环码的任意码组可表示为：A(x)=a6x6+a5x5+a4x4+a3x3+a2x2+a1x+a0如码组（1100101）对应的码多项式可表示为A7(x)=1x6+1 x5+0 x4+0 x3+1 x2+0 x+1=x6+x5+x2

14、+1,1、码多项式A(x),表 10-4(7,3)循环码,写出各个码字多项式？最低次多项式的次数是多少？,10.4.1 生成多项式及生成矩阵,如果一种码的所有码多项式都是多项式g(x)的倍式，则称g(x)为该码的生成多项式。在(n,k)循环码中任意码多项式A(x)都是最低次(r次)码多项式的倍式。如表 10-4 的(7,3)循环码中，,其它码多项式都是g(x)的倍式，即,可以证明生成多项式g(x)具有以下特性：（1）g(x)是一个常数项为1的 次多项式；（2）g(x)是 的一个因式；（3）该循环码中其它码多项式都是g(x)的倍式。,可以构造出两种循环码组；它们的d0、检错、纠错能力相同,g(x

15、)，xk-1g(x)都是许用码组，连同g(x)共k个许用码组，构成码的生成矩阵G(x),注：该生成矩阵并不是典型形式的，但可通过线性变换变换成典型的生成矩阵。,循环码的生成矩阵常用多项式的形式来表示,例如(7,3)循环码，n=7,k=3,r=4,其生成多项式及生成矩阵分别为,例：已知（7，4）循环码的全部码组为：,试写出该循环码的生成多项式g(x)和生成矩阵G，并将G化成典型矩阵。,解：n=7，k=4，n-k=3上述码组中的(n-k)=3次码多项式为第2组，它所对应的码多项式g(x)即为生成多项式：g(x)=x3+x+1。生成矩阵为：,10.4.2 监督多项式及监督矩阵,其中g(x)是常数项为

16、 1 的r次多项式，是生成多项式；h(x)是常数项为 1 的k次多项式，称为监督多项式。同理，可得监督矩阵H,是h(x)的逆多项式。例如(7，3)循环码，g(x)=x4+x3+x2+1，则,其中,10.4.3 编码方法和电路,思路：在编码时，首先要根据给定的(n,k)值选定生成多项式g(x)，即应在xn+1的因式中选一r=n-k次,常数项为1的多项式作为g(x)。设编码前的信息多项式m(x)为,循环码的码多项式可表示为,用xr乘m(x)，相当于把信息码后附加上r个“0”,用g(x)除xr m(x)，得到商式Q(x)和余式为R(x)编出码组为：A(x)=xr m(x)+R(x),即余式r(x)=

17、x2+1于是，对应码组A(x)=xn-k m(x)+r(x）=x6+x5+x2+1 编码为1100101,例题 设（7，3）循环码的生成多项式为g(x)=x4+x2+x+1，待编码信息位为110，求对应循环码码组。,解：m(x)=x2+x，xn-k m(x)=x4(x2+x)=x6+x5,编码电路：,由除法电路和适当的控制电路构成。除法电路：由移位寄存器和加法器构成。,图 10-3(7,3)循环码编码电路,编码电路：由除法电路和适当的控制电路(用一双刀双掷开关K代替)构成。1、g(x)的次数为移位寄存器的级数。2、g(x)的非零系数对应于移位寄存器的反馈抽头。,信码,1、图中有4级移存器，分别

18、用a,b,c,d表示。2、当信息位输入时，开关K倒向下，输入信码一方面送入除法器进行运算，另一方面直接输出，当k个移位脉冲后，移位寄存器中的数据即为除法余数，即监督码元。3、在信息位全部进入除法器后，开关转向上，这时输出端接到移存器，将移存器存储的除法余项依次取出，同时切断反馈线。4、用这种方法编出的码组，前面是原来的k个信息位，后面是n-k个监督位。因此它是系统分组码。,10.4.4 译码方法和电路(略),10.6 卷 积 码,10.6.1 基本概念,1、卷积码：用(n,k,m)表示，每个(n,k)码段(字码)中的n个码元不仅与该码段内的k个信息元有关，而且与前面m个信息元有关（有记忆性）。

19、2、编码器：由k个输入，n个输出，m个移位寄存器和一些辅助电路构成的有记忆系统。,例：卷积码(2,1,2)编码器,起始状态，各级移位寄存器清零，即S2S3为00。S1等于当前输入数据，移位寄存器状态S2S3存储以前的数据，输出码字C由下式确定：,表(2,1,2)编码器的工作过程,编码约束度：每1位数据，将影响(m+1)个输出字码，称(m+1)为编码约束度。例（2，1，2）编码约束度为3。约束长度：每个子码有n个码元，在卷积码中有约束关系的最大码元长度为(m+1).n，称为约束长度。例（2，1，2）约束长度为6。,10.6.2 卷积码的描述（用图解法）,1.树图,图 7-6(2,1,2)码的树图

20、,2状态图用状态图来描述。下图就是该（2，1，2）卷积码编码器的状态图。在图中有4个节点a、b、c、d，同样分别表示S3S2的4种可能状态。每个节点有两条线离开该节点，实线表示输入数据为0，虚线表示输入数据为1，线旁的数字即为输出码字。,图（2，1，2）卷积码的状态图,3.格图,图(2,1,2)码的格图,10.5.3 卷积码的译码（概率译码，略）,3格图 格图也称网络或篱笆图，它由状态图在时间上展开而得到，如图所示。图中画出所有可能数据输入时，状态转移的全部可能轨迹，实线表示数据为0，虚线表示数据为1，线旁数字为输出码字，节点表示状态。,以上的3种卷积码的描述方法，不但有助于求解输出码字，了解

21、编码工作过程，而且对研究解码方法也很有用。,图（2，1，2）卷积码的格图,三、卷积码的译码（略）卷积码的译码可分为代数译码和概率译码两大类。代数译码是利用生成矩阵和监督矩阵来译码，最主要的方法是大数逻辑译码。概率译码比较实用的有两种：维特比译码和序列译码。目前，概率译码已成为卷积码最主要的译码方法。,本章小结：1、信源编码、信道编码的概念和区别2、线性分组码、循环码的相关概念、编码、译码作业：10-12、10-13、10-20、10-24、10-25,将经过奇偶监督编码的码元序列按行排成方阵，每行为一组奇偶监督码，但发送时按列的顺序传输 接收端将码元排成发送时的方阵形式，再按行进行奇偶校验 能

22、够发现某行上所有奇数个错误以及突发长度不大于方阵行数的突发错误 编码效率,附录：2、水平奇偶监督码,水平奇偶监督码,水平奇偶监督码接收端出现突发误码示例,结论：能够发现突发长度不大于方阵行数的突发错误,又称为方阵码、行列监督码、二维奇偶监督码。将水平奇偶监督码推广到二维。即在水平监督基础上再对方阵中每一列进行奇偶校验，发送时按列的顺序传输 接收端将码元排成发送时的方阵形式，再分别按行、按列进行奇偶校验,3、水平垂直奇偶监督码,能够发现某行、某列上所有奇数个错误以及突发长度不大于方阵行数或列数的突发错误；有可能检测出偶数个错误（在行上检测不出，但有可能在列上检测出），但当偶数个错误刚好构成矩形时，则检测不出 可纠正一些错误,表 水平垂直奇偶监督码,发送顺序,水平垂直奇偶监督码接收端纠错示例,例如：当码组中仅在一行有奇数个错误时，能够确定错误位置，并纠正它。,水平垂直奇偶监督码接收端检错示例,0,1,1,构成矩形的偶数个误码检测不出。,0,0,水平垂直奇偶监督码接收端检错示例,0,1,有可能检测出偶数个误码。,0,0,1,