数据通信原理 第3章课件.ppt

数据通信原理,第3章 差错控制,第 3 章 差错控制,3.1 差错控制的基本概念及原理3.1.1 差错控制的基本概念3.1.2 差错控制的基本原理3.2 简单的差错控制编码 3.2.1 奇偶监督码 3.2.2 水平奇偶监督码3.2.3 二维奇偶监督码3.3 汉明码及线性分组码3.3.1 汉明码3.3.2 线性分组码,第 3 章 差错控制,3.4 循环码3.4.1 循环码的循环特性3.4.2 循环码的生成多项式和生成矩阵3.4.3 循环码的解码方法3.4.4 循环码的解码方法3.5 卷积码3.5.1 卷积码的基本概念3.5.2 卷积码的图解表示3.5.3 卷积码的概率解码,3.1 差错控制的基本概念及原理,数据信号在传输过程中不可避免地会发生差错，即出现误码。造成误码的主要原因可以归结为两个方面：信道不理想造成的符号间干扰 由于信道不理想使得接收波形发生畸变，在接收端抽样判决时会造成码间干扰，若此干扰严重时则导致误码。这种原因造成的误码可以通过均衡方法予以改善以至消除。噪声对信号的干扰 信道等噪声叠加在接收波形上，对接收端信号的判决造成影响，如果噪声干扰严重时也会导致误码。消除噪声干扰产生误码的方法就是进行差错控制。,3.1.1 差错控制的基本概念,1.差错分类 数据信号在信道中传输会受到噪声干扰，噪声大体分为两类：随机噪声和脉冲噪声。随机差错又称独立差错，指那些独立地、稀疏地和互不相关地发生的差错。存在这种差错的信道称为无记忆信道或随机信道。突发差错是指一串串，甚至是成片出现的差错，差错之间有相关性，差错出现是密集的。产生突发错误的信道称为有记忆信道或突发信道。实际信道是复杂的，所出现的错误也不是单一的，而是随机和突发错误并存的，这两类错误形式并存的信道称为组合信道或复合信道。,2.差错控制的基本思路,差错控制的核心是抗干扰编码，或差错控制编码，简称纠错编码，也叫信道编码发送端：将被传送的信息码（无规律）按照一定的规则加入监督码元后进行传输，加入的监督码元与信息码元存在某种确定的约束关系。接收端：检验信息码元与监督码元之间的既定的约束关系，如关系被破坏，则传输中有错。,信息码(k)+监督码(r)=码组(n),3.差错控制方式,差错控制方式,（1）检错重发（ARQ）,优缺点所需的监督码位数少，编码效率比较高；译码设备较简单；接收端检测到差错后，要通过反向信道发回NAK，要求发端重发，所以需要反向信道，实时性差,ARQ有3种重发方式，即停发等候重发，返回重发和选择重发。,差错控制方式,（2）前向纠错（FEC）,优缺点 不需要反向信道，自动纠错，不要求重发，因而实时性好；缺点是所选择的纠错码必须与信道的错码特性密切配合，否则 很难达到降低错码率的要求；要纠正较多的错码，译码设备复杂，且要求附加的监督码较多，编码效率低。,差错控制方式,（3）混合纠错检错（HEC）,是ARQ和FEC方式的折衷方案,优缺点 集合了ARQ和FEC的优点，在保证系统较高的有效性的同时,大幅度提高了整个系统的可靠性，但需要反向信道。,差错控制方式,（4）信息反馈（IRQ）,优缺点 优点是不需要纠错、检错，设备简单；缺点是需要和前向信道相同的反向信道，实时性差，且发送端需要一定容量的存储器。,3.1.2 差错控制的基本原理,1.差错控制的原理,AB,0 01 1,01,0110,准用码组,禁用码组,无检错能力无纠错能力,可检测1位错码,信息位1无监督位,信息位1 监督位1,方案1,方案2,3.1.2 差错控制的基本原理,1.差错控制的原理（续）,AB,0 0 01 1 1,001 010 100011 101 110,准用码组,禁用码组,可检测1到2位错码，或纠1位错码,要想具有检错和纠错能力，必须有禁用码组。禁用码组的获得方法：加监督位。,方案3,信息位1 监督位2,结论 若要传送A和B两个消息：若用1位码表示，则没有检错和纠错能力；若用2位码表示（加1位监督码），可以检错1位；若用3位码表示（加2位监督码），最多可以检出2位或纠错码1位。在纠错编码中将信息传输效率也称为编码效率，定义为 显然，R越大编码效率越高，它是衡量码性能的一个重要参数。对于一个好的编码方案，不但希望它检错纠错能力强，而且还希望它的编码效率高，但两方面的要求是矛盾的，在设计中要全面考虑。,差错控制的基本原理,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(et)位错码，要求最小码距,3.纠错编码的分类,(1)按码组的功能分，有检错码和纠错码两类。,(2)按码组中监督码元与信息码元之间的关系分，有线性码和 非线性码两类。,(3)按照信息码元与监督码元的约束关系，可分为分组码和 卷积码。,(4)按照信息码元在编码前后是否保持原来的形式不变，可分为系统码和非系统码。,(5)按纠正差错的类型可分为纠正随机错误的码和纠正突发 错误的码。,(6)按照每个码元取值来分，可分为二进制码与多进制码。,3.2 简单的差错控制编码,1.奇偶监督码,特点：只有一个监督位。,偶监督：码组中“1”的个数为偶数。,奇监督：码组中“1”的个数为奇数。,只能检出奇数位错码。,2.水平奇偶监督码,思想方法：将信息码序列按行排成方阵，每行后面加一个奇或偶监督码，即每行为一个奇（偶）监督码组，但发送时则按列的顺序传输：11101110011000010101，接收端仍将码元排成与发送端一样的方阵形式，然后按行进行奇偶校验。,水平偶监督码,可以检出奇数位错误和长度不大于方阵中行数的突发错误。,3.二维奇偶监督码（水平垂直奇偶监督码）,思想方法：在水平监督基础上对方阵中的每一列再进行奇偶校验。发送时按行或按列的顺序传输，接收端重新将码元排成与发送时的方阵形式，然后每行、每列都进行奇偶校验。,二维偶监督码,可以纠1位错码；可以检出某行或某列上的奇数位错码和长度不大于方阵中行数(列数)的突发错码；可以检出一部分偶数位错码；不能检出错码恰好分布在矩阵4个顶点上的偶数位错码。,3.3 汉明码及线性分组码,汉明码特点,可以纠正一位错码，且d0=3,3.3.1 汉明码,1.码长和监督位的关系：,若使用偶监督：只有一位监督位,接收端译码时，实际上就是计算：,若 无错；有错。,奇监督相反,校正子,1位监督位，有1个校正子。,只能表示有错和无错，不能指示错码位置。,码长和监督位的关系,2位监督位，就有2个监督关系式，也有2个校正子。,如果,无错,指示错码位置,（n,k）汉明码，监督位 r=n-k，可构造出r个监督关系式 来指示一位错码的n种可能位置，要求,若为：,1.（7,4）汉明码,a6 a5 a4 a3：信息码元；a2 a1 a0：监督码元,信息码元与监督码元的关系：,1）（7,4）汉明码,校正子与错码位置的关系,例3-1：接收端收到某（7,4）汉明码为1001010，问：此（7,4）汉明码是否有错？错码位置如何？,解：,计算校正子,得校正子 为110，,码组有错。,正确码组：1101010,2）（7,4）汉明码的产生,由监督关系式：,发端无错,移项，解出监督位：,解决问题：由信息位计算监督位,（7,4）汉明码的许用码组,假设发送端的码字是A15=1111111，传输过程中第4位a3出现了错误，即接收的码字是B=1110111 不是许用码组。,例3-2：已知信息码为1101，求所对应的（7,4）汉明码。,解：,计算监督位,汉明码码组：1101010,监督位,3）编码效率,（7,4）汉明码的编码效率：,3.3.2 线性分组码,线性码：监督码元与信息码元之间满足一组线性方程。,分组码：监督码元仅对本码组中的码元起监督作用。,1.监督矩阵,以（7,4）汉明码为例,改写为,简写为+,线性分组码：既是线性码又是分组码。,写成矩阵形式,监督矩阵,简写为,单位方阵,P,用矩阵表示为,其中：,监督位,信息位,监督位与信息位的关系（矩阵表示）,2.生成矩阵,用途：由信息位和生成矩阵可得出整个码组。,生成矩阵：,以（7,4）汉明码为例,生成矩阵,如（7,4）汉明码表中的第3个码组,求整个码组,注意：生成矩阵G各行本身就是一个码组。加例题！,二元域上只有两种运算：加和乘。运算规则如下：,3.监督矩阵和生成矩阵的关系,例3-3：某（7,4）线性分组码，监督方程如下，求监督矩阵H和典型的生成矩阵G。如信息码为0010，求整个码组。,解：,监督方程改写为,得监督矩阵：,典型生成矩阵：,如信息码为0010，则整个码组为,4.线性分组码的主要性质,(1)封闭性 是指一种线性分组码中的任意两个码组之逐位模2和仍为这种 码中的另一个许用码组。,(2)码的最小距离等于非零码的最小重量。,3.4 循环码,循环码是一种线性分组码。,3.4.1 循环码的循环特性,表3-1（7,3）循环码的一种码组,循环码的循环特性是指在循环码中任一许用码组经过循环移位后所得到的码组仍为它的一个许用码组。,第2码组右移1位得到第5码组；,第5码组右移1位得到第7码组。,2.码多项式的表示及运算规则,例如，码组为 则码多项式为：,码多项式的运算：加、减、乘、除运算,1）码多项式的加法运算：同幂次相加，系数进行异或运算,2）码多项式的减法运算：同加法运算,码组为,则码多项式为：,3）异或运算（逻辑加和逻辑减）的真值表,4）码多项式的乘法运算：服从一般的代数规律,5）码多项式的除法运算：服从一般的代数规律,6）码多项式的除法运算简化表示,例如,上式还可表示为,3.4.2 循环码的生成多项式和生成矩阵,1.生成多项式 g(x),生成多项式的寻找方法：,（n,k）循环码的 个码组中，有一个码组前k-1位码元均为0，第k位码元为1，最后一位为1，此码组对应的多项式为生成多项式。,对于线性分组码，有了典型的生成矩阵G，就可以由k个信息码得出整个码组。如果知道监督方程，便可得到监督矩阵H，而由监督矩阵和生成矩阵G之间的关系则可以求出生成矩阵G。这里介绍求生成矩阵G的另一种方法，即根据循环码的基本性质来找出它的生成矩阵。由于G的各行本身就是一个码组，如果能找到k个线性无关的码组，就能构成生成矩阵G。,例3-4:求表3-1所示的（7,3）循环码的生成多项式。,解：,生成多项式,2.生成矩阵G,典型的生成矩阵,通过线性变换可将非典型的生成矩阵转换为典型的生成矩阵,单位方阵,例3-5：求例3-4所示的（7,3）循环码的典型生成矩阵G。,解：,生成矩阵多项式,生成矩阵,非典型矩阵,典型矩阵,3.生成多项式的另一种求法,（n,k）循环码的生成多项式是 的一个（n-k）次因式。,例3-6：求（7,3）循环码的生成多项式。,解：,生成多项式有两个：,生成多项式不同，产生出的循环码码组也不同。,3.4.3 循环码的编码方法,步骤：,信息位对应的码多项式：,循环码的码多项式,循环码的编码,当M=110，所以,即所得的码字为A=1100101。,3.4.4 循环码的解码方法,1.检错的实现,无差错,判别方法,若码组有错，则,接收码组 若码组无错,检测到差错,解码器的核心：除法器,国际通信中常用的是循环冗余校验（CRC）,生成多项式为：,CRC-32,CRC IS-95 CDMA,3.5.1 卷积码的基本概念,卷积码又称连环码，是非分组码。没有严格的代数结构,卷积码的监督位不仅取决于这段时间的k个信息位，还取决于前N-1段规定时间内的信息位。,1.卷积码的概念,编码效率：,即卷积码的监督位不仅对本码组起监督作用，对前N-1个码组也起监督作用。,这N段时间内的码元数目nN称为约束长度。,卷积码的表示方式：(n,k,N),卷积编码器,(n，k，N)卷积编码器结构,卷积码的编码,(3，1，3)卷积码等效编码器,实例分析,3级编码器,n=3,k=1:每输入一个信息比特，产生3个输出比特；S1、S2、S3：移存器,3.5.2 卷积码的图解表示,根据卷积码的特点，它还可以用树状图、网格图和状态图来表示，它与卷积码的编码过程和解码方法有密切关系。1.树状图 输出移位寄存器用转换开关代替，转换开关每输入一个比特转换一次，这样，每输入一个比特，经编码器产生两个比特。图中m1,m2,m3为移位寄存器，假设移位寄存器的起始状态全为0，即m1,m2,m3为000。c1与c2表示为 c1=m1+m2+m3 c2=m1+m3 m1表示当前的输入比特，而移位寄存器存储以前的信息，表示编码器状态。,（2,1,3）卷积码编码器的状态变化过程,编码器中移位过程可能产生的各种序列用树状图表示,2.网格图,3.状态图 从树状图的第三级各节点状态a,b,c和d与第四级各节点a,b,c和d之间的关系，或者取出已达到稳定状态的一节网格(网格图中第三级到第四级节点间的一节网格)，我们就可将当前状态与下一个状态之间的关系用状态图来表示。,