第七讲差错控制编码教学文案

现代(xiàndài)通信原理

2010.9~2011.1第一页，共69页。主要(zhǔyào)内容差错编码的概念差错控制的基本方法(fāngfǎ)线性分组码的概念及基本原理汉明码循环码BCH码交织的概念为什么要进行差错编码？差错控制的几种(jǐzhǒnɡ)基本方法各有何优缺点？如何构造一个汉明码？如何构造循环码？如何构造BCH码？为什么要采用交织？第二页，共69页。研究(yánjiū)对象研究(yánjiū)对象在数字通信系统中的位置第三页，共69页。差错控制为什么要采用差错控制噪声所导致的传输差错与信息可靠传输需求的矛盾在普通通信设备中，噪声是不可消除的此外，码间串扰（ISI），多接入干扰（MAI）和邻小区干扰（ICI）等均可能导致误码匹配滤波，最佳判决等手段均不可能消除差错问题：是否可能实现(shíxiàn)可靠传输？或者至少降低传输的差错率？解决问题的方法：差错控制第四页，共69页。差错控制的基本(jīběn)方法三种基本方法反馈(fǎnkuì)检验检错重发ARQ前向纠错FEC反馈(fǎnkuì)检验——最原始的差错控制需要双向信道，和前向信道有相同的通信容量引入较大的停顿，不实时反馈(fǎnkuì)信道可靠时，可以纠正任何错误第五页，共69页。差错控制的基本(jīběn)方法检错重发——网络常用的方式差错判决放在接收端，只反馈差错状态自动请求重发，有效减少反馈量同样难以适用于实时业务多种实现方式——停发等候(děnghòu)、返回重发、选择重发第六页，共69页。差错控制的基本(jīběn)方法前向纠错FEC无需反馈信道直接在接收端对错误进行纠正，发端无需知道错误的状态适用于实时业务无需重传，发端不用存储，收端即时解码，发送的速率恒定依靠纠错编码——信道编码通过在码流中引入有结构(jiégòu)的冗余信息，纠正在传输中出现的错误第七页，共69页。信道编码一个简单的例子对称二进制信道BSC1个比特，只传1次，差错概率1个比特，重复传送3次，接收端做多数判决(pànjué)，错误概率付出或代价：增加了传输的冗余，降低(jiàngdī)了传输的效率收入或增益：提高(tígāo)了传输的可靠性，降低了误码率第八页，共69页。信道编码概念ChannelCoding：通过合理的增加冗余信息，纠正信道传输中可能出现的错误，也称为纠错码：ErrorCorrectionCoding信道编码的评价标准纠错性能——能纠正什么样的错误？能纠正多少错误？最终的误比特率性能如何(rúhé)？代价——增加了多少冗余的比特？信息比特占整个码流的百分比即码率如何(rúhé)？纠错码的理论基础基于代数理论的结构，便于译码第九页，共69页。信道编码重要性信息系统不可或缺的重要技术移动通信深空通信与探测(tàncè)可靠计算存储设备…第十页，共69页。信道编码的分类(fēnlèi)按功能分检错码：仅能检错纠错码：仅能纠错按信息码元和监督码元之间的校验关系(guānxì)分线性码：监督码元与信息码元之间线性关系(guānxì)非线性码：监督码元与信息码元之间非线性关系(guānxì)按信息码元和监督码元之间的约束方式分分组码：监督码元仅与当前码组相关卷积码：监督码元与当前及以前码组都有关系(guānxì)按照信息码元在编码后是否保持原来形式系统码：信息码元编码后不变非系统码：信息码元改变第十一页，共69页。信道编码的香农定理(dìnglǐ)有扰离散信道的编码定理存在噪声干扰的信道，若信道容量为C，只要发送端以低于C的速率R发送信息（R为输入到编码器的二进制码元速率），则一定存在一种编码方式，使编码的错误概率随着码长n的增加将按指数下降到任意小的值两个结论如码长及发送信息速率一定，可以(kěyǐ)通过增大信道容量，使错误概率减小如在信道容量及发送信息速率一定，可以(kěyǐ)通过增加码长，使错误概率减小给出了努力的方向(fāngxiàng)，但怎么做？第十二页，共69页。信道编码的基本原理看一个例子如用三位二进制编码(biānmǎ)来代表八个字母 000 A 100 E 001 B 101 F 010 C 110 G 011 D 111 H不管哪一位发生错误，都会使传输字母错误如用三位二进制码传四个字母 000 A 011 B 101 C 110 D发生一位错误，准用码字将变成禁用码字，接收端就能知道出错，但是不能纠错。第十三页，共69页。信道编码的基本原理如用三位二进制码传二个字母 000 A 111 B 检两个错误，纠正一个错误。结论具有检错或纠错的码组，其所用的比特数必须大于信息码组原来的比特数，引入冗余度；引入的冗余必须具有一定的结构，才能(cáinéng)进行检错及纠错第十四页，共69页。信道编码的基本原理几个基本概念码字二进制序列(xùliè)码重(weight)一个码组中“1”的数目码距(distance) 两个码组之间对应位置上1、0不同的位数 又叫汉明(Hamming)距

