通信原理填空画图_百度文库
赠送免券下载特权
10W篇文档免费专享
部分付费文档8折起
每天抽奖多种福利
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
通信原理填空画图
&&通信原理填空画图
阅读已结束，下载本文需要
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，同时保存到云知识，更方便管理
加入VIP
还剩15页未读，
定制HR最喜欢的简历
你可能喜欢通信原理中的过调幅现象的图怎么画_百度知道
通信原理中的过调幅现象的图怎么画
我有更好的答案
过调是当ma大于1，ma为调幅指数或调幅度，波形和调幅基本相同，但有一段时间振幅为零，这是已调波的包络产生严重失真，且所占频带较宽。具体图我没有，网上也没找到，你可以看下张肃文的《高频电子线路》（高教出版社）P359的图
来自：求助得到的回答
采纳率：15%
好迅速，正想说去IT精英网上问问呢
为您推荐：
其他类似问题
通信原理的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。一碗面简笔画怎么画，步骤图一看就会_百度经验
&&&&&&书画/音乐一碗面简笔画怎么画，步骤图一看就会听语音1234567
百度经验:jingyan.baidu.com面是人们经常吃的食品，特别是一碗香喷喷的比如肉丝面牛肉面等，更加诱人。简笔画非常好画，步骤图非常简单。百度经验:jingyan.baidu.com铅笔中性笔或者彩笔等绘画本或者图画纸张等百度经验:jingyan.baidu.com1第一步画上一个椭圆形，注意中间厚两边薄2第二步画上碗里面的弧线3第三步画上碗外面的弧线，注意两边稍微薄一点，中间稍微厚一点4画上碗的底部，注意不要太直线，而是稍微弯曲，显得有立体感5画上碗里面的面条，注意先从一侧开始画起，而且线条要稍微弯曲，显得自然6第六步接着画另一团面条，注意方向要有所变化，这样看起来显得自然有趣7继续接着画另外的面团，线条要流畅，注意 不必太多，要简练8第八步为了使得画面更加完整或者温馨，可以适当添加相关的物象比如一双筷子等。END百度经验:jingyan.baidu.com注意用大的几何形来概括物体的轮廓线注意面团的组合关系，注意方向的变化经验内容仅供参考，如果您需解决具体问题(尤其法律、医学等领域)，建议您详细咨询相关领域专业人士。作者声明：本篇经验系本人依照真实经历原创，未经许可，谢绝转载。投票(0)已投票(0)有得(0)我有疑问(0)◆◆说说为什么给这篇经验投票吧！我为什么投票...你还可以输入500字◆◆只有签约作者及以上等级才可发有得&你还可以输入1000字◆◆如对这篇经验有疑问，可反馈给作者，经验作者会尽力为您解决！你还可以输入500字相关经验00000热门杂志第1期暑假和宝宝一起来折纸446次分享第1期可爱萌萌小盆栽592次分享第1期时尚DIY--各种手工花729次分享第5期花卉的养护和注意事项444次分享第4期废物巧利用786次分享◆请扫描分享到朋友圈当前位置： >>
《通信原理》
通信原理1通信原理第11章差错控制编码2第11章差错控制编码?11.1 概述?信道分类：从差错控制角度看随机信道：错码的出现是随机的 ? 突发信道：错码是成串集中出现的 ? 混合信道：既存在随机错码又存在突发错码??差错控制技术的种类检错重发 ? 前向纠错 ? 反馈校验 ? 检错删除?3第11章差错控制编码?差错控制编码：常称为纠错编码监督码元：上述4种技术中除第3种外，都是在接收 端识别有无错码。所以在发送端需要在信息码元序 列中增加一些差错控制码元，它们称为监督码元。 ? 不同的编码方法，有不同的检错或纠错能力。 ? 多余度：就是指增加的监督码元多少。例如，若编 码序列中平均每两个信息码元就添加一个监督码元， 则这种编码的多余度为1/3。 ? 编码效率(简称码率) ：设编码序列中信息码元数量 为k，总码元数量为n，则比值k/n 就是码率。 ? 冗余度：监督码元数(n-k) 和信息码元数 k 之比。 ? 理论上，差错控制以降低信息传输速率为代价换取 提高传输可靠性。?4第11章差错控制编码?自动要求重发(ARQ)系统?3种ARQ系统?发送码组停止等待ARQ系统3ACK112 23NAK4ACK5ACK5NAK6ACKACK 接收码组t3有错码组?345有错码组5 t??数据按分组发送。每发送一组数据后发送端等待接 收端的确认(ACK)答复，然后再发送下一组数据。 图中的第3组接收数据有误，接收端发回一个否认 (NAK)答复。这时，发送端将重发第3组数据。 系统是工作在半双工状态，时间没有得到充分利用， 传输效率较低。5第11章差错控制编码?拉后ARQ系统3 4 5 6 7重发码组重发码组发送数据1256789 10 11 9 10 11 12NAK9ACK1NAK5ACK5接收数据123456756789 10 11 9 10 11 12有错码组?有错码组发送端连续发送数据组，接收端对于每个接收到的数 据组都发回确认(ACK)或否认(NAK)答复。例如，图中第5组接收数据有误，则在发送端收到第5 组接收的否认答复后，从第5组开始重发数据组。 在这种系统中需要对发送的数据组和答复进行编号， 以便识别。显然，这种系统需要双工信道6??第11章差错控制编码?选择重发ARQ系统重发码组 重发码组发送数据1234567589 10 11ACK59 12 13 14ACK9ACK1 接收数据NAK5NAK91234567589 10 11有错码组9 12 1314有错码组?它只重发出错的数据组，因此进一步提高了传输效率。7第11章差错控制编码?ARQ的主要优点：和前向纠错方法相比? ??监督码元较少即能使误码率降到很低，即码率较高； 检错的计算复杂度较低； 检错用的编码方法和加性干扰的统计特性基本无关， 能适应不同特性的信道。?ARQ的主要缺点：?? ??需要双向信道来重发，不能用于单向信道，也不能用 于一点到多点的通信系统。 因为重发而使ARQ系统的传输效率降低。 在信道干扰严重时，可能发生因不断反复重发而造成 事实上的通信中断。 在要求实时通信的场合，例如电话通信，往往不允许 使用ARQ法。8第11章差错控制编码?ARQ系统的原理方框图???在发送端，输入的信息码元在编码器中被分组编码（加入 监督码元）后，除了立即发送外，还暂存于缓冲存储器中。 若接收端解码器检出错码，则由解码器控制产生一个重发 指令。此指令经过反向信道送到发送端。由发送端重发控 制器控制缓冲存储器重发一次。 接收端仅当解码器认为接收信息码元正确时，才将信息码 元送给收信者，否则在输出缓冲存储器中删除接收码元。 当解码器未发现错码时，经过反向信道发出不需重发指令。 发送端收到此指令后，即继续发送后一码组，发送端的缓 9 冲存储器中的内容也随之更新。第11章差错控制编码?11.2 纠错编码的基本原理?分组码基本原理：举例说明如下。?设有一种由3位二进制数字构成的码组，它共有8种不同 的可能组合。若将其全部用来表示天气，则可以表示8种 不同天气，例如：“000”（晴），“001”（云）， “010”（阴），“011”（雨）， “100”（雪），“101”（霜），“110”（雾），“111”（雹）。?其中任一码组在传输中若发生一个或多个错码，则将变 成另一个信息码组。这时，接收端将无法发现错误。10第11章差错控制编码?若在上述8种码组中只准许使用4种来传送天气，例如： “000”＝晴 ＝雨?“011”＝云 “101”＝阴“110”这时，虽然只能传送4种不同的天气，但是接收端却 有可能发现码组中的一个错码。 例如，若“000”（晴）中错了一位，则接收码组将变 成“100”或“010”或“001”。这3种码组都是不准使 用的，称为禁用码组。 接收端在收到禁用码组时，就认为发现了错码。当发 生3个错码时，“000”变成了“111”，它也是禁用码 组，故这种编码也能检测3个错码。 但是这种码不能发现一个码组中的两个错码，因为发 11 生两个错码后产生的是许用码组。???第11章差错控制编码?检错和纠错????上面这种编码只能检测错码，不能纠正错码。例如，当接 收码组为禁用码组“100”时，接收端将无法判断是哪一位 码发生了错误，因为晴、阴、雨三者错了一位都可以变成 “100”。 要能够纠正错误，还要增加多余度。例如，若规定许用码 组只有两个：“000”（晴），“111”（雨），其他都是禁 用码组，则能够检测两个以下错码，或能够纠正一个错码。 例如，当收到禁用码组“100”时，若当作仅有一个错码， 则可以判断此错码发生在“1”位，从而纠正为“000” （晴）。因为“111”（雨）发生任何一位错码时都不会变 成“100”这种形式。 但是，这时若假定错码数不超过两个，则存在两种可能性： “000”错一位和“111”错两位都可能变成“100”，因而只 能检测出存在错码而无法纠正错码。 12第11章差错控制编码?分组码的结构?? ?将信息码分组，为每组信息码附加若干监督码的编码称 为分组码 。 在分组码中，监督码元仅监督本码组中的信息码元。 信息位和监督位的关系：举例如下信息位监督位晴云 阴 雨0001 10 1101 1 013第11章差错控制编码?分组码的一般结构?分组码的符号：(n, k) ? N － 码组的总位数，又称为码组的长度（码长）， ? k － 码组中信息码元的数目， ? n C k ＝ r － 码组中的监督码元数目，或称监督位数目。14第11章差错控制编码?分组码的码重和码距? ?码重：把码组中“1”的个数目称为码组的重量，简称码重。 码距：把两个码组中对应位上数字不同的位数称为码组的 距离，简称码距。码距又称汉明距离。 例如，“000”＝晴，“011”＝云，“101”＝阴，“110”＝ 雨，4个码组之间，任意两个的距离均为2。 最小码距：把某种编码中各个码组之间距离的最小值称为 最小码距(d0)。例如，上面的编码的最小码距d0 = 2。??15第11章差错控制编码?码距的几何意义(0,1,1)a1(0,1,0)(1,1,0) (1,1,1)(0,0,0)(1,0,0) (1,0,1)a2a0? ?(0,0,1)对于3位的编码组，可以在3维空间中说明码距的几何意义。 每个码组的3个码元的值(a1, a2, a3)就是此立方体各顶点的坐 标。而上述码距概念在此图中就对应于各顶点之间沿立方体 各边行走的几何距离。16?由此图可以直观看出，上例中4个准用码组之间的距离均为2。第11章差错控制编码?码距和检纠错能力的关系??一种编码的最小码距d0的大小直接关系着这种编码的检错 和纠错能力 为检测e个错码，要求最小码距 d0 ? e + 1 【证】设一个码组A位于O点。若码组A中发生一个错码， 则我们可以认为A的位置将移动至以O点为圆心，以1为半 径的圆上某点，但其位置不会超出此圆。 若码组A中发生两位错码，则其位置不会超出以O点为圆 心，以2为半径的圆。因此，只要最小码距不小于3，码组 A发生两位以下错码时， 不可能变成另一个准用 0 1 2 3 码组，因而能检测错码 A B 汉明距离 的位数等于2。 ed017第11章差错控制编码同理，若一种编码的最小码距为d0，则将能检测(d0 - 1)个错 码。反之，若要求检测e个错码，则最小码距d0至少应不小于 ( e + 1)。?为了纠正t个错码，要求最小码距d0 ? 2t + 1【证】图中画出码组A和B的距离为5。码组A或B若发生不多于 两位错码，则其位置均不会超出半径为2以原位置为圆心的 圆。这两个圆是不重叠的。判决规则为：若接收码组落于以 A为圆心的圆上就判决收到的是码组A，若落于以B为圆心的 圆上就判决为码组B。这样，就能够纠正两位错码。0 A123 4td0B5 汉明距离t18第11章差错控制编码若这种编码中除码组A和B外，还有许多种不同码组，但任两 码组之间的码距均不小于5，则以各码组的位置为中心以2为 半径画出之圆都不会互相重叠。这样，每种码组如果发生不 超过两位错码都将能被纠正。因此，当最小码距d0＝5时，能 够纠正2个错码，且最多能纠正2个。若错码达到3个，就将 落入另一圆上，从而发生错判。故一般说来，为纠正t个错码， 最小码距应不小于(2t + 1)。19第11章差错控制编码?为纠正t个错码，同时检测e个错码，要求最小码距d0 ? e ? t ? 1(e ? t )在解释此式之前，先来分析下图所示的例子。图中码组A和B 之间距离为5。按照检错能力公式，最多能检测4个错码，即 e = d0 C 1 = 5 C 1 = 4，按照纠错能力公式纠错时，能纠正2个 错码。但是，不能同时作到两者，因为当错码位数超过纠错 能力时，该码组立即进入另一码组的圆内而被错误地“纠正” 了。例如，码组A若错了3位，就会被误认为码组B错了2位造 成的结果，从而被 错“纠”为B。这就 是说，检错和纠错 公式不能同时成立0 A 1 2 3 4 B 5 汉明距离td0t20或同时运用。第11章差错控制编码所以，为了在可以纠正t个错码的同时，能够检测e个错码， 就需要像下图所示那样，使某一码组（譬如码组A）发生e 个错误之后所处的位置，与其他码组（譬如码组B）的纠 错圆圈至少距离等于1，不然将落在该纠错圆上从而发生 错误地“纠正”。因此，由此图可以直观看出，要求最小 码距d0 ? e ? t ? 1A(e ? t )Bt e1t汉明距离这种纠错和检错结合的工作方式简称纠检结合。21第11章差错控制编码这种工作方式是自动在纠错和检错之间转换的。当错码数量 少时，系统按前向纠错方式工作，以节省重发时间，提高传 输效率；当错码数量多时，系统按反馈重发方式纠错，以降 低系统的总误码率。所以，它适用于大多数时间中错码数量 很少，少数时间中错码数量多的情况。22第11章差错控制编码?11.3 纠错编码的性能?系统带宽和信噪比的矛盾：?由上节所述的纠错编码原理可知，为了减少接收错误码 元数量，需要在发送信息码元序列中加入监督码元。这 样作的结果使发送序列增长，冗余度增大。若仍须保持 发送信息码元速率不变，则传输速率必须增大，因而增 大了系统带宽。系统带宽的增大将引起系统中噪声功率 增大，使信噪比下降。信噪比的下降反而又使系统接收 码元序列中的错码增多。一般说来，采用纠错编码后， 误码率总是能够得到很大改善的。改善的程度和所用的 编码有关。23第11章差错控制编码?编码性能举例?10-1未采用纠错编码时， 若接收信噪比等于 10-2 7dB，编码前误码率 约为8?10-4，图中A 10-3 点，在采用纠错编码 P e 后，误码率降至约4 -4 10 ?10-5，图中B点。这样， 不增大发送功率 就能 10-5 降低误码率约一个半 数量级。A??EB? 编码后 ? D ? C10-6 信噪比 (dB)24第11章差错控制编码?由图还可以看出，若 保持误码率在10-5， 图中C点，未采用编 码时，约需要信噪比 Eb / n0 = 10.5 dB。在 采用这种编码时，约10-1 10-2 10-3 Pe 10-4B A ? ?E需要信噪比7.5 dB，图中D点。可以节省功率 2 dB。通常称这2 dB为? 编码后 ? D ? C10-5 10-6编码增益。?上面两种情况付出的代 价是带宽增大。信噪比 (dB)25第11章差错控制编码?传输速率和Eb/n0的关系 对于给定的传输系统Eb PsT Ps P ? ? ? s n0 n0 n0 (1/ T ) n0 RB10-1 10-2A ? ?式中，RB为码元速率。 10-3 若希望提高传输速率， Pe 由上式看出势必使信 10-4 噪比下降，误码率增 大。假设系统原来工作 在图中C点，提高速率后 10-5 由C点升到E点。但加用 纠错编码后，仍可将误码 -6 10 率降到D点。这时付出的 代价仍是带宽增大。EB? 编码后 ? D ? C信噪比 (dB)26第11章差错控制编码?11.4简单的实用编码?11.4.1 奇偶监督码?奇偶监督码分为奇数监督码和偶数监督码两种，两者的 原理相同。在偶数监督码中，无论信息位多少，监督位 只有1位，它使码组中“1”的数目为偶数，即满足下式条 件： an?1 ? an?2 ??? a0 ? 0式中a0为监督位，其他位为信息位。 这种编码能够检测奇数个错码。在接收端，按照上式求 “模2和”，若计算结果为“1”就说明存在错码，结果为 “0”就认为无错码。 奇数监督码与偶数监督码相似，只不过其码组中“1”的 数目为奇数： an?1 ? an?2 ? ? ? a0 ? 127第11章差错控制编码?11.4.2 二维奇偶监督码（方阵码）?二维奇偶监督码的构成它是先把上述奇偶监督码的若干码组排成矩阵，每一码组写 成一行，然后再按列的方向增加第二维监督位，如下图所示1 1 1 a1 a ? a a n ?1 n?2 1 0 2 2 2 2 an a ? a a ?1 n?2 1 0??? c0m m m m an a ? a a ?1 n?2 1 0cn ?1 cn ? 2 ? c1图中a01 a02 ? a0m为m行奇偶监督码中的m个监督位。 cn-1 cn-2 ? c1 c0为按列进行第二次编码所增加的监督位，它 们构成了一监督位行。 28第11章差错控制编码?二维奇偶监督码的性能?这种编码有可能检测偶数个错码。因为每行的监督位虽然 不能用于检测本行中的偶数个错码，但按列的方向有可能 由cn-1 cn-2 ? c1 c0等监督位检测出来。有一些偶数错码不 可能检测出来。例如，构成矩形的4个错码，譬如图中2 2 m m an a a a ?2 1 n ?2 1错了，就检测不出。?这种二维奇偶监督码适于检测突发错码。因为突发错码常 常成串出现，随后有较长一段无错区间。?由于方阵码只对构成矩形四角的错码无法检测，故其检错 能力较强。二维奇偶监督码不仅可用来检错，还可以用来纠正一些错 码。 例如，仅在一行中有奇数个错码时。 29?第11章差错控制编码?11.4.3 恒比码?在恒比码中，每个码组均含有相同数目的“1”（和 “0”）。由于“1”的数目与“0”的数目之比保持恒定， 故得此名。 这种码在检测时，只要计算接收码组中“1”的数目是 否对，就知道有无错码。 恒比码的主要优点是简单和适于用来传输电传机或其 他键盘设备产生的字母和符号。对于信源来的二进制 随机数字序列，这种码就不适合使用了。??30第11章差错控制编码?11.4.4 正反码?正反码的编码：??它是一种简单的能够纠正错码的编码。其中的监督位数 目与信息位数目相同，监督码元与信息码元相同或者相 反则由信息码中“1”的个数而定。 例如，若码长n = 10，其中信息位 k = 5，监督位 r = 5。 其编码规则为： ? 当信息位中有奇数个“1”时，监督位是信息位的简 单重复； ? 当信息位有偶数个“1”时，监督位是信息位的反码。 ? 例如，若信息位为11001，则码组为；若 信息位为10001，则码组为。31第11章差错控制编码?正反码的解码?在上例中，先将接收码组中信息位和监督位按模 2 相加， 得到一个5位的合成码组。然后，由此合成码组产生一个 校验码组。 若接收码组的信息位中有奇数个“1”，则合成码组就是校 验码组；若接收码组的信息位中有偶数个“1”，则取合成 码组的反码作为校验码组。 最后，观察校验码组中“1”的个数，按下表进行判决及纠 正可能发现的错码。??32第11章差错控制编码?校验码组和错码的关系错码情况 无错码 信息码中有1位错码，其位置对应校验码组中“0” 的位置 监督码中有1位错码，其位置对应校验码组中“1” 的位置 错码多于1个校验码组的组成 1 2 3 4 全为“0” 有4个“1”和1个 “0” 有4个“0”和1个 “1” 其他组成例如，若发送码组为，接收码组中无错码， 则合成码组应为=00000。由于接收码组信 息位中有奇数个“1”，所以校验码组就是00000。按上表 判决，结论是无错码。33第11章差错控制编码若传输中产生了差错，使接收码组变成，则合成 码组为＝01000。由于接收码组中信息位有偶数 个“1”，所以校验码组应取合成码组的反码，即10111。由 于其中有4个“1”和1个“0”，按上表判断信息位中左边第2 位为错码。 若接收码组错成，则合成码组变成 ＝10000。由于接收码组中信息位有奇数个“1”，故校验码 组就是10000，按上表判断，监督位中第1位为错码。 最后，若接收码组为，则合成码组为 ＝01010，校验码组与其相同，按上表判断，这 时错码多于1个。?上述长度为10的正反码具有纠正1位错码的能力，并能检测 全部2位以下的错码和大部分2位以上的错码。 34第11章差错控制编码?11.5 线性分组码?基本概念代数码：建立在代数学基础上的编码。 ? 线性码：按照一组线性方程构成的代数码。在线性 码中信息位和监督位是由一些线性代数方程联系着 的。 ? 线性分组码：按照一组线性方程构成的分组码 。?本节将以汉明码为例引入线性分组码的一般原理。35第11章差错控制编码?汉明码～能够纠正1位错码且编码效率较高的一种线性分组码 ? 汉明码的构造原理。?在偶数监督码中，由于使用了一位监督位a0，它和信息 位an-1 … a1一起构成一个代数式：an?1 ? an?2 ??? a0 ? 0 在接收端解码时，实际上就是在计算S ? an?1 ? an?2 ? ? ? a0若S = 0，就认为无错码；若S = 1，就认为有错码。现将 上式称为监督关系式，S称为校正子。由于校正子S只有 两种取值，故它只能代表有错和无错这两种信息，而不 能指出错码的位置。36第11章差错控制编码?若监督位增加一位，即变成两位，则能增加一个类似的监督 11，故能表示4种不同的信息。若用其中1种组合表示无错， 则其余3种组合就有可能用来指示一个错码的3种不同位置。 同理，r个监督关系式能指示1位错码的(2r C 1)个可能位置。 一般来说，若码长为n，信息位数为k，则监督位数r＝n－k。 如果希望用r个监督位构造出r个监督关系式来指示1位错码的 n种可能位置，则要求r r 2 ? 1 ? n 或 2 ? k ? r ?1 下面通过一个例子来说明如何具体构造这些监督关系式。关系式。由于两个校正子的可能值有4中组合： 00，01，10，?37第11章差错控制编码?例：设分组码(n, k)中k = 4，为了纠正1位错码，由上式可知， 要求监督位数 r ? 3。若取 r = 3，则n = k + r = 7。我们用a6 a5? a0表示这7个码元，用S1、S2和S3表示3个监督关系式中 的校正子，则S1、S2和S3的值与错码位置的对应关系可以规 定如下表所列：S1 S2 S3 001 010 100 011错码位置 a0 a1 a2 a3S1 S2 S3 101 110 111 000错码位置 a4 a5 a6 无错码38第11章差错控制编码由表中规定可见，仅当一位错码的位置在a2 、a4、a5或a6时， 校正子S1为1；否则S1为零。这就意味着a2 、a4、a5和a6四个 码元构成偶数监督关系：S1 ? a6 ? a5 ? a4 ? a2同理， a1、a3、a5和a6构成偶数监督关系：S2 ? a6 ? a5 ? a3 ? a1以及a0、a3、a4 和a6构成偶数监督关系S3 ? a6 ? a4 ? a3 ? a039第11章差错控制编码?在发送端编码时，信息位a6、a5、a4和a3的值决定于输入 信号，因此它们是随机的。监督位a2、a1和a0应根据信息 位的取值按监督关系来确定，即监督位应使上3式中S1、 S2和S3的值为0（表示编成的码组中应无错码）：?a 6 ? a 5 ? a 4 ? a 2 ? 0 ? ?a6 ? a5 ? a3 ? a1 ? 0 ?a ? a ? a ? a ? 0 4 3 0 ? 6上式经过移项运算，解出监督位? a 2 ? a 6 ? a5 ? a 4 ? ?a1 ? a6 ? a5 ? a3 ?a ? a ? a ? a 6 4 3 ? 0给定信息位后，可以直接按上式算出监督位， 结果见下表： 40第11章差错控制编码信息位 a6 a5 a4 a3 10 01
监督位 a2 a1 a0 000 011 101 110 110 101 011 000 信息位 a6 a5 a4 a3 10 01
监督位 a2 a1 a0 111 100 010 001 001 010 100 11141第11章差错控制编码?接收端收到每个码组后，先计算出S1、S2和S3，再查表判 断错码情况。例如，若接收码组为0000011，按上述公式 计算可得：S1 = 0，S2 = 1，S3 = 1。由于S1 S2 S3 等于011， 故查表可知在a3位有1错码。?按照上述方法构造的码称为汉明码。表中所列的(7, 4)汉明码 的最小码距d0 = 3。因此，这种码能够纠正1个错码或检测2 个错码。由于码率k/n = (n - r) /n =1 C r/n，故当n很大和r很小 时，码率接近1。可见，汉明码是一种高效码。42第11章差错控制编码?线性分组码的一般原理?线性分组码的构造?H矩阵 上面(7, 4)汉明码的例子有 ?a 6 ? a 5 ? a 4 ? a 2 ? 0 ? ?a6 ? a5 ? a3 ? a1 ? 0 ?a ? a ? a ? a ? 0 4 3 0 ? 6 现在将上面它改写为1 ? a 6 ? 1 ? a5 ? 1 ? a 4 ? 0 ? a3 ? 1 ? a 2 ? 0 ? a1 ? 0 ? a 0 ? 0? ? 1 ? a 6 ? 1 ? a5 ? 0 ? a 4 ? 1 ? a3 ? 0 ? a 2 ? 1 ? a1 ? 0 ? a 0 ? 0? 1 ? a 6 ? 0 ? a5 ? 1 ? a 4 ? 1 ? a3 ? 0 ? a 2 ? 0 ? a1 ? 1 ? a 0 ? 0? ?上式中已经将“?”简写成“+”。43第11章差错控制编码1 ? a 6 ? 1 ? a5 ? 1 ? a 4 ? 0 ? a3 ? 1 ? a 2 ? 0 ? a1 ? 0 ? a 0 ? 0? ? 1 ? a 6 ? 1 ? a5 ? 0 ? a 4 ? 1 ? a3 ? 0 ? a 2 ? 1 ? a1 ? 0 ? a 0 ? 0? 1 ? a 6 ? 0 ? a5 ? 1 ? a 4 ? 1 ? a3 ? 0 ? a 2 ? 0 ? a1 ? 1 ? a 0 ? 0? ?上式可以表示成如下矩阵形式： ?a6 ? ?a ? ? 5? ?1110100 ? ? a 4 ? ?0 ? ?1101010 ? ? a ? ? ?0 ? （模 2 ） ? ? ? 3? ? ? ? ? 0? ? ? ?1011001 ? ? a2 ? ? ? ? ?a1 ? ?a ? ? 0? 上式还可以简记为 H ? AT = 0T 或 A ? HT = 044第11章差错控制编码H ? AT = 0T 或 式中 A ? HT = 0?1110100 ? ? H ?? 1101010 ? ? ? ? ?1011001 ?A = [a6 a5 a4 a3 a2 a1 a0]0 = [000]右上标“T”表示将矩阵转置。例如，HT是H的转置，即HT的 第一行为H的第一列，HT的第二行为H的第二列等等。将H称为监督矩阵。只要监督矩阵H给定，编码时监督位和信息位的关系就完全 确定了。45第11章差错控制编码?H矩阵的性质： 1) H的行数就是监督关系式的数目，它等于监督位的数 目r。H的每行中“1”的位置表示相应码元之间存在的监 督关系。例如，H的第一行1110100表示监督位a2是由a6 a5 a4之和决定的。H矩阵可以分成两部分，例如?1110 ? 100? ? ? ?PI ? H ?? 1101 ? 010 r ? ? ? ?1011 ? 001? ?式中，P为r ? k阶矩阵，Ir为r ? r阶单位方阵。我们将具 有[P Ir]形式的H矩阵称为典型阵。46第11章差错控制编码2) 由代数理论可知，H矩阵的各行应该是线性无关的， 否则将得不到 r个线性无关的监督关系式，从而也得不到 r个独立的监督位。若一矩阵能写成典型阵形式[P Ir]，则 其各行一定是线性无关的。因为容易验证[Ir]的各行是线 性无关的，故[P Ir]的各行也是线性无关的。?G矩阵： 上面汉明码例子中的监督位公式为 ? a 2 ? a 6 ? a5 ? a 4 ? ?a1 ? a6 ? a5 ? a3 ?a ? a ? a ? a 6 4 3 ? 0?a6 ? 也可以改写成矩阵形式： ?a2 ? ?1110? ? ? ?a ? ? ?1101? ?a5 ? ? 1? ? ? ?a ? 4 ? ? ? ? 1011 a ? ? 0 ? ? ? ? a ? 3?47第11章差错控制编码?111? ?110? ?a2 a1a0 ? ? ?a6 a5 a4 a3 ?? ? ? ?a6 a5 a4 a3 ?Q ?101? ? ? 011 ? ??a6 ? ?a 2 ? ?1110? ? ? ?a ? ? ?1101? ?a5 ? ? 1? ? ? ?a ? 4 ? ? ? ? 1011 a ? ? ? ? 0? ? ? a3 ?或者写成式中，Q为一个k ? r阶矩阵，它为P的转置，即 Q = PT 上式表示，在信息位给定后，用信息位的行矩阵乘矩阵Q 就产生出监督位。48第11章差错控制编码我们将Q的左边加上1个k ? k阶单位方阵，就构成1个矩阵G ?111? ? ? ? 110 ? G ? ?I k Q ? ? ? ?? ? ? 0001 ? 011 ? ? G称为生成矩阵，因为由它可以产生整个码组，即有?a6 a5 a4 a3 a2 a1a0 ? ? ?a6 a5 a4 a3 ?? GA ? [a6 a5a4 a3 ] ? G或者因此，如果找到了码的生成矩阵G，则编码的方法就完全确 定了。具有[IkQ]形式的生成矩阵称为典型生成矩阵。由典型 生成矩阵得出的码组A中，信息位的位置不变，监督位附加 于其后。这种形式的码称为系统码。49第11章差错控制编码?G矩阵的性质： 1) G矩阵的各行是线性无关的。因为由上式可以看出， 任一码组A都是G的各行的线性组合。G共有k行，若它们 线性无关，则可以组合出2k种不同的码组A，它恰是有k 位信息位的全部码组。若G的各行有线性相关的，则不 可能由G生成2k种不同的码组了。2) 实际上，G的各行本身就是一个码组。因此，如果已 有k个线性无关的码组，则可以用其作为生成矩阵G，并 由它生成其余码组。50第11章差错控制编码?错码矩阵和错误图样 ? 一般说来，A为一个n列的行矩阵。此矩阵的n个元素就是 码组中的n个码元，所以发送的码组就是A。此码组在传 输中可能由于干扰引入差错，故接收码组一般说来与A不 一定相同。?若设接收码组为一n列的行矩阵B，即 B ? ?bn?1bn?2 ?b1b0 ? 则发送码组和接收码组之差为 B C A = E (模2) 它就是传输中产生的错码行矩阵E ? ?en?1en?2 ?e1e0 ?当bi ? ai 当 b i ? ai式中?0, ei ? ? ?1,51第11章差错控制编码因此，若ei = 0，表示该接收码元无错；若ei = 1，则表示该 接收码元有错。 BCA=E 可以改写成 B=A+E 例如，若发送码组A = [1000111]，错码矩阵E = [0000100]， 则接收码组B = [1000011]。 错码矩阵有时也称为错误图样。52第11章差错控制编码?校正子S 当接收码组有错时，E ? 0，将B当作A代入公式(A ? H T = 0) 后，该式不一定成立。在错码较多，已超过这种编码的检错 能力时，B变为另一许用码组，则该式仍能成立。这样的错 码是不可检测的。在未超过检错能力时，上式不成立，即其 右端不等于0。假设这时该式的右端为S，即 B?HT=S 将B = A + E代入上式，可得 S = (A + E) H T = A ? H T + E ? H T 由于A ? HT = 0，所以 S=E?HT 式中S称为校正子。它能用来指示错码的位置。 S和错码E之间有确定的线性变换关系。若S和E之间一一对 应，则S将能代表错码的位置。 53第11章差错控制编码?线性分组码的性质?封闭性：是指一种线性码中的任意两个码组之和仍为这种 码中的一个码组。 这就是说，若A1和A2是一种线性码中的两个许用码组，则 (A1+A2)仍为其中的一个码组。这一性质的证明很简单。若 A1和A2是两个码组，则有 A1 ? HT = 0, 将上两式相加，得出 A2 ? HT = 0A1 ? HT + A2 ? HT = (A1 + A2) HT = 0 所以(A1 + A2)也是一个码组。 由于线性码具有封闭性，所以两个码组(A1和A2)之间的距 离（即对应位不同的数目）必定是另一个码组(A1 + A2)的 重量（即“1”的数目）。因此，码的最小距离就是码的最 54 小重量（除全“0”码组外）。第11章差错控制编码?11.6 循环码?11.6.1 循环码原理?循环性：循环性是指任一码组循环一位（即将最右端的 一个码元移至左端，或反之）以后，仍为该码中的一个 码组。在下表中给出一种(7, 3)循环码的全部码组。码组编号 1 2 3信息位 a6a5a4 000 001 010监督位 a3a2a1a0 10码组编号 5 6 7信息位 a6a5a4 100 101 110监督位 a3a2a1a0 014011100181110010例如，表中的第2码组向右移一位即得到第5码组；第6码 55 组向右移一位即得到第7码组。第11章差错控制编码一般说来，若(an-1 an-2 …a0)是循环码的一个码组，则循环移 位后的码组 (an-2 an-3 … a0 an-1)(an-3 an-4 … an-1 an-2)……… (a0 an-1 …a2 a1)也是该编码中的码组。56第11章差错控制编码?码多项式?码组的多项式表示法 把码组中各码元当作是一个多项式的系数，即把一个长度 为n的码组表示成 T ( x) ? an?1 x n?1 ? an?2 x n?2 ? ? ? a1 x ? a0 例如，上表中的任意一个码组可以表示为 T ( x) ? a6 x6 ? a5 x5 ? a4 x 4 ? a3 x3 ? a2 x 2 ? a1 x ? a0 其中第7个码组可以表示为T ( x) ? 1? x 6 ? 1? x 5 ? 0 ? x 4 ? 0 ? x 3 ? 1 ? x 2 ? 0 ? x ? 1 ? x6 ? x5 ? x 2 ?1这种多项式中，x仅是码元位置的标记，例如上式表示第7 码组中a6、a5、a2和a0为“1”，其他均为0。因此我们并不 57 关心x的取值。第11章差错控制编码?码多项式的按模运算 ? 在整数运算中，有模n运算。例如，在模2运算中，有 1 + 1 = 2 ? 0 (模2)， 1 + 2 = 3 ? 1 (模2)， 2 ? 3 = 6 ? 0 (模2) 等等。一般说来，若一个整数m可以表示为 m p ?Q? , p?n n n 式中，Q － 整数， 则在模 n 运算下，有 m ? p (模 n ) 即，在模 n 运算下，一个整数m等于它被 n 除得的余数。58第11章差错控制编码?在码多项式运算中也有类似的按模运算。 若一任意多项式F(x)被一 n 次多项式N (x)除，得到商式 Q(x)和一个次数小于n的余式R(x)，即 F ( x) ? N ( x)Q( x) ? R( x) 则写为F ( x) ? R( x)（模N ( x) ）这时，码多项式系数仍按模2 运算，即系数只取 0 和1。 例如，x3被(x3 + 1)除，得到余项1。所以有 x3 ? 1 （模( x 3 ? 1) ） 同理 因为x 4 ? x2 ?1 ? x2 ? x ?1x x3 + 1 x4 +x2 + 1x4 + x（模( x3 ? 1) ）应当注意，由于在模2运算中， 用加法代替了减法，故余项不 是x2 C x + 1，而是x2 + x + 1。59x2 +x +1第11章差错控制编码?循环码的码多项式?在循环码中，若T(x)是一个长为n的许用码组，则xi?T(x)在 按模xn + 1运算下，也是该编码中的一个许用码组，即若 x i ? T ( x) ? T ?( x) （模( x n ? 1) ） 则T ?(x)也是该编码中的一个许用码组。 n?1 n ?2 【证】因为若 T ( x) ? an?1 x ? an?2 x ? ?? a1 x ? a0则 x i ? T ( x) ? an?1 x n?1?i ? an?2 x n?2?i ? ? ? an?1?i x n?1 ? ? ? a1 x1?i ? a0 x i? an?1?i x n?1 ? an?2?i x n?2 ? ? ? a0 x i ? an?1 x i ?1 ? ? ? an?i（模(xn + 1)）所以，这时有T ?( x) ? an?1?i x n?1 ? an?2?i x n?2 ? ? ? a0 x i ? an?1 x i ?1 ? ? ? an?i60第11章差错控制编码T ?( x) ? an?1?i x n?1 ? an?2?i x n?2 ? ? ? a0 x i ? an?1 x i ?1 ? ? ? an?i上式中T ?(x)正是T(x)代表的码组向左循环移位i次的结果。因 为原已假定T(x)是循环码的一个码组，所以T? (x)也必为该码 中一个码组。例如，循环码组T ( x) ? x 6 ? x5 ? x 2 ? 1其码长n = 7。现给定i = 3，则x 3 ? T ( x) ? x 3 ( x 6 ? x 5 ? x 2 ? 1) ? x9 ? x8 ? x5 ? x3 ? x5 ? x3 ? x2 ? x （模( x 7 ? 1) ）其对应的码组为0101110，它正是表中第3码组。 由上述分析可见，一个长为n的循环码必定为按模(xn + 1)运 算的一个余式。61第11章差错控制编码?循环码的生成矩阵G?由上节中公式 A ? [a6 a5a4 a3 ] ? G可知，有了生成矩阵G，就可以由k个信息位得出整个码组， 而且生成矩阵G的每一行都是一个码组。例如，在此式中， 若a6a5a4a3 = 1000，则码组A就等于G的第一行；若a6a5a4a3 = 0100，则码组A就等于G的第二行；等等。由于G是k行n 列的矩阵，因此若能找到k个已知码组，就能构成矩阵G。 如前所述，这k个已知码组必须是线性不相关的，否则给定 的信息位与编出的码组就不是一一对应的。?在循环码中，一个(n, k)码有2k个不同的码组。若用g(x)表 示其中前(k-1)位皆为“0”的码组，则g(x)，x g(x)，x2 g(x)， ?，xk-1 g(x)都是码组，而且这k个码组是线性无关的。因 此它们可以用来构成此循环码的生成矩阵G。 62第11章差错控制编码?在循环码中除全“0”码组外，再没有连续k位均为“0”的码组， 即连“0”的长度最多只能有(k - 1)位。否则，在经过若干次 循环移位后将得到一个k位信息位全为“0”，但监督位不全 为“0”的一个码组。这在线性码中显然是不可能的。因此， g(x)必须是一个常数项不为“0”的(n - k)次多项式，而且这个 g(x)还是这种(n, k)码中次数为(n C k)的唯一多项式。因为如果 且此码组多项式的次数将小于(n C k)，即连续“0”的个数多 于(k C 1)。显然，这是与前面的结论矛盾的，故是不可能的。 我们称这唯一的(n C k)次多项式g(x)为码的生成多项式。一旦 确定了g(x)，则整个(n, k)循环码就被确定了。63有两个，则由码的封闭性，把这两个相加也应该是一个码组，第11章差错控制编码?因此，循环码的生成矩阵G可以写成? x k ?1 g ( x) ? ? k ?2 ? ? x g ( x)? ? G ( x) ? ?? ? ? ? xg ( x) ? ? g ( x) ? ? ? ? ??例：在上表所给出的(7, 3)循环码中，n = 7, k = 3, n C k = 4。 由此表可见，唯一的一个(n C k) = 4次码多项式代表的码组是 第二码组0010111，与它相对应的码多项式（即生成多项式） g(x) = x4 + x2 + x + 1。将此g(x)代入上式，得到? x 2 g ( x)? ? ? G ( x) ? ? xg ( x) ? ? g ( x) ? ? ?或?1011100 ? ? G ( x) ? ? 0101110 ? ? ? ? ?0010111 ?64第11章差错控制编码由于上式不符合G = [IkQ]的形式，所以它不是典型阵。不过， 将它作线性变换，不难化成典型阵。 我们可以写出此循环码组，即? x 2 g ( x)? ? ? T ( x) ? [a6 a5 a4 ]G ( x) ? [a6 a5 a4 ]? xg ( x) ? ? g ( x) ? ? ? ? a6 x 2 g ( x) ? a5 xg ( x) ? a4 g ( x) ? ( a 6 x 2 ? a5 x ? a 4 ) g ( x )上式表明，所有码多项式T(x)都可被g(x)整除，而且任意一个 次数不大于(k C 1)的多项式乘g(x)都是码多项式。需要说明一 点，两个矩阵相乘的结果应该仍是一个矩阵。上式中两个矩 阵相乘的乘积是只有一个元素的一阶矩阵，这个元素就是 T(x)。为了简洁，式中直接将乘积写为此元素。 65第11章差错控制编码?如何寻找任一(n, k)循环码的生成多项式由上式可知，任一循环码多项式T(x)都是g(x)的倍式，故 它可以写成 T(x) = h(x)?g(x) 而生成多项式g(x)本身也是一个码组，即有 T ?(x) = g(x) 由于码组T ?(x)是一个(n C k)次多项式，故xk T ?(x)是一个n 次多项式。由下式x i ? T ( x) ? T ?( x)（模( x n ? 1) ）可知，xk T ?(x)在模(xn + 1)运算下也是一个码组，故可以写 成 x k T ?( x) T ( x) ? Q( x ) ? n n x ?1 x ?1 66第11章差错控制编码x k T ?( x) T ( x) ? Q ( x ) ? xn ?1 xn ?1上式左端分子和分母都是n次多项式，故商式Q(x) = 1。因此， 上式可以化成 x k T ?( x) ? ( x n ? 1) ? T ( x) 将T(x)和T?(x)表示式代入上式，经过化简后得到x n ? 1 ? g ( x)[x k ? h( x)]上式表明，生成多项式g(x)应该是(xn + 1)的一个因子。这一 结论为我们寻找循环码的生成多项式指出了一条道路，即循 环码的生成多项式应该是(xn +1)的一个(n C k)次因式。例如， (x7 + 1)可以分解为x 7 ? 1 ? ( x ? 1)(x3 ? x 2 ? 1)(x3 ? x ? 1)为了求(7, 3)循环码的生成多项式g(x)，需要从上式中找到一 个(n C k) = 4次的因子。不难看出，这样的因子有两个，即 67第11章差错控制编码( x ? 1)(x3 ? x 2 ? 1) ? x 4 ? x 2 ? x ? 1( x ? 1)(x3 ? x ? 1) ? x 4 ? x3 ? x 2 ? 1以上两式都可作为生成多项式。不过，选用的生成多项式不 同，产生出的循环码码组也不同。68第11章差错控制编码?11.6.2 循环码的编解码方法?循环码的编码方法?编码原则 在编码时，首先要根据给定的(n, k)值选定生成多项式 g(x)，即从(xn + 1)的因子中选一个(n - k)次多项式作为 g(x)。 由于所有码多项式T(x)都可以被g(x)整除。根据这条原则， 就可以对给定的信息位进行编码： 设m(x)为信息码多项式，其次数小于k。用xn - k乘m(x)， 得到的xn-k m(x)的次数必定小于n。用g(x)除xn - k m(x)，得 到余式r(x)，r(x)的次数必定小于g(x)的次数，即小于(n C k)。将此余式r(x)加于信息位之后作为监督位，即将r(x) 和xn - k m(x)相加，得到的多项式必定是一个码多项式。 因为它必须能被g(x)整除，且商的次数不大于(k C 1)。69第11章差错控制编码?编码步骤： n - k乘m(x)。这一运算实际上是在信息码后附加上(n C ? 用x k)个“0”。例如，信息码为110，它相当于m(x) = x2 + x。 当n C k = 7 C 3 = 4时，xn - k m(x) = x4 (x2 + x) = x6 + x5，它 相当于1100000。 n - k m(x)，得到商Q(x)和余式r(x)，即 ? 用g(x)除x x n?k m( x) r ( x) ? Q( x ) ? g ( x) g ( x) 例如，若选定g(x) = x4 + x2 + x + 1，则2 x n?k m( x) x6 ? x5 x ?1 2 ? 4 ? ( x ? x ? 1 ) ? g ( x) x ? x2 ? x ?1 x4 ? x2 ? x ?1 上式相当于 ? 111 ? 70第11章差错控制编码?编出的码组T(x)为 T(x) = xn - k m(x) + r(x) 在上例中，T(x) = 1100000 + 101 = 1100101，它就是上 表中的第7码组。71第11章差错控制编码?循环码的解码方法? ?解码要求：检错和纠错。 检错解码原理：由于任意一个码组多项式T(x)都应该能被 生成多项式g(x)整除，所以在接收端可以将接收码组R(x) 用原生成多项式g(x)去除。当传输中未发生错误时，接收 码组与发送码组相同，即R(x) = T(x)，故接收码组R(x)必 定能被g(x)整除；若码组在传输中发生错误，则R(x) ? T(x)， R(x)被g(x)除时可能除不尽而有余项，即有 R( x) / g ( x) ? Q( x) ? r ( x) / g ( x) 因此，就以余项是否为零来判别接收码组中有无错码。 需要指出，有错码的接收码组也有可能被g(x)整除。这时 的错码就不能检出了。这种错误称为不可检错误。不可检 错误中的误码数必定超过了这种编码的检错能力。72第11章差错控制编码?纠错解码原理：为了能够纠错，要求每个可纠正的错误图 样必须与一个特定余式有一一对应关系。因为只有存在上 述一一对应的关系时，才可能从上述余式唯一地决定错误 图样，从而纠正错码。因此，原则上纠错可按下述步骤进 行： 用生成多项式g(x)除接收码组R(x)，得出余式r(x)。 ? 按余式r(x)，用查表的方法或通过某种计算得到错误图 样E(x)；例如，通过计算校正子S和查表，就可以确定 错码的位置。 ? 从R(x)中减去E(x)，便得到已经纠正错码的原发送码组 T(x)。 通常，一种编码可以有几种纠错解码方法，上述解码方法 称为捕错解码法。???目前多采用软件运算实现上述编解码运算。73第11章差错控制编码?11.6.3 截短循环码????截短目的：在设计纠错编码方案时，常常信息位数k、码长 n和纠错能力都是预先给定的。但是，并不一定有恰好满足 这些条件的循环码存在。这时，可以采用将码长截短的方 法，得出满足要求的编码。 截短方法：设给定一个(n, k)循环码，它共有2k种码组，现 使其前i (0 & i & k)个信息位全为“0”，于是它变成仅有2k-i 种码组。然后从中删去这i位全“0”的信息位，最终得到一 个(n C i, k C i)的线性码。将这种码称为截短循环码。 截短循环码性能：循环码截短前后至少具有相同的纠错能 力，并且编解码方法仍和截短前的方法一样。 例：要求构造一个能够纠正1位错码的(13, 9)码。这时可以 由(15, 11)循环码的11种码组中选出前两信息位均为“0”的 码组，构成一个新的码组集合。然后在发送时不发送这两 位“0”。于是发送码组成为(13, 9)截短循环码。 74第11章差错控制编码?11.6.4 BCH码??什么是BCH码？它是一种获得广泛应用的能够纠正多个错 码的循环码，是以3位发明这种码的人名(Bose - Chaudhuri Hocguenghem)命名的。BCH码的重要性在于它解决了生成 多项式与纠错能力的关系问题，可以在给定纠错能力要求 的条件下寻找到码的生成多项式。有了生成多项式，编码 的基本问题就随之解决了。 BCH码分类： ? 本原BCH码：其生成多项式g(x)中含有最高次数为m的 本原多项式，且码长为n = 2m C 1，(m ? 3，为正整数)。 ? 非本原BCH码：其生成多项式中不含这种本原多项式， 且码长n是(2m C 1)的一个因子，即码长n一定除得尽2m C 1。 ? 本原多项式的概念将在下一章介绍。75第11章差错控制编码?BCH码的性能：?码长n与监督位、纠错个数 t 之间的关系： 对于正整数m (m ? 3)和正整数t & m / 2，必定存在一个码 长为n = 2m C 1，监督位为n C k ? mt，能纠正所有不多于t 个随机错误的BCH码。若码长n = (2m - 1) / i（i & 1，且除 得尽(2m -1)），则为非本原BCH码。?汉明码是能够纠正单个随机错误的码。可以证明，具有循 环性质的汉明码就是能纠正单个随机错误的本原BCH码。例如，(7, 4)汉明码就是以g1(x) = x3 + x + 1或g2(x) = x3 + x2 + 1生成的BCH码，而用g3(x) = x4 + x + 1或g4(x) = x4 + x3 + 1都能生成(15, 11)汉明码。76?第11章差错控制编码?BCH码的设计??在工程设计中，一般不需要用计算方法去寻找生成多项式 g(x)。因为前人早已将寻找到的g(x)列成表，故可以用查表 法找到所需的生成多项式。 下表给出了码长n ? 127的二进制本原BCH码生成多项式。77第11章差错控制编码n=3 k t 1 1 g(x) 7 g(x) 13 77 n = 63 k t 57 1 51 2 45 3 39 4 36 5 30 6 24 7 18 10 16 11 10 13 7 15 1 31 g(x) 103 7
全部为178n=7 k t 4 1 1 3n = 15 k t g(x) 11 1 23 7 2 721 5 3
77777第11章差错控制编码n = 31 k t 26 1 21 2 16 3 11 5 6 7 1 15 g(x) 45
n = 127 k t 120 1 113 2 106 3 99 4 92 5 85 6 78 7 71 9 64 10 57 11 50 13 43 15 36 ?15 29 ?22 22 ?23 15 ?27 8 ?31 1 63 g (x ) 211 43
53 0217 79 全部为1第11章差错控制编码?表中给出的生成多项式系数是用8进制数字列出的。 例如，g(x) = (13)8是指g(x) = x3 + x + 1，因为(13)8 = (1011)2，后者就是此3次方程g(x)的各项系数。?下表列出了部分非本原BCH码的生成多项式参数。t 2 2 3 2 4 g(x) 727 45 6647133 n 47 65 65 73 k 24 53 40 46 t 5 2 4 4 g(x) 61 n 17 21 23 33 41k 9 12 12 22 2180第11章差错控制编码?戈莱码： 在上表中的(23, 12)码称为戈莱(Golay)码。它能纠正3个随机 错码，并且容易解码，实际应用较多。?扩展BCH码：BCH码的长度都为奇数。在应用中，为了得到偶数长度的码， 并增大检错能力，可以在BCH码生成多项式中乘上一个因式 (x + 1)，从而得到扩展BCH码(n + 1, k)。扩展BCH码相当于 在原BCH码上增加了一个校验位，因此码距比原BCH码增加 1。扩展BCH码已经不再具有循环性。例如，广泛实用的扩 展戈莱码(24, 12)，其最小码距为8，码率为1/2，能够纠正3 个错码和检测4个错码。它比汉明码的纠错能力强很多，付 出的代价是解码更复杂，码率也比汉明码低。此外，它不再 是循环码了。81第11章差错控制编码?11.6.5 RS码：它是一类具有很强纠错能力的多进制BCH码。????若仍用n表示RS码的码长，则对于m进制的RS码，其码长需 要满足下式： n = m C 1 = 2q C 1 式中 q ? 2，为整数。 对于能够纠正t个错误的RS码，其监督码元数目为r = 2t，这 时的最小码距d0 = 2t + 1。 RS码的生成多项式为 g(x) = (x + ?)(x +?2) … (x +?2t) 式中，? － 伽罗华域GF(2q)中的本原元。 若将每个m进制码元表示成相应的q位二进制码元，则得到的 二进制码的参数为： 码长：n = q(2q C 1)（二进制码元） 监督码：r = 2qt （二进制码元）82第11章差错控制编码?由于RS码能够纠正t个m进制错码，或者说，能够纠正码 组中t个不超过q位连续的二进制错码，所以RS码特别适 用于存在突发错误的信道，例如移动通信网等衰落信道 中。此外，因为它是多进制纠错编码，所以特别适合用 于多进制调制的场合。83第11章差错控制编码?11.7 卷积码?非分组码概念：?卷积码是一种非分组码。通常它更适用于前向纠错，因 为对于许多实际情况它的性能优于分组码，而且运算较 简单。?卷积码在编码时虽然也是把k个比特的信息段编成n个比 特的码组，但是监督码元不仅和当前的k比特信息段有关， 而且还同前面m = (N C 1)个信息段有关。所以一个码组中 的监督码元监督着N个信息段。通常将N称为编码约束度， 并将nN称为编码约束长度。一般说来，对于卷积码，k 和 n 的值是比较小的整数。我们将卷积码记作(n, k, N)。 码率则仍定义为k / n。84第11章差错控制编码?11.7.1 卷积码的基本原理?编码器原理方框图1 … k 1 … k … 2k … 3k 1 … k 1 … k … … … …… … …每次输入 k比特Nk 1 … kNk级 移存器12… … … …nn个模2 加法器每输入k比特 旋转1周编码输出85第11章差错控制编码?例： (n, k, N) = (3, 1, 3)卷积码编码器?方框图输入biM1biM2 bi-1M3 bi-2ei di ci 编码输出?设输入信息比特序列是?bi-2 bi-1 bi bi+1?，则当输入bi时， 此编码器输出3比特ci di ei，输入和输出的关系如下：ci ? bi d i ? bi ? bi ?2 ei ? bi ? bi ?`1 ? bi ?286第11章差错控制编码在下图中用虚线示出了信息位bi的监督位和各信息位之间 的约束关系。这里的编码约束长度nN等于9。输入bi-2b i －1bi t输出ci-2di-2ei-2ci-1di-1ei-1cidieit87第11章差错控制编码?11.7.2 卷积码的代数表述上式表示卷积码也是一种线性码。一个线性码完全由一个监 督矩阵H或生成矩阵G所确定。下面就来寻找这两个矩阵。?监督矩阵H现在仍从上面的实例开始分析。假设上图中在第1个信 息位b1进入编码器之前，各级移存器都处于“0”状态， 则监督位di、ei和信息位bi之间的关系可以写为88第11章差错控制编码? ? e1 ? b1 ? ? d 2 ? b2 ? e2 ? b2 ? b1 ? ? 左式可以改写为 d3 ? b3 ? b1 ? e3 ? b3 ? b2 ? b1 ? ? ? d 4 ? b4 ? b2 ? e4 ? b4 ? b3 ? b2 ? ? ? d1 ? b1b1 ? d1 ? 0 ? ? b1 ? e1 ? 0 ? ? b2 ? d 2 ? 0 ? b1 ? b2 ? e2 ? 0 ? ? b1 ? b3 ? d3 ? 0 ? b1 ? b2 ? b3 ? e3 ? 0 ? ? b2 ? b4 ? d 4 ? 0 ? ? b2 ? b3 ? b4 ? e4 ? 0 ? ? ?在上面两个式子和后面的式子中，为简便计，用“＋”代替 “?”。 将上式用矩阵表示时，可以写成89第11章差错控制编码?b1 ? ?d ? 1 ? ? 11 ? ? ?101 ? ?e1 ? ? ? ?b2 ? ?00011 ?? ? ? ? ?d 2 ? ?100101 ? ?e ? ? ? ? 2 ? ? ?O ? ? ? ?b3 ? ? ? ? ? ?d 3 ? ? ? 1 ? ? ? ? e3 01? ? ? ? ????? ? ?b4 ? ? ?? ? ?d 4 ? ?e ? ? 4?与11.5节公式H ? AT = 0T对比，可以看出监督矩阵为90第11章差错控制编码?11 ? ?101 ? ? ? ?00011 ? ? ? 100101 ? ? ? H ? ? ? ? ? ? ? 1 ? ? ? 01? ? ????? ? ? ?由此例可见，卷积码的监督矩阵H是一个有头无尾的半无 穷矩阵。此外，这个矩阵的每3列的结构是相同的，只是后 3列比前3列向下移了两行。例如，第4 ~ 6列比第1 ~ 3列低2 行。自第7行起，每两行的左端比上两行多了3个“0”。 91第11章差错控制编码虽然这样的半无穷矩阵不便于研究，但是只要研究产生前9 个码元（9为约束长度）的监督矩阵就足够了。不难看出， 这种截短监督矩阵的结构形式如下图所示：nnCkH1 =(n C k)N由此图可见，H1的最左边是n列(n-k)N行的一个子矩阵，且向 右的每n列均相对于前n列降低(n - k)行。92第11章差错控制编码此例中码的截短监督矩阵可以写成如下形式：?11 ? ?101 ? ? ? ? P1 I 2 ? ?00011 ? ? ? H1 ? ? ? P O P I ? ? 2 2 1 2 ? 100101 ? ? ?P O P O P I ? 2 2 2 1 2? ?? ? 3 ? ? ? ? ? ?式中?10? I2 ? ? ? ?01?― 2阶单位方阵；Pi ― 1 ? 2阶矩阵，i = 1, 2, 3； O2 ― 2阶全零方阵。93第11章差错控制编码一般说来，卷积码的截短监督矩阵具有如下形式： ? P1 I n? k ? ?P O ? P I n?k ? 2 n?k 1 ? ? H 1 ? ? P3 O n? k P2 O n? k P1 I n?k ? ? ? ? ? ? ? ? ? ? ? PN O n? k PN ?1 O n? k PN ? 2 O n? k ? P1 I n?k ? ? ? 式中 In-k ― (n C k)阶单位方阵； Pi ― k ? (n C k)阶矩阵； On-k ― (n C k)阶全零方阵。有时还将H1的末行称为基本监督矩阵h h = [PN On-k PN-1 On-k PN-2 On-k ? ? ? P1 In-k]它是卷积码的一个最重要的矩阵，因为只要给定了h，则H1 也就随之决定了。或者说，我们从给定的h不难构造出H1。 94第11章差错控制编码?生成矩阵G上例中的输出码元序列可以写成 [ b1 d1 e1 b2 d2 e2 b3 d3 e3 b4 d4 e4 ? ? ? ]= [ b1 b1 b1 b2 b2 (b2 + b1) b3 (b3 + b1) (b3 + b2 + b1) b4 (b4 + b2) (b4 + b3 + b2) ? ? ? ]?111 001 011 000 0 ? ? ?000 111 001 011 0 ? ? ? ? ?000 000 111 001 0 ? ? ? ? 000 000 000 111 0 ? ? ? ?b1b2b3b4 ??? ?000 000 000 000 1? ? ? ? ?000 000 000 000 0 ?? ?000 000 000 000 0 ?? ? ? ? ?? ? ? ? ? ? ? ? ?95第11章差错控制编码此码的生成矩阵G即为上式最右矩阵：?111 001 011 000 0? ? ?000 111 001 011 0? ? ? ? ?000 000 111 001 0? ? ? ? 000 000 000 111 0 ? ? G?? ?000 000 000 000 1? ? ? ? ?000 000 000 000 0?? ?000 000 000 000 0?? ? ? ? ?? ? ? ? ? ? ? ? ?它也是一个半无穷矩阵，其特点是每一行的结构相同，只是 比上一行向右退后3列（因现在n = 3）。96第11章差错控制编码?截短生成矩阵：类似地，也有截短生成矩阵?111 001 011? ? I1 Q1 O Q2 O Q3 ? ? ??? G1 ? ? 000 111 001 I Q O Q 1 1 2 ? ? ? ? ? I1 Q1 ? ?000 000 111? ? ? ? ? 式中 I1 － 一阶单位方阵；Qi － 2 ? 1阶矩阵。 与H1矩阵比较可见，Qi是矩阵PiT的转置： Qi = PiT (i = 1, 2, ?) 一般说来，截短生成矩阵具有如下形式：97第11章差错控制编码? I k Q1 O k Q 2 O k Q3 ? I k Q1 O k Q 2 ? G1 ? ? I k Q1 ? ? ? ? ? Ok Q N ? Ok ? Ok ? ? Ik ? Q N ?1 ? ? Q N ?2 ? ? ? Q1 ? ?式中 Ik － k阶单位方阵； Qi － (n C k)?k阶矩阵； Ok － k阶全零方阵。 并将上式中矩阵第一行称为基本生成矩阵 g ＝ [Ik Q1 Ok Q2 Ok Q3?Ok QN] 同样，如果基本生成矩阵g已经给定，则可以从已知 的信息位得到整个编码序列。98第11章差错控制编码?11.7.3 卷积码的解码?分类：?代数解码：利用编码本身的代数结构进行解码，不考虑 信道的统计特性。大数逻辑解码，又称门限解码，是卷 积码代数解码的最主要一种方法，它也可以应用于循环 码的解码。大数逻辑解码对于约束长度较短的卷积码最 为有效，而且设备较简单。 概率解码：又称最大似然解码。它基于信道的统计特性 和卷积码的特点进行计算。针对无记忆信道提出的序贯 解码就是概率解码方法之一。另一种概率解码方法是维 特比算法。当码的约束长度较短时，它比序贯解码算法 的效率更高、速度更快，目前得到广泛的应用。99?第11章差错控制编码?大数逻辑解码 ? 工作原理信息位信息位移存器 校正子计算输入 监督位??? ???修正校正子输出校正子移存器 错码检测????图中首先将接收信息位暂存于移存器中，并从接收码 元的信息位和监督位计算校正子。然后，将计算得出 的校正子暂存，并用它来检测错码的位置。在信息位 移存器输出端，接有一个模2加电路；当检测到输出 的信息位有错时，在输出的信息位上加“1”，从而纠 正之。100第11章差错控制编码?这里的错码检测是采用二进制码的大数逻辑解码算法。 它利用一组“正交”校验方程进行计算。 这里的“正交” 定义：若被校验的那个信息位出现在校 验方程组的每一个方程中，而其他的信息位至多在一个 方程中出现，则称这组方程为正交校验方程。这样就可 以根据被错码影响了的方程数目在方程组中是否占多数 来判断该信息位是否错了。下面将用一个实例来具体讲 述这一过程。?101第11章差错控制编码?例：(2, 1, 6)卷积码 输入 ? 编码器方框图b6b5b4b3b2b1 ci bi输出?监督位和信息位的关系 当输入序列为b1 b2 b3 b4 ?时，监督位为 c1 = b1 c2 = b2 c3 = b3 c4 = b1 + b4 c5 = b1 + b2 + b5 c6 = b1 + b2 + b3 + b6 ?????bi ci?102第11章差错控制编码??监督关系式 参照11.5节中监督关系的定义式，容易写出 S1 = c1 + b1 S2 = c2 + b2 S3 = c3 + b3 S4 = c4 + b1 + b4 S5 = c5 + b1 + b2 + b5 S6 = c6 + b1 + b2 + b3 + b6 上式中的Si (i = 1 ~ 6)称为校正子。 正交校验方程组 上式经过简单线性变换后，得出如下正交校验方程组：103第11章差错控制编码S1 = c1 + b1 S4 = c4 + b1 + b4 S5 = c5 + b1 + b2 + b5 S2 + S6 = c2 + c6 + b1 + b3 + b6在上式中，只有信息位b1出现在每个方程中，监督位和其他 信息位均最多只出现一次。因此，在接收端解码时，考察b1、 c1至b6、c6等12个码元，仅当b1出错时，式中才可能有3个或3 个以上方程等于“1”。从而能够纠正b1的错误。104第11章差错控制编码?解码器方框图 按照这一原理画出的此(2, 1, 6)卷积码解码器方框图如下6 输入 5信息位移存器 4 3 21b6b5b4b3b2b1输出重算监督位ci接收监督位计算校正子Si校正子S i校正子移存器S6S5S4S3S2S1门限电路：“1”的个数? 3？Y105第11章差错控制编码由此图可见，当信息位出现一个错码时，仅当它位于信息位移 存器的第6、3、2和1级时，才使校正子等于“1”。因此，这时 的校正子序列为100111；反之，当监督位出现一个错码时，校正子序列将为100000。由此可见，当校正子序列中出现第一个“1”时，表示已经检出 一个错码。后面的几位校正子则指出是信息位错了，还是监督 位错了。 图中门限电路的输入代表式中4个方程的4个电压。门限电路将 这4个电压（非模2）相加。当相加结果大于或等于3时，门限 电路输出“1”，它除了送到输出端的模2加法器上纠正输出码 元b1的错码外，还送到校正子移存器纠正其中错误。?此卷积码除了能够纠正两位在约束长度中的随机错误 外，还能纠正部分多于两位的错误。106第11章差错控制编码?卷积码的几何表述?码树图：现仍以上面(3, 1, 3)码为例，介绍卷积码的码树c d e 2 000 2 22 c d e
c d e 4 000 4 4ab c d a b c111001 110 011↑0a111 001a↓1111a b c d a b c d a b c d a b c d0 信息位 1 状态 M3M2 a 00 b 01 c 10 d 11信息位100 010上 半 部↑0 起点b110 011101 000 111 001 110 011 100 010a↓1 111 ↑0 ↓1001c100 010b下 半 部110d1010d101111107第11章差错控制编码将图中移存器M1，M2和M3的初始状态000作为码树的起点。 现在规定：输入信息位为“0”，则状态向上支路移动；输入 信息位为“1”，则状态向下支路移动。于是，就可以得出图 中所示的码树。 设现在的输入码元序列为1101，则当第1个信息位b1 = 1输入 后，各移存器存储的信息分别为M1 = 1，M2 = M3 = 0。此时 的输出为c1 d1 e1= 111，码树的状态将从起点a向下到达状态b； 此后，第2个输入信息位b2 = 1，故码树状态将从状态b向下 到达状态d。这时M2 = 1，M3 = 0，此时，c2d2e2 = 110。第3 位和后继各位输入时，编码器将按照图中粗线所示的路径前 进，得到输出序列：111 110 010 100 …。 由此码树图还可以看到，从第4级支路开始，码树的上半部 和下半部相同。这意味着，从第4个输入信息位开始，输出 码元已经与第1位输入信息位无关，即此编码器的约束度N = 3。108第11章差错控制编码若观察在新码元输入时编码器的过去状态，即观察M2 M3的 状态和输入信息位的关系，则可以得出图中的a b c和d四种 状态。这些状态和M2 M3的关系也在图中给出了。?码树图原则上还可以用于解码。在解码时，按照汉明距 离最小的准则沿上面的码树进行搜索。例如，若接收码 元序列为111 010 010 110 …，和发送序列相比可知第4和 第11码元为错码。当接收到第4～6个码元“010”时，将 这3个码元和对应的第2级的上下两个支路比较，它和上 支路“001”的汉明距离等于2，和下支路“110”的汉明距 离等于1，所以选择走下支路。类似地，当接收到第10～12个码元“110”时，和第4级的 上下支路比较，它和上支路的“011”的汉明距离等于2， 和下支路“100”的汉明距离等于1，所以走下支路。这样， 就能够纠正这两个错码。109第11章差错控制编码一般说来，码树搜索解码法并不实用，因为随着信息序列 的增长，码树分支数目按指数规律增长；在上面的码树图 中，只有4个信息位，分支已有24 = 16个。但是它为以后 实用解码算法建立了初步基础。110第11章差错控制编码?状态图 上面的码树可以改进为下述的状态图。 由上例的编码器结构可知，输出码元ci di ei决定于当前输入 信息位bi和前两位信息位bi-1和bi-2（即移存器M2和M3的状 态）。在上图中已经为M2和M3的4种状态规定了代表符号a, b, c 和d。所以，可以将当前输入信息位、移存器前一状态、 移存器下一状态和输出码元之间的关系归纳于下表中。111第11章差错控制编码移存器前一状态 当前输入信息位 输出码元 移存器下一状态M3 M2 a (00) b (01) c (10) d (11)bi 0 1 0 1 0 1 0 1cidiei 000 111 001 110 011 100 010 101M 3 M2 a (00) b (01) c (10) d (11) a (00) b (01) c (10) d (11)由上表看出，前一状态a只能转到下一状态a或b，前一状态b 只能转到下一状态c或d，等等。 按照此表中的规律，可以画出状态图如下图所示。112第11章差错控制编码b000 a111100 011 c110001 010 d101在此图中，虚线表示输入信息位为“0”时状态转变的路线； 实线表示输入信息位为“1”时状态转变的路线。线条旁的3 位数字是编码输出比特。利用这种状态图可以方便地从输入 序列得到输出序列。113第11章差错控制编码?网格图 将状态图在时间上展开，可以得到网格图如下：000 111 000 111 001110a b c d000 111 011 100 001110 101000 111 011 100 001110 101010010000 a 111 011 b 100 001 c 110 010 d 101图中画出了5个时隙。在此图中，仍用虚线表示输入信息位 为“0”时状态转变的路线；实线表示输入信息位为“1”时状 态转变的路线。可以看出，在第4时隙以后的网格图形完全 是重复第3时隙的图形。这也反映了此(3, 1, 3)卷积码的约束 长度为3。114第11章差错控制编码a b 100 c d 110 010 d 001 c 111 a b在上图中给出了输入信息位为11010时，在网格图中的编码 路径。图中示出这时的输出编码序列是：111 110 010 100 011…。由上述可见，用网格图表示编码过程和输入输出关 系比码树图更为简练。 有了上面的状态图和网格图，下面就可以讨论维特比解码算 法了。115第11章差错控制编码?维特比解码算法?基本原理 将接收到的信号序列和所有可能的发送信号序列比较，选 择其中汉明距离最小的序列认为是当前发送信号序列。若 发送一个k位序列，则有2k种可能的发送序列。计算机应存 储这些序列，以便用作比较。当k较大时，存储量太大，使实用受到限制。维特比算法对 此作了简化，使之能够实用。现在仍用上面(3, 1, 3)卷积码的例子来说明维特比算法的原 理。116第11章差错控制编码?例： (3, 1, 3)卷积码 设现在的发送信息位为1101，为了使图中移存器的信息位全 部移出，在信息位后面加入3个“0”，故编码后的发送序列 为111 110 010 100 001 011 000。并且假设接收序列为111 010 010 110 001 011 000，其中第4和第11个码元为错码。 由于这是一个(n, k, N) = (3, 1, 3)卷积码，发送序列的约束度N = 3，所以首先需考察nN ＝ 9比特。第1步考察接收序列前9 位“111 010 010”。由此码的网格图可见，沿路径每一级有4 种状态a, b, c和d。每种状态只有两条路径可以到达。故4种 状态共有8条到达路径。现在比较网格图中的这8条路径和接收序列之间的汉明距离。117第11章差错控制编码a b c d 000 111 000 111001110000 111 011 100 001 110000 111 011 100 001 110010010101101000 a 111 011 b 100 001 c 110 010 d 101例如，由出发点状态a经过3级路径后到达状态a的两条路径 中上面一条为“000 000 000”。它和接收序列“111 010 010” 的汉明距离等于5；下面一条为“111 001 011”,它和接收序列 的汉明距离等于3。同样，由出发点状态a经过3级路径后到 达状态b、c和d的路径分别都有两条，故总共有8条路径。在 下表中列出了这8条路径和其汉明距离。118第11章差错控制编码序号 12 3路径 aaaaabca aaab对应序列 000 000 000111 001 011 000 000 111汉明距离 53 6幸存否 否是 否45 6 7 8abcbaabc abdc aabd abdd111 001 100000 111 001 111 110 010 000 111 110 111 110 10147 1 6 4是否 是 否 是现在将到达每个状态的两条路径的汉明距离作比较，将距离 小的一条路径保留，称为幸存路径。若两条路径的汉明距离 相同，则可以任意保存一条。这样就剩下4条路径了，即表 中第2, 4, 6和8条路径。 119第11章差错控制编码序号 1 2 3 4 5 6 7 8 路径 abca+a abdc+a abca+b abdc+b abcb+c abdd+c abcb+d abdd+d 原幸存路径 的距离 3 1 3 1 4 4 4 4 新增 路径段 aa ca ab cb bc dc bd dd 新增距离 2 2 1 1 3 1 0 2 总距离 5 3 4 2 7 5 4 6 幸存否 否 是 否 是 否 是 是 否第2步继续考察接收序列的后继3个比特“110”。计算4条幸 存路径上增加1级后的8条可能路径的汉明距离。结果如下表。表中最小的总距离等于2，其路径是abdc+b，相应序列为111 110 010 100。它和发送序列相同，故对应发送信息位1101。 120 按照表中的幸存路径画出的网格图示于下图中。第11章差错控制编码a b 111 001 110 100 011 100 110 010 a b c dcd010 101图中粗红线路径是汉明距离最小（等于2）的路径。121第11章差错控制编码上面提到过，为了使输入的信息位全部通过编码器的移存器， 使移存器回到初始状态，在信息位1101后面加了3个“0”。 若把这3个“0”仍然看作是信息位，则可以按照上述算法继 续解码。这样得到的幸存路径网格图示于下图中。a b 001 c d 110 000 111 100 010 101 000 a b c011 100 010001011 001011101101d图中的粗红线仍然是汉明距离最小的路径。但是，若已知这 3个码元是（为结尾而补充的）“0”，则在解码计算时就预 先知道在接收这3个“0”码元后，路径必然应该回到状态a。 而由图可见，只有两条路径可以回到a状态。所以，这时上 122 图可以简化成下图。第11章差错控制编码a b 001 c d 110000111 100 010 011 100 001 011 001000 011a bc 010 101 d 101在上例中卷积码的约束度N = 3，需要存储和计算8条路径的 参量。由此可见，维特比解码算法的复杂度随约束长度N按 指数形式2N增长。故维特比解码算法适合约束度较小（N ? 10）的编码。对于约束度大的卷积码，可以采用其他解码算 法。123第11章差错控制编码?11.8 Turbo码??什么是Turbo码？它是一种特殊的链接码。由于其性能 接近信息理论上能够达到的最好性能，所以在编码理论 上是带有革命性的进步。这种码，特别是解码运算，非 常复杂，这里只对其基本概念作一简明介绍。 基本原理?由于分组码和卷积码的复杂度随码组长度或约束度的增 大按指数规律增长，所以为了提高纠错能力，人们大多 不是单纯增大一种码的长度，而是将两种或多种简单的 编码组合成复合编码。Turbo码的编码器在两个并联或串联的分量码编码器之间 增加一个交织器，使之具有很大的码组长度，能在低信 噪比条件下得到接近理想的性能。124?第11章差错控制编码?Turbo码的译码器有两个分量码译码器，译码在两个分量译码 器之间进行迭代译码，故整个译码过程类似涡轮（turbo）工 作，所以又形象地称为Turbo码。?编码器的基本结构：它由一对递归系统卷积码(RSCC)编码 器和一个交织器组成，如下图所示： bi?RSCC编码器和卷积码编码器之间的主要区别是从 bi移存器输出端到信息位输 入端之间有反馈路径。原交织器RSCC编码器c1 i c2 iRSCC编码器?来的卷积码编码器像是一个FIR数字滤波器。增加了反馈路径 后，它就变成了一个IIR滤波器，或称递归滤波器。 两个RSCC编码器是相同的。它们的输入经过一个交织器并联。 此Turbo码的输入信息位是bi，输出是bic1ic2i，故码率等于1/3。125第11章差错控制编码?RSCC编码器举例：?方框图：如下图所示bibi D D ci??它是一个码率等于1/2的卷积码编码器，输入为bi，输出为 bici。 因为输出中第1位是信息位，所以它是系统码。126第11章差错控制编码?矩阵交织器：? ?a?原理方框图：见右图 ? ? ? a a a 21 22 2m 其基本形式是矩阵交 ? ? ? ? ? ? 织器，它由容量为 ? ? ? a a a (n-1)m比特的存储器 n1 n2 nm 构成。将信号码元按 行的方向输入存储器，再按列的方向输出。 若输入码元序列是：a11a12…a1m a21a22…a2m…an1…anm，则 输出序列是：a11a21…an1a12a22…an2…a1m…anm。11a12???a1m?交织的目的是将突发错码分散开，变成随机错码。例如， 若图中第1行的m个码元构成一个码组，并且连续发送到信 道上，则当遇到脉冲干扰，造成大量错码时，可能因超出 纠错能力而无法纠正错误。但是，若在发送前进行了交织， 按列发送，则能够将集中的错码分散到各个码组，从而有 127 利于纠错。这种交织器常用于分组码。第11章差错控制编码?卷积交织器1交织器1 2 3 4解交织器x?方 框 图 举 例2 3 4xxx1xxx1 x xxxx x xxxxx(a) 第1~4比特输入时的状态56 7 8 562 xxx2551 27 384xxx x xxxxx(b) 第5~8比特输入时的状态9 10 11 12 910 11 126x369973 x5 61 2 3xxxx84(c) 第9~12比特输入时的状态1313 14 15 16134 7 10 1314 15 16 11 12 810 7 45 10 6 794321(d) 第13~16比特输入时的状态128第11章差错控制编码? ? ????它是由3个移存器构成。第1个移存器只有1比特容量；第 2个移存器可以存2比特；第3个移存器可以存3比特。 交织器的输入码元依次进入各个移存器。 在图 (a)的交织器中示出，第1个输入码元没有经过存储 而直接输出；第2个输入码元存入第1个移存器中；第3个 输入码元存入第2个移存器中；第4个码元存入第3个移存 器中。在这4个码元期间，交织器的输出为“1 x x x”。这 里的“x”表示移存器初始的随机状态。 在图 (b)中的交织器则示出第5至8个码元输入时的工作状 态。 在图 (c)和 (d)中示出的是第9至12个码元以及第13至16个 码元输入时的工作状态。 这样，交织器输出码元的次序将是：1 x x x 5 2 x x 9 6 3 x 13 10 7 4。129第11章差错控制编码?接收端解交织器的工作过程与此相反，如图所示，解交 织器的输出码元的次序将是：x x x x x x x x x x x x 1 2 3 4， 其中前面接收的12个码元无意义，从第13个码元开始才 是有效码元。?一般说来，第1个移存器的容量可以是k比特，第2个移存器 的容量是2k比特，第3个移存器的容量是3k比特，…，直至 第N个移存器的容量是Nk比特。 卷积交织法和矩阵交织法相比，主要优点是延迟时间短和需 要的存储容量小。卷积交织法端到端的总延迟时间和两端所 需的总存储容量均为k(N+1)N个码元，是矩阵交织法的一半。?130第11章差错控制编码?交织器容量和误码率关系?由此曲线可以看 到，交织器容量 大时误码率低， 这是因为交织范 围大可以使交织 器输入码元得到 更好的随机化。10-110-2解10-3 码 后 -4 的10 误 码10-5 率10-610-720交织器容量 100信噪比 (dB)131第11章差错控制编码?11.9 低密度奇偶校验码??低密度奇偶校验(LDPC)码是一种线性分组码，和 Turbo码同属于复合码类。两者的性能相近，且两者的 译码延迟都相当长，所以它们更适用于一些实时性要求 不很高的通信。但是LDPC码比Turbo码的译码简单，更 易实现。 LDPC码的分类：? ? ?规则LDPC码： H矩阵每列具有相同个数的“1” 非规则LDPC码： H矩阵每列中 “1”的个数不一定相同 非规则LDPC码是在规则LDPC码基础上发展出的，它使 解码性能得到改善，使误码率性能比Turbo码还好。132第11章差错控制编码?非规则LDPC码和Turbo码的误比特率性能比较Pe香 农 限图中的虚线是Turbo码的性能，实线是LDPC码的性能 133 当码长n大约在104以上时，LDPC码的性能才比Turbo码好。第11章差错控制编码?LDPC码的构造：?LDPC码和普通的奇偶监督码一样，可以由有n列、m行的奇 偶监督矩阵H确定；n是码长，m是校正子个数。但是其H矩 阵和普通奇偶监督码的有所不同：?首先它是稀疏矩阵，即矩阵中“1”的个数很少，密度很 低；设H矩阵每列有j个“1”，每行有k个“1”，则应有j && m，k && n，且j ? 3。 其次其H矩阵的任意两行的元素不能在相同位置上为 “1”，即H矩阵中没有四角由“1”构成的矩形。??LDPC码通常用上述3个参量(n, j, k)表示。在编码时，设计 好H矩阵后，由H矩阵可以导出生成矩阵G。这样，对于给 定的信息位，不难算出码组。134第11章差错控制编码?LDPC码的解码方法 LDPC码的解码方法也和一般的奇偶监督码的解码方法 不同。基本的解码算法称为置信传播算法，通常简称 BP算法。这种算法实质上是求最大后验概率，类似于 一般的最大似然准则解码算法，但是它需要进行多次迭 代运算，逐步逼近最优的解码值。 LDPC码的具体编解码算法十分复杂，这里不再深入讨 论。135第11章差错控制编码?11.10 网格编码调制?11.10.1网格编码调制(TCM)的基本概念下面将利用一个实例给出TCM的基本概念 ? 复习QPSK系统：QPSK是一个4相相移键控系统，它的每个码元传输2 比 特信息。若在接收端判决时因干扰而将信号相位错判至 相邻相位，则将出现错码。现在，将系统改成8PSK，它 的每个码元可以传输3 比特信息。但是我们仍然令每个 码元传输2 比特信息。第3 比特用于纠错码，例如，采用 码率为2/3的卷积码。这时接收端的解调和解码是作为一 个步骤完成的，不像传统作法，先解调得到基带信号后 再为纠错去解码。136第11章差错控制编码?在纠错编码理论中，码组间的最小汉明距离决定着这种编码 的纠错能力。在TCM中，由于是直接对于已调信号（现在是 8PSK信号）解码，码元之间的差别是载波相位之差，这个差 别是欧氏距离。 在右图中示 出了8PSK信1 d0 = 2sin(?/8) = 0.765?号星座图中的8个信号点。 图中已假设信号振幅等于1，则相邻两信号点 的欧氏距离d0等于0.765。137d1 = √2第11章差错控制编码?两个信号序列的欧氏距离越大，即它们的差别越大，则 因干扰造成互相混淆的可能性越小。 图中的信号点代表某个确定相位的已调信号波形。 为了利用卷积码维特比解码的优点，这时仍然需要用到 网格图。但是，和卷积码维特比解码时的网格图相比， 在TCM中是将这些波形映射为网格图，故TCM网格图中 的各状态是波形的状态。? ?138第11章差错控制编码?11.10.2 TCM信号的产生?集划分方法??基本原则：将信号星座图划分成若干子集，使子集中的 信号点间距离比原来的大。每划分一次，新的子集中信 号点间的距离就增大一次。 A0 d 例：见右图 ? A0是8PSK信号 d B0 B1 的星座图，其中 任意两个信号点 d =2 间的距离为d0。 C1 C0 C2 C3 这个星座被划分 为B0和B1两个子 集，在子集中相 邻信号点间的距 (000) (001) (010) (011) (100) (101) (110) (111) 139 离为d1。0 1 2第11章差错控制编码A0 d0d1B0d2=2B1C0C1C2C3(000) (001)(010)(011)(100)(101)(110)(111)140第11章差错控制编码?在上图中已经示出d1 & d0。将这两个子集再划分一次， 得到4个子集：C0, C1, C2, C3，它们中相邻信号点间的距 离为d2 = 2。显然，d2 & d1 & d0。?在这个例子中，需要根据已编码的3个比特来选择信号点， 即选择波形的相位。 c1, c2, 和c3表示已编码的3个码元，图中最下一行注明了 (c1c2c3)的值。若c1等于“0”，则从A0向左分支走向B0； 若c1等于“1”，则从A0向右分支走向B1。第2和3个码元c2 和c3也按照这一原则选择下一级的信号点。?141第11章差错控制编码?卷积码编码器的方框图：1 k1b 12b 2输入k2未编码比 特c2 c3c1编码输出由上图可见，这个卷积码的约束长度等于3。编码器输出的 前两个比特c1和c2用来选择星座图划分的路径，最后1个比特 c3用于选定星座图第3级（最低级）中的信号点。142第11章差错控制编码?TCM编码器结构? ?方框图 原理： 将k比特输入 信息段分为k1 和k2两段；前k1卷积码 编码器n1选择 子集 选择 子集 中的点 信号点k2k1比特通过一个(n1, k1, m)卷积码编码器，产生n1比特输出，用于选择信号星座图中划分之一，后面的k2比特用于选定 星座图中的信号点。 这表明星座图被划分为2n1个子集，每个子集中含有个信号 点。 在上例编码器方框图中k1 = k2 = 1143第11章差错控制编码?TCM系统8PSK的网格图由于未编码比特有两 b1 b2 ti 时刻 种取值，所以每个状 状态 a 00 态下，有两根线。例 如，设初始状态b1 b2 = 00，k1 = k2 = 0。c1 c2 c3 000 001 010 011 010 011 000 ti +1时刻b10001当输入信号序列k1为 “0110100”时，移存器状态和输出c1与c2之间c01110 111 110 111 100 101100 101的关系示于下表中。d11144第11章差错控制编码?移存器状态和输出之间的关系 k1 b1 b2 0 0状态ac1 0c2 00 1 1 0 1 0 0 00 0 1 1 0 1 0 00 0 0 1 1 0 1 0a a b d c b c a0 0 1 1 0 1 0 00 1 1 1 0 0 1 0145第11章差错控制编码?在第1个输入码元“1” 到达后，输出码元c1状态ab1 b2 ti 时刻 00?和c2由“00”变成“01”， 但是这时的输入信息 位k2可能是“0”或“1”， b 10 所以输出c1 c2 c3可能是 “010”或“011”，这就是 c 01 右图中最高的两条平行 虚线。 在第1个输入码元“1”进入 b1后，b1 b2的状态由“00” d11c1 c2 c3 000 001 010 011 010ti +1时刻011 000001111 110100 110 101111 100 101(a)变到“10”(b)，输出c1 c2 c3可能是“110”或“111”，b1 b2 的状态由b变到d，如图中虚线所示。依此类推。146第11章差错控制编码?网格图和星座图之间的对应关系?每对平行转移必须对应最下一级划分同一子集中的两个信号 点。例如，图中的“000”和“001”同属于子集C0，“010”和 “011”同属于子集C1，等等。这些对信号点具有最大的欧氏 距离(d2 = 2)。 从某一状态出发的所有转移，或到达某一状态的所有转移， 必须属于同一上级子集。例如，图中从状态a出发的转移 “000”、“001”、“010”和“011”都属于子集B0。或者说， 此两对平行转移应具有最大可能的欧氏距离。?147第11章差错控制编码?11.10.3 TCM信号的解调?TCM信号的解调算法?通常采用维特比算法，但是现在的网格图表示的状态是 波形，而不是码组。解码器的任务是计算接收信号序列 路径和各种可能的编码网格路径间的距离。若所有发送 信号序列是等概率的，则判定与接收序列距离最小的可 能路径（又称为最大似然路径）为发送序列。 因为卷积码是线性码，它具有封闭性，故要考察的路径 距离与所用的测试序列无关。所以，不失一般性，可以 选用全“0”序列作为测试序列。?148第11章差错控制编码?例：8PSK信号解码路径 ? 用全“0”序列作为测试序列时，如下图中虚线路径U 所示。图中还用实线示出另一许用波形序列路径V， 它从全“0”序列路径分开又回到全“0”序列路径。 ? 若发送序列是全“0”序列，但是接收序列有错误，使 接收序列路径离开全“0”路径然后又回到全“0”序列， 且中间没有返回状态a，则解码器需要比较此接收序 列路径和U的距离与接收序列路径和V的距离之大小。 若后者小，则将发生一次错误判决。这里的距离是指 欧氏距离。U0 V0 U1 V1 V2 U2 W V3 U3 U4状态a bb1 b200V410 01 11cd149第11章差错控制编码?自由欧氏距离Fed：??自由欧氏距离是指许用波形序列集合中各元素之间的最小 距离。它决定了产生错误判决的概率。自由欧氏距离越大， 错误判决概率越小。 在上例中，U和V两条路径间的欧氏距离d由下式决定：d 2 ? d 2 (U 1 ,V1 ) ? d 2 (U 2 ,V2 ) ? d 2 (U 3 ,V3 ) ? d 2 (000 ， 010) ? d 2 (000 ， 100) ? d 2 (000 ， 010) ??? 2?2? (0.765) ?2? 2?2? 2 ? 0.585? 2 ? 4.585上式是按照在欧氏空间求矢量和的方法计算的。因此，d ? 4.585 ? 2.14150第11章差错控制编码?另外一种许用波形序列的路径是，U1WU3（见上图）。它和 V序列相似，从状态a开始，离开U（虚线路径），再回到状 态a。这个路径和U的距离等于 d 2 ? d 2 (U 1 ,U 1 ) ? d 2 (U 2 ,W ) ? d 2 (U 3 ,U 3 )? d 2 (000 ， 000) ? d 2 (000 ， 001 ) ? d 2 (000 ， 010) ? 0 ? (2) 2 ? 0 ? 4 d＝2即 比较上面两条路径可见，路径U1WU3和路径V相比，前者和 路径U的距离更小。并且，可以逐个验证，这是和路径U距 离最小的许用序列的路径。因此，按照上述定义，上式中的 距离就是这种编码的自由欧氏距离。故可以将其写为 dFed = 2151第11章差错控制编码? ?另一方面，未编码的QPSK信号的相继码元（波形）没有约 束。若将其自由欧氏距离作为参考距离dref，则由下图可知， d ref ? d1 ? 2 所以，可以证明，和未编码QPSK系统相比，8PSK的TCM系 统可以获得的渐近编码增益等于 G8PSK / QPSK ? 20lg(dFed / dref ) ? 3.01 (dB)1 d0 = 2sin(?/8) = 0.765d1 = √2152第11章差错控制编码?在下表中列出了通过大量仿真计算得出的部分8PSK/TCM系 统的(渐近)编码增益。状态数目kG8PSK/QPSK4 816 32 64 1281 22 2 2 23.01 3.604.13 4.59 5.01 5.1725625.75153第11章差错控制编码?11.11 小结154
《通信原理》第六版_樊昌信_曹丽娜答案_理学_高等教育_教育专区。《通信原理》第六版_樊昌信_曹丽娜答案 第二章 2-1 试证明图 P2-1 中周期性信号可以展开为 ...《通信原理》_工学_高等教育_教育专区。通信原理 第 二章 2-1 试证明图 P2-1 中周期性信号可以展开为 (图略) s (t ) = 证明:因为 (?1) n cos(2n ...《通信原理》第六版_樊昌信_曹丽娜答案完整版_电子/电路_工程科技_专业资料 暂无评价|0人阅读|0次下载|举报文档《通信原理》第六版_樊昌信_曹丽娜答案完整版_电子...《通信原理》第六版_樊昌信_曹丽娜答案完整版 2 《通信原理》第六版_樊昌信_曹丽娜答案完整版 2《通信原理》第六版_樊昌信_曹丽娜答案完整版 2隐藏&& 第二章 ...专升本《通信原理》_试卷_答案_教育学_高等教育_教育专区。10. 六十四进制数字基带系统的最大频带利用率的理论值为( )。(2 分) 专升本《通信原理》一、 (共...《通信原理》第六版_樊昌信_曹丽娜作业参考答案_工学_高等教育_教育专区。很完整的答案《通信原理》作业参考答案 通信原理》 1 2 5-17 已知某单频调频波的振幅...《通信原理》思考题答案_工学_高等教育_教育专区。通信原理思考题答案,个人整理。1.2 何谓数字信号,何谓模拟信号,两者的根本区别是什么? 数字信号指电信号的参量仅...《通信原理》第六版_樊昌信、曹丽娜课后答案_第三章__随机过程[1]_理学_高等教育_教育专区。本章练习题: 3-1.设是 其中 查看参考答案 的高斯随机变量,试确定...二、与《通信原理》课相关的前续课程 前面我们已经提到许多通信工专业的基础课,其中与《通信原理》课最相关的是《高等 数学》 、工程数学中的《概率与随机过程》...专升本《通信原理》_试卷_答案_其它_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档专升本《通信原理》_试卷_答案_其它_高等教育_教育专区。专升本《通信...
All rights reserved Powered by
www.tceic.com
copyright &copyright 。文档资料库内容来自网络，如有侵犯请联系客服。