第十一章纠错码709202925课件.ppt

1、第十一章 差错控制编码梅顺良现代通信原理2023/2/82008年春季学期 现代通信原理2通信的基本任务 将信息有效、可靠地由信源传递到信宿2023/2/82008年春季学期 现代通信原理3 教学目录u分组码u循环码uBCH码u纠正和监测突发错误的分组码u纠错码的误码性能2023/2/82008年春季学期 现代通信原理4差错控制概述通信的挑战误码误码分类u噪声引入的随机误码均匀分布u由干扰、快衰落引起的突发误码在一段时间内集中出现如何应对误码？u从信源编码的角度，用容错技术减小误码对性能的损伤；u从传输的角度，采用抗干扰能力强的调制方式；l如均衡，扰码u从信道编码的角度，采用差错控制技术。l如

2、纠错码，交织数字通信中，要求误码率 以下，必须进行差错控制8102023/2/82008年春季学期 现代通信原理5差错控制概述差错控制分类u反馈检验法u检错重发法（ARQ）u前向纠错（FEC）重点2023/2/82008年春季学期 现代通信原理6分组存储发收收发kIkI控制差错控制概述反馈检验法u缺点l需要双向信道。和前向通道要求有相同的通信容量。l引入较大的停顿。u优点l可以纠正任何错误。2023/2/82008年春季学期 现代通信原理7检错重发法（ARQ）u收端检测到错误后，自动请求重发。u需要反向信道，但容量可以降低。u也会引入停顿检错编码存储发收收发kIkI检错译码差错控制概述2023

3、/2/82008年春季学期 现代通信原理8前向纠错 Forward Error Correction（FEC）u优点l不需要双向信道l不会引入停顿u缺点l靠纠错编码实现，不保证纠正所有误码。差错控制概述2023/2/82008年春季学期 现代通信原理9差错控制编码基本原理引入受控的冗余u例：如用三位二进制编码来代表八个字母000 A100E001 B101F010C110G011D111H不管哪一位发生错误，都会使传输字母错误u如用三位二进制码传四个字母 000 A 011 B 101 C 110 D 发生一位错误，准用码字将变成禁用码字，接收端就能知道出错，但是不能纠错。差错控制概述无冗余，

4、所有码位都用于表示信息没发生错误时，不可能出现001，101，100，1112023/2/82008年春季学期 现代通信原理10差错控制编码基本原理引入受控的冗余u如用三位二进制码传二个字母 000 A 111B 可以检两个错误，纠正一个错误。u结论：具有检错或纠错的码组，其所用的比特数必须大于信息码组原来的比特数冗余度 差错控制概述若收到001，发送A的概率较大2023/2/82008年春季学期 现代通信原理11 例：1011 0 码重：301100 码重：2 二者码距：3差错控制编码基本概念u码重l一个码组中“1”的数目u码距l两个码组之间不同的码位的个数，也称汉明(Hamming)距 差

