1通信原理第第11章章 差错控制编码差错控制编码 2第11章差错控制编码l11.1 概述概述n信道分类：从差错控制角度看u随机信道：错码的出现是随机的 u突发信道：错码是成串集中出现的u混合信道：既存在随机错码又存在突发错码 n差错控制技术的种类u 检错重发u前向纠错 u反馈校验u检错删除 3第11章差错控制编码n差错控制编码：常称为纠错编码u监督督码元：元：上述4种技术中除第3种外，都是在接收端识别有无错码。所以在发送端需要在信息码元序列中增加一些差错控制码元，它们称为监督码元。 u不同的编码方法，有不同的检错或纠错能力。u多余度多余度：就是指增加的监督码元多少。例如，若编码序列中平均每两个信息码元就添加一个监督码元，则这种编码的多余度为1/3。u编码效率效率(简称码率率) ：设编码序列中信息码元数量为k，总码元数量为n，则比值k/n 就是码率。u冗余度：冗余度：监督码元数(n-k) 和信息码元数 k 之比。u理论上，差错控制以降低信息传输速率为代价换取提高传输可靠性。4第11章差错控制编码n自动要求重发(ARQ)系统u3种ARQ系统p停止等待ARQ系统 数据按分组发送。每发送一组数据后发送端等待接收端的确认(ACK)答复，然后再发送下一组数据。图中的第3组接收数据有误，接收端发回一个否认(NAK)答复。这时，发送端将重发第3组数据。系统是工作在半双工状态，时间没有得到充分利用，传输效率较低。 接收码组ACKACKNAKACKACKNAKACKt1233455发送码组12334556t有错码组有错码组5第11章差错控制编码p拉后ARQ系统发送端连续发送数据组，接收端对于每个接收到的数据组都发回确确认(ACK)或否否认(NAK)答复。 例如，图中第5组接收数据有误，则在发送端收到第5组接收的否认答复后，从第5组开始重发数据组。在这种系统中需要对发送的数据组和答复进行编号，以便识别。显然，这种系统需要双工信道 接收数据有错码组有错码组910 1110 1112214365798576ACK1NAK5NAK9ACK5发送数据576952143679810 1110 11 12重发码组重发码组6第11章差错控制编码p选择重发ARQ系统它只重发出错的数据组，因此进一步提高了传输效率。接收数据有错码组有错码组9214365759810 11131412发送数据995852143671011131412重发码组重发码组NAK9ACK1NAK5ACK5ACK97第11章差错控制编码uARQ的主要优点：和前向纠错方法相比p监督码元较少即能使误码率降到很低，即码率较高；p检错的计算复杂度较低；p检错用的编码方法和加性干扰的统计特性基本无关，能适应不同特性的信道。uARQ的主要缺点：p需要双向信道来重发，不能用于单向信道，也不能用于一点到多点的通信系统。p因为重发而使ARQ系统的传输效率降低。p在信道干扰严重时，可能发生因不断反复重发而造成事实上的通信中断。p在要求实时通信的场合，例如电话通信，往往不允许使用ARQ法。8第11章差错控制编码uARQ系统的原理方框图p在发送端，输入的信息码元在编码器中被分组编码（加入监督码元）后，除了立即发送外，还暂存于缓冲存储器中。若接收端解码器检出错码，则由解码器控制产生一个重发指令。此指令经过反向信道送到发送端。由发送端重发控制器控制缓冲存储器重发一次。p接收端仅当解码器认为接收信息码元正确时，才将信息码元送给收信者，否则在输出缓冲存储器中删除接收码元。p当解码器未发现错码时，经过反向信道发出不需重发指令。发送端收到此指令后，即继续发送后一码组，发送端的缓冲存储器中的内容也随之更新。9第11章差错控制编码l11.2 纠错编码的基本原理的基本原理n分组码基本原理：举例说明如下。u设有一种由3位二进制数字构成的码组，它共有8种不同的可能组合。若将其全部用来表示天气，则可以表示8种不同天气， 例如：“000”（晴），“001”（云）， “010”（阴），“011”（雨）， “100”（雪），“101”（霜）， “110”（雾），“111”（雹）。u其中任一码组在传输中若发生一个或多个错码，则将变成另一个信息码组。这时，接收端将无法发现错误。10第11章差错控制编码u若在上述8种码组中只准许使用4种来传送天气，例如：“000”晴 “011”云 “101”阴 “110”雨p这时，虽然只能传送4种不同的天气，但是接收端却有可能发现码组中的一个错码。p例如，若“000”（晴）中错了一位，则接收码组将变成“100”或“010”或“001”。这3种码组都是不准使用的，称为禁用禁用码组。p接收端在收到禁用码组时，就认为发现了错码。当发生3个错码时，“000”变成了“111”，它也是禁用码组，故这种编码也能检测3个错码。p但是这种码不能发现一个码组中的两个错码，因为发生两个错码后产生的是许用用码组。11第11章差错控制编码u检错和纠错p上面这种编码只能检测错码，不能纠正错码。例如，当接收码组为禁用码组“100”时，接收端将无法判断是哪一位码发生了错误，因为晴、阴、雨三者错了一位都可以变成“100”。p要能够纠正错误，还要增加多余度。例如，若规定许用码组只有两个：“000”（晴），“111”（雨），其他都是禁用码组，则能够检测两个以下错码，或能够纠正一个错码。p例如，当收到禁用码组“100”时，若当作仅有一个错码，则可以判断此错码发生在“1”位，从而纠正为“000”（晴）。因为“111”（雨）发生任何一位错码时都不会变成“100”这种形式。 p但是，这时若假定错码数不超过两个，则存在两种可能性：“000”错一位和“111”错两位都可能变成“100”，因而只能检测出存在错码而无法纠正错码。12第11章差错控制编码u分组码的结构p将信息码分组，为每组信息码附加若干监督码的编码称为分分组码 。p在分组码中，监督码元仅监督本码组中的信息码元。 p信息位和监督位的关系：举例如下信息位监督位晴000云011阴101雨11013第11章差错控制编码p分组码的一般结构u分组码的符号：(n, k)pN 码组的总位数，又称为码组的长度（码长），pk 码组中信息码元的数目，pn k r 码组中的监督码元数目，或称监督位数目。 14第11章差错控制编码u分组码的码重和码距p码重：把码组中“1”的个数目称为码组的重量，简称码重重。p码距：把两个码组中对应位上数字不同的位数称为码组的距离，简称码距距。码距又称汉明距离明距离。p例如，“000”晴，“011”云，“101”阴，“110”雨，4个码组之间，任意两个的距离均为2。p最小码距：把某种编码中各个码组之间距离的最小值称为最小最小码距距(d0)。例如，上面的编码的最小码距d0 = 2。15第11章差错控制编码u码距的几何意义p对于3位的编码组，可以在3维空间中说明码距的几何意义。 p每个码组的3个码元的值(a1, a2, a3)就是此立方体各顶点的坐标。而上述码距概念在此图中就对应于各顶点之间沿立方体各边行走的几何距离。p由此图可以直观看出，上例中4个准用码组之间的距离均为2。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a116第11章差错控制编码u码距和检纠错能力的关系p一种编码的最小码距d0的大小直接关系着这种编码的检错和纠错能力p为检测e个错码，要求最小码距 d0 e + 1【证】设一个码组A位于O点。若码组A中发生一个错码，则我们可以认为A的位置将移动至以O点为圆心，以1为半径的圆上某点，但其位置不会超出此圆。 若码组A中发生两位错码，则其位置不会超出以O点为圆心，以2为半径的圆。因此，只要最小码距不小于3，码组A发生两位以下错码时，不可能变成另一个准用码组，因而能检测错码的位数等于2。 0123BA汉明距离ed017第11章差错控制编码同理，若一种编码的最小码距为d0，则将能检测(d0 - 1)个错码。反之，若要求检测e个错码，则最小码距d0至少应不小于( e + 1)。p为了纠正t个错码，要求最小码距d0 2t + 1【证】图中画出码组A和B的距离为5。码组A或B若发生不多于两位错码，则其位置均不会超出半径为2以原位置为圆心的圆。这两个圆是不重叠的。判决规则为：若接收码组落于以A为圆心的圆上就判决收到的是码组A，若落于以B为圆心的圆上就判决为码组B。这样，就能够纠正两位错码。 BtA汉明距离012345td018第11章差错控制编码若这种编码中除码组A和B外，还有许多种不同码组，但任两码组之间的码距均不小于5，则以各码组的位置为中心以2为半径画出之圆都不会互相重叠。这样，每种码组如果发生不超过两位错码都将能被纠正。因此，当最小码距d05时，能够纠正2个错码，且最多能纠正2个。若错码达到3个，就将落入另一圆上，从而发生错判。故一般说来，为纠正t个错码，最小码距应不小于(2t + 1)。19第11章差错控制编码p为纠正t个错码，同时检测e个错码，要求最小码距在解释此式之前，先来分析下图所示的例子。图中码组A和B之间距离为5。按照检错能力公式，最多能检测4个错码，即e = d0 1 = 5 1 = 4，按照纠错能力公式纠错时，能纠正2个错码。但是，不能同时作到两者，因为当错码位数超过纠错能力时，该码组立即进入另一码组的圆内而被错误地“纠正”了。例如，码组A若错了3位，就会被误认为码组B错了2位造成的结果，从而被错“纠”为B。这就是说，检错和纠错公式不能同时成立或同时运用。 BtA汉明距离012345td020第11章差错控制编码所以，为了在可以纠正t个错码的同时，能够检测e个错码，就需要像下图所示那样，使某一码组（譬如码组A）发生e个错误之后所处的位置，与其他码组（譬如码组B）的纠错圆圈至少距离等于1，不然将落在该纠错圆上从而发生错误地“纠正”。因此，由此图可以直观看出，要求最小码距这种纠错和检错结合的工作方式简称纠检结合合。 ABe1tt汉明距离21第11章差错控制编码这种工作方式是自动在纠错和检错之间转换的。当错码数量少时，系统按前向纠错方式工作，以节省重发时间，提高传输效率；当错码数量多时，系统按反馈重发方式纠错，以降低系统的总误码率。所以，它适用于大多数时间中错码数量很少，少数时间中错码数量多的情况。22第11章差错控制编码l11.3 纠错编码的性能的性能n系统带宽和信噪比的矛盾：u由上节所述的纠错编码原理可知，为了减少接收错误码元数量，需要在发送信息码元序列中加入监督码元。这样作的结果使发送序列增长，冗余度增大。若仍须保持发送信息码元速率不变，则传输速率必须增大，因而增大了系统带宽。系统带宽的增大将引起系统中噪声功率增大，使信噪比下降。信噪比的下降反而又使系统接收码元序列中的错码增多。一般说来，采用纠错编码后，误码率总是能够得到很大改善的。改善的程度和所用的编码有关。23第11章差错控制编码u编码性能举例p未采用纠错编码时，若接收信噪比等于7dB，编码前误码率约为810-4，图中A点，在采用纠错编码后，误码率降至约410-5，图中B点。这样，不增大发送功率 就能降低误码率约一个半数量级。10-610-510-410-310-210-1编码后PeCDEAB信噪比 (dB)24第11章差错控制编码p由图还可以看出，若保持误码率在10-5，图中C点，未采用编码时，约需要信噪比Eb / n0 = 10.5 dB。在采用这种编码时，约需要信噪比7.5 dB，图中D点。可以节省功率2 dB。通常称这2 dB为编码增益。p上面两种情况付出的代价是带宽增大。10-610-510-410-310-210-1编码后PeCDEAB信噪比 (dB)25第11章差错控制编码p传输速率和Eb/n0的关系对于给定的传输系统式中，RB为码元速率。若希望提高传输速率，由上式看出势必使信噪比下降，误码率增大。假设系统原来工作在图中C点，提高速率后由C点升到E点。但加用纠错编码后，仍可将误码率降到D点。这时付出的代价仍是带宽增大。10-610-510-410-310-210-1编码后PeCDEAB信噪比 (dB)26第11章差错控制编码l11.4简单的的实用用编码n11.4.1 奇偶监督码u奇偶监督码分为奇数监督码和偶数监督码两种，两者的原理相同。在偶数监督码中，无论信息位多少，监督位只有1位，它使码组中“1”的数目为偶数，即满足下式条件：式中a0为监督位，其他位为信息位。这种编码能够检测奇数个错码。在接收端，按照上式求“模2和”，若计算结果为“1”就说明存在错码，结果为“0”就认为无错码。奇数监督码与偶数监督码相似，只不过其码组中“1”的数目为奇数：27第11章差错控制编码n11.4.2 二维奇偶监督码（方阵码）u二维奇偶监督码的构成它是先把上述奇偶监督码的若干码组排成矩阵，每一码组写成一行，然后再按列的方向增加第二维监督位，如下图所示图中a01 a02 a0m为m行奇偶监督码中的m个监督位。cn-1 cn-2 c1 c0为按列进行第二次编码所增加的监督位，它们构成了一监督位行。28第11章差错控制编码u二维奇偶监督码的性能p这种编码有可能检测偶数个错码。因为每行的监督位虽然不能用于检测本行中的偶数个错码，但按列的方向有可能由cn-1 cn-2 c1 c0等监督位检测出来。有一些偶数错码不可能检测出来。例如，构成矩形的4个错码，譬如图中错了，就检测不出。p这种二维奇偶监督码适于检测突发错码。因为突发错码常常成串出现，随后有较长一段无错区间。p由于方阵码只对构成矩形四角的错码无法检测，故其检错能力较强。 p二维奇偶监督码不仅可用来检错，还可以用来纠正一些错码。 例如，仅在一行中有奇数个错码时。29第11章差错控制编码n 11.4.3 恒比恒比码u在恒比码中，每个码组均含有相同数目的“1”（和“0”）。由于“1”的数目与“0”的数目之比保持恒定，故得此名。u这种码在检测时，只要计算接收码组中“1”的数目是否对，就知道有无错码。u恒比码的主要优点是简单和适于用来传输电传机或其他键盘设备产生的字母和符号。对于信源来的二进制随机数字序列，这种码就不适合使用了。30第11章差错控制编码n11.4.4 正反正反码u正反码的编码：p它是一种简单的能够纠正错码的编码。其中的监督位数目与信息位数目相同，监督码元与信息码元相同或者相反则由信息码中“1”的个数而定。p例如，若码长n = 10，其中信息位 k = 5，监督位 r = 5。其编码规则为：当信息位中有奇数个“1”时，监督位是信息位的简单重复；当信息位有偶数个“1”时，监督位是信息位的反码。例如，若信息位为11001，则码组为1100111001；若信息位为10001，则码组为1000101110。31第11章差错控制编码u正反码的解码p在上例中，先将接收码组中信息位和监督位按模 2 相加，得到一个5位的合成码组。然后，由此合成码组产生一个校验码组。p若接收码组的信息位中有奇数个“1”，则合成码组就是校验码组；若接收码组的信息位中有偶数个“1”，则取合成码组的反码作为校验码组。p最后，观察校验码组中“1”的个数，按下表进行判决及纠正可能发现的错码。 32第11章差错控制编码p校验码组和错码的关系 例如，若发送码组为1100111001，接收码组中无错码，则合成码组应为1100111001=00000。由于接收码组信息位中有奇数个“1”，所以校验码组就是00000。按上表判决，结论是无错码。 校验码组的组成错码情况1全为“0”无错码2有4个“1”和1个“0”信息码中有1位错码，其位置对应校验码组中“0”的位置3有4个“0”和1个“1”监督码中有1位错码，其位置对应校验码组中“1”的位置4其他组成错码多于1个33第11章差错控制编码若传输中产生了差错，使接收码组变成1000111001，则合成码组为100011100101000。由于接收码组中信息位有偶数个“1”，所以校验码组应取合成码组的反码，即10111。由于其中有4个“1”和1个“0”，按上表判断信息位中左边第2位为错码。若接收码组错成1100101001，则合成码组变成110010100110000。由于接收码组中信息位有奇数个“1”，故校验码组就是10000，按上表判断，监督位中第1位为错码。最后，若接收码组为1001111001，则合成码组为100111100101010，校验码组与其相同，按上表判断，这时错码多于1个。p上述长度为10的正反码具有纠正1位错码的能力，并能检测全部2位以下的错码和大部分2位以上的错码。34第11章差错控制编码l11.5 线性分性分组码n基本概念u代数代数码：建立在代数学基础上的编码。u线性性码：按照一组线性方程构成的代数码。在线性码中信息位和监督位是由一些线性代数方程联系着的。u线性分性分组码：按照一组线性方程构成的分组码 。本节将以汉明码为例引入线性分组码的一般原理。35第11章差错控制编码n汉明明码能够纠正1位错码且编码效率较高的一种线性分组码u汉明码的构造原理。p在偶数监督码中，由于使用了一位监督位a0，它和信息位an-1 a1一起构成一个代数式：在接收端解码时，实际上就是在计算若S = 0，就认为无错码；若S = 1，就认为有错码。现将上式称为监督关系式督关系式，S称为校正子校正子。由于校正子S只有两种取值，故它只能代表有错和无错这两种信息，而不能指出错码的位置。 36第11章差错控制编码p若监督位增加一位，即变成两位，则能增加一个类似的监督关系式。由于两个校正子的可能值有4中组合： 00，01，10，11，故能表示4种不同的信息。若用其中1种组合表示无错，则其余3种组合就有可能用来指示一个错码的3种不同位置。同理，r个监督关系式能指示1位错码的(2r 1)个可能位置。p一般来说，若码长为n，信息位数为k，则监督位数rnk。如果希望用r个监督位构造出r个监督关系式来指示1位错码的n种可能位置，则要求下面通过一个例子来说明如何具体构造这些监督关系式。37第11章差错控制编码p例：设分分组码(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错码位置S1 S2 S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错码38第11章差错控制编码由表中规定可见，仅当一位错码的位置在a2 、a4、a5或a6时，校正子S1为1；否则S1为零。这就意味着a2 、a4、a5和a6四个码元构成偶数监督关系：同理， a1、a3、a5和a6构成偶数监督关系：以及a0、a3、a4 和a6构成偶数监督关系39第11章差错控制编码在发送端编码时，信息位a6、a5、a4和a3的值决定于输入信号，因此它们是随机的。监督位a2、a1和a0应根据信息位的取值按监督关系来确定，即监督位应使上3式中S1、S2和S3的值为0（表示编成的码组中应无错码）：上式经过移项运算，解出监督位给定信息位后，可以直接按上式算出监督位， 结果见下表：40第11章差错控制编码信息位a6 a5 a4 a3监督位a2 a1 a0信息位a6 a5 a4 a3监督位a2 a1 a0000000010001110001011100110000101011010010001111010110010100110110000101011011101010011001111101000111000111111141第11章差错控制编码接收端收到每个码组后，先计算出S1、S2和S3，再查表判断错码情况。例如，若接收码组为0000011，按上述公式计算可得：S1 = 0，S2 = 1，S3 = 1。由于S1 S2 S3 等于011，故查表可知在a3位有1错码。 p按照上述方法构造的码称为汉明码。表中所列的(7, 4)汉明码的最小码距d0 = 3。因此，这种码能够纠正1个错码或检测2个错码。由于码率k/n = (n - r) /n =1 r/n，故当n很大和r很小时，码率接近1。可见，汉明码是一种高效码。 42第11章差错控制编码n线性分组码的一般原理u线性分组码的构造pH矩阵上面(7, 4)汉明码的例子有现在将上面它改写为上式中已经将“”简写成“+”。 43第11章差错控制编码上式可以表示成如下矩阵形式：上式还可以简记为H AT = 0T 或A HT = 044第11章差错控制编码H AT = 0T 或A HT = 0式中 A = a6 a5 a4 a3 a2 a1 a00 = 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矩阵可以分成两部分，例如 式中，P为r k阶矩阵，Ir为r r阶单位方阵。我们将具有P Ir形式的H矩阵称为典型典型阵。46第11章差错控制编码2) 由代数理论可知，H矩阵的各行应该是线性无关的，否则将得不到 r个线性无关的监督关系式，从而也得不到 r个独立的监督位。若一矩阵能写成典型阵形式P Ir，则其各行一定是线性无关的。因为容易验证Ir的各行是线性无关的，故P Ir的各行也是线性无关的。pG矩阵： 上面汉明码例子中的监督位公式为 也可以改写成矩阵形式：47第11章差错控制编码或者写成式中，Q为一个k r阶矩阵，它为P的转置，即 Q = PT 上式表示，在信息位给定后，用信息位的行矩阵乘矩阵Q就产生出监督位。48第11章差错控制编码我们将Q的左边加上1个k k阶单位方阵，就构成1个矩阵G 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章差错控制编码p错码矩阵和错误图样 一般说来，A为一个n列的行矩阵。此矩阵的n个元素就是码组中的n个码元，所以发送的码组就是A。此码组在传输中可能由于干扰引入差错，故接收码组一般说来与A不一定相同。若设接收码组为一n列的行矩阵B，即则发送码组和接收码组之差为B A = E (模2)它就是传输中产生的错码行矩矩阵 式中51第11章差错控制编码因此，若ei = 0，表示该接收码元无错；若ei = 1，则表示该接收码元有错。 B A = E 可以改写成 B = A + E例如，若发送码组A = 1000111，错码矩阵E = 0000100，则接收码组B = 1000011。错码矩阵有时也称为错误图样。52第11章差错控制编码p校正子S当接收码组有错时，E 0，将B当作A代入公式(A H T = 0)后，该式不一定成立。在错码较多，已超过这种编码的检错能力时，B变为另一许用码组，则该式仍能成立。这样的错码是不可检测的。在未超过检错能力时，上式不成立，即其右端不等于0。假设这时该式的右端为S，即B H T = S将B = A + E代入上式，可得S = (A + E) H T = A H T + E H T由于A HT = 0，所以S = E H T式中S称为校正子。它能用来指示错码的位置。S和错码E之间有确定的线性变换关系。若S和E之间一一对应，则S将能代表错码的位置。53第11章差错控制编码u线性分组码的性质p封封闭性：性：是指一种线性码中的任意两个码组之和仍为这种码中的一个码组。这就是说，若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”码组外）。54第11章差错控制编码l11.6 循循环码n11.6.1 循环码原理u循循环性性：循环性是指任一码组循环一位（即将最右端的一个码元移至左端，或反之）以后，仍为该码中的一个码组。在下表中给出一种(7, 3)循环码的全部码组。例如，表中的第2码组向右移一位即得到第5码组；第6码组向右移一位即得到第7码组。 码组编号信息位监督位码组编号信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0100000005100101120010111610111003010111071100101401110018111001055第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章差错控制编码u码多项式p码组的多项式表示法把码组中各码元当作是一个多项式的系数，即把一个长度为n的码组表示成例如，上表中的任意一个码组可以表示为其中第7个码组可以表示为这种多项式中，x仅是码元位置的标记，例如上式表示第7码组中a6、a5、a2和a0为“1”，其他均为0。因此我们并不关心x的取值。 57第11章差错控制编码p 码多项式的按模运算在整数运算中，有模n运算。例如，在模2运算中，有1 + 1 = 2 0 (模2)，1 + 2 = 3 1 (模2)， 2 3 = 6 0 (模2)等等。一般说来，若一个整数m可以表示为式中，Q 整数，则在模 n 运算下，有m p (模n)即，在模 n 运算下，一个整数m等于它被 n 除得的余数。 58第11章差错控制编码在码多项式运算中也有类似的按模运算。若一任意多项式F(x)被一 n 次多项式N (x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即则写为这时，码多项式系数仍按模2 运算，即系数只取 0 和1。例如，x3被(x3 + 1)除，得到余项1。所以有同理因为 xx3 + 1 x4 +x2 + 1 x4 + x x2 +x +1应当注意，由于在模2运算中，用加法代替了减法，故余项不是x2 x + 1，而是x2 + x + 1。59第11章差错控制编码u循环码的码多项式p在循环码中，若T(x)是一个长为n的许用码组，则xiT(x)在按模xn + 1运算下，也是该编码中的一个许用码组，即若则T (x)也是该编码中的一个许用码组。【证】因为若则（模(xn + 1)）所以，这时有60第11章差错控制编码上式中T (x)正是T(x)代表的码组向左循环移位i次的结果。因为原已假定T(x)是循环码的一个码组，所以T (x)也必为该码中一个码组。例如，循环码组其码长n = 7。现给定i = 3，则其对应的码组为0101110，它正是表中第3码组。由上述分析可见，一个长为n的循环码必定为按模(xn + 1)运算的一个余式。61第11章差错控制编码u循环码的生成矩阵Gp由上节中公式可知，有了生成矩阵G，就可以由k个信息位得出整个码组，而且生成矩阵G的每一行都是一个码组。例如，在此式中，若a6a5a4a3 = 1000，则码组A就等于G的第一行；若a6a5a4a3 = 0100，则码组A就等于G的第二行；等等。由于G是k行n列的矩阵，因此若能找到k个已知码组，就能构成矩阵G。如前所述，这k个已知码组必须是线性不相关的，否则给定的信息位与编出的码组就不是一一对应的。p在循环码中，一个(n, k)码有2k个不同的码组。若用g(x)表示其中前(k-1)位皆为“0”的码组，则g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是码组，而且这k个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵G。62第11章差错控制编码p在循环码中除全“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章差错控制编码p因此，循环码的生成矩阵G可以写成 p例：在上表所给出的(7, 3)循环码中，n = 7, k = 3, n k = 4。由此表可见，唯一的一个(n k) = 4次码多项式代表的码组是第二码组0010111，与它相对应的码多项式（即生成多项式）g(x) = x4 + x2 + x + 1。将此g(x)代入上式，得到或64第11章差错控制编码由于上式不符合G = IkQ的形式，所以它不是典型阵。不过，将它作线性变换，不难化成典型阵。我们可以写出此循环码组，即上式表明，所有码多项式T(x)都可被g(x)整除，而且任意一个次数不大于(k 1)的多项式乘g(x)都是码多项式。需要说明一点，两个矩阵相乘的结果应该仍是一个矩阵。上式中两个矩阵相乘的乘积是只有一个元素的一阶矩阵，这个元素就是T(x)。为了简洁，式中直接将乘积写为此元素。65第11章差错控制编码u如何寻找任一(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次多项式。由下式可知，xk T (x)在模(xn + 1)运算下也是一个码组，故可以写成66第11章差错控制编码 上式左端分子和分母都是n次多项式，故商式Q(x) = 1。因此，上式可以化成将T(x)和T(x)表示式代入上式，经过化简后得到上式表明，生成多项式g(x)应该是(xn + 1)的一个因子。这一结论为我们寻找循环码的生成多项式指出了一条道路，即循环码的生成多项式应该是(xn +1)的一个(n k)次因式。例如，(x7 + 1)可以分解为为了求(7, 3)循环码的生成多项式g(x)，需要从上式中找到一个(n k) = 4次的因子。不难看出，这样的因子有两个，即67第11章差错控制编码 以上两式都可作为生成多项式。不过，选用的生成多项式不同，产生出的循环码码组也不同。68第11章差错控制编码n11.6.2 循环码的编解码方法u循环码的编码方法p编码原则在编码时，首先要根据给定的(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)。69第11章差错控制编码p编码步骤：用xn - k乘m(x)。这一运算实际上是在信息码后附加上(n k)个“0”。例如，信息码为110，它相当于m(x) = x2 + x。当n k = 7 3 = 4时，xn - k m(x) = x4 (x2 + x) = x6 + x5，它相当于1100000。用g(x)除xn - k m(x)，得到商Q(x)和余式r(x)，即例如，若选定g(x) = x4 + x2 + x + 1，则 上式相当于70第11章差错控制编码编出的码组T(x)为T(x) = xn - k m(x) + r(x) 在上例中，T(x) = 1100000 + 101 = 1100101，它就是上表中的第7码组。71第11章差错控制编码u循环码的解码方法p解码要求：检错和纠错。p检错解码原理：由于任意一个码组多项式T(x)都应该能被生成多项式g(x)整除，所以在接收端可以将接收码组R(x)用原生成多项式g(x)去除。当传输中未发生错误时，接收码组与发送码组相同，即R(x) = T(x)，故接收码组R(x)必定能被g(x)整除；若码组在传输中发生错误，则R(x) T(x)，R(x)被g(x)除时可能除不尽而有余项，即有因此，就以余项是否为零来判别接收码组中有无错码。需要指出，有错码的接收码组也有可能被g(x)整除。这时的错码就不能检出了。这种错误称为不可检错误。不可检错误中的误码数必定超过了这种编码的检错能力。72第11章差错控制编码p纠错解码原理：为了能够纠错，要求每个可纠正的错误图样必须与一个特定余式有一一对应关系。因为只有存在上述一一对应的关系时，才可能从上述余式唯一地决定错误图样，从而纠正错码。因此，原则上纠错可按下述步骤进行：用生成多项式g(x)除接收码组R(x)，得出余式r(x)。按余式r(x)，用查表的方法或通过某种计算得到错误图样E(x)；例如，通过计算校正子S和查表，就可以确定错码的位置。从R(x)中减去E(x)，便得到已经纠正错码的原发送码组T(x)。p通常，一种编码可以有几种纠错解码方法，上述解码方法称为捕错解码法。 u目前多采用软件运算实现上述编解码运算。73第11章差错控制编码n11.6.3 截短循截短循环码u截短目的：在设计纠错编码方案时，常常信息位数k、码长n和纠错能力都是预先给定的。但是，并不一定有恰好满足这些条件的循环码存在。这时，可以采用将码长截短的方法，得出满足要求的编码。u截短方法：设给定一个(n, k)循环码，它共有2k种码组，现使其前i (0 i k)个信息位全为“0”，于是它变成仅有2k-i种码组。然后从中删去这i位全“0”的信息位，最终得到一个(n i, k i)的线性码。将这种码称为截短循环码。 u截短循环码性能：循环码截短前后至少具有相同的纠错能力，并且编解码方法仍和截短前的方法一样。 u例：要求构造一个能够纠正1位错码的(13, 9)码。这时可以由(15, 11)循环码的11种码组中选出前两信息位均为“0”的码组，构成一个新的码组集合。然后在发送时不发送这两位“0”。于是发送码组成为(13, 9)截短循环码。 74第11章差错控制编码n11.6.4 BCH码u什么是BCH码？它是一种获得广泛应用的能够纠正多个错码的循环码，是以3位发明这种码的人名(Bose - Chaudhuri - Hocguenghem)命名的。BCH码的重要性在于它解决了生成多项式与纠错能力的关系问题，可以在给定纠错能力要求的条件下寻找到码的生成多项式。有了生成多项式，编码的基本问题就随之解决了。uBCH码分类：p本原BCH码：其生成多项式g(x)中含有最高次数为m的本原多项式，且码长为n = 2m 1，(m 3，为正整数)。p非本原BCH码：其生成多项式中不含这种本原多项式，且码长n是(2m 1)的一个因子，即码长n一定除得尽2m 1。p本原多项式的概念将在下一章介绍。 75第11章差错控制编码uBCH码的性能：p码长n与监督位、纠错个数 t 之间的关系：对于正整数m (m 3)和正整数t 1，且除得尽(2m -1)），则为非本原BCH码。p汉明码是能够纠正单个随机错误的码。可以证明，具有循环性质的汉明码就是能纠正单个随机错误的本原BCH码。p例如，(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章差错控制编码uBCH码的设计p在工程设计中，一般不需要用计算方法去寻找生成多项式g(x)。因为前人早已将寻找到的g(x)列成表，故可以用查表法找到所需的生成多项式。p下表给出了码长n 127的二进制本原BCH码生成多项式。77第11章差错控制编码n = 3k t g(x)1 1 7n = 63k t g(x)57 1 10351 2 1247145 3 170131739 4 16662356736 5 103350042330 6 15746416534724 7 1732326040444118 10 136302651235172516 11 633114136723545310 13 4726223055272501557 15 52310455435032717371 31 全部为1n = 7k t g(x)4 1 131 3 77n = 15k t g(x)11 1 23 7 2 721 5 3 2467 1 7 7777778第11章差错控制编码n = 31 k t g(x)26 1 4521 2 355116 3 10765711 5 54233256 7 3133650471 15 17777777777n = 127 k t g(x)120 1 211113 2 41567106 3 11554743 99 4 3447023271 92 5 624730022327 85 6 130704476322273 78 7 26230002166130115 71 9 6255010713253127753 64 10 1206534025570773100045 57 11 235265252505705053517721 50 13 54446512523314012421501421 43 15 17721772213651227521220574343 36 15 3146074666522075044764574721735 29 22 403114461367670603667530141176155 22 23 123376070404722522435445626637647043 15 27 22057042445604554770523013762217604353 8 31 7047264052751030651476224271567733130217 1 63 全部为179第11章差错控制编码p表中给出的生成多项式系数是用8进制数字列出的。例如，g(x) = (13)8是指g(x) = x3 + x + 1，因为(13)8 = (1011)2，后者就是此3次方程g(x)的各项系数。p下表列出了部分非本原BCH码的生成多项式参数。nktg(x)nktg(x)1721233341912122221223247271663534351456647133476565732453404652444307335710761354300067171777353780第11章差错控制编码p戈莱码：在上表中的(23, 12)码称为戈莱(Golay)码。它能纠正3个随机错码，并且容易解码，实际应用较多。p扩展BCH码：BCH码的长度都为奇数。在应用中，为了得到偶数长度的码，并增大检错能力，可以在BCH码生成多项式中乘上一个因式(x + 1)，从而得到扩展BCH码(n + 1, k)。扩展BCH码相当于在原BCH码上增加了一个校验位，因此码距比原BCH码增加1。扩展BCH码已经不再具有循环性。例如，广泛实用的扩展戈莱码(24, 12)，其最小码距为8，码率为1/2，能够纠正3个错码和检测4个错码。它比汉明码的纠错能力强很多，付出的代价是解码更复杂，码率也比汉明码低。此外，它不再是循环码了。81第11章差错控制编码n11.6.5 RS码：它是一类具有很强纠错能力的多进制BCH码。u若仍用n表示RS码的码长，则对于m进制的RS码，其码长需要满足下式：n = m 1 = 2q 1 式中 q 2，为整数。u对于能够纠正t个错误的RS码，其监督码元数目为r = 2t，这时的最小码距d0 = 2t + 1。uRS码的生成多项式为g(x) = (x + )(x +2) (x +2t)式中， 伽罗华域GF(2q)中的本原元。u若将每个m进制码元表示成相应的q位二进制码元，则得到的二进制码的参数为：码长：n = q(2q 1)（二进制码元）监督码：r = 2qt（二进制码元）82第11章差错控制编码u由于RS码能够纠正t个m进制错码，或者说，能够纠正码组中t个不超过q位连续的二进制错码，所以RS码特别适用于存在突发错误的信道，例如移动通信网等衰落信道中。此外，因为它是多进制纠错编码，所以特别适合用于多进制调制的场合。83第11章差错控制编码l11.7 卷卷积码n非分组码概念：u卷积码是一种非分组码。通常它更适用于前向纠错，因为对于许多实际情况它的性能优于分组码，而且运算较简单。u卷积码在编码时虽然也是把k个比特的信息段编成n个比特的码组，但是监督码元不仅和当前的k比特信息段有关，而且还同前面m = (N 1)个信息段有关。所以一个码组中的监督码元监督着N个信息段。通常将N称为编码约束度，并将nN称为编码约束长度。一般说来，对于卷积码，k 和 n 的值是比较小的整数。我们将卷积码记作(n, k, N)。码率则仍定义为k / n。 84第11章差错控制编码n11.7.1 卷积码的基本原理u编码器原理方框图编码输出每次输入k比特1k1k1k1k 1 k2k3kNk 12nNk级移存器n个模2加法器每输入k比特旋转1周85第11章差错控制编码u例： (n, k, N) = (3, 1, 3)卷积码编码器p方框图p设输入信息比特序列是bi-2 bi-1 bi bi+1，则当输入bi时，此编码器输出3比特ci di ei，输入和输出的关系如下：bi-2bi输入bibi-1编码输出dicieiM2M3M186ci-2di-2ei-2ci-1di-1ei-1cidieibi-2bi1bitt输入输出第11章差错控制编码在下图中用虚线示出了信息位bi的监督位和各信息位之间的约束关系。这里的编码约束长度nN等于9。 87第11章差错控制编码n11.7.2 卷积码的代数表述上式表示卷积码也是一种线性码。一个线性码完全由一个监督矩阵H或生成矩阵G所确定。下面就来寻找这两个矩阵。u 监督矩阵H现在仍从上面的实例开始分析。假设上图中在第1个信息位b1进入编码器之前，各级移存器都处于“0”状态，则监督位di、ei和信息位bi之间的关系可以写为88第11章差错控制编码 左式可以改写为在上面两个式子和后面的式子中，为简便计，用“”代替“”。将上式用矩阵表示时，可以写成89第11章差错控制编码与11.5节公式H AT = 0T对比，可以看出监督矩阵为90第11章差错控制编码 由此例可见，卷积码的监督矩阵H是一个有头无尾的半无穷矩阵。此外，这个矩阵的每3列的结构是相同的，只是后3列比前3列向下移了两行。例如，第4 6列比第1 3列低2行。自第7行起，每两行的左端比上两行多了3个“0”。 91第11章差错控制编码虽然这样的半无穷矩阵不便于研究，但是只要研究产生前9个码元（9为约束长度）的监督矩阵就足够了。不难看出，这种截短监督矩阵的结构形式如下图所示：由此图可见，H1的最左边是n列(n-k)N行的一个子矩阵，且向右的每n列均相对于前n列降低(n - k)行。H1 =nn k(n k)N92第11章差错控制编码此例中码的截短监督矩阵可以写成如下形式：式中 2阶单位方阵； Pi 1 2阶矩阵，i = 1, 2, 3； O2 2阶全零方阵。93第11章差错控制编码一般说来，卷积码的截短监督矩阵具有如下形式：式中 In-k (n k)阶单位方阵； Pi k (n k)阶矩阵； On-k (n k)阶全零方阵。有时还将H1的末行称为基本监督矩阵hh = PN On-k PN-1 On-k PN-2 On-k P1 In-k它是卷积码的一个最重要的矩阵，因为只要给定了h，则H1也就随之决定了。或者说，我们从给定的h不难构造出H1。94第11章差错控制编码u生成矩生成矩阵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) 95第11章差错控制编码此码的生成矩阵G即为上式最右矩阵： 它也是一个半无穷矩阵，其特点是每一行的结构相同，只是比上一行向右退后3列（因现在n = 3）。96第11章差错控制编码u截短生成矩阵：类似地，也有截短生成矩阵式中 I1 一阶单位方阵；Qi 2 1阶矩阵。与H1矩阵比较可见，Qi是矩阵PiT的转置：Qi = PiT (i = 1, 2, )一般说来，截短生成矩阵具有如下形式：97第11章差错控制编码式中 Ik k阶单位方阵； Qi (n k)k阶矩阵； Ok k阶全零方阵。并将上式中矩阵第一行称为基本生成矩阵g Ik Q1 Ok Q2 Ok Q3Ok QN同样，如果基本生成矩阵g已经给定，则可以从已知的信息位得到整个编码序列。98第11章差错控制编码n11.7.3 卷积码的解码u分类：p代数解码：利用编码本身的代数结构进行解码，不考虑信道的统计特性。大数逻辑解码，又称门限解码，是卷积码代数解码的最主要一种方法，它也可以应用于循环码的解码。大数逻辑解码对于约束长度较短的卷积码最为有效，而且设备较简单。p概率解码：又称最大似然解码。它基于信道的统计特性和卷积码的特点进行计算。针对无记忆信道提出的序贯解码就是概率解码方法之一。另一种概率解码方法是维特比算法。当码的约束长度较短时，它比序贯解码算法的效率更高、速度更快，目前得到广泛的应用。99第11章差错控制编码u大数逻辑解码p工作原理图中首先将接收信息位暂存于移存器中，并从接收码元的信息位和监督位计算校正子。然后，将计算得出的校正子暂存，并用它来检测错码的位置。在信息位移存器输出端，接有一个模2加电路；当检测到输出的信息位有错时，在输出的信息位上加“1”，从而纠正之。 校正子计算信息位移存器校正子移存器错码检测 输入输出修正校正子信息位监督位100第11章差错控制编码这里的错码检测是采用二进制码的大数逻辑解码算法。它利用一组“正交”校验方程进行计算。这里的“正交” 定义：若被校验的那个信息位出现在校验方程组的每一个方程中，而其他的信息位至多在一个方程中出现，则称这组方程为正交校验方程。这样就可以根据被错码影响了的方程数目在方程组中是否占多数来判断该信息位是否错了。下面将用一个实例来具体讲述这一过程。101第11章差错控制编码p例：(2, 1, 6)卷积码编码器方框图监督位和信息位的关系当输入序列为b1 b2 b3 b4 时，监督位为c1 = b1c2 = b2c3 = b3c4 = b1 + b4c5 = b1 + b2 + b5c6 = b1 + b2 + b3 + b6 b6b5b4b3b2b1bi ci输入输出bici102第11章差错控制编码监督关系式 参照11.5节中监督关系的定义式，容易写出 S1 = c1 + b1S2 = c2 + b2S3 = c3 + b3S4 = c4 + b1 + b4S5 = c5 + b1 + b2 + b5S6 = c6 + b1 + b2 + b3 + b6上式中的Si (i = 1 6)称为校正子。正交校验方程组上式经过简单线性变换后，得出如下正交校验方程组：103第11章差错控制编码S1 = c1 + b1S4 = c4 + b1 + b4S5 = c5 + b1 + b2 + b5S2 + S6 = c2 + c6 + b1 + b3 + b6在上式中，只有信息位b1出现在每个方程中，监督位和其他信息位均最多只出现一次。因此，在接收端解码时，考察b1、c1至b6、c6等12个码元，仅当b1出错时，式中才可能有3个或3个以上方程等于“1”。从而能够纠正b1的错误。 104输入输出Yb6b5b4b3b2b1S6S5S4S3S2S1门限电路：“1”的个数 3？校正子Si校正子移存器信息位移存器重算监督位ci接收监督位计算校正子Si6 5 4 3 2 1第11章差错控制编码解码器方框图按照这一原理画出的此(2, 1, 6)卷积码解码器方框图如下105第11章差错控制编码由此图可见，当信息位出现一个错码时，仅当它位于信息位移存器的第6、3、2和1级时，才使校正子等于“1”。因此，这时的校正子序列为100111；反之，当监督位出现一个错码时，校正子序列将为100000。由此可见，当校正子序列中出现第一个“1”时，表示已经检出一个错码。后面的几位校正子则指出是信息位错了，还是监督位错了。图中门限电路的输入代表式中4个方程的4个电压。门限电路将这4个电压（非模2）相加。当相加结果大于或等于3时，门限电路输出“1”，它除了送到输出端的模2加法器上纠正输出码元b1的错码外，还送到校正子移存器纠正其中错误。此卷积码除了能够纠正两位在约束长度中的随机错误外，还能纠正部分多于两位的错误。 106第11章差错控制编码u卷积码的几何表述p码树图：现仍以上面(3, 1, 3)码为例，介绍卷积码的码树 起点信息位状态 M3M2 a 0 0 b 0 1 c 1 0 d 1 1信息位信息位 11 0 1000111c1d1e1000111001110011100010101000111001110011100010101c4d4e4111000001110c2d2e22000100111011001101110010c3d3e3abcdabcdabcdabcd上半部下半部ba10aabcdabcdcdab011001107第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码元为错码。当接收到第46个码元“010”时，将这3个码元和对应的第2级的上下两个支路比较，它和上支路“001”的汉明距离等于2，和下支路“110”的汉明距离等于1，所以选择走下支路。 类似地，当接收到第1012个码元“110”时，和第4级的上下支路比较，它和上支路的“011”的汉明距离等于2，和下支路“100”的汉明距离等于1，所以走下支路。这样，就能够纠正这两个错码。 109第11章差错控制编码一般说来，码树搜索解码法并不实用，因为随着信息序列的增长，码树分支数目按指数规律增长；在上面的码树图中，只有4个信息位，分支已有24 = 16个。但是它为以后实用解码算法建立了初步基础。110第11章差错控制编码p状态图上面的码树可以改进为下述的状态图。由上例的编码器结构可知，输出码元ci di ei决定于当前输入信息位bi和前两位信息位bi-1和bi-2（即移存器M2和M3的状态）。在上图中已经为M2和M3的4种状态规定了代表符号a, b, c 和d。所以，可以将当前输入信息位、移存器前一状态、移存器下一状态和输出码元之间的关系归纳于下表中。111第11章差错控制编码由上表看出，前一状态a只能转到下一状态a或b，前一状态b只能转到下一状态c或d，等等。按照此表中的规律，可以画出状态图如下图所示。 移存器前一状态M3 M2当前输入信息位 bi输出码元cidiei移存器下一状态M3 M2a (00)01000111a (00)b (01)b (01)01001110c (10)d (11)c (10)01011100a (00)b (01)d (11)01010101c (10)d (11)112第11章差错控制编码在此图中，虚线表示输入信息位为“0”时状态转变的路线；实线表示输入信息位为“1”时状态转变的路线。线条旁的3位数字是编码输出比特。利用这种状态图可以方便地从输入序列得到输出序列。 abcd000111101110010011100001113第11章差错控制编码p网格图将状态图在时间上展开，可以得到网格图如下：图中画出了5个时隙。在此图中，仍用虚线表示输入信息位为“0”时状态转变的路线；实线表示输入信息位为“1”时状态转变的路线。可以看出，在第4时隙以后的网格图形完全是重复第3时隙的图形。这也反映了此(3, 1, 3)卷积码的约束长度为3。 110110110110011011011010010010101101101001001001001abcdabcd000000000000000111111111111111100100100114第11章差错控制编码在上图中给出了输入信息位为11010时，在网格图中的编码路径。图中示出这时的输出编码序列是：111 110 010 100 011。由上述可见，用网格图表示编码过程和输入输出关系比码树图更为简练。有了上面的状态图和网格图，下面就可以讨论维特比解码算法了。abcdabcd110010001111100115第11章差错控制编码u维特比解码算法p基本原理将接收到的信号序列和所有可能的发送信号序列比较，选择其中汉明距离最小的序列认为是当前发送信号序列。若发送一个k位序列，则有2k种可能的发送序列。计算机应存储这些序列，以便用作比较。当k较大时，存储量太大，使实用受到限制。维特比算法对此作了简化，使之能够实用。现在仍用上面(3, 1, 3)卷积码的例子来说明维特比算法的原理。116第11章差错控制编码p例： (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条路径和接收序列之间的汉明距离。 117110110110110011011011010010010101101101001001001001abcdabcd000000000000000111111111111111100100100第11章差错控制编码例如，由出发点状态a经过3级路径后到达状态a的两条路径中上面一条为“000 000 000”。它和接收序列“111 010 010”的汉明距离等于5；下面一条为“111 001 011”,它和接收序列的汉明距离等于3。同样，由出发点状态a经过3级路径后到达状态b、c和d的路径分别都有两条，故总共有8条路径。在下表中列出了这8条路径和其汉明距离。118第11章差错控制编码现在将到达每个状态的两条路径的汉明距离作比较，将距离小的一条路径保留，称为幸存路径。若两条路径的汉明距离相同，则可以任意保存一条。这样就剩下4条路径了，即表中第2, 4, 6和8条路径。序号路径对应序列汉明距离幸存否1aaaa000 000 0005否2abca111 001 0113是3aaab000 000 1116否4abcb111 001 1004是5aabc000 111 0017否6abdc111 110 0101是7aabd000 111 1106否8abdd111 110 1014是119第11章差错控制编码第2步继续考察接收序列的后继3个比特“110”。计算4条幸存路径上增加1级后的8条可能路径的汉明距离。结果如下表。表中最小的总距离等于2，其路径是abdc+b，相应序列为111 110 010 100。它和发送序列相同，故对应发送信息位1101。按照表中的幸存路径画出的网格图示于下图中。 序号路径原幸存路径的距离新增路径段新增距离总距离幸存否1abca+a3aa25否2abdc+a1ca23是3abca+b3ab14否4abdc+b1cb12是5abcb+c4bc37否6abdd+c4dc15是7abcb+d4bd04是8abdd+d4dd26否120第11章差错控制编码图中粗红线路径是汉明距离最小（等于2）的路径。 abcd011010010101001abcd111100100110110121第11章差错控制编码上面提到过，为了使输入的信息位全部通过编码器的移存器，使移存器回到初始状态，在信息位1101后面加了3个“0”。若把这3个“0”仍然看作是信息位，则可以按照上述算法继续解码。这样得到的幸存路径网格图示于下图中。图中的粗红线仍然是汉明距离最小的路径。但是，若已知这3个码元是（为结尾而补充的）“0”，则在解码计算时就预先知道在接收这3个“0”码元后，路径必然应该回到状态a。而由图可见，只有两条路径可以回到a状态。所以，这时上图可以简化成下图。110011010010101101001001abcdabcd000 111100100000 011011001101122第11章差错控制编码在上例中卷积码的约束度N = 3，需要存储和计算8条路径的参量。由此可见，维特比解码算法的复杂度随约束长度N按指数形式2N增长。故维特比解码算法适合约束度较小（N 10）的编码。对于约束度大的卷积码，可以采用其他解码算法。 110011010010101101001001abcdabcd000 111100100000 011011001123第11章差错控制编码l11.8 Turbo码n什么是Turbo码？它是一种特殊的链接码。由于其性能接近信息理论上能够达到的最好性能，所以在编码理论上是带有革命性的进步。这种码，特别是解码运算，非常复杂，这里只对其基本概念作一简明介绍。n基本原理u由于分组码和卷积码的复杂度随码组长度或约束度的增大按指数规律增长，所以为了提高纠错能力，人们大多不是单纯增大一种码的长度，而是将两种或多种简单的编码组合成复合编码。u Turbo码的编码器在两个并联或串联的分量码编码器之间增加一个交织器，使之具有很大的码组长度，能在低信噪比条件下得到接近理想的性能。 124第11章差错控制编码uTurbo码的译码器有两个分量码译码器，译码在两个分量译码器之间进行迭代译码，故整个译码过程类似涡轮（turbo）工作，所以又形象地称为Turbo码。n编码器的基本结构：它由一对递归系统卷积码(RSCC)编码器和一个交织器组成，如下图所示：u RSCC编码器和卷积码编码器之间的主要区别是从移存器输出端到信息位输入端之间有反馈路径。原来的卷积码编码器像是一个FIR数字滤波器。增加了反馈路径后，它就变成了一个IIR滤波器，或称递归滤波器。u两个RSCC编码器是相同的。它们的输入经过一个交织器并联。此Turbo码的输入信息位是bi，输出是bic1ic2i，故码率等于1/3。RSCC编码器交织器RSCC编码器bibic1ic2i125第11章差错控制编码uRSCC编码器举例：p方框图：如下图所示p它是一个码率等于1/2的卷积码编码器，输入为bi，输出为bici。p因为输出中第1位是信息位，所以它是系统码。DDbibici126第11章差错控制编码u矩阵交织器：p原理方框图：见右图p其基本形式是矩阵交织器，它由容量为(n-1)m比特的存储器构成。将信号码元按行的方向输入存储器，再按列的方向输出。p若输入码元序列是：a11a12a1m a21a22a2man1anm，则输出序列是：a11a21an1a12a22an2a1manm。 p交织的目的是将突发错码分散开，变成随机错码。例如，若图中第1行的m个码元构成一个码组，并且连续发送到信道上，则当遇到脉冲干扰，造成大量错码时，可能因超出纠错能力而无法纠正错误。但是，若在发送前进行了交织，按列发送，则能够将集中的错码分散到各个码组，从而有利于纠错。这种交织器常用于分组码。 a11a12a1ma21a22a2man1an2anm127第11章差错控制编码u卷积交织器p方 框图举例xxx1234xxx1234x x x 1 xxx1xxx x x x (a) 第14比特输入时的状态xx2567834x5678x x 2 5 x2x51xx x x x (b) 第58比特输入时的状态x369362951x x x x 9101112101112784x 3 6 9(c) 第912比特输入时的状态101376954 3 2 1 14151611128131415164710134 7 10 13(d) 第1316比特输入时的状态交织器解交织器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个码元开始才是有效码元。p一般说来，第1个移存器的容量可以是k比特，第2个移存器的容量是2k比特，第3个移存器的容量是3k比特，直至第N个移存器的容量是Nk比特。p卷积交织法和矩阵交织法相比，主要优点是延迟时间短和需要的存储容量小。卷积交织法端到端的总延迟时间和两端所需的总存储容量均为k(N+1)N个码元，是矩阵交织法的一半。 130解码后的误码率信噪比 (dB) 20交织器容量 10010-110-210-310-410-510-610-7第11章差错控制编码u交织器容量和误码率关系p由此曲线可以看到，交织器容量大时误码率低，这是因为交织范围大可以使交织器输入码元得到更好的随机化。131第11章差错控制编码l11.9 低密度奇偶校低密度奇偶校验码n低密度奇偶校验(LDPC)码是一种线性分组码，和Turbo码同属于复合码类。两者的性能相近，且两者的译码延迟都相当长，所以它们更适用于一些实时性要求不很高的通信。但是LDPC码比Turbo码的译码简单，更易实现。nLDPC码的分类：u规则LDPC码： H矩阵每列具有相同个数的“1”u非非规则LDPC码： H矩阵每列中 “1”的个数不一定相同u非规则LDPC码是在规则LDPC码基础上发展出的，它使解码性能得到改善，使误码率性能比Turbo码还好。 132第11章差错控制编码n非规则LDPC码和Turbo码的误比特率性能比较图中的虚线是Turbo码的性能，实线是LDPC码的性能 当码长n大约在104以上时，LDPC码的性能才比Turbo码好。 香农限Pe133第11章差错控制编码nLDPC码的构造：uLDPC码和普通的奇偶监督码一样，可以由有n列、m行的奇偶监督矩阵H确定；n是码长，m是校正子个数。但是其H矩阵和普通奇偶监督码的有所不同：p首先它是稀疏矩阵，即矩阵中“1”的个数很少，密度很低；设H矩阵每列有j个“1”，每行有k个“1”，则应有j m，k 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章差错控制编码卷积码编码器的方框图：由上图可见，这个卷积码的约束长度等于3。编码器输出的前两个比特c1和c2用来选择星座图划分的路径，最后1个比特c3用于选定星座图第3级（最低级）中的信号点。 c2c1c3编码输出输入k1k212b2b1未编码比特142第11章差错控制编码uTCM编码器结构p方框图p原理：将k比特输入信息段分为k1和k2两段；前k1比特通过一个(n1, k1, m)卷积码编码器，产生n1比特输出，用于选择信号星座图中划分之一，后面的k2比特用于选定星座图中的信号点。这表明星座图被划分为2n1个子集，每个子集中含有个信号点。 在上例编码器方框图中k1 = k2 = 1 选择子集选择子集中的点卷积码编码器k1k2n1信号点143第11章差错控制编码uTCM系统8PSK的网格图由于未编码比特有两种取值，所以每个状态下，有两根线。例如，设初始状态b1 b2 = 00，k1 = k2 = 0。当输入信号序列k1为“0110100”时，移存器状态和输出c1与c2之间的关系示于下表中。 0010a0111c1 c2 c30 0 0011010011010101000 001100 100 110111110111101b1 b2ti +1时刻ti 时刻bcd0 0 1状态144u移存器状态和输出之间的关系 第11章差错控制编码00a00010c10001b01000c10111d11011b01110a00100a0000000c2c1状 态b2b1k1a145第11章差错控制编码p在第1个输入码元“1”到达后，输出码元c1和c2由“00”变成“01”，但是这时的输入信息位k2可能是“0”或“1”，所以输出c1 c2 c3可能是“010”或“011”，这就是右图中最高的两条平行虚线。p在第1个输入码元“1”进入b1后，b1 b2的状态由“00”(a)变到“10”(b)，输出c1 c2 c3可能是“110”或“111”，b1 b2的状态由b变到d，如图中虚线所示。依此类推。 0010a0111c1 c2 c30 0 0011010011010101000 001100 100 110111110111101b1 b2ti +1时刻ti 时刻bcd0 0 1状态146第11章差错控制编码u网格图和星座图之间的对应关系p每对平行转移必须对应最下一级划分同一子集中的两个信号点。例如，图中的“000”和“001”同属于子集C0，“010”和“011”同属于子集C1，等等。这些对信号点具有最大的欧氏距离(d2 = 2)。p从某一状态出发的所有转移，或到达某一状态的所有转移，必须属于同一上级子集。例如，图中从状态a出发的转移“000”、“001”、“010”和“011”都属于子集B0。或者说，此两对平行转移应具有最大可能的欧氏距离。 147第11章差错控制编码n11.10.3 TCM信号的解调uTCM信号的解调算法p通常采用维特比算法，但是现在的网格图表示的状态是波形，而不是码组。解码器的任务是计算接收信号序列路径和各种可能的编码网格路径间的距离。若所有发送信号序列是等概率的，则判定与接收序列距离最小的可能路径（又称为最大似然路径）为发送序列。p因为卷积码是线性码，它具有封闭性，故要考察的路径距离与所用的测试序列无关。所以，不失一般性，可以选用全“0”序列作为测试序列。148第11章差错控制编码u例：8PSK信号解码路径p用全“0”序列作为测试序列时，如下图中虚线路径U所示。图中还用实线示出另一许用波形序列路径V，它从全“0”序列路径分开又回到全“0”序列路径。p若发送序列是全“0”序列，但是接收序列有错误，使接收序列路径离开全“0”路径然后又回到全“0”序列，且中间没有返回状态a，则解码器需要比较此接收序列路径和U的距离与接收序列路径和V的距离之大小。若后者小，则将发生一次错误判决。这里的距离是指欧氏距离。10011100b1 b2abcd状态U0U1U2U3U4V0V1V2V3V4W149第11章差错控制编码u自由欧氏距离Fed：p自由欧氏距离是指许用波形序列集合中各元素之间的最小距离。它决定了产生错误判决的概率。自由欧氏距离越大，错误判决概率越小。p在上例中，U和V两条路径间的欧氏距离d由下式决定：p上式是按照在欧氏空间求矢量和的方法计算的。因此，150第11章差错控制编码p另外一种许用波形序列的路径是，U1WU3（见上图）。它和V序列相似，从状态a开始，离开U（虚线路径），再回到状态a。这个路径和U的距离等于即 d 2比较上面两条路径可见，路径U1WU3和路径V相比，前者和路径U的距离更小。并且，可以逐个验证，这是和路径U距离最小的许用序列的路径。因此，按照上述定义，上式中的距离就是这种编码的自由欧氏距离。故可以将其写为dFed = 2 151第11章差错控制编码p另一方面，未编码的QPSK信号的相继码元（波形）没有约束。若将其自由欧氏距离作为参考距离dref，则由下图可知，p所以，可以证明，和未编码QPSK系统相比，8PSK的TCM系统可以获得的渐近编码增益等于 1d0 = 2sin(/8) = 0.765d1 = 2152第11章差错控制编码p在下表中列出了通过大量仿真计算得出的部分8PSK/TCM系统的(渐近)编码增益。状态数目kG8PSK/QPSK413.01823.601624.133224.596425.0112825.1725625.75153第11章差错控制编码l11.11 小小结