现代通信原理课件-曹志刚钱亚生-清华大学出版社-第11章

1、1 第第1111章章 差错控制编码和线性分组码差错控制编码和线性分组码2 11.1.1 差错控制分类差错控制分类差错控制分类差错控制分类差错控制分类差错控制分类 11.1.2 差错控制编码的基本原理差错控制编码的基本原理差错控制编码的基本原理差错控制编码的基本原理差错控制编码的基本原理差错控制编码的基本原理 11.1.3. 差错控制编码分类差错控制编码分类差错控制编码分类差错控制编码分类差错控制编码分类差错控制编码分类 3 11.111.1 概述概述误码分类误码分类噪声引入的随机误码，均匀分布由干扰、快衰落引起的突发误码如何减少误码？如何减少误码？从信源编码看，误码引起的性能恶化尽可能小，容错

2、技术从传输看，可采用抗干扰能力强的调制方式，信道特性不理想可采用均衡。特别需要差错控制技术。数字通信中，要求误码率108以下，必须采用差错控制。4 11.1.111.1.1 差错控制分类差错控制分类需要双向信道，和前向信道有相同的通信容。引入较大的停顿（不实时）。可以纠正任何错误。分组存储发收收发kIkI1. 反馈检验法反馈检验法5 2.2. 检错重发法检错重发法（ARQARQ）自动请求重发也需要反向信道，但容量可以降低，也会引入停顿检错编码存储发收收发kIkI检错译码63. 前向纠错前向纠错（FEC forward error corection）不需要双向信道不需要双向信道不会引入停顿靠纠

3、错编码7 11.1.2 11.1.2 差错控制编码的基本原理差错控制编码的基本原理如如用用三位二进制编码来代表八个字母三位二进制编码来代表八个字母000 A100E001 B101F010C110G011D111H不管哪一位发生错误，都会使传输字母错误如用三位字母传四个字母如用三位字母传四个字母000 A011B101 C 110D发生一位错误，准用码字将变成禁用码字，接收端就能知道出错，但是不能纠错。8 差错控制编码差错控制编码如用三位字母传二个字母如用三位字母传二个字母000 A111B检三个错误，纠正一个错误。结论结论具有检错或纠错的码组，其所用的比特数必须大于信息码组原来的比特数引入余

4、度。9 码重、码距码重、码距码重码重(weight) 一个码组中“1”的数目码距码距(distance) 两个码组之间对应位置上1、0不同的位数，又叫汉明(Hamming)距。1 0 1 1 0 码重：码重：30 1 1 0 0 码重：码重： 2 码距码距：310 检错、纠错能力检错、纠错能力1)1) 为为检查检查l l个错误，要求最小码距为个错误，要求最小码距为min1dl min21dtmin1()dltlt 2) 2) 为纠正为纠正t t个错误，要求最小码距为个错误，要求最小码距为3) 3) 为纠正为纠正t t个错误，并且检查出个错误，并且检查出l l个个 错误，要求最小码距为错误，要求

5、最小码距为1111.1.3.11.1.3. 差错控制编码分类差错控制编码分类按按功能分功能分 检错码 纠错码 纠删码（发现不可纠正的错误时，可发出指示或删除）按信息码元和监督码元之间的校验关系分按信息码元和监督码元之间的校验关系分 线性码 非线性码按信息码元和监督码元之间的约束方式分按信息码元和监督码元之间的约束方式分 分组码 卷积码12 香农理论香农理论香农定理香农定理存在噪声干扰的信道，若信道容量为C，只要发送端以低于C的速率R发送信息（R为输入道编码器的二进制码元速率），则一定存在一种编码方式，使编码的错误概率随着码长n的增加将按指数下降道任一的值，即nE RPe纠错码建立在香农理论基础