10110码重：3 01100 码重：2 码距：3第十五页，共69页。信道编码的基本原理检错和纠错能力与码距的关系考虑码字000错成001，Hamming距1，概率(gàilǜ)错成101，Hamming距2，概率(gàilǜ)错成111，Hamming距3，概率(gàilǜ)总结两个码字的Hamming距离越大，则一个码字误判成另一个码字的可能性越小码距与检错、纠错能力紧密相关第十六页，共69页。信道编码的基本原理检错和纠错能力与码距的关系先考虑检测码字是否出错？——可检测e个误码一个码字出错后不会变成另一个正确的码字，即可判断出错；如果一个码字内出现e个错误(cuòwù)，则正确码字之间的间距必须大于e第十七页，共69页。信道编码的基本原理检错和纠错能力与码距的关系考虑单个码字的纠错——可纠正t个错误码字出现t个错误仍能正确判别(pànbié)的原则是：其他码字的各种错误情况不会进入到本码字t为半径的圆内；其他码字可能的最大圆的半径也为t，则要求正确码字之间的码距大于2t第十八页，共69页。信道编码的基本原理检错和纠错能力与码距的关系考虑既检错又纠错——检测e个错误，纠t个错误检测e个错误，要求码字间距大于e考虑纠t个错误，则此时间距要考虑的不是正确码字之间的距离。而是正确码字和可能的错误码字之间的距离，所以(suǒyǐ)在检错基础上还需要加t第十九页，共69页。信道编码的基本原理检错和纠错能力与码距的关系总结在一个码组内检测e个误码，则要求最小的码间距在一个码组内纠正(jiūzhèng)t个误码，则要求的最小码间距在一个码组内纠正(jiūzhèng)t个错误，同时检测e个错误，则要求的最小码间距第二十页，共69页。信道编码的基本原理信道编码的准则(zhǔnzé)可靠性准则(zhǔnzé)——能纠正更多的错误最大化最小码距有效性准则(zhǔnzé)给出尽可能多的需用码字码率尽可能高码率k/n，k为信息位数，n为总码长第二十一页，共69页。分组码概念编码后的码元序列每n为分为一组，其中k个信息码元，r个附加的监督码元，而且监督码元仅与本组的信息码元有关，而与其他(qítā)码组的的信息码元无关二进制序列分段，每段k个，针对每段按照一定规则附加r个监督码元分组码的优点容易以系统的数学理论进行建模分析实现电路简单，复杂度低线性分组码信息码元和监督码元之间的关系可以用线性方程表示第二十二页，共69页。分组码检错分组码的例子奇偶监督码偶监督奇监督如果以上关系被破坏，则出现错误，因此能检查(jiǎnchá)出奇数个错误，但不能检测偶数个错误。最小码距为dmin=2检错能力不高第二十三页，共69页。分组码水平奇偶(qíǒu)监督码将码字按行排成方阵，每行采用奇偶(qíǒu)监督码，发送时按列的顺序传送，接收时仍将码字排列成发送时方阵形式，然后按行进行奇偶(qíǒu)校验在不增加冗余度时，不仅能发现某一行上奇数个错误，而且也能发现不大于方阵行数的突发错误没有增加冗余度，但通过增加码长提高了检错能力最小码距dmin=2第二十四页，共69页。线性分组码概念信息码元和监督码元可以使用线性方程联系主要性质任意两个需用码组之和（模2和）仍为需用码组最小码距为非零码的最小码重先看一个例子构造一个（7，4）线性分组码，能纠正1位错误1位错误可能出现在7个码位中的任何(rènhé)一位上，错误的情形有7种，加上无错，共8种状态需要知识构造3位校正子，共8种组合，正好可以指示7种错误和无错的状态 第二十五页，共69页。线性分组码任意设计一种错误位置和校正子的对应关系(guānxì)由上表得到校正子与各码元关系(guānxì)第二十六页，共69页。线性分组码由校正子关系确定编码方程，保证无误码及校正子为000，并由此解出监督(jiāndū)码元的编码方程由此得到许用码组最小码距3纠1个错检2个错第二十七页，共69页。线性分组码纠错对错误码组计算校正子，根据校正子与错误位置的对应关系(guānxì)纠正错误 接收到的码字为1101110，计算校正子为100，对应错误位置为3，则译码输出为1100110第二十八页，共69页。线性分组码线性系统分组码的矩阵表示(biǎoshì)编码过程编码过程可以看成信息序列与一个矩阵的相乘，这个矩阵成为生成矩阵（n，k）线性分组码，A为n维行向量，X为信息序列构成的k维行向量，I为kXk的单位矩阵，Q为kXr的矩阵典型形式的生成矩阵，生成的一定是系统码第二十九页，共69页。线性分组码线性系统分组码的矩阵表示检错的矩阵表示出错的条件(tiáojiàn)监督矩阵第三十页，共69页。线性分组码线性系统分组码的矩阵表示校正子计算的矩阵表示接收信号的表示校正子的计算——校正子与错误图样有确定的关系纠错(jiūcuò)：根据错误图样与校正子的关系确定错误位置进行纠正第三十一页，共69页。线性分组码线性系统分组码的矩阵表示(biǎoshì)校正子与误码位置的关系对于纠1比特错误的校正子（以书11-24的校验矩阵为例）按上述矩阵方式构成的线性系统分组码的监督矩阵的每列实际上是按照码字顺序(shùnxù)给出了每个比特的校验子！第三十二页，共69页。线性分组码利用矩阵构造线性系统分组码第一个问题(wèntí)：先构造生成矩阵还是监督矩阵？回顾第一个例子，监督矩阵确定了如何纠错，是构造者自己确定的，是根本，因此先确定监督矩阵线性系统码的监督矩阵的形式是确定的，要确定的是QQ的列确定了信息位的校验子（可任意确定，各列不同，且须与I中的列不同），I确定了监督位的校验子第三十三页，共69页。线性分组码利用矩阵构造(gòuzào)线性系统分组码第二步：由监督矩阵得到生成矩阵第三步：由生成矩阵可得许用码组第三十四页，共69页。线性分组码线性分组码的分析——（n.k）中n和k如何确定只考虑纠正一位错误线性分组码的基本思想：用校正子指示错误位置(wèizhi)校正子有r位，可以指示的错误图样线性分组码码长为n位，如果只考虑一位错误，共有错误情况n种，还需要一种指示用于表征没出错，共需指示n+1种情况能够纠正1位错误需要满足的关系式等号成立(chénglì)时的特殊情况的码称为汉明码第三十五页，共69页。线性分组码线性分组码的分析考虑纠正t位错误按照(ànzhào)同样的分析，可得到信息码元的位数（d为最小码距）线性分组码存在的界——吉尔伯特界汉明界，r的最小值普洛特金界(jīnjiè)，k的最大值吉尔伯特界，r的最大值第三十六页，共69页。线性分组码汉明码（hanming）能纠正单个错误的线性分组码码长监督(jiāndū)码位信息码位最小码距码率第三十七页，共69页。循环码概念是一种线性分组码，通常是系统码具有循环性质，即需用码组经过若干位的循环移位后仍未需用码组实现简单，可用带反馈的移位寄存器实现纠错能力强，可纠正突发错误循环码的数学描述方式多项式矩阵二元域上的预算：加法和乘法，注意与普通(pǔtōng)的数学上的多项式运算的不同第三十八页，共69页。循环码循环码的循环性循环码的多项式表示(biǎoshì)第三十九页，共69页。循环码循环码的循环性左移一位与循环码的多项式表示相比较，上式显然(xiǎnrán)不能表示一个循环码组，对这一表达式进行变形余式可以(kěyǐ)表示一个新的码字，是循环左移一位形成的新的码字第四十页，共69页。循环码循环码的循环性左移k位的情况按循环码的循环特性，新的码字可以(kěyǐ)描述为按照二指域的多项式计算验证上式第四十一页，共69页。循环码循环码的循环性循环性的一般描述循环码的构造信息码组的多项式表示为M(D)，则循环码编码(biānmǎ)后的码组多项式为g(D)为生成多项式g(D)是n-k阶多项式G(D)能被整除第四十二页，共69页。循环码循环码的构造生成多项式每一个g(D)对应一个循环码，阶数低于n且能被g(D)整除的一组多项式就构成一个循环码循环码（n,k)的构造：给定g(D)，根据g(D)的阶数确定M(D)的最高阶数，所有(suǒyǒu)M(D)和g(D)相乘得到的就是循环码的许用码组g(D)寻找：的因式——保证循环性第四十三页，共69页。循环码循环码的构造(gòuzào)一个例子第四十四页，共69页。循环码循环码的生成矩阵(jǔzhèn)和监督矩阵(jǔzhèn)非系统(xìtǒng)码！如何变成系统(xìtǒng)码？第四十五页，共69页。循环码循环码的生成矩阵和监督矩阵系统循环码的矩阵形式应该什么(shénme)样子？？G(D)如何(rúhé)构造，保证循环性？第四十六页，共69页。循环码循环码的生成矩阵和监督矩阵考虑系统(xìtǒng)码的码多项式如果生成多项式为g(D)，由循环码的生成规则可知g(D)和r(D)的阶数相同，则按照二值域上的运算规则有考虑k个特殊的信息码字，即只有一个1的k个特殊码字有对应的监督码多项式由此，生成矩阵的每行对应的码多项式就是我们(wǒmen)希望的！第四十七页，共69页。循环码循环码的生成矩阵和监督矩阵总结系统码的生成矩阵根据(gēnjù)g(D)求各行r(D);由各行r(D)，根据(gēnjù)标准形式写出生成矩阵系统码的监督矩阵第四十八页，共69页。循环码系统循环码的编码器系统循环码的码多项式只需要求出r(D)系统循环码的编码可以采用多项式长除的方法，利用线性反馈(fǎnkuì)移位寄存器实现第四十九页，共69页。循环码循环码的译码定义(dìngyì)误差多项式校正子的定义(dìngyì)和计算和编码一样，可用反馈(fǎnkuì)移位寄存器第五十页，共69页。循环码循环码的译码由校正(jiàozhèng)子确定错误图样例如：对于1位错误，如错误在第i位，则校正(jiàozhèng)子为译码结果第五十一页，共69页。循环码循环码的译码第五十二页，共69页。BCH码上述循环码有一个问题没有讲？循环码的码距循环码是线性分组码，线性分组码的码距的求解方法可以直接应用码距和生成多项式的关系如何？确定码距后能否快速确定生成多项式？BCH码的特点BCH码是循环码具有(jùyǒu)纠多个随机错误的能力构造容易由码的最小距离，可以很快得到码的生成多项式第五十三页，共69页。BCH码本原(běnyuán)BCH码码长为生成多项式最小码距

