通信原理》_樊昌信_曹丽娜_编著_第六版课件_第11章
《通信原理》_樊昌信_曹丽娜_编著_第六版课件_第11章_基础医学_医药卫生_专业资料。《通信原理》_樊昌信_曹丽娜_编著_第六版课件_第11章
1通信原理?第11章差错控制编码 2第11章差错控制编码?11.1 概述?信道分类：从差错控制角度看随机信道：错码的出现是随机的 ? 突发信道：错码是成串集中出现的 ? 混合信道：既存在随机错码又存在突发错码??差错控制技术的种类检错重发 ? 前向纠错 ? 反馈校验 ? 检错删除? 3第11章差错控制编码?差错控制编码：常称为纠错编码监督码元：上述4种技术中除第3种外，都是在接收 端识别有无错码。所以在发送端需要在信息码元序 列中增加一些差错控制码元，它们称为监督码元。 ? 不同的编码方法，有不同的检错或纠错能力。 ? 多余度：就是指增加的监督码元多少。例如，若编 码序列中平均每两个信息码元就添加一个监督码元 ，则这种编码的多余度为1/3。 ? 编码效率(简称码率) ：设编码序列中信息码元数量 为k，总码元数量为n，则比值k/n 就是码率。 ? 冗余度：监督码元数(n-k) 和信息码元数 k 之比。 ? 理论上，差错控制以降低信息传输速率为代价换取 提高传输可靠性。?3 4第11章差错控制编码?自动要求重发(ARQ)系统?3种ARQ系统?停止等待ARQ系统3ACK 3发送码组123NAK 34ACK 45ACK 55NAK 56tACK接收码组 ACK 2 1有错码组?有错码组t??数据按分组发送。每发送一组数据后发送端等待接 收端的确认(ACK)答复，然后再发送下一组数据。 图中的第3组接收数据有误，接收端发回一个否认 (NAK)答复。这时，发送端将重发第3组数据。 系统是工作在半双工状态，时间没有得到充分利用 ，传输效率较低。 5第11章差错控制编码?拉后ARQ系统3 4 5 6 7重 发 码重 发 码发 送 数1 据25组 6 7 5 6789 10 11 9 10 11 12 组接 收 数1据2ACK13456NAK5ACK578NAK 9 10 11 9 9 10 11 12有错码 有错码组?组 发送端连续发送数据组，接收端对于每个接收到的数 据组都发回确认(ACK)或否认(NAK)答复。?例如，图中第5组接收数据有误，则在发送端收到第5 组接收的否认答复后，从第5组开始重发数据组。 在这种系统中需要对发送的数据组和答复进行编号， 以便识别。显然，这种系统需要双工信道? 6第11章差错控制编码?选择重发ARQ系统2 3 4 5 6 5 8 9 10 11重发码组 7 重发码组 9 12 13 14NAK5 ACK5 NAK9 ACK91发送数据 接收数据12ACK134567589 10 119 12 1314有错码组?有错码组它只重发出错的数据组，因此进一步提高了传输效率 。 7第11章差错控制编码?ARQ的主要优点：和前向纠错方法相比?? ?监督码元较少即能使误码率降到很低，即码率较高 ； 检错的计算复杂度较低； 检错用的编码方法和加性干扰的统计特性基本无关 ，能适应不同特性的信道。 需要双向信道来重发，不能用于单向信道，也不能 用于一点到多点的通信系统。 因为重发而使ARQ系统的传输效率降低。 在信道干扰严重时，可能发生因不断反复重发而造 成事实上的通信中断。 在要求实时通信的场合，例如电话通信，往往不允 许使用ARQ法。?ARQ的主要缺点：?? ?? 第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个错码。 但是这种码不能发现一个码组中的两个错码，因为 发生两个错码后产生的是许用码组。??? 1 1第11章差错控制编码?检错和纠错????这种编码只能检测错码，不能纠正错码。例如，当接 收码组为禁用码组“100”时，接收端将无法判断是哪一位 码发生了错误，因为晴、阴、雨三者错了一位都可以变成 “100”。 要能够纠正错误，还要增加多余度。例如，若许用码 组只有两个：“000”（晴），“111”（雨），其他都是禁 用码组，则能够检测两个以下错码，或能够纠正一个错码 。 例如，当收到禁用码组“100”时，若当作仅有一个错码， 则可以判断此错码发生在“1”位，从而纠正为“000”（晴 ）。因为“111”（雨）发生任何一位错码时都不会变成 “100”这种形式。 但是，这时若假定错码数不超过两个，则存在两种可能性 ：“000”错一位和“111”错两位都可能变成“100”，因而 1 2第11章差错控制编码?分组码的结构?? ?将信息码分组，为每组信息码附加若干监督码的编码称 为分组码 。 在分组码中，监督码元仅监督本码组中的信息码元。 信息位和监督位的关系：举例如下信息位 晴 云 阴 雨 00 01 10 11监督位 0 1 1 0 1 3第11章差错控制编码?分组码的一般结构?分组码的符号：(n, k) ? N － 码组的总位数，又称为码组的长度（码长）， ? k － 码组中信息码元的数目， ? n – k ＝ r － 码组中的监督码元数目，或称监督位数目。 第11章差错控制编码?分组码的码重和码距?码重：把码组中“1”的个数目称为码组的重量，简称码重 。 码距：把两个码组中对应位上数字不同的位数称为码组的 距离，简称码距。码距又称汉明距离。 例如，“000”＝晴，“011”＝云，“101”＝阴，“110”＝ 雨，4个码组之间，任意两个的距离均为2。 最小码距：把某种编码中各个码组之间距离的最小值称为 最小码距(d0)。例如，的编码的最小码距d0 = 2。??? 1 5第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)就是此立方体各顶点的坐 标。而上述码距概念在此图中就对应于各顶点之间沿立方体 各边行走的几何距离。 由此图可以直观看出，上例中4个准用码组之间的距离均为2 。? 1 6第11章差错控制编码?码距和检纠错能力的关系??一种编码的最小码距d0的大小直接关系着这种编码的检错 和纠错能力 为检测e个错码，要求最小码距 d0 ? e + 1 【证】设一个码组A位于O点。若码组A中发生一个错码， 则我们可以认为A的将移动至以O点为圆心，以1为半 径的圆上某点，但其不会超出此圆。 若码组A中发生两位错码，则其不会超出以O点为圆 心，以2为半径的圆。因此，只要最小码距不小于 3，码组 A发生两位以下错码时， 不可能变成另一个准用 0 1 2 3 码组，因而能检测错码 A B 汉明距离 的位数等于2。 ed0 1 7第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 汉明距离t 1 8第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 – 1 = 5 – 1 = 4，按照纠错能力公式纠错时，能纠正 2 个错码。但是，不能同时作到两者，因为当错码位数超过纠 错能力时，该码组立即进入另一码组的圆内而被错误地“纠 正”了。例如，码组A若错了3位，就会被误认为码组B错了 2位造成的结果，从而被 错“纠”为B。这就 是说，检错和纠错 公式不能同时成立0 A 1 2 3 4 B 5 汉明距离td0t或同时运用。 20第11章差错控制编码所以，为了在可以纠正t个错码的同时，能够检测e个错码 ，就需要像下图所示那样，使某一码组（譬如码组 A）发 生e个错误之后所处的，与其他码组（譬如码组 B）的 纠错圆圈至少距离等于1，不然将落在该纠错圆上从而发 生错误地“纠正”。因此，由此图可以直观看出，要求最 小码距d0 ? e ? t ?1A(e ? t )Bt e1t汉明距离这种纠错和检错结合的工作方式简称纠检结合。 2 1第11章差错控制编码这种工作方式是自动在纠错和检错之间转换的。当错码数量 少时，系统按前向纠错方式工作，以节省重发时间，提高传 输效率；当错码数量多时，系统按反馈重发方式纠错，以降 低系统的总误码率。所以，它适用于大多数时间中错码数量 很少，少数时间中错码数量多的情况。 2 2第11章差错控制编码?11.3 纠错编码的性能?系统带宽和信噪比的矛盾：?由上节所述的纠错编码原理可知，为了减少接收错误码 元数量，需要在发送信息码元序列中加督码元。这 样作的结果使发送序列增长，冗余度增大。若仍须保持 发送信息码元速率不变，则传输速率必须增大，因而增 大了系统带宽。系统带宽的增大将引起系统中噪声功率 增大，使信噪比下降。信噪比的下降反而又使系统接收 码元序列中的错码增多。一般说来，采用纠错编码后， 误码率总是能够得到很大改善的。改善的程度和所用的 编码有关。 2 3第11章差错控制编码?编码性能举例?10-1未采用纠错编码时， 若接收信噪比等于 10-2 7dB，编码前误码率 约为8?10-4，图中A 10-3 点，在采用纠错编码 P e 后，误码率降至约4 -4 10 ?10-5，图中B点。这样， 不增大发送功率就能 10-5 降低误码率约一个半 数量级。? A ?EB?编码后 ? ? C D10-6 信噪比 (dB) 2 4第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为?编码后 ? ? C D10-5 10-6编码增益。?两种情况付出的代 价是带宽增大。信噪比 (dB) 2 5第11章差错控制编码?传输速率和Eb/n0的关系 对于给定的传输系统Eb PsT Ps P ? ? ? s n0 n0 n0 (1 / T ) n0 RB10-1 10-2? A ?式中，RB为码元速率。 10-3 若希望提高传输速率， Pe 由上式看出势必使信 10-4 噪比下降，误码率增 大。假设系统原来工作 在图中C点，提高速率后 10-5 由C点升到E点。但加用 纠错编码后，仍可将误码 -6 10 率降到D点。这时付出的 代价仍是带宽增大。EB? 编码后 ? D ? C信噪比 (dB) 2 6第11章差错控制编码?11.4简单的实用编码?11.4.1 奇偶监督码?奇偶监督码分为奇数监督码和偶数监督码两种，两者的 原理相同。在偶数监督码中，无论信息位多少，监督位 只有1位，它使码组中“1”的数目为偶数，即满足下式条 件： an?1 ? an?2 ? ? ? a0 ? 0式中a0为监督位，其他位为信息位。 这种编码能够检测奇数个错码。在接收端，按照上式求 “模2和”，若计算结果为“1”就说明存在错码，结果为 “0”就认为无错码。 奇数监督码与偶数监督码相似，只不过其码组中“ 1”的 数目为奇数： an?1 ? an?2 ? ? ? a0 ? 1 2 7第11章差错控制编码?11.4.2 二维奇偶监督码（方阵码）?二维奇偶监督码的构成它是先把上述奇偶监督码的若干码组排成矩阵，每一码组 写成一行，然后再按列的方向增加第二维监督位，如下图 1 1 1 所示 a1 a ? a a n ?1 n?2 1 02 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为按列进行第二次编码所增加的监督位，它 第11章差错控制编码?二维奇偶监督码的性能?这种编码有可能检测偶数个错码。因为每行的监督位虽 然不能用于检测本行中的偶数个错码，但按列的方向有 可能由cn-1 cn-2 ? c1 c0等监督位检测出来。有一些偶数错 码不可能检测出来。例如，构成矩形的4个错码，譬如图 2 2 m m 中 an a a a ?2 1 n?2 1 错了，就检测不出。?这种二维奇偶监督码适于检测突发错码。因为突发错码 常常成串出现，随后有较长一段无错区间。 由于方阵码只对构成矩形四角的错码无法检测，故其检 错能力较强。??二维奇偶监督码不仅可用来检错，还可以用来纠正一些 2 9第11章差错控制编码?11.4.3 恒比码?在恒比码中，每个码组均含有相同数目的“1”（和 “0”）。由于“1”的数目与“0”的数目之比保持恒定 ，故得此名。 这种码在检测时，只要计算接收码组中“1”的数目是 否对，就知道有无错码。 恒比码的主要优点是简单和适于用来传输电传机或其 他键盘设备产生的字母和符号。对于信源来的二进制 随机数字序列，这种码就不适合使用了。?? 3 0第11章差错控制编码?11.4.4 正反码?正反码的编码：??它是一种简单的能够纠正错码的编码。其中的监督位数 目与信息位数目相同，监督码元与信息码元相同或者相 反则由信息码中“1”的个数而定。 例如，若码长n = 10，其中信息位 k = 5，监督位 r = 5。 其编码规则为： ? 当信息位中有奇数个“ 1”时，监督位是信息位的简 单重复； ? 当信息位有偶数个“ 1”时，监督位是信息位的反码 。 ? 例如，若信息位为11001，则码组为1100111001；若 信息位为10001，则码组为1000101110。 3 1第11章差错控制编码?正反码的解码?在上例中，先将接收码组中信息位和监督位按模 2 相加 ，得到一个5位的合成码组。然后，由此合成码组产生一 个校验码组。 若接收码组的信息位中有奇数个“1”，则合成码组就是 校验码组；若接收码组的信息位中有偶数个“ 1”，则取 合成码组的反码作为校验码组。 最后，观察校验码组中“1”的个数，按下表进行判决及 纠正可能发现的错码。?? 第11章差错控制编码?校验码组和错码的关系错码情况 无错码 信息码中有1位错码，其对应校验码组中 “0”的 监督码中有1位错码，其对应校验码组中 “1”的 错码多于1个校验码组的组成 1 2 3 4 全为“0” 有4个“1”和1个 “0” 有4个“0”和1个 “1” 其他组成例如，若发送码组为1100111001，接收码组中无错码， 则合成码组应为11001?11001=00000。由于接收码组信 息位中有奇数个“1”，所以校验码组就是00000。按上表 判决，结论是无错码。 3 3第11章差错控制编码若传输中产生了差错，使接收码组变成1000111001，则合成 码组为10001?11001＝01000。由于接收码组中信息位有偶 数个“1”，所以校验码组应取合成码组的反码，即10111。 由于其中有4个“1”和1个“0”，按上表判断信息位中左边第 2位为错码。 若接收码组错成1100101001，则合成码组变成11001?01001 ＝10000。由于接收码组中信息位有奇数个“ 1”，故校验码 组就是10000，按上表判断，监督位中第1位为错码。 最后，若接收码组为1001111001，则合成码组为 10011?11001＝01010，校验码组与其相同，按上表判断， 这时错码多于1个。?上述长度为10的正反码具有纠正1位错码的能力，并能检测 全部2位以下的错码和大部分2位以上的错码。 第11章差错控制编码?11.5 线性分组码?基本概念代数码：建立在代数学基础上的编码。 ? 线性码：按照一组线性方程构成的代数码。在线性 码中信息位和监督位是由一些线性代数方程联系着 的。 ? 线性分组码：按照一组线性方程构成的分组码 。?本节将以汉明码为例引入线性分组码的一般原理 。 3 5第11章差错控制编码?汉明码～能够纠正1位错码且编码效率较高的一种线性分组码 ? 汉明码的构造原理。?在偶数监督码中，由于使用了一位监督位 a0，它和信息 位an-1 … a1一起构成一个代数式：an?1 ? an?2 ? ? ? a0 ? 0 在接收端解码时，实际上就是在计算S ? an?1 ? an?2 ? ? ? a0若S = 0，就认为无错码；若S = 1，就认为有错码。现 将上式称为监督关系式，S称为校正子。由于校正子S 只有两种取值，故它只能代表有错和无错这两种信息， 而不能指出错码的。 3 6第11章差错控制编码?若监督位增加一位，即变成两位，则能增加一个类似的监督 关系式。由于两个校正子的可能值有4中组合： 00，01，10 ，11，故能表示4种不同的信息。若用其中1种组合表示无错 ，则其余3种组合就有可能用来一个错码的3种不同 。同理，r个监督关系式能1位错码的(2r – 1)个可能 。 一般来说，若码长为n，信息位数为k，则监督位数r＝n－k 。如果希望用r个监督位构造出r个监督关系式来1位错 码的n种可能，则要求2r ?1 ? n 或 2r ? k ? r ? 1?下面通过一个例子来说明如何具体构造这些监督关系式。 3 7第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错码 a0 a1S1 S2 S3 101 110错码 a4 a5100011a2a3111000a6无错码 38第11章差错控制编码由表中可见，仅当一位错码的在 a2 、a4、a5或a6时 ，校正子S1为1；否则S1为零。这就意味着a2 、a4、a5和a6四 个码元构成偶数监督关系：S1 ? a6 ? a5 ? a4 ? a2同理， a1、a3、a5和a6构成偶数监督关系：S 2 ? a6 ? a5 ? a3 ? a1以及a0、a3、a4 和a6构成偶数监督关系S 3 ? a 6 ? a 4 ? a3 ? a 0 第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 0000 0001 0010 监督位 a2 a1 a0 000 011 101 信息位 a6 a5 a4 a3 1000 1001 1010 监督位 a2 a1 a0 111 100 0100011 1101011011 0111 4 1第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 – r/n，故当n很大和r很 小时，码率接近1。可见，汉明码是一种高效码。 4 2第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? ?a4 ? ?0? ?1101010? ?a ? ? ?0? ? ? ? 3? ? ? ? ? 0? ? ?1011001? ? ? a2 ? ? ? ? ?a1 ? ?a ? ? 0? 上式还可以简记为 H ? AT = 0 T 或 A ? HT = 0（模 2 ） 44第11章差错控制编码H ? AT = 0 T 或 式中 A ? HT = 0?1110100? ? H ?? 1101010 ? ? ? ?1011001? ?A = [ a 6 a 5 a 4 a 3 a 2 a 1 a 0]0 = [000]右上标“T”表示将矩阵转置。例如，HT是H的转置，即HT的 第一行为H的第一列，HT的第二行为H的第二列等等。将H称为监督矩阵。只要监督矩阵H给定，编码时监督位和信息位的关系就完全 确定了。 第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矩阵称为典型阵。 4 6第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 ? a 也可以改写成矩阵形式： ? 2 ? ?1110? ? ? ?a ? ? ?1101? ?a5 ? ? 1? ? ? ?a ? 4 ? ? ? ? 1011 a ? ? ? ? 0? ? ? a3 ? 4 7第11章差错控制编码?111 ? ?110 ? ?a2 a1a0 ? ? ?a6 a5 a4 a3 ?? ? ? ?a6 a5 a4 a3 ?Q ?101 ? ? ? 011 ? ??a6 ? ?a2 ? ?1110? ? ? ?a ? ? ?1101? ?a5 ? ? 1? ? ? ?a ? 4 ? ? ? ? 1011 a ? ? ? ? 0? ? ? a3 ?或者写成式中，Q为一个k ? r阶矩阵，它为P的转置，即 Q = PT 上式表示，在信息位给定后，用信息位的行矩阵乘矩阵 Q就 产生出监督位。 4 8第11章差错控制编码我们将Q的左边加上1个k ? k阶单位方阵，就构成1个矩阵G ?1000?111 ? ?0100?110? ? G ? ?I k Q ? ? ? ?0010?101? ? ? 0001 ? 011 ? ? G称为生成矩阵，因为由它可以产生整个码组，即有?a6 a5 a 4 a3 a 2 a1a0 ? ? ?a6 a5 a 4 a3 ?? GA ? [a6 a5 a4 a3 ] ? G或者因此，如果找到了码的生成矩阵G，则编码的方法就完全确 定了。具有[IkQ]形式的生成矩阵称为典型生成矩阵。由典型 生成矩阵得出的码组A中，信息位的不变，监督位附加 于其后。这种形式的码称为系统码。 4 9第11章差错控制编码?G矩阵的性质： 1) G矩阵的各行是线性无关的。因为由上式可以看出， 任一码组A都是G的各行的线性组合。G共有k行，若它们 线k种不同的码组A，它恰是有k 位信息位的全部码组。若G的各行性相关的，则不 可能由G生成2k种不同的码组了。2) 实际上，G的各行本身就是一个码组。因此，如果已 有k个线性无关的码组，则可以用其作为生成矩阵 G，并 由它生成其余码组。 5 0第11章差错控制编码?错码矩阵和错误图样 ? 一般说来，A为一个n列的行矩阵。此矩阵的 n个元素就 是码组中的n个码元，所以发送的码组就是A。此码组在 传输中可能由于干扰引入差错，故接收码组一般说来与 A不一定相同。?若设接收码组为一n列的行矩阵B，即 B ? ?bn ?1bn ? 2 ? b1b0 ? 则发送码组和接收码组之差为 B – A = E (模2) 它就是传输中产生的错码行矩阵E ? ?en ?1en ? 2 ? e1e0 ?当bi ? ai 当b i ? ai式中?0, ei ? ? ?1, 5 1第11章差错控制编码因此，若ei = 0，表示该接收码元无错；若ei = 1，则表示该 接收码元有错。 B–A=E 可以改写成 B=A+E 例如，若发送码组A = [1000111]，错码矩阵E = [0000100]， 则接收码组B = [1000011]。 错码矩阵有时也称为错误图样。 5 2第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 = 0 将上两式相加，得出 A1 ? HT + A2 ? HT = (A1 + A2) HT = 0 所以(A1 + A2)也是一个码组。 由于线性码具有封闭性，所以两个码组(A1和A2)之间的距 离（即对应位不同的数目）必定是另一个码组 (A1 + A2)的 重量（即“1”的数目）。因此，码的最小距离就是码的最 小重量（除全“0”码组外）。 第11章差错控制编码?11.6 循环码?11.6.1 循环码原理?循环性：循环性是指任一码组循环一位（即将最右端的 一个码元移至左端，或反之）以后，仍为该码中的一个 码组。在下表中给出一种(7, 3)循环码的全部码组。码组编号 1 2信息位 a6a5a4 000 001监督位 a3a2a1a0 0000 0111码组编号 5 6信息位 a6a5a4 100 101监督位 a3a2a1a0 1011 010010例如，表中的第2码组向右移一位即得到第5码组；第6码 组向右移一位即得到第7码组。 5 5第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) 也是该编码中的码组。 5 6第11章差错控制编码?码多项式?码组的多项式表示法 把码组中各码元当作是一个多项式的系数，即把一个长度 为n的码组表示成 T ( x) ? a n ?1 x n ?1 ? a n ? 2 x n ? 2 ? ? ? a1 x ? a 0 例如，上表中的任意一个码组可以表示为T ( x) ? a6 x 6 ? a5 x 5 ? a4 x 4 ? a3 x 3 ? 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 ? x2 ?1这种多项式中，x仅是码元的标记，例如上式表示第 7 码组中a6、a5、a2和a0为“1”，其他均为0。因此我们并不 关心x的取值。 5 7第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 除得的余数。 5 8第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) ） 同理 因为x4 ? x2 ?1 ? x2 ? x ?1x x3 + 1 x4 +x2 + 1x4 + x（模( x 3 ? 1) ）应当注意，由于在模2运算中， 用加法代替了减法，故余项不 是x2 – x + 1，而是x2 + x + 1 。x2 +x +1 5 9第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) ? a n ?1?i x n ?1 ? a n ? 2?i x n ? 2 ? ? ? a 0 x i ? a n ?1 x i ?1 ? ? ? a n ?i 6 0第11章差错控制编码T ?( x) ? a n ?1?i x n ?1 ? a n ? 2?i x n ? 2 ? ? ? a 0 x i ? a n ?1 x i ?1 ? ? ? a n ?i上式中T ?(x)正是T(x)代表的码组向左循环移位i次的结果。 因为原已假定T(x)是循环码的一个码组，所以T? (x)也必为该 码中一个码组。例如，循环码组T ( x) ? x 6 ? x 5 ? 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)运 算的一个余式。 第11章差错控制编码?循环码的生成矩阵G?由上节中公式 A ? [a6 a5 a4 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。 第11章差错控制编码?在循环码中除全“0”码组外，再没有连续k位均为“0”的码 组，即连“0”的长度最多只能有(k - 1)位。否则，在经过若 干次循环移位后将得到一个k位信息位全为“0”，但监督位 不全为“0”的一个码组。这在线性码中显然是不可能的。因 此，g(x)必须是一个项不为“0”的(n - k)次多项式，而 且这个g(x)还是这种(n, k)码中次数为(n – k)的唯一多项式。 因为如果有两个，则由码的封闭性，把这两个相加也应该是 一个码组，且此码组多项式的次数将小于 (n – k)，即连续 “0”的个数多于(k – 1)。显然，这是与前面的结论矛盾的， 故是不可能的。我们称这唯一的(n – 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 – k = 4。 由此表可见，唯一的一个(n – 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? ? 6 4第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 – 1)的多项式乘g(x)都是码多项式。需要说 明一点，两个矩阵相乘的结果应该仍是一个矩阵。上式中两 个矩阵相乘的乘积是只有一个元素的一阶矩阵，这个元素就 是T(x)。为了简洁，式中直接将乘积写为此元素。 6 5第11章差错控制编码?如何寻找任一(n, k)循环码的生成多项式由上式可知，任一循环码多项式T(x)都是g(x)的倍式，故 它可以写成 T (x ) = h (x )? g (x ) 而生成多项式g(x)本身也是一个码组，即有 T ? (x ) = g (x ) 由于码组T ?(x)是一个(n – 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 第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 – k)次因式。例如 ，(x7 + 1)可以分解为x 7 ? 1 ? ( x ? 1)( x 3 ? x 2 ? 1)( x 3 ? x ? 1)为了求(7, 3)循环码的生成多项式g(x)，需要从上式中找到一 个(n – k) = 4次的因子。不难看出，这样的因子有两个，即 6 7第11章差错控制编码( x ? 1)( x 3 ? x 2 ? 1) ? x 4 ? x 2 ? x ? 1( x ? 1)( x 3 ? x ? 1) ? x 4 ? x 3 ? x 2 ? 1 以上两式都可作为生成多项式。不过，选用的生成多项式不同，产生出的循环码码组也不同。 6 8第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 – k)。将此余式r(x)加于信息位之后作为监督位，即将 r(x)和xn - k m(x)相加，得到的多项式必定是一个码多项 式。因为它必须能被g(x)整除，且商的次数不大于(k – 1) 6 9第11章差错控制编码?编码步骤： n - k乘m(x)。这一运算实际上是在信息码后附加上(n – ? 用x k)个“0”。例如，信息码为110，它相当于m(x) = x2 + x 。当n – k = 7 – 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 上式相当于1100000 101 ? 111 ? 10111 10111 第11章差错控制编码?编出的码组T(x)为 T(x) = xn - k m(x) + r(x) 在上例中，T(x) = 1100000 + 101 = 1100101，它就是上 表中的第7码组。 7 1第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)整除。这时 的错码就不能检出了。这种错误称为不可检错误。不可 检错误中的误码数必定超过了这种编码的检错能力。 7 2第11章差错控制编码?纠错解码原理：为了能够纠错，要求每个可纠正的错误图 样必须与一个特定余式有一一对应关系。因为只有存在上 述一一对应的关系时，才可能从上述余式唯一地决定错误 图样，从而纠正错码。因此，原则上纠错可按下述步骤进 行： 用生成多项式g(x)除接收码组R(x)，得出余式r(x)。 ? 按余式r(x)，用查表的方法或通过某种计算得到错误图 样E(x)；例如，通过计算校正子S和查表，就可以确定 错码的。 ? 从R(x)中减去E(x)，便得到已经纠正错码的原发送码组 T(x)。 通常，一种编码可以有几种纠错解码方法，上述解码方法 称为捕错解码法。???目前多采用软件运算实现上述编解码运算。 7 3第11章差错控制编码?11.6.3 截短循环码????截短目的：在设计纠错编码方案时，常常信息位数 k、码 长n和纠错能力都是预先给定的。但是，并不一定有恰好 满足这些条件的循环码存在。这时，可以采用将码长截短 的方法，得出满足要求的编码。 截短方法：设给定一个(n, k)循环码，它共有2k种码组，现 使其前i (0 i k)个信息位全为“0”，于是它变成仅有2k-i 种码组。然后从中删去这i位全“0”的信息位，最终得到一 个(n – i, k – i)的线性码。将这种码称为截短循环码。 截短循环码性能：循环码截短前后至少具有相同的纠错能 力，并且编解码方法仍和截短前的方法一样。 例：要求构造一个能够纠正1位错码的(13, 9)码。这时可以 由(15, 11)循环码的11种码组中选出前两信息位均为“0”的 码组，构成一个新的码组集合。然后在发送时不发送这两 位“0”。于是发送码组成为(13, 9)截短循环码。 第11章差错控制编码?11.6.4 BCH码??什么是BCH码？它是一种获得广泛应用的能够纠正多个错 码的循环码，是以3位发明这种码的人名(Bose - Chaudhuri - Hocguenghem)命名的。BCH码的重要性在于它解决了生 成多项式与纠错能力的关系问题，可以在给定纠错能力要 求的条件下寻找到码的生成多项式。有了生成多项式，编 码的基本问题就随之解决了。 BCH码分类： ? 本原BCH码：其生成多项式 g(x)中含有最高次数为 m的 本原多项式，且码长为n = 2m – 1，(m ? 3，为正整数)。 ? 非本原BCH码：其生成多项式中不含这种本原多项式 ，且码长n是(2m – 1)的一个因子，即码长n一定除得尽 2m – 1。 ? 本原多项式的概念将在下一章介绍。 7 5第11章差错控制编码?BCH码的性能：?码长n与监督位、纠错个数 t 之间的关系： 对于正整数m (m ? 3)和正整数t m / 2，必定存在一个码 长为n = 2m – 1，监督位为n – 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)汉明码。? 7 6第11章差错控制编码?BCH码的设计??在工程设计中，一般不需要用计算方法去寻找生成多项式 g(x)。因为前人早已将寻找到的g(x)列成表，故可以用查 表法找到所需的生成多项式。 下表给出了码长n ? 127的二进制本原BCH码生成多项式。 7 7第11章差错控制编码n=3 k t 1 1 n=7 k t 4 1 1 3 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 12471 1701317 166623567 1033500423 7 441 5 3 155 1737 全部为1n = 15 k t g(x) 11 1 23 7 2 721 5 3 2467 1 7 77777 7 8第11章差错控制编码n = 31 k t 26 1 21 2 16 3 11 5 6 7 1 15 n = 127 g(x) k t g(x) 45 120 1 211 3551 113 2 41567 107657 106 3 11554743 5423325 99 4 3447023271 313365047 92 5 7 85 6 78 7 15 71 9 7753 64 10 3100045 57 11 053517721 50 13 43 15 343 36 ?15 5 29 ?22 155 22 ?23 647043 15 ?27 17604353 8 ?31 7733130217 7 9第11章差错控制编码?表中给出的生成多项式系数是用8进制数字列出的。 例如，g(x) = (13)8是指g(x) = x3 + x + 1，因为(13)8 = (1011)2，后者就是此3次方程g(x)的各项系数。 下表列出了部分非本原BCH码的生成多项式参数。t g(x) n k t g(x)?nk17 21 23 33 419 12 12 22 212 2 3 2 4727 1663 5343 5145 664713347 65 65 7324 53 40 465 2 4 443073357 10761 354300067 1717773537 8 0第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个错码。它比汉明码的纠错能力强很多， 付出的代价是解码更复杂，码率也比汉明码低。此外，它不 再是循环码了。 8 1第11章差错控制编码?11.6.5 RS码：它是一类具有很强纠错能力的多进制BCH码。????若仍用n表示RS码的码长，则对于m进制的RS码，其码长需 要满足下式：n = m – 1 = 2q – 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 – 1)（二进制码元） 监督码：r = 2qt（二进制码元） 第11章差错控制编码?由于RS码能够纠正t个m进制错码，或者说，能够纠正 码组中t个不超过q位连续的二进制错码，所以RS码特别 适用于存在突发错误的信道，例如移动通信网等衰落信 道中。此外，因为它是多进制纠错编码，所以特别适合 用于多进制调制的场合。 8 3第11章差错控制编码?11.7 卷积码?非分组码概念：?卷积码是一种非分组码。通常它更适用于前向纠错，因 为对于许多实际情况它的性能优于分组码，而且运算较 简单。 卷积码在编码时虽然也是把k个比特的信息段编成n个比 特的码组，但是监督码元不仅和当前的k比特信息段有关 ，而且还同前面m = (N – 1)个信息段有关。所以一个码 组中的监督码元监督着N个信息段。通常将N称为编码约 束度，并将nN称为编码约束长度。一般说来，对于卷积 码，k 和 n 的值是比较小的整数。我们将卷积码记作(n, k, N)。码率则仍定义为k / n。? 8 4第11章差错控制编码?11.7.1 卷积码的基本原理?编码器原理方框图… … 2k … 3k 1 k 1 … k 1 … k 1 … k … … … … … … … Nk1 … k Nk级 移存器每次输 入 k比特12… … … …nn个模2 加每输入k比特旋转1周 编码输出 85第11章差错控制编码?例： (n, k, N) = (3, 1, 3)卷积码编码器?方框图输入biM bi 1M bi-1 2M b 3 i-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 ? 2 8 6第11章差错控制编码在下图中用虚线示出了信息位bi的监督位和各信息位之间 的约束关系。这里的编码约束长度nN等于9。输入bi-2b i －1bi t输出ci-2di-2ei-2ci-1di-1ei-1cidieit 87第11章差错控制编码?11.7.2 卷积码的代数表述上式表示卷积码也是一种线性码。一个线性码完全由一个 监督矩阵H或生成矩阵G所确定。下面就来寻找这两个矩阵 。?监督矩阵H现在仍从的实例开始分析。假设上图中在第 1个信 息位b1进入编码器之前，各级移存器都处于“ 0”状态， 则监督位di、ei和信息位bi之间的关系可以写为 8 8第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 ? b1? ? 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 ? ? ? ? ? ? b1 ? d1 ? 0在两个式子和后面的式子中，为简便计，用“＋”代替 “?”。 将上式用矩阵表示时，可以写成 8 9第11章差错控制编码?b1 ? ?d ? 1 ? ? 11 ? ? ?101 ? ?e1 ? ? ? ?b2 ? ?00011 ?? ? ? ? ?d 2 ? ?100101 ? ?e ? ?10000011 ? ? 2 ? ? ?O ? ? ? ?b3 ? ?100100101 ?? ? ? ? ?d 3 ? ? ? ? e3 ? ?1? ? ? ????? ? ?b4 ? ? ?? ? ?d 4 ? ?e ? ? 4?与11.5节公式H ? AT = 0T对比，可以看出监督矩阵为 9 0第11章差错控制编码?11 ? ?101 ? ? ? ?00011 ? ? ? 100101 ? ? ? H ? ?10000011 ? ? ?100100101 ? ? ? ? ? ?1? ????? ? ? ?由此例可见，卷积码的监督矩阵H是一个有头无尾的半无 穷矩阵。此外，这个矩阵的每3列的结构是相同的，只是 后3列比前3列向下移了两行。例如，第4 ~ 6列比第1 ~ 3列 低2行。自第7行起，每两行的左端比上两行多了3个“0” 9 1第11章差错控制编码虽然这样的半无穷矩阵不便于研究，但是只要研究产生前 9 个码元（9为约束长度）的监督矩阵就足够了。不难看出， 这种截短监督矩阵的结构形式如下图所示：nn–kH1 =(n – k)N由此图可见，H1的最左边是n列(n-k)N行的一个子矩阵，且 向右的每n列均相对于前n列降低(n - k)行。 9 2第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? ?10000011 ? ? 3 ? ? 100100101 ? ? ? ?式中 ?10 ? I2 ? ? ? — 2阶单位方阵； ?01? Pi — 1 ? 2阶矩阵，i = 1, 2, 3； O2 — 2阶全零方阵。 9 3第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 – k)阶单位方阵； Pi — k ? (n – k)阶矩阵； On-k — (n – k)阶全零方阵。有时还将H1的末行称为基本监督矩阵h h = [PN On-k PN-1 On-k PN-2 On-k ? ? ? P1 In-k]它是卷积码的一个最重要的矩阵，因为只要给定了 h，则H1 也就随之决定了。或者说，我们从给定的 h不难构造出H1。 9 4第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）。 第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的转置： Q i = P iT (i = 1, 2, ?) 一般说来，截短生成矩阵具有如下形式： 第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 – k)?k阶矩阵； Ok － k阶全零方阵。 并将上式中矩阵第一行称为基本生成矩阵 g ＝ [Ik Q1 Ok Q2 Ok Q3?Ok QN] 同样，如果基本生成矩阵g已经给定，则可以从已知 的信息位得到整个编码序列。 9 8第11章差错控制编码?11.7.3 卷积码的解码?分类：?代数解码：利用编码本身的代数结构进行解码，不考虑 信道的统计特性。大数逻辑解码，又称门限解码，是卷 积码代数解码的最主要一种方法，它也可以应用于循环 码的解码。大数逻辑解码对于约束长度较短的卷积码最 为有效，而且设备较简单。 概率解码：又称最大似然解码。它基于信道的统计特性 和卷积码的特点进行计算。针对无记忆信道提出的序贯 解码就是概率解码方法之一。另一种概率解码方法是维 特比算法。当码的约束长度较短时，它比序贯解码算法 的效率更高、速度更快，目前得到广泛的应用。? 9 9第11章差错控制编码?大数逻辑解码 ? 工作原理信息位信息位移存器 校正子计算输入 监督位??? ???输出修正校正子校正子移存器 错码检测????图中首先将接收信息位暂存于移存器中，并从接收码 元的信息位和监督位计算校正子。然后，将计算得出 的校正子暂存，并用它来检测错码的。在信息位 移存器输出端，接有一个模2加电；当检测到输出 的信息位有错时，在输出的信息位上加“ 1”，从而纠 正之。 100第11章差错控制编码?这里的错码检测是采用二进制码的大数逻辑解码算法。 它利用一组“正交”校验方程进行计算。 这里的“正交” 定义：若被校验的那个信息位出现在校 验方程组的每一个方程中，而其他的信息位至多在一个 方程中出现，则称这组方程为正交校验方程。这样就可 以根据被错码影响了的方程数目在方程组中是否占多数 来判断该信息位是否错了。下面将用一个实例来具体讲 述这一过程。? 1 0 1?第11章差错控制编码例：(2, 1, 6)卷积码 ? 编码器方框图 输入b6 b5 b4 b3 b2 b1 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? 1 0 2第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)称为校正子。 正交校验方程组 上式经过简单线性变换后，得出如下正交校验方程组： 1 0 3第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的错误。 1 0 4第11章差错控制编码?解码器方框图 按照这一原理画出的此(2, 1, 6)卷积码解码器方框图如下6 b6输入信息位移存器 5 4 3 2 b5 b4 b3 b2重算监督位ci1 b1输出接督位计算校正子Si校正子S iS6S5校正子移存器 S4 S3 S2 S1门限电：“1”的个数? 3 ？Y 1 0 5第11章差错控制编码由此图可见，当信息位出现一个错码时，仅当它位于信息位移 存器的第6、3、2和1级时，才使校正子等于“1”。因此，这时 的校正子序列为100111；反之，当监督位出现一个错码时，校正子序列将为 100000。由此可见，当校正子序列中出现第一个“ 1”时，表示已经检出 一个错码。后面的几位校正子则指出是信息位错了，还是监督 位错了。 图中门限电的输入代表式中4个方程的4个电压。门限电将 这4个电压（非模2）相加。当相加结果大于或等于3时，门限 电输出“1”，它除了送到输出端的模2加上纠正输出码 元b1的错码外，还送到校正子移存器纠正其中错误。?此卷积码除了能够纠正两位在约束长度中的随机错误 外，还能纠正部分多于两位的错误。 1 0 6?第11章差错控制编码卷积码的几何表述?码树图：现仍以(3, 1, 3)码为例，介绍卷积码的码树c d e 3000 3 3c d e 1000 1 1↑0c d e 2 000 2 22ab c d a b cc d e 4 000 4 4a111001 110 011 100 010 101 000 111 001 110 011 100 010 101111 001a b c d a b c d a b c d a b c da↓1111上 半 部0 信息位 1 起点↑0b110 011a↓1 111 ↑0 ↓1110 001c100 010状 态 M3M2 a 00 b 01 c 10信息位b下 半 部d1010d111 1 0 7第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。 1 0 8第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，所以走下支。这样 ，就能够纠正这两个错码。 1 0 9第11章差错控制编码一般说来，码树搜索解码法并不实用，因为随着信息序列 的增长，码树分支数目按指数规律增长；在的码树图 中，只有4个信息位，分支已有24 = 16个。但是它为以后 实用解码算法建立了初步基础。 第11章差错控制编码?状态图 的码树可以改进为下述的状态图。 由上例的编码器结构可知，输出码元ci di ei决定于当前输入 信息位bi和前两位信息位bi-1和bi-2（即移存器M2和M3的状态 ）。在上图中已经为M2和M3的4种状态了代表符号a, b, c 和d。所以，可以将当前输入信息位、移存器前一状态、移 存器下一状态和输出码元之间的关系归纳于下表中。 1 1 1第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 101M3 M 2 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在此图中，虚线”时状态转变的线； 实线”时状态转变的线 位数字是编码输出比特。利用这种状态图可以方便地从输入 序列得到输出序列。 113第11章差错控制编码?网格图 将状态图在时间上展开，可以得到网格图如下：000 111 000 111 001110a b c d000 111 011 100 001110 101000 111 011 100 001110 0 a 111 011 b 100 001 c 110 010 d 101图中画出了5个时隙。在此图中，仍用虚线”时状态转变的线；实线”时状 态转变的线时隙以后的网格图形完全 是重复第3时隙的图形。这也反映了此(3, 1, 3)卷积码的约束 长度为3。 1 1 4第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)卷积码的例子来说明维特比算法的原 理。 1 1 6?第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条径和接收序列之间的汉明距离 。 1 1 7第11章差错控制编码a b c d 000 111 000 0 111 011 100 001 110000 111 011 100 001 000 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条径和其汉明距离。 第11章差错控制编码序号 12 3 4 5 6 7 8径 aaaaabca aaab abcb aabc abdc aabd abdd对应序列 000 000 000111 001 011 000 000 111 111 001 100 000 111 001 111 110 010 000 111 110 111 110 101汉明距离 53 6 4 7 1 6 4幸存否 否是 否 是 否 是 否 是现在将到达每个状态的两条径的汉明距离作比较，将距离 小的一条径保留，称为幸存径。若两条径的汉明距离 相同，则可以任意保存一条。这样就剩下 4条径了，即表 中第2, 4, 6和8条径。 1 1 9第11章差错控制编码第2步继续考察接收序列的后继3个比特“110”。计算4条幸 存径上增加1级后的8条可能径的汉明距离。结果如下表 序号 。 径 新增 总距离 幸存否 原幸存径 新增距的距离 1 abca+a 3 径段 aa 离 2 5 否23 4 5 6 7 8abdc+aabca+b abdc+b abcb+c abdd+c abcb+d abdd+d13 1 4 4 4 4caab cb bc dc bd dd21 1 3 1 0 234 2 7 5 4 6是否 是 否 是 是 否表中最小的总距离等于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 1d图中的粗红线仍然是汉明距离最小的径。但是，若已知这 3个码元是（为结尾而补充的）“0”，则在解码计算时就预 先知道在接收这3个“0”码元后，径必然应该回到状态 a。 而由图可见，只有两条径可以回到a状态。所以，这时上 图可以简化成下图。 1 2 2第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）的编码。对于约束度大的卷积码，可以采用其他解码算 法。 第11章差错控制编码?11.8 Turbo码??什么是Turbo码？它是一种特殊的链接码。由于其性能 接近信息理论上能够达到的最好性能，所以在编码理 论上是带有性的进步。这种码，特别是解码运算 ，非常复杂，这里只对其基本概念作一简明介绍。 基本原理?由于分组码和卷积码的复杂度随码组长度或约束度的增 大按指数规律增长，所以为了提高纠错能力，人们大多 不是单纯增大一种码的长度，而是将两种或多种简单的 编码组合成复合编码。 Turbo码的编码器在两个并联或的分量码编码器之 间增加一个交织器，使之具有很大的码组长度，能在低 信噪比条件下得到接近理想的性能。? 1 2 4第11章差错控制编码?Turbo码的译码器有两个分量码译码器，译码在两个分量译码 器之间进行迭代译码，故整个译码过程类似涡轮（ turbo）工 作，所以又形象地称为Turbo码。?编码器的基本结构：它由一对递归系统卷积码(RSCC)编码 器和一个交织器组成，如下图所示： bi?RSCC编码器和卷积码编码器之间的主要区别是从 bi移存器输出端到信息位输 入端之间有反馈径。原交织器RSCC编码器c1 i c2 iRSCC编码器?来的卷积码编码器像是一个FIR数字滤波器。增加了反馈径 后，它就变成了一个IIR滤波器，或称递归滤波器。 两个RSCC编码器是相同的。它们的输入经过一个交织器并联 。此Turbo码的输入信息位是bi，输出是bic1ic2i，故码率等于 1/3。 1 2 5第11章差错控制编码?RSCC编码器举例：?方框图：如下图所示bibi D D ci??它是一个码率等于1/2的卷积码编码器，输入为bi，输出为 bici。 因为输出中第1位是信息位，所以它是系统码。 1 2 6?第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。 交织的目的是将突发错码分散开，变成随机错码。例如， 若图中第1行的m个码元构成一个码组，并且连续发送到 信道上，则当遇到脉冲干扰，造成大量错码时，可能因超 出纠错能力而无法纠正错误。但是，若在发送前进行了交 织，按列发送，则能够将集中的错码分散到各个码组，从 而有利于纠错。这种交织器常用于分组码。11a12???a1m? 1 2 7?第11章差错控制编码卷积交织器1交织器1 2 3 4解交织器x x?方 框 图 举 例2 3 x 4 11 x x x x x x(a) 第1~4比特输入时的状态5 2 x x56 7 86 7 3 x 8 4x x 25(b) 第5~8比特输入时的状态5 1 x 2 x x x9 10 11 12 6910 11 12 73 xx 3 6984(c) 第9~12比特输入时的状态13 109 5 1 6 2 313 x13 14 15 164 7 10 1314 15 16 11 12 87 4109 5 6 74321(d) 第13~16比特输入时的状态 第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。 第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个码元，是矩阵交织法的一半 。? 1 3 0第11章差错控制编码?交织器容量和误码率关系?由此曲线可以看 到，交织器容量 大时误码率低， 这是因为交织范 围大可以使交织 器输入码元得到 更好的随机化。10-1 10-2 解 10-3 码 后 的 10-4 误 码 10-5 率 10-6 10-7 信噪比 (dB)20交织器容量 100 第11章差错控制编码?11.9 低密度奇偶校验码??低密度奇偶校验(LDPC)码是一种线性分组码，和 Turbo码同属于复合码类。两者的性能相近，且两者的 译码延迟都相当长，所以它们更适用于一些实时性要 求不很高的通信。但是LDPC码比Turbo码的译码简单 ，更易实现。 LDPC码的分类：? ??规则LDPC码： H矩阵每列具有相同个数的“1” 非规则LDPC码： H矩阵每列中 “1”的个数不一定相同 非规则LDPC码是在规则LDPC码基础上发展出的，它使 解码性能得到改善，使误码率性能比Turbo码还好。 第11章差错控制编码?非规则LDPC码和Turbo码的误比特率性能比较Pe香 农 限图中的虚线是Turbo码的性能，实线是LDPC码的性能 当码长n大约在104以上时，LDPC码的性能才比Turbo码好。 133第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。这样，对于给 定的信息位，不难算出码组。 第11章差错控制编码?LDPC码的解码方法 LDPC码的解码方法也和一般的奇偶监督码的解码方法 不同。基本的解码算法称为置信算法，通常简称 BP算法。这种算法实质上是求最大后验概率，类似于 一般的最大似然准则解码算法，但是它需要进行多次迭 代运算，逐步逼近最优的解码值。 LDPC码的具体编解码算法十分复杂，这里不再深入讨 论。 1 3 5第11章差错控制编码?11.10 网格编码调制?11.10.1网格编码调制(TCM)的基本概念下面将利用一个实例给出TCM的基本概念 ? 复习QPSK系统：QPSK是一个4相相移键控系统，它的每个码元传输 2 比 特信息。若在接收端判决时因干扰而将信号相位错判至 相邻相位，则将出现错码。现在，将系统改成 8PSK， 它的每个码元可以传输3 比特信息。但是我们仍然令每 个码元传输2 比特信息。第3 比特用于纠错码，例如， 采用码率为2/3的卷积码。这时接收端的解调和解码是作 为一个步骤完成的，不像传统作法，先解调得到基带信 号后再为纠错去解码。 1 3 6第11章差错控制编码?在纠错编码理论中，码组间的最小汉明距离决定着这种编码 的纠错能力。在TCM中，由于是直接对于已调信号（现在是 8PSK信号）解码，码元之间的差别是载波相位之差，这个差 别是欧氏距离。 在右图中示 出了8PSK信1 d0 = 2sin(?/8) = 0.765?号星座图中的8个信号点。 图中已假设信号振幅等于1，则相邻两信号点 的欧氏距离d0等于0.765。d1 = √2 1 3 7第11章差错控制编码?两个信号序列的欧氏距离越大，即它们的差别越大，则 因干扰造成互相混淆的可能性越小。 图中的信号点代表某个确定相位的已调信号波形。 为了利用卷积码维特比解码的优点，这时仍然需要用到 网格图。但是，和卷积码维特比解码时的网格图相比， 在TCM中是将这些波形映射为网格图，故TCM网格图 中的各状态是波形的状态。? ? 1 3 8第11章差错控制编码?11.10.2 TCM信号的产生?集划分方法??基本原则：将信号星座图划分成若干子集，使子集中的 信号点间距离比原来的大。每划分一次，新的子集中信 号点间的距离就增大一次。 A0 d 例：见右图 0 ? A0是8PSK信号 d1 B0 B1 的星座图，其中 任意两个信号点 d 2 间的距离为d0。 =2 C C1 C2 C3 0 这个星座被划分 为B0和B1两个子 集，在子集中相 (001) (010) (011) (100) (101) (110) 邻信号点间的距 (000) (111) 离为d1。 139第11章差错控制编码A0 d0d1B0d2=2B1C0C1C2C3(000) (001)(010)(011)(100)(101)(110)(111) 第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也按照这一原则选择下一级的信号点。?? 1 4 1第11章差错控制编码?卷积码编码器的方框图：k1b11b22输入k2 未编码比 特c2 c3c1编码输出由上图可见，这个卷积码的约束长度等于 3。编码器输出的 前两个比特c1和c2用来选择星座图划分的径，最后1个比特 c3用于选定星座图第3级（最低级）中的信号点。 1 4 2?第11章差错控制编码TCM编码器结构? ?方框图 原理： 将k比特输入 信息段分为k1 和k2两段；前k1卷积码 编码器n1选择 子集 选择 子集 中的点信号点k2k1比特通过一个(n1, k1, m)卷积码编码器，产生n1比特输出，用于选择信号星座图中划分之一，后面的k2比特用于选 定星座图中的信号点。 这表明星座图被划分为2n1个子集，每个子集中含有个信号 点。 在上例编码器方框图中k1 = k2 = 1 第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时刻b10当输入信号序列k1为 “0110100”时，移存器状态和输出c1与c2之间001c01110 111 110 111 100 101100 101的关系示于下表中。d11 144第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 0 1 4 5第11章差错控制编码?在第1个输入码元“1” 到达后，输出码元c1状态ab1 b2 ti 时刻 00?和c2由“00”变成“01”， 但是这时的输入信息 位k2可能是“0”或“1”， b 10 所以输出c1 c2 c3可能是 “010”或“011”，这就是 c 01 右图中最高的两条平行 虚线 011 010ti +1时刻011 000001111 110100 110 101b1后，b1 b2的状态由“00” d 11 101 (a)变到“10”(b)，输出c1 c2 c3可能是“110”或“111”，b1 b2 的状态由b变到d，如图中虚线章差错控制编码?网格图和星座图之间的对应关系?每对平行转移必须对应最下一级划分同一子集中的两个信号 点。例如，图中的“000”和“001”同属于子集C0，“010”和 “011”同属于子集C1，等等。这些对信号点具有最大的欧氏 距离(d2 = 2)。 从某一状态出发的所有转移，或到达某一状态的所有转移， 必须属于同一上级子集。例如，图中从状态a出发的转移 “000”、“001”、“010”和“011”都属于子集B0。或者说， 此两对平行转移应具有最大可能的欧氏距离。? 第11章差错控制编码?11.10.3 TCM信号的解调?TCM信号的解调算法?通常采用维特比算法，但是现在的网格图表示的状态是 波形，而不是码组。解码器的任务是计算接收信号序列 径和各种可能的编码网格径间的距离。若所有发送 信号序列是等概率的，则判定与接收序列距离最小的可 能径（又称为最大似然径）为发送序列。 因为卷积码是线性码，它具有封闭性，故要考察的径 距离与所用的测试序列无关。所以，不失一般性，可以 选用全“0”序列作为测试序列。? 1 4 8第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 b00 2 10 01 11V4cd 1 4 9?第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.14 第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 = 2 151第11章差错控制编码?另一方面，未编码的QPSK信号的相继码元（波形）没有约 束。若将其欧氏距离作为参考距离dref，则由下图可知 ， d ref ? d1 ? 2 所以，可以证明，和未编码QPSK系统相比，8PSK的TCM G8 PSK / QPSK ? 20 lg(d Fed / d ref ) ? 3.01 (dB) 系统可以获得的渐近编码增益等于?1 d0 = 2sin(?/8) = 0.765d1 = √2 第11章差错控制编码?在下表中列出了通过大量仿线PSK/TCM系 统的(渐近)编码增益。状态数目 4 8 16k 1 2 2G8PSK/QPSK 3.01 3.60 4.133264224.595..175.75
推荐：