6、上 结论结论如码长及发送信息速率一定，可以通过增大信道容量，使P减小。如在信道容量及发送信息速率一定，可以通过增加码长，使错误概率下降。13 分组码分组码表示：表示： (n,k)n : 帧长帧长k/n : 编码效率编码效率特点特点监督码只用来监督本帧中的信息位分类分类线性码 信息码与监督码之间为线性关系非线性码 不存在线性关系14 奇偶监督码奇偶监督码如果以上关系被破坏，则出现错误，因此能检查出如果以上关系被破坏，则出现错误，因此能检查出奇数个错误，但不能检测偶数个错误。奇数个错误，但不能检测偶数个错误。最小码距为最小码距为 dmin=201221 aaaaann信息位监督位12100nnaa

7、aa12101nnaaaa偶监督偶监督奇监督奇监督思考：这种码检错能力不高，采用什么方法提高呢思考：这种码检错能力不高，采用什么方法提高呢？15水平奇偶监督码和水平垂直监督码水平奇偶监督码和水平垂直监督码又叫二维奇偶监督码又叫二维奇偶监督码水平奇偶监督码水平奇偶监督码检码字按行排成方阵，每行采用奇偶监督码，发送时按列的顺序传送，接收时仍将码字排列成发送时方阵形式，然后按行尽心奇偶校验。在不增加冗余度时，不仅发现某一行上奇数个错误，而且也能发现不大于方阵行数的突发错误。水平垂直奇偶监督码水平垂直奇偶监督码不仅对行进行奇偶校验，而且也对列进行奇偶校验。16 等比码等比码在码长一定时，在码长一定时，

8、“1”码和码和“0”码的比码的比例恒定。已用于电报传输中。例恒定。已用于电报传输中。五中取三五中取三0101111001表示十位数字，表示十位数字，C53=10种种许用码组。许用码组。17 分组码分组码 (1)(1)分组码的监督方程分组码的监督方程654265316430000aaaaaaaaaaaa6543210111010001101010010110010Taaaaaaa 矩阵形式矩阵形式18 分组码分组码 (2)(2)监督矩阵监督矩阵11101001101010,1011001r rr kr rHPIH矩阵称为典型形式，各行一定是线性无关的。而一个非典型形式的经过运算可以化成典型形式，

9、通过监督矩阵可以知道监督码和信息码的监督关系。19 分组码分组码 (3)(3)生成矩阵生成矩阵 ，通过生成矩阵可以得到生成码，通过生成矩阵可以得到生成码组。组。如果输入码组为如果输入码组为 001110001110100110,00101010001011kGIQTQP10001110100110001 1001 1001 1 1 1000101010001011AG20 分组码分组码 (4)(4)由这种方式得到的生成矩阵称为典型生成矩阵，由它产生的分组码必定为系统码，也就是信息码字保持不变，监督位附加其后，每行一定是线性无关的，每行都是一个生成码组。00110011 11021 汉明码汉明码

10、汉明码监督位为 位，因此它可以组成 个可能情况，其中一个为无错。因此可以监督码位共 要纠正一个错误，必须满足r2r21r21, 21rrnkr 即min3d最小码距最小码距如果 r 位监督位所组成的校正子码组与误码图样一一对应，这种码组称为完备码（取等号时）22 扩展汉明码扩展汉明码如果在汉明码基础上，再加上一位对所如果在汉明码基础上，再加上一位对所有码字进行校验的监督位有码字进行校验的监督位监督码字由 r 位增加到 r+1 位信息位不变 码长 码结构 纠 1 位错，检测 2 位错 如 （8，4），（16，11） 2rn (2 , 21)rrr 23 扩展汉明码矩阵扩展汉明码矩阵 111100

11、0EHH24 缩短汉明码缩短汉明码(n,k) (n,k) (n-s, k-s) (n-s, k-s)如如 (15,11)(15,11) (12,8) (12,8)监督矩阵监督矩阵 Hs Hs 是将是将原原 H H 的前的前 3 3 列列 去掉去掉缩短汉明码的最小码距至少和原来码缩短汉明码的最小码距至少和原来码的码距相同，因为监督位没有变。的码距相同，因为监督位没有变。25 线性码线性码能能纠纠 t 个错误的个错误的(n,k)应应满足满足120221trn ktinnnniCCCC 不同结构的线性码其纠错能力不同，不同结构的线性码其纠错能力不同，能力和能力和dmin 有关，有关，dmin 越大越

