数字通信原理差错控制课件.ppt

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

1、第10章 差错控制,学习要求,1.理解差错控制的基本概念及其原理等；2.掌握信道编码的基本原理；3.了解常用检错码的特性；4.掌握线性分组码的一般特性；5.掌握汉明码以及循环码的编译码及其实现原理；6.掌握卷积码的编译码基本原理。,10.1 差错控制的基本概念及原理,1.差错分类,10.1.1 差错控制的基本概念,随机差错：又称独立差错，它是指那些独立地、稀疏地和互不相关地发生的差错。,突发差错：是指一串串，甚至成片出现的差错，差错之间有相关性。,目的：提高通信系统的可靠性,噪声分类：随机噪声和脉冲噪声。,误码产生原因：信道不理想造成的符号间干扰；噪声对信号的干扰。,重点讨论,由随机噪声引起,

2、由脉冲噪声引起,2.错误图样,E中，“0”表示正确，“1”表示错误,随机错误错误图样,错误图样,突发错误错误图样,2.差错控制的基本思路,发送端：将被传送的信息码（无规律）按照一定的规则加入监督码元后进行传输，加入的监督码元与信息码元存在某种确定的约束关系。,接收端：检验信息码元与监督码元之间的既定的约束关系，如关系被破坏，则传输中有错。,差错控制也称纠错编码，信道编码。,信息码(k)+监督码(r)=码组(n),信息码元(k)+监督码元(r)=码组(n),3.差错控制方式,（1）检错重发（ARQ）,优缺点所需的监督码位数少，编码效率比较高；译码设备较简单；接收端检测到差错后，要通过反向信道发回

3、NAK，要求发端重发，所以需要反向信道，实时性差,ARQ有3种重发方式，即停发等候重发，返回重发和选择重发。,a）停发等候重发,b）返回重发,c）选择重发,（2）前向纠错（FEC）,优缺点 不需要反向信道，自动纠错，不要求重发，因而实时性好；缺点是所选择的纠错码必须与信道的错码特性密切配合，否则 很难达到降低错码率的要求；要纠正较多的错码，译码设备复杂，且要求附加的监督码较多，编码效率低。,（3）混合纠错检错（HEC）,是ARQ和FEC方式的折衷方案,优缺点 集合了ARQ和FEC的优点，在保证系统较高的有效性的同时,大幅度提高了整个系统的可靠性，但需要反向信道。,（4）信息反馈（IRQ）,优缺

4、点 优点是不需要纠错、检错，设备简单；缺点是需要和前向信道相同的反向信道，实时性差，且发送端需要一定容量的存储器。,10.1.2 差错控制的基本原理,1.差错控制的原理,AB,0 01 1,01,0110,准用码组,禁用码组,无检错能力无纠错能力,可检测1位错码,举例说明,信息位1无监督位,信息位1 监督位1,方案1,方案2,10.1.2 差错控制的基本原理（续）,1.差错控制的原理（续）,AB,0 0 01 1 1,001 010 100011 101 110,准用码组,禁用码组,可检测1到2位错码，或纠1位错码,要想具有检错和纠错能力，必须有禁用码组。禁用码组的获得方法：加监督位。,方案3

5、,信息位1 监督位2,码长：码组或码字中编码的总位数为码组的长度。,2.汉明距离与检错和纠错能力的关系,（1）几个概念,码重：码组中非零码元的数目为码组的重量。例如“11010”的码长为5，码重为3。,码距：两个等长码组中对应码位上具有不同二进制码的数目 称为码距。,例如：码组1 11010 码组2 01101,码距：d0=4,在一种编码中，任意两个许用码组间距离的最小值。,000 001 010 100111 011 101 110,dmin=1,（2）汉明距离和检错和纠错能力的关系,a)为了检测e位错码，要求最小码距,b)为了纠正t位错码，要求最小码距,c)为了纠正t位错码，同时检测e(e

6、t)位错码，要求最小码距,3.纠错编码的分类,(1)按码组的功能分，有检错码和纠错码两类。,(2)按码组中监督码元与信息码元之间的关系分，有线性码和 非线性码两类。,(3)按照信息码元与监督码元的约束关系，可分为分组码和 卷积码。,(4)按照信息码元在编码前后是否保持原来的形式不变，可分为系统码和非系统码。,(5)按纠正差错的类型可分为纠正随机错误的码和纠正突发 错误的码。,(6)按照每个码元取值来分，可分为二进制码与多进制码。,10.2.1 奇偶监督码,10.2 简单的差错控制编码,特点：只有一个监督位。,偶监督：码组中“1”的个数为偶数。,奇监督：码组中“1”的个数为奇数。,只能检出奇数位

7、错码。,10.2.2 水平奇偶监督码,思想方法：将信息码序列按行排成方阵，每行后面加一个奇或偶监督码，即每行为一个奇（偶）监督码组，但发送时则按列的顺序传输：11101110011000010101，接收端仍将码元排成与发送端一样的方阵形式，然后按行进行奇偶校验。,水平偶监督码,可以检出奇数位错误和长度不大于方阵中行数的突发错误。,10.2.3 二维奇偶监督码（水平垂直奇偶监督码）,思想方法：在水平监督基础上对方阵中的每一列再进行奇偶校验。发送时按行或按列的顺序传输，接收端重新将码元排成与发送时的方阵形式，然后每行、每列都进行奇偶校验。,二维偶监督码,可以纠1位错码；可以检出某行或某列上的奇数