LCM：最小公倍数：最小多项式由码长及码距可快速确定(quèdìng)生成多项式第五十四页，共69页。线性分组码的扩展(kuòzhǎn)与缩短线性分组码的扩展在原有码组基础上增加一位校验位，对所有(suǒyǒu)码字进行校验，码距增加1扩展线性分组码的监督矩阵扩展循环码的生成多项式第五十五页，共69页。线性分组码的扩展(kuòzhǎn)与缩短缩短线性分组码(n,k)线性分组码的码长和信息位同时缩短s位，形成新的(n-s,k-s)分组码为缩短线性分组码缩短线性分组码的监督(jiāndū)矩阵：去掉元监督(jiāndū)矩阵的前s列即可第五十六页，共69页。交织(jiāozhī)编码为什么要采用交织(jiāozhī)？前述的线性分组码只能纠正零散随机错误通信系统中往往存在不可抗拒的突发错误无线信道的衰落引起的误码突发强干扰引起的错误…如何对抗突发的的错误思想：将突发错误化解为零散的错误交织(jiāozhī)编码第五十七页，共69页。交织(jiāozhī)编码交织的基本(jīběn)思想第五十八页，共69页。交织(jiāozhī)编码交织编码的基本原理为了对付突发的信道差错，交织器改变(gǎibiàn)发送码元的时间顺序将原本相邻的码元在时间上的距离最大化时间上相邻的突发错误属于不同的码组，可分别纠错第五十九页，共69页。交织(jiāozhī)编码交织(jiāozhī)码的纠错能力交织(jiāozhī)码的结构——码组方阵行：分组码的一个码组列：交织(jiāozhī)的深度i纠错能力分组码：纠正t个随机错误——交织(jiāozhī)码：纠正tXi个突发错误分组码：纠正b个突发错误——交织(jiāozhī)码：纠正bXi个突发错误第六十页，共69页。交织(jiāozhī)编码交织码的解码(jiěmǎ)竖着写入，横着读出交织的代价：延时增大第六十一页，共69页。其他(qítā)信道编码常用其他编码RS码非二进制BCH码，常用语纠正突发误码Turbo码两个简单编码器通过伪随机交织器并行(bìngx