5、错控制概述2023/2/82008年春季学期 现代通信原理12检错/纠错能力u码距的几何解释u为检查出e个错误，要求最小码距为u为纠正t个错误，要求最小码距为u为纠正t个错误，同时检验出e个错误，要求最小码距为差错控制概述收到的码组与A和B距离相等码组A码组B汉明距d判为A判为Bmin1de 12min td)(1minteted2023/2/82008年春季学期 现代通信原理13纠错码的香农信息论基础u香农定理u结论l如码长及发送信息速率一定，可通过增大信道容量，使P小。l如在信道容量及发送信息速率一定，可通过增加码长，使错误概率下降。差错控制概述存在噪声干扰的信道，若信道容量为C，只要发送

6、端以低于C的速率R发送信息（R为输入到编码器的二进制码元速率），则一定存在一种编码方式，使编码的错误概率P随着码长n的增加将按指数下降到任一的值，即()nE RPe2023/2/82008年春季学期 现代通信原理14差错控制编码分类u按功能分l检错码 l纠错码l纠删码发现不可纠正的错误时，可发出指示或删除u按信息码元和监督码元之间的校验关系分l线性码l非线性码u按信息码元和监督码元之间的约束方式分l分组码l卷积码差错控制概述2023/2/82008年春季学期 现代通信原理15差错控制码示例(1)奇偶校验码u偶校验u奇校验差错控制概述01221 aaaaann信息位监督位00121aaaann1

7、0121aaaann当以上关系被破坏，则出现错误，因此能检查出奇数个错误，但不能检测偶数个错误最小码距为min2d这种码检错能力不高，采用什么方法提高呢？2023/2/82008年春季学期 现代通信原理16差错控制码示例(2)水平奇偶校验码和水平垂直监督码u水平奇偶校验码l检码字按行排成方阵，每行采用奇偶监督码，发送时按列的顺序传送，接收时仍将码字排列成发送时方阵形式，然后按行进行奇偶校验。l在不增加冗余度时，不仅能发现某一行上奇数个错误，而且也能发现不大于方阵行数的突发错误。u水平垂直奇偶校验码也称二维奇偶校验码l不仅对行进行奇偶校验，而且也对列进行奇偶校验。差错控制概述2023/2/820

8、08年春季学期 现代通信原理17差错控制概述已用于电报传输中差错控制码示例(3)等比码u在码长一定时，“1”码和“0”码的比例恒定。五中取三法：01011，11001，共 种许用码组，表示十位数字。3510C 2023/2/82008年春季学期 现代通信原理18 教学目录u差错控制概述u循环码uBCH码u纠正和检测突发错误的分组码u纠错码的误码性能2023/2/82008年春季学期 现代通信原理19表示：(n,k)n:帧长k/n:编码效率特点u监督码只用来监督本帧中的信息位分类u线性码 信息码与监督码之间为线性关系u非线性码 不存在线性关系kn-k信息位监督位n分组码2023/2/82008年

9、春季学期 现代通信原理20分组码第一种分组码汉明码(1)u能纠一个错误的分组码例：(7，4)汉明码6543210,a a a aa a a4个信息位3个监督位265416530643aaaaaaaaaaaa监督位的生成：2023/2/82008年春季学期 现代通信原理21分组码汉明码(2)在接收端，按如下规律运算034631356224561aaaaSaaaaSaaaaS1230123456001010100011101110111000SSSaaaaaaa错码位置无错）。称为校正子（或伴随式、因此应纠为：错误。，知道，运算后得到如收到的结果，就可以纠错。、根据3213321321000101

10、1100000011SSSaSSSSSS265416530643aaaaaaaaaaaa监督位的生成：2023/2/82008年春季学期 现代通信原理22分组码分组码的监督方程监督方程的矩阵形式000034613562456aaaaaaaaaaaa0001001101010101100101110123456Taaaaaaa无误码时，结果为0，有误码可能非0，用以“监督”是否有误码2023/2/82008年春季学期 现代通信原理23分组码监督矩阵u以上矩阵被称为典型形式(右边是单位矩阵)，各行一定是线性无关的。而一个非典型形式的经过运算可以化成典型形式，通过监督矩阵可以知道监督码和信息码的监督

11、关系。rrkrrrIPH,100110101010110010111单位阵2023/2/82008年春季学期 现代通信原理24分组码生成矩阵1101010111111000010000100001,QIGk265416530643(7 4)aaaaaaaaaaaa以，汉明码为例：P111010011010101011001r rH监督矩阵TPQ 通过生成矩阵可以得到生成码组。设输入码组为0011：10001110100110001 1001 1001 1 1 1000101010001011AG0011 00111102023/2/82008年春季学期 现代通信原理25分组码系统码u定义：信息

12、码字保持不变，监督位附加其后。典型生成矩阵u以上方式得到的生成矩阵称为典型生成矩阵。l由它产生的分组码必定为系统码；l典型矩阵每行一定是线性无关的，每行都是一个生成码组。10001110100110,00101010001011kGIQ生成矩阵单位阵，保持输入码字不变2023/2/82008年春季学期 现代通信原理26分组码再回到汉明码u汉明码监督位为 位，因此它可以组成 个可能情况，其中一个为无错。因此可以监督码位共 种。u要纠正一个错误，必须满足u最小码距完备码u如果 r 位监督位所组成的校正子码组与误码图样一一对应，这种码组称为完备码r2r21r12 ,12rknrr即3mind2023

13、/2/82008年春季学期 现代通信原理27分组码扩展汉明码u在汉明码基础上，再加上一位对所有码字进行(奇偶)校验的监督位l监督码字由 r 位增加到 r+1 位l信息位不变q码长 码结构q纠 1 位错，检测 2 位错 如（8，4），（16，11）rn2)12 ,2(rrr2023/2/82008年春季学期 现代通信原理28分组码扩展汉明码监督矩阵0001111HHE如(7,4)汉明码(8,4)汉明码2023/2/82008年春季学期 现代通信原理29分组码缩短汉明码u将码组前s位置为0，同时将监督矩阵的前s列去掉u码长缩短s，信息位减少s位l(n,k)(n-s,k-s)u生成矩阵在原来基础上去

14、掉前s行和前s列u缩短汉明码的最小码距至少和原来码的码距相同，因为监督位没有变。例如(15,11)(12,8)，监督矩阵 Hs 是将原 H 的前 3 列 去掉2023/2/82008年春季学期 现代通信原理30分组码分组码基本理论(1)u能纠 t 个错误的(n,k)码应满足u完备码：上述等式成立的(n,k)码为完备码u不同代数结构的线性码其纠错能力不同，能力和 有关，越大纠错能力越强。tiintnnnknrCCCC021122所有错误图样都能被监督码组涵盖mindmind2023/2/82008年春季学期 现代通信原理31分组码分组码基本理论(2)最小码距界限u上界：汉明界，普洛特金界u下界：

15、吉尔伯特界u问题：给定码长与编码效率，寻找 u例：,码长=63 的分组码设计从汉明界得，因此信息位最多可以取mindmin5d263min022(5,2)rn kiiCd纠 个错误22017,11n krnk最小监督位数63 11 52k 上界2023/2/82008年春季学期 现代通信原理32分组码分组码基本理论(3)最小码距界限 再通过吉尔伯特界求下界 所以，存在一种 的线性码。k 越接近 52，编码效率越高。20225,635,63 15 48drn riniCdnrk信息位 4852k5248k下界2023/2/82008年春季学期 现代通信原理33 教学目录u差错控制概述u分组码uB

16、CH码u纠正和检测突发错误的分组码u纠错码的误码性能2023/2/82008年春季学期 现代通信原理34循环码1957 年发现特点u是一种线性分组码u循环性任一许用码字经过循环移位后，得到的码组仍为一个许用码组如 是循环码的一许用码组 则 也是一许用码组 )(0123456aaaaaaa)(1234560aaaaaaa欲详细了解循环码的原理，请参见抽象代数有关书籍以及王新梅著纠错码原理与方法2023/2/82008年春季学期 现代通信原理35循环码循环码的多项式表示u码组码多项式例：码组 码多项式u左移一位u左移 i 位)(1012nnaaaaA)1011100(A)(0121aaaaAnn)

