第七讲差错控制编码课件

现代通信原理

2010.9~2011.1现代通信原理

2010.9~2011.1主要内容差错编码的概念差错控制的基本方法线性分组码的概念及基本原理汉明码循环码BCH码交织的概念为什么要进行差错编码？差错控制的几种基本方法各有何优缺点？如何构造一个汉明码？如何构造循环码？如何构造BCH码？为什么要采用交织？主要内容差错编码的概念为什么要进行差错编码？研究对象研究对象在数字通信系统中的位置研究对象研究对象在数字通信系统中的位置3差错控制为什么要采用差错控制噪声所导致的传输差错与信息可靠传输需求的矛盾在普通通信设备中，噪声是不可消除的此外，码间串扰（ISI），多接入干扰（MAI）和邻小区干扰（ICI）等均可能导致误码匹配滤波，最佳判决等手段均不可能消除差错问题：是否可能实现可靠传输？或者至少降低传输的差错率？解决问题的方法：差错控制差错控制为什么要采用差错控制差错控制的基本方法三种基本方法反馈检验检错重发ARQ前向纠错FEC反馈检验——最原始的差错控制需要双向信道，和前向信道有相同的通信容量引入较大的停顿，不实时反馈信道可靠时，可以纠正任何错误差错控制的基本方法三种基本方法差错控制的基本方法检错重发——网络常用的方式差错判决放在接收端，只反馈差错状态自动请求重发，有效减少反馈量同样难以适用于实时业务多种实现方式——停发等候、返回重发、选择重发差错控制的基本方法检错重发——网络常用的方式差错控制的基本方法前向纠错FEC无需反馈信道直接在接收端对错误进行纠正，发端无需知道错误的状态适用于实时业务无需重传，发端不用存储，收端即时解码，发送的速率恒定依靠纠错编码——信道编码通过在码流中引入有结构的冗余信息，纠正在传输中出现的错误差错控制的基本方法前向纠错FEC信道编码一个简单的例子对称二进制信道BSC1个比特，只传1次，差错概率1个比特，重复传送3次，接收端做多数判决，错误概率付出或代价：增加了传输的冗余，降低了传输的效率收入或增益：提高了传输的可靠性，降低了误码率信道编码一个简单的例子付出或代价：增加了传输的冗余，降低了传信道编码概念ChannelCoding：通过合理的增加冗余信息，纠正信道传输中可能出现的错误，也称为纠错码：ErrorCorrectionCoding信道编码的评价标准纠错性能——能纠正什么样的错误？能纠正多少错误？最终的误比特率性能如何？代价——增加了多少冗余的比特？信息比特占整个码流的百分比即码率如何？纠错码的理论基础基于代数理论的结构，便于译码信道编码概念信道编码重要性信息系统不可或缺的重要技术移动通信深空通信与探测可靠计算存储设备…信道编码重要性信道编码的分类按功能分检错码：仅能检错纠错码：仅能纠错按信息码元和监督码元之间的校验关系分线性码：监督码元与信息码元之间线性关系非线性码：监督码元与信息码元之间非线性关系按信息码元和监督码元之间的约束方式分分组码：监督码元仅与当前码组相关卷积码：监督码元与当前及以前码组都有关系按照信息码元在编码后是否保持原来形式系统码：信息码元编码后不变非系统码：信息码元改变信道编码的分类按功能分信道编码的香农定理有扰离散信道的编码定理存在噪声干扰的信道，若信道容量为C，只要发送端以低于C的速率R发送信息（R为输入到编码器的二进制码元速率），则一定存在一种编码方式，使编码的错误概率随着码长n的增加将按指数下降到任意小的值两个结论如码长及发送信息速率一定，可以通过增大信道容量，使错误概率减小如在信道容量及发送信息速率一定，可以通过增加码长，使错误概率减小给出了努力的方向，但怎么做？信道编码的香农定理有扰离散信道的编码定理给出了努力的方向，但信道编码的基本原理看一个例子如用三位二进制编码来代表八个字母

000 A 100 E 001 B 101 F 010 C 110 G 011 D 111 H

不管哪一位发生错误，都会使传输字母错误如用三位二进制码传四个字母

000 A 011 B 101 C 110 D发生一位错误，准用码字将变成禁用码字，接收端就能知道出错，但是不能纠错。信道编码的基本原理看一个例子信道编码的基本原理如用三位二进制码传二个字母

000 A 111 B 检两个错误，纠正一个错误。结论具有检错或纠错的码组，其所用的比特数必须大于信息码组原来的比特数，引入冗余度；引入的冗余必须具有一定的结构，才能进行检错及纠错信道编码的基本原理如用三位二进制码传二个字母信道编码的基本原理几个基本概念码字二进制序列码重(weight)一个码组中“1”的数目码距(distance)

两个码组之间对应位置上1、0不同的位数 又叫汉明(Hamming)距