8、位错码和长度不大于方阵中行数(列数)的突发错码；可以检出一部分偶数位错码；不能检出错码恰好分布在矩阵4个顶点上的偶数位错码。,10.3 汉明码及线性分组码,汉明码特点,可以纠正一位错码，且d0=3,10.3.1 汉明码,1.码长和监督位的关系：,若使用偶监督：只有一位监督位,接收端译码时，实际上就是计算：,若 无错；有错。,奇监督相反,校正子,1位监督位，有1个校正子。,只能表示有错和无错，不能指示错码位置。,码长和监督位的关系,2位监督位，就有2个监督关系式，也有2个校正子。,如果,无错,指示错码位置,（n,k）汉明码，监督位 r=n-k，可构造出r个监督关系式 来指示一位错码的n种可能位置

9、，要求,若为：,1.（7,4）汉明码,a6 a5 a4 a3：信息码元；a2 a1 a0：监督码元,信息码元与监督码元的关系：,表10.3.1（7,4）汉明码的许用码组 P322,假设发送端的码字是A15=1111111，传输过程中第4位a3出现了错误，即接收的码字是B=1110111 不是许用码组。,1.（7,4）汉明码,校正子与错码位置的关系,例10-1 接收端收到某（7,4）汉明码为1001010，问：此（7,4）汉明码是否有错？错码位置如何？,解：,计算校正子,得校正子 为110，,码组有错。,正确码组：1101010,2）（7,4）汉明码的产生,由监督关系式：,发端无错,移项，解出监

10、督位：,解决问题：由信息位计算监督位,例10-2 已知信息码为1101，求所对应的（7,4）汉明码。,解：,计算监督位,汉明码码组：1101010,监督位,3）编码效率,（7,4）汉明码的编码效率：,10.3.2 线性分组码,线性码：监督码元与信息码元之间满足一组线性方程。,分组码：监督码元仅对本码组中的码元起监督作用。,1.监督矩阵,以（7,4）汉明码为例,改写为,简写为+,线性分组码：既是线性码又是分组码。,写成矩阵形式,监督矩阵,简写为,单位方阵,P,用矩阵表示为,其中：,监督位,信息位,监督位与信息位的关系（矩阵表示）,2.生成矩阵,用途：由信息位和生成矩阵可得出整个码组。,生成矩阵：

11、,以（7,4）汉明码为例,生成矩阵,如（7,4）汉明码表中的第3个码组 P322,求整个码组,注意：生成矩阵G各行本身就是一个码组。加例题！,二元域上只有两种运算：加和乘。运算规则如下：,3.监督矩阵和生成矩阵的关系,例10-3（课后练习）某（7,4）线性分组码，监督方程如下，求监督矩阵H和典型的生成矩阵G。如信息码为0010，求整个码组。,解：,监督方程改写为,得监督矩阵：,典型生成矩阵：,如信息码为0010，则整个码组为,4.线性分组码的主要性质,(1)封闭性 是指一种线性分组码中的任意两个码组之逐位模2和仍为这种 码中的另一个许用码组。,(2)码的最小距离等于非零码的最小重量。,5.线性

12、分组码的纠错能力,10.4 循环码,循环码是一种线性分组码。,10.4.1 循环码的循环特性,表10.4.1（7,3）循环码的一种码组 P328,循环码的循环特性是指在循环码中任一许用码组经过循环移位后所得到的码组仍为它的一个许用码组。,第2码组右移1位得到第5码组；,第5码组右移1位得到第7码组。,2.码多项式的表示及运算规则,例如，码组为 则码多项式为：,码多项式的运算：加、减、乘、除运算,1）码多项式的加法运算：同幂次相加，系数进行异或运算,2）码多项式的减法运算：同加法运算,码组为,则码多项式为：,3）异或运算（逻辑加和逻辑减）的真值表,4）码多项式的乘法运算：服从一般的代数规律,5）

13、码多项式的除法运算：服从一般的代数规律,6）码多项式的除法运算简化表示,例如,上式还可表示为,10.4.2 循环码的生成多项式和生成矩阵,1.生成多项式 g(x),生成多项式的寻找方法：,（n,k）循环码的 个码组中，有一个码组前k-1位码元均为0，第k位码元为1，最后一位为1，此码组对应的多项式为生成多项式。,例10-5 求表10.4.1所示的（7,3）循环码的生成多项式。,解：,生成多项式,2.生成矩阵G,典型的生成矩阵,通过线性变换可将非典型的生成矩阵转换为典型的生成矩阵,单位方阵,例10-5（续）求表10-6所示的（7,3）循环码的典型生成矩阵G。,解：,生成矩阵多项式,生成矩阵,非典