12、好。越大越好。取等号时为完备码取等号时为完备码26 最小码距界限最小码距界限上界：上界： 汉明界，汉明界， 普洛特金界普洛特金界下界：下界： 吉尔伯特界吉尔伯特界问题：问题： 给定码长与编码效率，寻找给定码长与编码效率，寻找 dmin例：例： dmin=5, 码长码长=63 的分组码设计的分组码设计从汉明界得，从汉明界得，263min022(5,2)rn kiiCd纠 个错误22017,11n krnk最小监督位数63 11 52 上界因此信息位最多可以取因此信息位最多可以取27 最小码距界限最小码距界限通过吉尔伯特界求下界通过吉尔伯特界求下界20225,635,63 15 48drn rin

13、iCdnr信息位 下界4852k线性码线性码 k 越接近越接近 52， 效率越高。效率越高。28 11.3 11.3 循环码循环码 (Cyclic code)(Cyclic code) 1957 年发现年发现特点特点线性分组码循环性任一许用码字经过循环移位后，得到的码组仍为一个许用码组 如 用码组 如6543210()a a a a a a a0654321()a a a a a a a是循环码的一许也是一许用码组29 码多项式表示码多项式表示码组码组码多项式码多项式码组码多项式左移一位左移一位左移左移i i位位1210()nnAaaa a121210( ) ()nnnnA Da Da DaD

14、 a(1011100)A 6432()A DDDDD2101()nnAaa a a(1)122301()()nnnnnADaDaDa Da121()nininin iAaaaa ( )12121()()innnininin iADaDaDaDa 30 循环码性质循环码性质 为许用码组，则为许用码组，则 也是也是许用码组许用码组性质性质若若 是长度为是长度为n的循环码组，则的循环码组，则 在按模在按模 进行运算后，也是一个进行运算后，也是一个循环码组，也就是循环码组，也就是 用用 多项式除后所得之余式，即为所求的码组。多项式除后所得之余式，即为所求的码组。 ()A D()()iiA DD A D

15、( )iD A D1nD ()A D( )iD A D1nD 31 循环码例子循环码例子码组码组左移左移 3 位位去除去除 得余式得余式如如 左移左移 3 位后，得位后，得 是许用码组是许用码组656510()A Da Da Da Da398436510()D A Da Da Da Da D71D 653254a Da Da Da1100101A010111032循环码生成多项式循环码生成多项式g(D)g(D)g(D) 是是 D的的 (n-k) 次即次即r 次多项式次多项式信息多项式为信息多项式为M(D),k 位，位，(k-1)次多次多项式项式111()101rrrig DDgDg Dg或11

16、10()kkM DmDm Dm33 g(D)Theo.一个一个(n,k) 的的二进制循环码可以二进制循环码可以看成是唯一由它的生成多项式产生，即看成是唯一由它的生成多项式产生，即J如如(7,3)循环码，循环码，n=7, k=3, r=4J如果信息位为 010， M(D)=D 生成码为 0111010()( ) ()A DM d g D432()1g DDDD543()() ()A DM D g DDDDD34 生成矩阵生成矩阵 G(D)G(D)由于由于 k 位信息位共有位信息位共有 个码组，都可用此个码组，都可用此法产生，如果现有信息码法产生，如果现有信息码 生成生成K个码字，且这个码字，且这

17、 k 个码字都线性无关，个码字都线性无关，用这用这 k 个码字作为一个矩阵个码字作为一个矩阵G 的的 k行行 构成生成矩阵构成生成矩阵 G(D)120()()()1kkM DDM DDM DD12()()()1()kkDg DDg DG Dg D2k35 (7,3)(7,3) 循环码循环码(7,3) 循环码循环码432()1g DDDD24326542432543432432(1)()(1)1 (1)1DDDDDDDDG DDDDDDDDDDDDDDD1110100( )01110100011010G D36 生成矩阵和监督矩阵生成矩阵和监督矩阵这样构成的循环码并非是系统码这样构成的循环码并非