17、(121)(ininininiaaaaA121210()()nnnnA DaDaDa Da6432()A DDDDD(1)122301()()nnnnnADaDaDa Da()12121()()innnininin iADaDaDaDa 2023/2/82008年春季学期 现代通信原理36循环码循环码性质u若 是长度为n的循环码组，则 在按模 进行运算后，也是一个循环码组，也就是 用 多项式 除后所得之余式，即为所求的码组。()A D()iD A D1nD()iD A D1nD例：码组 左移 3 位 去除 得余式 如 左移 3 位后，得 是许用码组17D656510()A Da Da Da D

18、a398436510()D A Da Da Da Da D653254a Da Da Da1100101A0101110有限域GF(2)上元素的运算规则：11=1,10=01=00=0，1+1=0+0=0，0+1=1+0=1。(详见抽象代数有关书籍)2023/2/82008年春季学期 现代通信原理37循环码循环码生成多项式g(D)ug(D)是 D的(n-k)次即r 次多项式uK位信息码的信息多项式为M(D)，(k-1)次多项式111()101rrrig DDgDg Dg或1110()kkM DmDm Dm2023/2/82008年春季学期 现代通信原理38循环码循环码生成多项式g(D)u定理.

19、一个(n,k)的二进制循环码可以看成是唯一由它的生成多项式产生，即J如(7,3)循环码，n=7,k=3,r=4如果信息位为 010，M(D)=D生成码为 0111010()()()A DM D g D432()1g DDDD543()()()A DM D g DDDDD2023/2/82008年春季学期 现代通信原理39循环码循环码生成多项式g(D)u由于 k 位信息位共有 个码组，都可用此法产生，如果现有信息码 生成 k 个码字，且这 k 个码组都线性无关，用这 k 个码组作为一个矩阵G 的 k行 构成生成矩阵 G(D)2k120()()()1kkM DDM DDM DD12()()()1(

20、)kkDg DDg DG Dg D循环码的生成矩阵多项式2023/2/82008年春季学期 现代通信原理40循环码循环码举例(7,3)循环码432()1g DDDD24326542432543432432(1)()(1)1(1)1DDDDDDDDG DDDDDDDDDDDDDDD111010001110100011010G生成矩阵7 32023/2/82008年春季学期 现代通信原理41循环码系统循环码的生成矩阵和监督矩阵u以上方法构成的循环码并非是系统码u系统码的生成矩阵典型形式 u非系统码 系统码l生成矩阵l监督矩阵kGIQrTIQH列行NK2023/2/82008年春季学期 现代通信原理

21、42循环码系统循环码的生成矩阵和监督矩阵u系统码的码多项式为u例如，(7,4)码，信息位为1011()()()n kA DM DDr D32()1g DDD3()1M DDD3643()M DDDDD()()()()()n kDM Dr Dq Dg Dg D32326436535454221DDDDDDDDDDDDDDDD2()r DD监督位为101110111002023/2/82008年春季学期 现代通信原理43循环码系统循环码的生成矩阵和监督矩阵12()()()1()kkDg DDg DG Dg D1122()()()1()()()krnkrnrn kn in iDDrDDDrDG DD

22、rDrDg DD是除所得的余式100111001001110011101G非系统码系统码例：（7，3）码的生成矩阵2023/2/82008年春季学期 现代通信原理44循环码寻找循环码的生成多项式u循环码的生成多项式必须能除尽 ，即 ，h(D)是监督多项式，是k阶多项式u例：要构成(7,3)循环码，求g(D).解：g(D)应为4阶 都能生成(7,3)码q生成(7,6)循环码（奇偶校验码）q生成(7,1)循环码（重复码）1nD1()()nDg D h D 7323324234321(1)(1)(1)()(1)(1)1()(1)(1)1DDDDDDg DDDDDDDg DDDDDDD 或()1g D

23、D323()(1)(1)g DDDDD2023/2/82008年春季学期 现代通信原理45循环码循环码的编码器u原理：按系统码的生成方式：将信息码多项式升(n-k)次幂后，再除生成多项式，然后将余式置于升幂后的信息多项式之后。()()()n kA DM DDr D32()1g DDD()()()()()n kDM Dr Dq Dg Dg D以(7，3)码为例：编码器：2023/2/82008年春季学期 现代通信原理46循环码循环码的译码器u译码比编码复杂得多u译码分三步l第一步：伴随式S的计算l第二步：由S得到错误图样l第三步：纠正误码2023/2/82008年春季学期 现代通信原理47循环码

24、循环码的译码器u伴随式的计算l发送码组 l接收码组l误差码组校正子只与 E 有关，关键是计算校正子120nnAaaa120nnbbbb0,1,iiiiiieabeab如果则则BAE120nnEeeeBAETTTTT()SB HAEHAHEHEH2023/2/82008年春季学期 现代通信原理48循环码循环码的译码器u校正子S的计算()()Mod()S DB Dg D2023/2/82008年春季学期 现代通信原理49 教学目录u差错控制概述u分组码u循环码u纠正和检测突发错误的分组码u纠错码的误码性能2023/2/82008年春季学期 现代通信原理50BCH码1959年，Hocquenghem

25、 和 1960年，Bose&Ray-Chaudhuri分别提出。BCH码特点：u它属于循环码，有严格的代数结构；u具有纠多个随机错误的能力；u构造容易，编码简单；u纠错能力强，在中短码长下性能接近理论值。BCH码是迄今为止研究最详尽，分析最透彻，取得成果最多的码类之一。2023/2/82008年春季学期 现代通信原理51BCH码BCH码的代数理论基础u既约多项式(部分既约多项式参见教材表11-12)l一个 m 次多项式不能被二元域上任何次数小于m的，大于0的多项式除尽，如 是即约的。u本原多项式l能让m次多项式p(x)除尽 的最小正整数 n满足 则该多项式就称为本原的。l如 能除尽 ，但除不尽

26、 ，所以p(x)是本原的。l如 是即约的，但不是本原的，因它能除尽 。521DD1nx 21mn 4()1p xxx151x(115)n1nx 4321xxxx51x 2023/2/82008年春季学期 现代通信原理52BCH码本原循环码u由本原多项式构成的码称为本原码。u特点l码长为l它的生成多项式是由若干m阶或以m的因子为最高阶的多项式相乘而构成。21,mm为正整数(,),21,21mmn k nrnkk 要判定(n,k)的循环码是否存在，只需要判断 n-k 阶的生成多项式是否能由 的因式构成。1nD 2023/2/82008年春季学期 现代通信原理53BCH码本原码的一些结论u生成多项式

27、的阶次为r,该生成多项式由 的因式构成。u一个m阶即约多项式一定能除尽u如，m5，共有6个5阶即约多项式。u再加上 因子，是以上7个多项式的乘积。1nD 2111mnDD 525432542535321543111111DDDDDDDDDDDDDDDDDDDD(1)D311D2023/2/82008年春季学期 现代通信原理54BCH码BCH码的生成多项式ut为纠错个数，为最小多项式 为最小公倍数，由这种方式生成的循环码是BCH码u最小码距 uBCH码的分类l码长为 的BCH码称为 本原BCH码（狭义BCH码）l码长为 则称为非本原BCH码1321()LCM(),(),(),tg Dm D m

28、DmD)(DmiLCM21dt21mn 21mn 关于最小多项式和本原多项式的详细定义与判别方法，请参见抽象代数有关书籍2023/2/82008年春季学期 现代通信原理55BCH码BCH码的生成多项式u由于g(D)有t个因式，且每个因式的最高次为m，因此监督码元最多有mt位。u对于纠t 个错误的本原BCH码，其生成多项式u纠单个错误的本原BCH码为汉明码。1321()()()()tg Dm D m DmD表1113给出了 nn-k+1的错误，其中不可检测的这类错误只占 ；l（4）所有许用码阻码距dmin1的错误；l（5）所有奇数个随机错误。(1)2n k()2n k2023/2/82008年春

29、季学期 现代通信原理68纠正和检测突发错误的分组码循环冗余校验码（CRC）表11-16 常用的四种CRC码，已经成为国际标准。码生成多项式CRC-12CRC-16CRC-32CRC-CCITTD12+D11+D3+D2+D+1D16+D15+D2+1D16+D12+D5+1D32+D26+D23+D22+D16+D12+D11+D10+D8+D7+D5+D4+D2+D+12023/2/82008年春季学期 现代通信原理69 教学目录u差错控制概述u分组码u循环码uBCH码u纠正和检测突发错误的分组码2023/2/82008年春季学期 现代通信原理70纠错码的误码性能任何纠错码的能力都是有限的，

30、超出纠错码能力的错误不可能纠正，甚至会出现乱纠的现象。采用纠错后，误码性能有多大改善？由于纠错码种类很多，纠错能力各不相同，译码方法也不同，因此其性能必须根据具体分析和计算。影响纠错码性能的因素u码的代数结构u编码方法u译码方法u信道特性和误码种类 2023/2/82008年春季学期 现代通信原理71纠错码的误码性能两种基本信道中纠错码误码性能的计算uBSCl如果纠正 t 个随机错误，则 uAWGNl以BPSK为例 用(n,k)码纠错后，符号速率变为原来n/k倍11(1)niin ibneei tPiC PPn Pe是不加纠错时的误码率00cbEEknnn0(2/)ebPQEn002(2/)b

31、ecEkPQEnQnn2023/2/82008年春季学期 现代通信原理72纠错码的误码性能AWGN信道uPb减小，Pe增加，编码增益取决于二者的折中 Rb Rc Eb Ec 这时的功率要降低 Rb采用1/2编码时，Rc=2Rb Eb Eb，降低了3dB 编码增益 G=加纠错和不加纠错时，达到同样误码率时的信噪比之差2023/2/82008年春季学期 现代通信原理73本章知识要点信道编码的本质，冗余在其中的作用。前向纠错和反馈重传有什么特点，对编码性能的要求有什么不同。码长及编码效率，及它们与码性能之间的关系。什么是汉明距离，汉明距离与纠错能力和检错能力的关系。香农信道容量定理。线性分组码的生成矩阵、校验矩阵。2023/2/82008年春季学期 现代通信原理74本章知识要点系统循环码的编码器电路结构循环码的伴随式译码纠t个错的BCH码的设计方法误码率曲线读图交织码纠检突发错的原理