14、型矩阵,典型矩阵,3.生成多项式的另一种求法,（n,k）循环码的生成多项式是 的一个（n-k）次因式。,例 求（7,3）循环码的生成多项式。,解：,生成多项式有两个：,表10.4.1循环码用,生成多项式不同，产生出的循环码码组也不同。,10.4.3 循环码的编码方法,步骤：,信息位对应的码多项式：,循环码的码多项式,10.4 循环码的编码,当M=110，所以,即所得的码字为A=1100101。,10.4.4 循环码的解码方法,1.检错的实现,无差错,判别方法,若码组有错，则,接收码组 若码组无错,检测到差错,解码器的核心：除法器,10.4 循环码,r级线性移位寄存器的初始状态为全零，所有开关均

15、向下连通；,在寄存器时钟的控制下进行k次移位，输出M(x)的系数(即信息 码组)，同时实现除法电路的功能；,编码器工作过程,10.4 循环码,所有开关向下连通，输入下一组信息重复上述过程。,实例分析,所有开关均倒向上方连通，在寄存器时钟的控制下再经过r=n-k 次移位，将监督元输出到信道；,本节前面给出的(7，3)循环码生成多项式：g(x)=x4+x2+x+1 由其可得编码电路如下图所示：,10.4 循环码,假设M=110，编码器工作过程如下表所示,a6a5a4,a3a2a1a0,循环码的编码器电路设计,2.纠错的实现,概念：错误图样,发送码组,接收码组,错误码组,错误码组的各种不同的具体采样

16、称错误图样,纠错的步骤：,得原发送码组。,10.4 循环码,纠错译码原理,确定循环码的纠错能力;,根据 模g(x)计算伴随式，若S(x)0则判定传输出错。,根据 模g(x)找到校正子对应的错误图样,由A(x)=B(x)+E(x)纠错。,10.4 循环码,检错译码原理图：P334，335,10.4 循环码,寄存器置零，开关S向下连通；,在寄存器时钟的控制下经n次移位后将接收码字B输入，此时寄存器中存储的即校正子,(n，k)循环码校正子计算电路,其工作过程如下：,将开关向上打开，经r=n-k次移位读出校正子。,国际通信中常用的是循环冗余校验（CRC）,生成多项式为：,CRC-32,CRC IS-9

17、5 CDMA,10.6 卷积码,本节内容提要：,卷积码是一类非线性有记忆编码，本节将简要介绍卷积码的编 译码原理。,10.6.1 卷积码编码器 10.6.2 卷积码的解析描述 10.6.3 卷积码的图解描述 10.6.4 维特比译码原理,10.6 卷积码,卷积码又称连环码，是非分组码。没有严格的代数结构,10.6.1 卷积码的基本概念,卷积码的监督位不仅取决于这段时间的k个信息位，还取决于前N-1段规定时间内的信息位。,1.卷积码的概念,编码效率：,即卷积码的监督位不仅对本码组起监督作用，对前N-1个码组也起监督作用。,这N段时间内的码元数目nN称为约束长度。,卷积码的表示方式：(n,k,N)

18、,10.6.1 卷积编码器,(n，k，N)卷积编码器结构,10.6.1 卷积编码器,(3，1，3)卷积码的两种等效编码器,实例分析,3级编码器,n=3,k=1:每输入一个信息比特，产生3个输出比特；S1、S2、S3：移存器,10.6.2 卷积码的解析描述,仍然以上图中的(3，1，3)卷积码为例，由其单位冲击响应可构造生成矩阵为：,生成矩阵法,其中未写出的元素为0。和分组码不同，卷积码并不以块的形式出现，即其码字可能无限长，故上式所示的矩阵称为半无限矩阵,此时卷积码可由C=MG得到，例如M=11101时,10.6.2 卷积码的解析描述,卷积编码器也可以用n个生成多项式来描述，分别对应n个输出支路

19、。,生成多项式法,(3，1，3)卷积码编码器,上图所示的卷积编码器可以用以下所示的3个生成多项式描述,10.6.2 卷积码的解析描述,则对应的码多项式为,所以对应的码字是：C=111 110 101 010 100 001 011,输入信息为M=11101，对应的多项式为 则各支路码多项式分别为：,10.6.2 卷积码的解析描述,10.6.3 卷积码的图解描述,实例分析以下图所示的(3，1，3)卷积码器,mj、mj-1、mj-2：移存器；y1、y2、y3：3个输出比特。,实线,虚线,000,111,110,001,011,010,100,101,状态图法,10.6.3 卷积码的图解描述,假设初始状态为a，输入序列为M=110101，则有状态图很容易得到编码序列为C=111 110 010 100 001 100。,10.6.3 卷积码的图解描述,树图法,输入为110101时，编码输出为111 110 010 100 001 100，如图中虚线所示,10.6.3 卷积码的图解描述,网格图法,实线：传 0,虚线：传 1,粗实线：编码过程,10.6.4 维特比译码原理,（有错）收码：1 1 0 0 1 0 0 1 0 1 1 0 0 0 1 0 1 1,红线：码距最小的幸存路径,Thank You!,通信理论教研室 518,