18、是系统码系统码的生成矩阵典型形式系统码的生成矩阵典型形式 非系统码非系统码 系统码系统码生成矩阵监督矩阵1110100100 1110()0111010010 01110011010001 0001KIQG DkGIQTrHQI1 0 1 1 1 0 01 1 1 00 1 00 1 1 0 1 0 1H37 非系统码非系统码 系统码系统码系统码的码多项式为系统码的码多项式为例如，例如，(7,4)码，码，1011()()()n kA DM DDr D32()1g DDD3()1M DDD3643()M DDDDD()()()()()n kDM Dr Dq Dg Dg D323264365354

19、54221DDDDDDDDDDDDDDDD2()r DD监督位为1011101110038 非系统码非系统码 系统码系统码(7,3)码码12()()()1()kkDg DDg DG Dg D1122()()()1()()()krnkrnrn kn in iDDrDDDrDG DDrDrDg DD是除所得的余式1110100()01110100011010G D39 寻找生成多项式寻找生成多项式Theo. 循环码的生成多项式必须能除尽循环码的生成多项式必须能除尽 h(D)是监督多项式是监督多项式例：要构成例：要构成(7,3)循环码，求循环码，求g(D). 解：解：g(D)应为应为4阶阶 生成(7

20、,6)循环码 生成(7,1)循环码 1nD 1() ()nDg D h D 7323324234321 (1)(1)(1)( ) (1)(1)1( ) (1)(1)1DDDDDDg DDDDDDDg DDDDDDDD 或 ()1g DD323()(1)(1)g DDDDD40循环码的编码器循环码的编码器原理：按系统码的生成方式原理：按系统码的生成方式以以(7,4)码为例码为例 ()()()n kA DM DDr D32()1g DDD()()()()()n kDM Dr Dq Dg Dg DD1D2+D3+输入校验位码字输出41 循环码的译码器循环码的译码器译码比编码复杂得多译码比编码复杂得多

21、译码三步译码三步伴随式S的计算由S得到错误图样纠正42 伴随式的计算伴随式的计算发送码组发送码组 接收码组接收码组误差码组误差码组 校正子只与校正子只与 E 有关，根本是计算校正子有关，根本是计算校正子120nnAaaa120nnbbbbBAE120nnElll0,1,iiiiiilablab如果则则BAETTTTT()SB HAEHAHEHEH43 校正子校正子S S的计算的计算生成多项式生成多项式 g(D)去除接收码字去除接收码字B(D)()()Mod()S DB Dg D44 11.4 11.4 BCHBCH码码即约多项式即约多项式一个 m 次多项式不能被二元域上任何二次数小于的，但大于

22、0的多项式除尽，如 是即约的。本原多项式本原多项式若m次多项式P(x)除尽的 的最小正整数 n 满足 ，就称为本原的。如 能除尽 ，但除不尽 的 。如 ： 是即约的，但不是本原的，因它能除尽 。 521DD1nx 21mn 4( )1p xxx151x115n1nx 4321xxxx51x 4511.4.1 11.4.1 本原循环码本原循环码由本原多项式构成的码称为本由本原多项式构成的码称为本原码。原码。特点特点码长为它的生成多项式是由若干m阶或以m的因子为最高阶的多项式相乘而构成。要判定(n,k) 的循环码是否存在，只需要判断 n-k 阶的生成多项式是否能由 Dn+1的因式构成。 21,mm

23、为正整数46 循环码例子循环码例子生成多项式的阶次为生成多项式的阶次为 r, 该生成多项式是否该生成多项式是否是是 的因此一个的因此一个m阶即约多项式一定能阶即约多项式一定能除尽除尽如，如，m5，共有共有6个个5阶即约多项式。阶即约多项式。 再加上再加上 因子，因子， 是以上是以上7个多项式个多项式的乘积。的乘积。 ( , ),21,21mmn k nrnkk 1nD 2111mnDD 525432542535321543111111DDDDDDDDDDDDDDDDDDDD(1)D311D47 11.4.2 BCH 11.4.2 BCH 码的生成多项式码的生成多项式如果循环码形式的形式为如果循

