第七讲差错控制编码ppt课件.ppt
,现代通信原理2010.92011.1,主要内容,差错编码的概念差错控制的基本方法线性分组码的概念及基本原理汉明码循环码BCH码交织的概念,为什么要进行差错编码？差错控制的几种基本方法各有何优缺点？如何构造一个汉明码？如何构造循环码？如何构造BCH码？为什么要采用交织？,研究对象,研究对象在数字通信系统中的位置,差错控制,为什么要采用差错控制噪声所导致的传输差错与信息可靠传输需求的矛盾在普通通信设备中，噪声是不可消除的此外，码间串扰（ISI），多接入干扰（MAI）和邻小区干扰（ICI）等均可能导致误码匹配滤波，最佳判决等手段均不可能消除差错问题：是否可能实现可靠传输？或者至少降低传输的差错率？解决问题的方法：差错控制,差错控制的基本方法,三种基本方法反馈检验检错重发ARQ前向纠错FEC反馈检验最原始的差错控制需要双向信道，和前向信道有相同的通信容量引入较大的停顿，不实时反馈信道可靠时，可以纠正任何错误,差错控制的基本方法,检错重发网络常用的方式差错判决放在接收端，只反馈差错状态自动请求重发，有效减少反馈量同样难以适用于实时业务多种实现方式停发等候、返回重发、选择重发,差错控制的基本方法,前向纠错FEC无需反馈信道直接在接收端对错误进行纠正，发端无需知道错误的状态适用于实时业务无需重传，发端不用存储，收端即时解码，发送的速率恒定依靠纠错编码信道编码通过在码流中引入有结构的冗余信息，纠正在传输中出现的错误,信道编码,一个简单的例子对称二进制信道BSC1个比特，只传1次，差错概率1个比特，重复传送3次，接收端做多数判决，错误概率,付出或代价：增加了传输的冗余，降低了传输的效率,收入或增益：提高了传输的可靠性，降低了误码率,信道编码,概念Channel Coding：通过合理的增加冗余信息，纠正信道传输中可能出现的错误，也称为纠错码：Error Correction Coding信道编码的评价标准纠错性能能纠正什么样的错误？能纠正多少错误？最终的误比特率性能如何？代价增加了多少冗余的比特？信息比特占整个码流的百分比即码率如何？纠错码的理论基础基于代数理论的结构，便于译码,信道编码,重要性信息系统不可或缺的重要技术移动通信深空通信与探测可靠计算存储设备,信道编码的分类,按功能分检错码：仅能检错 纠错码：仅能纠错按信息码元和监督码元之间的校验关系分线性码：监督码元与信息码元之间线性关系非线性码：监督码元与信息码元之间非线性关系按信息码元和监督码元之间的约束方式分分组码：监督码元仅与当前码组相关卷积码：监督码元与当前及以前码组都有关系按照信息码元在编码后是否保持原来形式系统码：信息码元编码后不变非系统码：信息码元改变,信道编码的香农定理,有扰离散信道的编码定理存在噪声干扰的信道，若信道容量为C，只要发送端以低于C的速率R发送信息（R为输入到编码器的二进制码元速率），则一定存在一种编码方式，使编码的错误概率随着码长n的增加将按指数下降到任意小的值两个结论如码长及发送信息速率一定，可以通过增大信道容量，使错误概率减小如在信道容量及发送信息速率一定，可以通过增加码长，使错误概率减小,给出了努力的方向，但怎么做？,信道编码的基本原理,看一个例子如用三位二进制编码来代表八个字母000 A100E001 B101F010C110G011D111H 不管哪一位发生错误，都会使传输字母错误如用三位二进制码传四个字母000 A011B101 C110D发生一位错误，准用码字将变成禁用码字，接收端就能知道出错，但是不能纠错。,信道编码的基本原理,如用三位二进制码传二个字母000 A111B检两个错误，纠正一个错误。结论具有检错或纠错的码组，其所用的比特数必须大于信息码组原来的比特数，引入冗余度；引入的冗余必须具有一定的结构，才能进行检错及纠错,信道编码的基本原理,几个基本概念码字二进制序列码重(weight)一个码组中“1”的数目码距(distance) 两个码组之间对应位置上1、0不同的位数 又叫汉明(Hamming)距10 1 1 0 码重：301 1 00 码重： 2 码距：3,信道编码的基本原理,检错和纠错能力与码距的关系考虑码字000错成001，Hamming距1，概率错成101，Hamming距2，概率错成111，Hamming距3，概率总结两个码字的Hamming距离越大，则一个码字误判成另一个码字的可能性越小码距与检错、纠错能力紧密相关,信道编码的基本原理,检错和纠错能力与码距的关系先考虑检测码字是否出错？可检测e个误码一个码字出错后不会变成另一个正确的码字，即可判断出错；如果一个码字内出现e个错误，则正确码字之间的间距必须大于e,信道编码的基本原理,检错和纠错能力与码距的关系考虑单个码字的纠错可纠正t个错误码字出现t个错误仍能正确判别的原则是：其他码字的各种错误情况不会进入到本码字t为半径的圆内；其他码字可能的最大圆的半径也为t，则要求正确码字之间的码距大于2t,信道编码的基本原理,检错和纠错能力与码距的关系考虑既检错又纠错检测e个错误，纠t个错误检测e个错误，要求码字间距大于e考虑纠t个错误，则此时间距要考虑的不是正确码字之间的距离。而是正确码字和可能的错误码字之间的距离，所以在检错基础上还需要加t,信道编码的基本原理,检错和纠错能力与码距的关系总结在一个码组内检测e个误码，则要求最小的码间距在一个码组内纠正t个误码，则要求的最小码间距在一个码组内纠正t个错误，同时检测e个错误，则要求的最小码间距,信道编码的基本原理,信道编码的准则可靠性准则能纠正更多的错误最大化最小码距有效性准则给出尽可能多的需用码字码率尽可能高码率k/n，k为信息位数，n为总码长,分组码,概念编码后的码元序列每n为分为一组，其中k个信息码元，r个附加的监督码元，而且监督码元仅与本组的信息码元有关，而与其他码组的的信息码元无关二进制序列分段，每段k个，针对每段按照一定规则附加r个监督码元分组码的优点容易以系统的数学理论进行建模分析实现电路简单，复杂度低线性分组码信息码元和监督码元之间的关系可以用线性方程表示,分组码,检错分组码的例子奇偶监督码偶监督奇监督如果以上关系被破坏，则出现错误，因此能检查出奇数个错误，但不能检测偶数个错误。最小码距为 dmin=2检错能力不高,分组码,水平奇偶监督码将码字按行排成方阵，每行采用奇偶监督码，发送时按列的顺序传送，接收时仍将码字排列成发送时方阵形式，然后按行进行奇偶校验在不增加冗余度时，不仅能发现某一行上奇数个错误，而且也能发现不大于方阵行数的突发错误没有增加冗余度，但通过增加码长提高了检错能力最小码距dmin=2,线性分组码,概念信息码元和监督码元可以使用线性方程联系主要性质任意两个需用码组之和（模2和）仍为需用码组最小码距为非零码的最小码重先看一个例子构造一个（7，4）线性分组码，能纠正1位错误1位错误可能出现在7个码位中的任何一位上，错误的情形有7种，加上无错，共8种状态需要知识构造3位校正子，共8种组合，正好可以指示7种错误和无错的状态,线性分组码,任意设计一种错误位置和校正子的对应关系由上表得到校正子与各码元关系,线性分组码,由校正子关系确定编码方程，保证无误码及校正子为000，并由此解出监督码元的编码方程由此得到许用码组最小码距3纠1个错检2个错,线性分组码,纠错 对错误码组计算校正子，根据校正子与错误位置的对应关系纠正错误接收到的码字为1101110，计算校正子为100，对应错误位置为3，则译码输出为1100110,线性分组码,线性系统分组码的矩阵表示编码过程编码过程可以看成信息序列与一个矩阵的相乘，这个矩阵成为生成矩阵（n，k）线性分组码，A为n维行向量，X为信息序列构成的k维行向量，I为kXk的单位矩阵，Q为kXr的矩阵典型形式的生成矩阵，生成的一定是系统码,线性分组码,线性系统分组码的矩阵表示检错的矩阵表示出错的条件监督矩阵,线性分组码,线性系统分组码的矩阵表示校正子计算的矩阵表示接收信号的表示校正子的计算校正子与错误图样有确定的关系纠错：根据错误图样与校正子的关系确定错误位置进行纠正,线性分组码,线性系统分组码的矩阵表示校正子与误码位置的关系对于纠1比特错误的校正子（以书11-24的校验矩阵为例）,按上述矩阵方式构成的线性系统分组码的监督矩阵的每列实际上是按照码字顺序给出了每个比特的校验子！,线性分组码,利用矩阵构造线性系统分组码第一个问题：先构造生成矩阵还是监督矩阵？回顾第一个例子，监督矩阵确定了如何纠错，是构造者自己确定的，是根本，因此先确定监督矩阵线性系统码的监督矩阵的形式是确定的，要确定的是QQ的列确定了信息位的校验子（可任意确定，各列不同，且须与I中的列不同），I确定了监督位的校验子,线性分组码,利用矩阵构造线性系统分组码第二步：由监督矩阵得到生成矩阵第三步：由生成矩阵可得许用码组,线性分组码,线性分组码的分析（n. k）中n和k如何确定只考虑纠正一位错误线性分组码的基本思想：用校正子指示错误位置校正子有r位，可以指示的错误图样线性分组码码长为n位，如果只考虑一位错误，共有错误情况n种，还需要一种指示用于表征没出错，共需指示n+1种情况能够纠正1位错误需要满足的关系式,等号成立时的特殊情况的码称为汉明码,线性分组码,线性分组码的分析考虑纠正t位错误按照同样的分析，可得到信息码元的位数（d为最小码距）线性分组码存在的界吉尔伯特界,汉明界，r的最小值,普洛特金界，k的最大值,吉尔伯特界，r的最大值,线性分组码,汉明码（hanming）能纠正单个错误的线性分组码码长监督码位信息码位最小码距码率,循环码,概念是一种线性分组码，通常是系统码具有循环性质，即需用码组经过若干位的循环移位后仍未需用码组实现简单，可用带反馈的移位寄存器实现纠错能力强，可纠正突发错误循环码的数学描述方式多项式矩阵二元域上的预算：加法和乘法，注意与普通的数学上的多项式运算的不同,循环码,循环码的循环性循环码的多项式表示,循环码,循环码的循环性左移一位与循环码的多项式表示相比较，上式显然不能表示一个循环码组，对这一表达式进行变形,余式可以表示一个新的码字，是循环左移一位形成的新的码字,循环码,循环码的循环性左移k位的情况按循环码的循环特性，新的码字可以描述为按照二指域的多项式计算验证上式,循环码,循环码的循环性循环性的一般描述循环码的构造信息码组的多项式表示为M(D)，则循环码编码后的码组多项式为g(D)为生成多项式g(D)是n-k阶多项式G(D)能被 整除,循环码,循环码的构造生成多项式每一个g(D)对应一个循环码，阶数低于n且能被g(D)整除的一组多项式就构成一个循环码循环码（n,k)的构造：给定g(D)，根据g(D)的阶数确定M(D)的最高阶数，所有M(D)和g(D)相乘得到的就是循环码的许用码组g(D)寻找： 的因式保证循环性,循环码,循环码的构造一个例子,循环码,循环码的生成矩阵和监督矩阵,非系统码！如何变成系统码？,循环码,循环码的生成矩阵和监督矩阵系统循环码的矩阵形式应该什么样子？,？,G(D)如何构造，保证循环性？,循环码,循环码的生成矩阵和监督矩阵考虑系统码的码多项式如果生成多项式为g(D)，由循环码的生成规则可知g(D)和r(D)的阶数相同，则按照二值域上的运算规则有考虑k个特殊的信息码字，即只有一个1的k个特殊码字有对应的监督码多项式由此，生成矩阵的每行对应的码多项式,就是我们希望的！,循环码,循环码的生成矩阵和监督矩阵总结系统码的生成矩阵根据g(D)求各行r(D);由各行r(D)，根据标准形式写出生成矩阵系统码的监督矩阵,循环码,系统循环码的编码器系统循环码的码多项式只需要求出r(D)系统循环码的编码可以采用多项式长除的方法，利用线性反馈移位寄存器实现,循环码,循环码的译码定义误差多项式校正子的定义和计算,和编码一样，可用反馈移位寄存器,循环码,循环码的译码由校正子确定错误图样例如：对于1位错误，如错误在第i位，则校正子为译码结果,循环码,循环码的译码,BCH码,上述循环码有一个问题没有讲？循环码的码距循环码是线性分组码，线性分组码的码距的求解方法可以直接应用码距和生成多项式的关系如何？确定码距后能否快速确定生成多项式？BCH码的特点BCH码是循环码具有纠多个随机错误的能力 构造容易由码的最小距离，可以很快得到码的生成多项式,BCH码,本原BCH码码长为生成多项式最小码距,LCM：最小公倍数：最小多项式,由码长及码距可快速确定生成多项式,线性分组码的扩展与缩短,线性分组码的扩展在原有码组基础上增加一位校验位，对所有码字进行校验，码距增加1扩展线性分组码的监督矩阵扩展循环码的生成多项式,线性分组码的扩展与缩短,缩短线性分组码(n,k)线性分组码的码长和信息位同时缩短s位，形成新的(n-s,k-s)分组码为缩短线性分组码缩短线性分组码的监督矩阵：去掉元监督矩阵的前s列即可,交织编码,为什么要采用交织？前述的线性分组码只能纠正零散随机错误通信系统中往往存在不可抗拒的突发错误无线信道的衰落引起的误码突发强干扰引起的错误如何对抗突发的的错误思想：将突发错误化解为零散的错误交织编码,交织编码,交织的基本思想,交织编码,交织编码的基本原理为了对付突发的信道差错，交织器改变发送码元的时间顺序将原本相邻的码元在时间上的距离最大化时间上相邻的突发错误属于不同的码组，可分别纠错,交织编码,交织码的纠错能力交织码的结构码组方阵行：分组码的一个码组列：交织的深度i纠错能力分组码：纠正t个随机错误交织码：纠正tXi个突发错误分组码：纠正b个突发错误交织码：纠正bXi个突发错误,交织编码,交织码的解码竖着写入，横着读出交织的代价：延时增大,其他信道编码,常用其他编码RS码非二进制BCH码，常用语纠正突发误码Turbo码两个简单编码器通过伪随机交织器并行级联，多次迭代译码，具有接近香农极限的性能，很复杂LDPC码低密度奇偶校验码，性能更优于Turbo，复杂CRC码强检错功能，常用于数据网络喷泉码,纠错码的误码性能,编码增益的来源编码增益加纠错和不加纠错时，达到同样误码率时的信噪比之差加信道编码后的损失由于码率增加，在相同的总功率下，每个比特的平均功率或能量减小，导致误码率增大未编码误比特率编码后误比特率,纠错码的误码性能,编码增益的来源加信道编码后的增益译码后误码减少，达到相同的译码后误比特率所需的译码前误比特率增大，即译码前误比特率要求可降低，所需的信噪比减小未加信道编码时，误码组率加信道编码后的误码组率和近似比特率,纠错码的误码性能,编码增益在相同的码率情况下，码长越长，编码增益越高绝大多数情况系，信道编码可获得增益,本讲回顾,信道编码的概念差错控制的几种方法及其优缺点反馈检验检错重发前向纠错信道编码的基本原理检错的基本原理纠错的基本原理检错和纠错能力与码距的关系线性分组码概念,本讲回顾,基本构造方法生成矩阵、监督矩阵编码、译码的方法汉明码循环码概念、特点生成多项式、系统码生成矩阵、监督矩阵基于长除的编码方法BCH码的构造交织概念,本章回顾,交织码的编解码交织码的抗差错能力,作业,第一次作业：11.1，11.2，11.7第二次作业：11.3，11.9，11.10,
