数字信号最佳接收.pptx

1第11章差错控制编码11.2 纠错编码的基本原理分组码的结构将信息码分组，为每组信息码附加若干监督码的编码称为分组码。在分组码中，监督码元仅监督本码组中的信息码元。信息位和监督位的关系：举例如下信息位监督位晴000云011阴101雨110第1页/共75页2第11章差错控制编码分组码的一般结构分组码的符号：(n,k)N 码组的总位数，又称为码组的长度（码长），k 码组中信息码元的数目，n k r 码组中的监督码元数目，或称监督位数目。第2页/共75页3第11章差错控制编码分组码的码重和码距码重：把码组中“1”的个数目称为码组的重量，简称码重。码距：把两个码组中对应位上数字不同的位数称为码组的距离，简称码距。码距又称汉明距离。例如，“000”晴，“011”云，“101”阴，“110”雨，4个码组之间，任意两个的距离均为2。最小码距：把某种编码中各个码组之间距离的最小值称为最小码距(d0)。例如，上面的编码的最小码距d0=2。第3页/共75页4第11章差错控制编码码距和检纠错能力的关系一种编码的最小码距d0的大小直接关系着这种编码的检错和纠错能力为检测e个错码，要求最小码距 d0 e+1为了纠正t个错码，要求最小码距d0 2t+1为纠正t个错码，同时检测e个错码，要求最小码距 第4页/共75页5第11章差错控制编码11.4简单的实用编码11.4.1 奇偶监督码奇偶监督码分为奇数监督码和偶数监督码两种，两者的原理相同。在偶数监督码中，无论信息位多少，监督位只有1位，它使码组中“1”的数目为偶数，即满足下式条件：式中a0为监督位，其他位为信息位。这种编码能够检测奇数个错码。在接收端，按照上式求“模2和”，若计算结果为“1”就说明存在错码，结果为“0”就认为无错码。奇数监督码与偶数监督码相似，只不过其码组中“1”的数目为奇数：第5页/共75页6第11章差错控制编码11.4.2 二维奇偶监督码（方阵码）二维奇偶监督码的构成它是先把上述奇偶监督码的若干码组排成矩阵，每一码组写成一行，然后再按列的方向增加第二维监督位，如下图所示图中a01 a02 a0m为m行奇偶监督码中的m个监督位。cn-1 cn-2 c1 c0为按列进行第二次编码所增加的监督位，它们构成了一监督位行。第6页/共75页7第11章差错控制编码 11.4.3 恒比码在恒比码中，每个码组均含有相同数目的“1”（和“0”）。由于“1”的数目与“0”的数目之比保持恒定，故得此名。这种码在检测时，只要计算接收码组中“1”的数目是否对，就知道有无错码。恒比码的主要优点是简单和适于用来传输电传机或其他键盘设备产生的字母和符号。对于信源来的二进制随机数字序列，这种码就不适合使用了。第7页/共75页8第11章差错控制编码11.4.4 正反码正反码的编码：它是一种简单的能够纠正错码的编码。其中的监督位数目与信息位数目相同，监督码元与信息码元相同或者相反则由信息码中“1”的个数而定。例如，若码长n=10，其中信息位 k=5，监督位 r=5。其编码规则为：当信息位中有奇数个“1”时，监督位是信息位的简单重复；当信息位有偶数个“1”时，监督位是信息位的反码。例如，若信息位为11001，则码组为1100111001；若信息位为10001，则码组为1000101110。第8页/共75页9第11章差错控制编码11.5 线性分组码基本概念代数码：建立在代数学基础上的编码。线性码：按照一组线性方程构成的代数码。在线性码中信息位和监督位是由一些线性代数方程联系着的。线性分组码：按照一组线性方程构成的分组码。本节将以汉明码为例引入线性分组码的一般原理。第9页/共75页10第11章差错控制编码汉明码能够纠正1位错码且编码效率较高的一种线性分组码。汉明码的构造原理。在偶数监督码中，由于使用了一位监督位a0，它和信息位an-1 a1一起构成一个代数式：在接收端解码时，实际上就是在计算若S=0，就认为无错码；若S=1，就认为有错码。现将上式称为监督关系式，S称为校正子。由于校正子S只有两种取值，故它只能代表有错和无错这两种信息，而不能指出错码的位置。第10页/共75页11第11章差错控制编码如果希望用r个监督位构造出r个监督关系式来指示1位错码的n种可能位置，则要求第11页/共75页12第11章差错控制编码例：以分组码(n,k)中的（7,4）汉明码为例，用S1、S2和S3表示3个监督关系式中的校正子，则S1、S2和S3的值与错码位置的对应关系可以规定如下表所列：S1 S2 S3错码位置S1 S2 S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错码汉明码的最小码距d0=3。因此，这种码能够纠正1个错码或检测2个错码。由于码率k/n=(n-r)/n=1 r/n，故当n很大和r很小时，码率接近1。可见，汉明码是一种高效码。第12页/共75页13第11章差错控制编码由表中规定可见，仅当一位错码的位置在a2、a4、a5或a6时，校正子S1为1；否则S1为零。这就意味着a2、a4、a5和a6四个码元构成偶数监督关系：同理，a1、a3、a5和a6构成偶数监督关系：以及a0、a3、a4 和a6构成偶数监督关系第13页/共75页14第11章差错控制编码在发送端编码时，信息位a6、a5、a4和a3的值决定于输入信号，因此它们是随机的。监督位a2、a1和a0应根据信息位的取值按监督关系来确定，即监督位应使上3式中S1、S2和S3的值为0（表示编成的码组中应无错码）：上式经过移项运算，解出监督位给定信息位后，可以直接按上式算出监督位，结果见下表：第14页/共75页15第11章差错控制编码信息位a6 a5 a4 a3监督位a2 a1 a0信息位a6 a5 a4 a3监督位a2 a1 a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111第15页/共75页16第11章差错控制编码接收端收到每个码组后，先计算出S1、S2和S3，再查表判断错码情况。例如，若接收码组为0000011，按上述公式计算可得：S1=0，S2=1，S3=1。由于S1 S2 S3 等于011，故查表可知在a3位有1错码。第16页/共75页17第11章差错控制编码线性分组码的一般原理线性分组码的构造H矩阵上面(7,4)汉明码的例子有现在将上面它改写为上式中已经将“”简写成“+”。第17页/共75页18第11章差错控制编码上式可以表示成如下矩阵形式：上式还可以简记为H AT=0T 或A HT=0第18页/共75页19第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给定，编码时监督位和信息位的关系就完全确定了。第19页/共75页20第11章差错控制编码H矩阵的性质：1)H的行数就是监督关系式的数目，它等于监督位的数目r。H的每行中“1”的位置表示相应码元之间存在的监督关系。例如，H的第一行1110100表示监督位a2是由a6 a5 a4之和决定的。H矩阵可以分成两部分，例如 式中，P为r k阶矩阵，Ir为r r阶单位方阵。我们将具有P Ir形式的H矩阵称为典型阵。第20页/共75页21第11章差错控制编码G矩阵：上面汉明码例子中的监督位公式为 也可以改写成矩阵形式：第21页/共75页22第11章差错控制编码或者写成式中，Q为一个k r阶矩阵，它为P的转置，即 Q=PT 上式表示，在信息位给定后，用信息位的行矩阵乘矩阵Q就产生出监督位。第22页/共75页23第11章差错控制编码我们将Q的左边加上1个k k阶单位方阵，就构成1个矩阵G G称为生成矩阵，因为由它可以产生整个码组，即有或者因此，如果找到了码的生成矩阵G，则编码的方法就完全确定了。具有IkQ形式的生成矩阵称为典型生成矩阵。由典型生成矩阵得出的码组A中，信息位的位置不变，监督位附加于其后。这种形式的码称为系统码。第23页/共75页24第11章差错控制编码错码矩阵和错误图样 一般说来，A为一个n列的行矩阵。此矩阵的n个元素就是码组中的n个码元，所以发送的码组就是A。此码组在传输中可能由于干扰引入差错，故接收码组一般说来与A不一定相同。若设接收码组为一n列的行矩阵B，即则发送码组和接收码组之差为B A=E(模2)它就是传输中产生的错码行矩阵 式中第24页/共75页25第11章差错控制编码因此，若ei=0，表示该接收码元无错；若ei=1，则表示该接收码元有错。B A=E 可以改写成 B=A+E例如，若发送码组A=1000111，错码矩阵E=0000100，则接收码组B=1000011。错码矩阵有时也称为错误图样。第25页/共75页26第11章差错控制编码校正子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将能代表错码的位置。第26页/共75页27第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”码组外）。第27页/共75页28第11章差错控制编码11.6 循环码11.6.1 循环码原理循环性：循环性是指任一码组循环一位（即将最右端的一个码元移至左端，或反之）以后，仍为该码中的一个码组。在下表中给出一种(7,3)循环码的全部码组。例如，表中的第2码组向右移一位即得到第5码组；第6码组向右移一位即得到第7码组。码组编号信息位监督位码组编号信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001011200101116101110030101110711001014011100181110010第28页/共75页29第11章差错控制编码码多项式码组的多项式表示法把码组中各码元当作是一个多项式的系数，即把一个长度为n的码组表示成例如，上表中的任意一个码组可以表示为其中第7个码组可以表示为这种多项式中，x仅是码元位置的标记，例如上式表示第7码组中a6、a5、a2和a0为“1”，其他均为0。因此我们并不关心x的取值。第29页/共75页30第11章差错控制编码 码多项式的按模运算在整数运算中，有模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 除得的余数。第30页/共75页31第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。第31页/共75页32第11章差错控制编码循环码的码多项式在循环码中，若T(x)是一个长为n的许用码组，则xiT(x)在按模xn+1运算下，也是该编码中的一个许用码组，即若则T(x)也是该编码中的一个许用码组。【证】因为若则（模(xn+1)）所以，这时有第32页/共75页33第11章差错控制编码上式中T(x)正是T(x)代表的码组向左循环移位i次的结果。因为原已假定T(x)是循环码的一个码组，所以T(x)也必为该码中一个码组。例如，循环码组其码长n=7。现给定i=3，则其对应的码组为0101110，它正是表中第3码组。由上述分析可见，一个长为n的循环码必定为按模(xn+1)运算的一个余式。第33页/共75页34第11章差错控制编码循环码的生成矩阵G在循环码中，一个(n,k)码有2k个不同的码组。若用g(x)表示其中前(k-1)位皆为“0”的码组，则g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是码组，而且这k个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵G。在一个（n,k）循环码中，有 且只有一个次数为(n k)的多项式g(x)，称其为码的生成多项式。一旦确定了g(x)，则整个(n,k)循环码就被确定了。第34页/共75页35第11章差错控制编码因此，循环码的生成矩阵G可以写成 例：在上表所给出的(7,3)循环码中，n=7,k=3,n k=4。由此表可见，唯一的一个(n k)=4次码多项式代表的码组是第二码组0010111，与它相对应的码多项式（即生成多项式）g(x)=x4+x2+x+1。将此g(x)代入上式，得到或第35页/共75页36第11章差错控制编码由于上式不符合G=IkQ的形式，所以它不是典型阵。不过，将它作线性变换，不难化成典型阵。我们可以写出此循环码组，即上式表明，所有码多项式T(x)都可被g(x)整除，而且任意一个次数不大于(k 1)的多项式乘g(x)都是码多项式。第36页/共75页37第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次多项式。由下式可知，xk T(x)在模(xn+1)运算下也是一个码组，故可以写成第37页/共75页38第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次的因子。不难看出，这样的因子有两个，即第38页/共75页39第11章差错控制编码 以上两式都可作为生成多项式。不过，选用的生成多项式不同，产生出的循环码码组也不同。第39页/共75页40第11章差错控制编码11.6.2 循环码的编解码方法循环码的编码方法编码原则在编码时，首先要根据给定的(n,k)值选定生成多项式g(x)，即从(xn+1)的因子中选一个(n-k)次多项式作为g(x)。第40页/共75页41第11章差错控制编码编码步骤：（1）用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。（2）用g(x)除xn-k m(x)，得到商Q(x)和余式r(x)，即例如，若选定g(x)=x4+x2+x+1，则 上式相当于第41页/共75页42第11章差错控制编码（3）编出的码组T(x)为T(x)=xn-k m(x)+r(x)在上例中，T(x)=1100000+101=1100101，它就是上表中的第7码组。第42页/共75页43第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)除时可能除不尽而有余项，即有因此，就以余项是否为零来判别接收码组中有无错码。需要指出，有错码的接收码组也有可能被g(x)整除。这时的错码就不能检出了。这种错误称为不可检错误。不可检错误中的误码数必定超过了这种编码的检错能力。第43页/共75页44第11章差错控制编码纠错解码原理：为了能够纠错，要求每个可纠正的错误图样必须与一个特定余式有一一对应关系。因为只有存在上述一一对应的关系时，才可能从上述余式唯一地决定错误图样，从而纠正错码。因此，原则上纠错可按下述步骤进行：用生成多项式g(x)除接收码组R(x)，得出余式r(x)。按余式r(x)，用查表的方法或通过某种计算得到错误图样E(x)；例如，通过计算校正子S和查表，就可以确定错码的位置。从R(x)中减去E(x)，便得到已经纠正错码的原发送码组T(x)。通常，一种编码可以有几种纠错解码方法，上述解码方法称为捕错解码法。目前多采用软件运算实现上述编解码运算。第44页/共75页45第11章差错控制编码11.7 卷积码非分组码概念：卷积码是一种非分组码。通常它更适用于前向纠错，因为对于许多实际情况它的性能优于分组码，而且运算较简单。卷积码在编码时虽然也是把k个比特的信息段编成n个比特的码组，但是监督码元不仅和当前的k比特信息段有关，而且还同前面m=(N 1)个信息段有关。所以一个码组中的监督码元监督着N个信息段。通常将N称为编码约束度，并将nN称为编码约束长度。一般说来，对于卷积码，k 和 n 的值是比较小的整数。我们将卷积码记作(n,k,N)。码率则仍定义为k/n。第45页/共75页46第11章差错控制编码11.7.1 卷积码的基本原理编码器原理方框图编码输出每次输入k比特1k1k1k1k 1 k2k3kNk 12nNk级移存器n个模2加法器每输入k比特旋转1周第46页/共75页47第11章差错控制编码例：(n,k,N)=(3,1,3)卷积码编码器方框图设输入信息比特序列是bi-2 bi-1 bi bi+1，则当输入bi时，此编码器输出3比特ci di ei，输入和输出的关系如下：bi-2bi输入bibi-1编码输出dicieiM2M3M1第47页/共75页48ci-2di-2ei-2ci-1di-1ei-1cidieibi-2bi1bitt输入输出第11章差错控制编码在下图中用虚线示出了信息位bi的监督位和各信息位之间的约束关系。这里的编码约束长度nN等于9。第48页/共75页49第11章差错控制编码11.7.2 卷积码的代数表述上式表示卷积码也是一种线性码。一个线性码完全由一个监督矩阵H或生成矩阵G所确定。下面就来寻找这两个矩阵。监督矩阵H现在仍从上面的实例开始分析。假设上图中在第1个信息位b1进入编码器之前，各级移存器都处于“0”状态，则监督位di、ei和信息位bi之间的关系可以写为第49页/共75页50第11章差错控制编码 左式可以改写为在上面两个式子和后面的式子中，为简便计，用“”代替“”。将上式用矩阵表示时，可以写成第50页/共75页51第11章差错控制编码与11.5节公式H AT=0T对比，可以看出监督矩阵为第51页/共75页52第11章差错控制编码 由此例可见，卷积码的监督矩阵H是一个有头无尾的半无穷矩阵。此外，这个矩阵的每3列的结构是相同的，只是后3列比前3列向下移了两行。例如，第4 6列比第1 3列低2行。自第7行起，每两行的左端比上两行多了3个“0”。第52页/共75页53第11章差错控制编码虽然这样的半无穷矩阵不便于研究，但是只要研究产生前9个码元（9为约束长度）的监督矩阵就足够了。不难看出，这种截短监督矩阵的结构形式如下图所示：由此图可见，H1的最左边是n列(n-k)N行的一个子矩阵，且向右的每n列均相对于前n列降低(n-k)行。H1=nn k(n k)N第53页/共75页54第11章差错控制编码此例中码的截短监督矩阵可以写成如下形式：式中 2阶单位方阵；Pi 1 2阶矩阵，i=1,2,3；O2 2阶全零方阵。第54页/共75页55第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。第55页/共75页56第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)第56页/共75页57第11章差错控制编码此码的生成矩阵G即为上式最右矩阵：它也是一个半无穷矩阵，其特点是每一行的结构相同，只是比上一行向右退后3列（因现在n=3）。第57页/共75页58第11章差错控制编码截短生成矩阵：类似地，也有截短生成矩阵式中 I1 一阶单位方阵；Qi 2 1阶矩阵。与H1矩阵比较可见，Qi是矩阵PiT的转置：Qi=PiT (i=1,2,)一般说来，截短生成矩阵具有如下形式：第58页/共75页59第11章差错控制编码式中 Ik k阶单位方阵；Qi (n k)k阶矩阵；Ok k阶全零方阵。并将上式中矩阵第一行称为基本生成矩阵g Ik Q1 Ok Q2 Ok Q3Ok QN同样，如果基本生成矩阵g已经给定，则可以从已知的信息位得到整个编码序列。第59页/共75页60第11章差错控制编码11.7.3 卷积码的解码分类：代数解码：利用编码本身的代数结构进行解码，不考虑信道的统计特性。大数逻辑解码，又称门限解码，是卷积码代数解码的最主要一种方法，它也可以应用于循环码的解码。大数逻辑解码对于约束长度较短的卷积码最为有效，而且设备较简单。概率解码：又称最大似然解码。它基于信道的统计特性和卷积码的特点进行计算。针对无记忆信道提出的序贯解码就是概率解码方法之一。另一种概率解码方法是维特比算法。当码的约束长度较短时，它比序贯解码算法的效率更高、速度更快，目前得到广泛的应用。第60页/共75页61第11章差错控制编码大数逻辑解码工作原理图中首先将接收信息位暂存于移存器中，并从接收码元的信息位和监督位计算校正子。然后，将计算得出的校正子暂存，并用它来检测错码的位置。在信息位移存器输出端，接有一个模2加电路；当检测到输出的信息位有错时，在输出的信息位上加“1”，从而纠正之。校正子计算信息位移存器校正子移存器错码检测 输入输出修正校正子信息位监督位第61页/共75页62第11章差错控制编码例：(2,1,6)卷积码编码器方框图监督位和信息位的关系当输入序列为b1 b2 b3 b4 时，监督位为c1=b1c2=b2c3=b3c4=b1+b4c5=b1+b2+b5c6=b1+b2+b3+b6 b6b5b4b3b2b1bi ci输入输出bici第62页/共75页63第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)称为校正子。正交校验方程组上式经过简单线性变换后，得出如下正交校验方程组：第63页/共75页64第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的错误。第64页/共75页65输入输出Yb6b5b4b3b2b1S6S5S4S3S2S1门限电路：“1”的个数 3？校正子Si校正子移存器信息位移存器重算监督位ci接收监督位计算校正子Si6 5 4 3 2 1第11章差错控制编码解码器方框图按照这一原理画出的此(2,1,6)卷积码解码器方框图如下第65页/共75页66第11章差错控制编码由此图可见，当信息位出现一个错码时，仅当它位于信息位移存器的第6、3、2和1级时，才使校正子等于“1”。因此，这时的校正子序列为100111；反之，当监督位出现一个错码时，校正子序列将为100000。由此可见，当校正子序列中出现第一个“1”时，表示已经检出一个错码。后面的几位校正子则指出是信息位错了，还是监督位错了。图中门限电路的输入代表式中4个方程的4个电压。门限电路将这4个电压（非模2）相加。当相加结果大于或等于3时，门限电路输出“1”，它除了送到输出端的模2加法器上纠正输出码元b1的错码外，还送到校正子移存器纠正其中错误。此卷积码除了能够纠正两位在约束长度中的随机错误外，还能纠正部分多于两位的错误。第66页/共75页67第11章差错控制编码卷积码的几何表述码树图：现仍以上面(3,1,3)码为例，介绍卷积码的码树 起点信息位状态 M3M2 a 0 0 b 0 1 c 1 0 d 1 1信息位信息位 11 0 1000111c1d1e1000111001110011100010101000111001110011100010101c4d4e4111000001110c2d2e22000100111011001101110010c3d3e3abcdabcdabcdabcd上半部下半部ba10aabcdabcdcdab011001第67页/共75页68第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。第68页/共75页69第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，所以走下支路。这样，就能够纠正这两个错码。第69页/共75页70第11章差错控制编码状态图上面的码树可以改进为下述的状态图。由上例的编码器结构可知，输出码元ci di ei决定于当前输入信息位bi和前两位信息位bi-1和bi-2（即移存器M2和M3的状态）。在上图中已经为M2和M3的4种状态规定了代表符号a,b,c 和d。所以，可以将当前输入信息位、移存器前一状态、移存器下一状态和输出码元之间的关系归纳于下表中。第70页/共75页71第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)第71页/共75页72第11章差错控制编码在此图中，虚线表示输入信息位为“0”时状态转变的路线；实线表示输入信息位为“1”时状态转变的路线。线条旁的3位数字是编码输出比特。利用这种状态图可以方便地从输入序列得到输出序列。abcd000111101110010011100001第72页/共75页73第11章差错控制编码网格图将状态图在时间上展开，可以得到网格图如下：图中画出了5个时隙。在此图中，仍用虚线表示输入信息位为“0”时状态转变的路线；实线表示输入信息位为“1”时状态转变的路线。可以看出，在第4时隙以后的网格图形完全是重复第3时隙的图形。这也反映了此(3,1,3)卷积码的约束长度为3。110110110110011011011010010010101101101001001001001abcdabcd000000000000000111111111111111100100100第73页/共75页74第11章差错控制编码在上图中给出了输入信息位为11010时，在网格图中的编码路径。图中示出这时的输出编码序列是：111 110 010 100 011。由上述可见，用网格图表示编码过程和输入输出关系比码树图更为简练。有了上面的状态图和网格图，下面就可以讨论维特比解码算法了。abcdabcd110010001111100第74页/共75页75感谢您的观看。第75页/共75页