10110码重：3 01100 码重：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分组码水平奇偶监督码24线性分组码概念信息码元和监督码元可以使用线性方程联系主要性质任意两个需用码组之和（模2和）仍为需用码组最小码距为非零码的最小码重先看一个例子构造一个（7，4）线性分组码，能纠正1位错误1位错误可能出现在7个码位中的任何一位上，错误的情形有7种，加上无错，共8种状态需要知识构造3位校正子，共8种组合，正好可以指示7种错误和无错的状态 线性分组码概念线性分组码任意设计一种错误位置和校正子的对应关系由上表得到校正子与各码元关系线性分组码任意设计一种错误位置和校正子的对应关系26线性分组码由校正子关系确定编码方程，保证无误码及校正子为000，并由此解出监督码元的编码方程由此得到许用码组最小码距3纠1个错检2个错线性分组码由校正子关系确定编码方程，保证无误码及校正子为00线性分组码纠错对错误码组计算校正子，根据校正子与错误位置的对应关系纠正错误 接收到的码字为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位错误需要满足的关系式等号成立时的特殊情况的码称为汉明码线性分组码线性分组码的分析——（n.k）中n和k如何确定等线性分组码线性分组码的分析考虑纠正t位错误按照同样的分析，可得到信息码元的位数（d为最小码距）线性分组码存在的界——吉尔伯特界汉明界，r的最小值普洛特金界，k的最大值吉尔伯特界，r的最大值线性分组码线性分组码的分析汉明界，r的最小值普洛特金界，k的线性分组码汉明码（hanming）能纠正单个错误的线性分组码码长监督码位信息码位最小码距码率线性分组码汉明码（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)，由循环码的生成规则可知g(D)和r(D)的阶数相同，则按照二值域上的运算规则有考虑k个特殊的信息码字，即只有一个1的k个特殊码字有对应的监督码多项式由此，生成矩阵的每行对应的码多项式就是我们希望的！循环码循环码的生成矩阵和监督矩阵就是我们希望的！循环码循环码的生成矩阵和监督矩阵总结系统码的生成矩阵根据g(D)求各行r(D);由各行r(D)，根据标准形式写出生成矩阵系统码的监督矩阵循环码循环码的生成矩阵和监督矩阵循环码系统循环码的编码器系统循环码的码多项式只需要求出r(D)系统循环码的编码可以采用多项式长除的方法，利用线性反馈移位寄存器实现循环码系统循环码的编码器循环码循环码的译码定义误差多项式校正子的定义和计算和编码一样，可用反馈移位寄存器循环码循环码的译码和编码一样，可用反馈移位寄存器循环码循环码的译码由校正子确定错误图样例如：对于1位错误，如错误在第i位，则校正子为译码结果循环码循环码的译码循环码循环码的译码循环码循环码的译码BCH码上述循环码有一个问题没有讲？循环码的码距循环码是线性分组码，线性分组码的码距的求解方法可以直接应用码距和生成多项式的关系如何？确定码距后能否快速确定生成多项式？BCH码的特点BCH码是循环码具有纠多个随机错误的能力构造容易由码的最小距离，可以很快得到码的生成多项式BCH码上述循环码有一个问题没有讲？BCH码本原BCH码码长为生成多项式最小码距

LCM：最小公倍数：最小多项式由码长及码距可快速确定生成多项式BCH码本原BCH码LCM：最小公倍数由码长及码距可快速确定线性分组码的扩展与缩短线性分组码的扩展在原有码组基础上增加一位校验位，对所有码字进行校验，码距增加1扩展线性分组码的监督矩阵扩展循环码的生成多项式线性分组码的扩展与缩短线性分组码的扩展线性分组码的扩展与缩短缩短线性分组码(n,k)线性分组码的码长和信息位同时缩短s位，形成新的(n-s,k-s)分组码为缩短线性分组码缩短线性分组码的监督矩阵：去掉元监督矩阵的前s列即可线性分组码的扩展与缩短缩短线性分组码交织编码为什么要采用交织？前述的线性分组码只能纠正零散随机错误通信系统中往往存在不可抗拒的突发错误无线信道的衰落引起的误码突发强干扰引起的错误…如何对抗突发的的错误思想：将突发错误化解为零散的错误交织编码交织编码为什么要采用交织？交织编码交织的基本思想交织编码交织的基本思想交织编码交织编码的基本原理为了对付突发的信道差错，交织器改变发送码元的时间顺序将原本相邻的码元在时间上的距离最大化时间上相邻的突发错误属于不同的码组，可分别纠错交织编码交织编码的基本原理交织编码交织码的纠错能力交织码的结构——码组方阵行：分组码的一个码组列：交织的深度i纠错能力分组码：纠正t个随机错误——交织码：纠正tXi个突发错误分组码：纠正b个突发错误——交织码：纠正bXi个突发错误交织编码交织码的纠错能力交织编码交