24、环码形式的形式为 为纠错个数 ， 为最小多项式， 为最小公倍数最小码距 码长为 的BCH码称为本BCH码（侠义） 码长为 则称为非本原BCH码1321()LCM(),(),(),tg Dm D m DmD()im DLCMt21mn 21mn 21dt48 BCH BCH 码码由于由于g(D)g(D)有有t t个因式，且每个因式的最高次个因式，且每个因式的最高次为为m m，因此监督码元最多有因此监督码元最多有mtmt位。位。对于纠对于纠t t 个错误的本原个错误的本原BCHBCH码，其生成多项码，其生成多项式式纠单个错误的本原纠单个错误的本原BCHBCH码字为汉明码。码字为汉明码。表1113给

25、出了 n5的本原BCH码。 11111414给出了部分非本原给出了部分非本原BCHBCH码。码。1321()()()()tg Dm D m DmD49 BCH BCH 码例子码例子纠正纠正 3 个错误，码长为个错误，码长为15的的BCH码码解：解：n=15, m=5 查表查表11-12得，得，233707 这是这是(15,5)码。码。 13544322108542()()()()(1)(1)(1)1g Dm D m D m DDDDDDDDDDDDDDD50 重要的重要的BCHBCH码码 (23,12)(23,12)表表11111414中最重要的中最重要的BCHBCH码码是是(23,12)(2

26、3,12)称为格雷码，码间为称为格雷码，码间为7 7，能纠正，能纠正3 3个错误。个错误。生成多项式生成多项式在实际通信系统中，所要求的在实际通信系统中，所要求的n n、k k并不是并不是码表中所推荐的值，在这时我们可以采用码表中所推荐的值，在这时我们可以采用缩短或扩展的方式加以修正，也就是通过缩短或扩展的方式加以修正，也就是通过增加信息符号或校验符号来增加码组长度，增加信息符号或校验符号来增加码组长度，或减少信息和校验位来减少码组长度。或减少信息和校验位来减少码组长度。119765()1g DDDDDDD51 BCHBCH码码如 BCH码的码长为奇数，而有时需要偶数码长，这时可以在原BCH码

27、生成多项式中乘以（D+1)因子，从而得到（n+1,k）扩展BCH码，这时相当于在原BCH码上加一个全校验位，从而将码距增加1，这时的码字不具有循环性。如果BCH码不是2m-1或它的因式，这时可以采用缩短的方式，去掉s位信息，(n-s , k-s)52 RS RS码码 Reed-SolomonReed-Solomon非二进制非二进制BCH码，输入以符号来考虑码，输入以符号来考虑假定每组有假定每组有 K 个符号，每个符号用个符号，每个符号用m比特，比特，输入信息将是输入信息将是 Km 比特。比特。53 RSRS码码RS码适合于纠正突发错误，纠正的错误图样码适合于纠正突发错误，纠正的错误图样有有对于

28、一个长度为 符号的RS码，每个符号都可以看成是有限域 中的一个元素，如RS码的最小码距为d符号，则生成多项式111(1)1(3)13(21)21btmbtmbtimii总长度为比特的单个突发总长度为比特的 个突发总长度为比特的 个突发21m(2 )mGR231()()()()()dg DDDDD()imGR是中的一个元素54 11.5 11.5 纠正和检测突发错误的分组码纠正和检测突发错误的分组码 交织码交织码interleavedinterleaved在水平垂直监督码中将信息码排列成方阵，然后对行和列分别进行检验，可以达到检测突发错误的目的。如果方阵中行码是能纠 t 个随机错误，交织后能纠t个长度为i的突发错误。i称为交织深度。it55 循环码构成交织码循环码构成交织码采用循环码构成交织码时，可以不采用方采用循环码构