通信原理第9章-差错控制编码课件培训讲学

通信原理第9章--差错控制编码课件

二进制数字信号在传输中发生的错误，主要有两种类型：随机错误和突发错误。随机错误的特点是码元间的错误互相独立，即每个码元的错误概率与它前后码元的错误与否是无关的。突发错误则不然，一个码元的错误往往影响前后码元的错误概率。或者说，一个码元产生错误，则后面几个码元都可能发生错误。在实际信道中，上述两种错误形式往往兼而有之。移动通信的传输信道属于变参信道，它不仅会引起随机错误，而更重要的是造成突发错误。能发现错误的编码叫检错码；能纠正错误的编码叫纠错码。一般说来，纠错码一定能检错。反过来，检错码不一定能纠错。或者说，同一个码，检错能力比纠错能力强。二、差错控制方式在数字通信系统中，利用纠错码或检错码进行差错控制的方式有3种：检错重发、前向纠错和混合纠错，它们的系统构成如图9-1所示，图中有斜线的方框图表示在该端检出错误。1．检错控制方式

检错重发又称自动请求重传方式，记作ARQ(AutomaticRepeatRequest)。发送端发出能够发现（检测）错误的码，接收端收到通过信道传来的码后，在译码器根据该码的编码规则，判决收到的码序列中有无错误产生，如果发现错误，则通过反向信道把这一判决结果反馈给发端。然后，发端根据这些判决信号，把接收端认为有错误的信息再次传送，直到接收端认为正确接收为止。

从上可知，应用ARQ方式必须有一反馈信道，一般较适用于一个用户对一个用户（点对点）的通信，且要求信源能够控制，系统收发两端必须互相配合、密切协作。由于反馈重发的次数与信道干扰情况有关，若信道干扰很频繁，则系统经常处于重发消息的状态，因此这种方式传送消息的连贯性和实时性较差。该方式的优点是：编译码设备简单；在一定的多余度码元下，检错码的检错能力比纠错码的纠错能力要高得多，因此这种系统的适应性很强，特别适应于短波、散射、有线等干扰情况特别复杂的信道中。2．前向纠错方式

前向纠错方式记作FEC（ForwordError-Correction)。发送端发送能够被纠错的码，接收端收到这些码后，通过纠错译码器不仅能够自动地发现错误，而且能自动地纠正接受码字传输中的错误。这种方式的优点是不需要反馈信道，能进行一个用户对多个用户的同播通信，译码实时性较好。其缺点是译码设备比较复杂，所选用的纠错码必须与信道的干扰情况相匹配，因此对信道的适应性较差。编码效率低。但由于这种方式能同播，特别适用于军用通信。

3．混合纠错方式

混合纠错方式记作HEC(HybridError-Correction)是FEC和ARQ方式的结合，这种方式是发送端发送的码不仅能够被检测出错误，而且还具有一定的纠错能力。接收端收到码后，首先检查差错情况，如果在纠错码的纠错能力范围以内，则自动纠错，如果错误过多，超过了码的纠错能力，但能检测出来，则接收端通过反馈信道，要求发端重新传送有错的消息。这种方式具有自动纠错和检错重发的优点，并可达到较低的误码率。因此，在实际中的应用越来越广。

在移动通信系统中，几乎都采用前向纠错的差错控制方式。除了上述三种主要方式以外，还有所谓狭义信息反馈系统（IRQ—InformationRepeatRequest）。这种方式是接收端把收到的消息原封不动地通过反馈信道送回发送端，发送端比较发送的与反馈回来的消息，从而发现错误，并且把传错部分对应的原消息再次传送，最后达到使对方正确接收消息的目的。三、纠错码的分类１.线性码与非线性码

根据纠错码各码组信息和监督元的函数关系，可分为线性码和非线性码。如果函数关系是线性的，即满足一组线性方程式，则称为线性码，否则为非线性码。线性码集合中的所有码字在加法和乘法运算时是封闭的，而非线性码则不封闭。换言之，线性码实际上就是n维线性空间的一个k（k<n）维子空间。目前大量使用的均为线性码。２．分组码与卷积码

根据码组中监督码元与信息码元相互关联的长度，可分为分组码和卷积码。分组码的各码元仅与本组的信息元有关；卷积码中的码元不仅与本组的信息元有关，而且还与前面若干组的信息元有关。分组码把信息序列以k个码元分组，通过编码器将每组的k元信息按一定规律产生r个多余码元（称为校验元或监督元）输出长为n=k+r的一个码字（码组）。因此，每一码组的r个校验元仅与本组的信息元有关而与别组无关。分组码用(n，k)表示，n为码长，k表示信息位数目。卷积码将信息序列以k0个码元分段，通过编码器输出长为n0的一段码组。但是该码的n0-k0个校验元不仅与本段的信息源有关，而且也与其前m段的信息源有关，故卷积码用（n0，k0，m0）表示。３．检错码和纠错码

根据码的用途，可分为检错码和纠错码。检错码以检错为目的，不一定能纠错；而纠错码以纠错为目的，一定能检错。另外，在分组码中按照码的结构特点，可以分为循环码和非循环码；根据纠（检）错误的类型来分，可以分为纠正随机错误的码、纠正突发错误的码和纠正同步错误的码；根据码元取值的进制来分，可分为二进制码和多进制码；等等，这里不一一赘述。四、纠错编码的基本原理下面以分组码为例来说明纠错码检错和纠错的基本原理。1．分组码

分组码一般可用（n，k）表示。其中，k是每个码组二进制信息码元的数目，n是编码组的码元总位数，又称为码组长度，简称码长。n-k=r为每个码组中的监督码元数目。简单地说，分组码是对每段k位长的信息组以一定的规则增加r个监督元，组成长为n的码字。在二进制情况下，共有2k个不同的信息组，相应地可得到2k个不同的码字，称为许用码组。其余2n-2k个码未被选用，称为禁用码组。

两个等长码组之间相应位取值不同的数目称为这两个码组的汉明（Hamming）距离，简称码距。例如11000与10011之间的距离d=3。码组集合中任意两个码字之间距离的最小值称为码的最小距离，用d0表示。最小码距是码的一个重要参数，它是衡量码检错、纠错能力的依据。在分组码中，非零码元的数目称为码字的汉明重量，简称码重。例如，码字10110，码重w=3。

2．检错和纠错能力

我们以重复码为例，说明为什么纠错码能够检错或纠错。若分组码码字中的监督元在信息元之后，而且是信息元的简单重复，则称该分组码为重复码。它是一种简单实用的检错码，并有一定的纠错能力。例如（2，1）重复码，两个许用码组是00与11，d0=2，收端译码，出现01、10禁用码组时，可以发现传输中的一位错误。如果是（3，1）重复码，两个许用码为000、111，d0=3；当收端出现两个或三个1时，判为1，否则判为0。此时，可以纠正一个错误，或者该码可以检出两个错误。

从上面的例子中，可以看出：码的最小距离d0直接关系着码的检错和纠错能力；任一（n，k）分组码，若要在码字内检测e个随机错误，则要求码的最小距离：

d0

≥e+1要纠正t个随机错误，则要求码的最小距离：

d0≥2t+1要纠正t个错误同时检测e个错误（e≥t），则要求码的最小距离：

d0≥t+e+13．编码效率

采用差错控制编码是提高了通信系统的可靠性，但是以降低有效性为代价换来的。通常定义编码效率R来衡量有效性：

R=k/n其中，k是一个码组中信息元的个数，n为码长。对纠错码的基本要求是：检错和纠错能力尽量强；编码效率尽量高；编码规律尽量简单。实际中要根据具体指标要求，保证有一定纠、检错能力和编码效率，并且易于实现。第二节常用的几种简单分组码

纠错编码的种类很多，较早出现的、应用较多的大多属于分组码。本节仅介绍其中一些较为常用的简单编码。一、奇偶监督码

奇偶监督码是在原信息码后面附加一个监督元，使得码组中“1”的个数是奇数或偶数。或者说，它是含一个监督元，码重为奇数或偶数的（n，n-1）系统分组码。奇偶监督码又分为奇监督码和偶监督码。

设码字A=〔an-1，an-2，a1，a0〕，对偶监督码有

(9-1)

式中an-1，an-2，…a1为信息元，a0为监督元。由于该码的每一个码字均按同一规则构成式（9-1），故又称为一致监督码。接收端译码时，按式（9-1）将码组中的码元模二相加，若结果为“0”就认为无错（包括有偶数个错误）；结果为“1”，就可断定该码组经传输后有奇数个错误。奇监督码情况相似，只是码组中“1”的数目为奇数，即满足条件

而检错能力与偶监督码相同。奇偶监督码的编码效率为R=（n-1）/n，奇偶校验码的编码率是最高的。

二维奇偶监督码把上述奇偶监督码的若干码组排列成矩阵，每一码组写成一行，然后再按列的方向增加第二维监督位，设a01a02××××××a0m为m行奇偶监督位；cn-1

cn-2××××××

c0为按列进行第二次编码所增加的监督位，它们构成了一监督位行。由此组成的二维奇偶监督码阵如下：

二、二维奇偶监督码an-11

an-11…a11a01an-12

an-12…a12a02…an-1man-1m…

a1ma0mcn-1

cn-2…

c1c0

这种码有可能检测偶数个错误。因为每行的监督位虽然不能用于检测本行中的偶数个错误，但按列的方向有可能由cn-1、cn-2××××××、c0等监督位检测出来。有一些偶数错码不可能检测出，例如，构成矩形的四个错码就检测不出来,比如阵列中的an-22,a12,an-2m,a1m。这种二维奇偶监督码适于检测突发错误。前述的一维奇偶监督码一般只适于检测随机错误。二维奇偶监督码不仅可用来检错，还可以用于纠错。例如，当码组中仅在一行中有奇数个错误时，则能够确定错码的位置，从而纠正它。an-11

an-11…a11a01an-12

an-12…a12a02…an-1man-1m…

a1ma0mcn-1

cn-2…

c1c0三、恒比码

码字中1的数目与0的数目保持恒定比例的码称为恒比码。由于恒比码中，每个码组均含有相同数目的1和0，因此恒比码又称等重码，定1码。这种码在检测时，通过计算接收码元中1的数目是否正确，就知道有无错误。

目前我国电传通信中普遍采用3：2码，又称“5中取3”的恒比码，即每个码组长度为5，其中3个“1”。这时可能编成的不同码组数目等于从5中取3的组合数10，这10个许用码组恰好可表示10个阿拉伯数字，如表7-1所示。而每个汉字又是以四位十进制数来代表的。实践证明，采用这种码后，我国汉字电报的差错率大为降低。目前国际上通用的ARQ电报通信系统中，采用3：4码，即“7中取3”的恒比码。100119011108111007101016001115110104101103110012010111011010码字数字表9-13：2恆比码第三节线性分组码一、基本概念

线性分组码在所有可能的分组码（BlockCode）中只占很少的一部分，然而，它却几乎是惟一具有实际价值的分组码。线性分组码是所有纠错编码中最基本最容易研究的一类码，它概念清楚，易于理解，而且能方便地反映出各类编码中广为使用的一些基本参数和名称，因此，线性分组码就成了讨论其他各类码的基础。在（n，k）分组码中，若每一个监督元都是码组中某些信息元按模2和得到的，即监督元是信息元按线性关系相加而得到的，则称线性分组码。或者说，可用线性方程组表述码规律性的分组码称为线性分组码。线性分组码是一类重要的纠错码，应用很广泛。对于偶监督码，使用了一位监督位a0，设码字A=〔an-1，an-2，a1，a0〕，有

在接收端解码时，实际上就是计算上式S的结果，若结果为1，则认为有错，结果为0，则认为无错。式中，S称为校正子，取值只有两种，故只能代表有错和无错两种信息，若增加一位监督位，则能增加一个类似于上式的监督关系式。则有两个校正子，它们有4中可能值组合，故能表示4种不同信息，则除了表示有无错信息外，还能有其余可能值来表示错误的位置信息。同理，r个监督位能只是一位错码的2r-1个可能位置。

现以（7，4）分组码为例来说明线性分组码的特点。设其码字为A=〔a6

a5

a4

a3

a2

a1

a0〕，其中前4位是信息元，后3位是监督元，可用下列线性方程组来描述该分组码，产生监督元。

显然，这3个方程是线性无关的。经计算可得（7，4）码的全部码字，如表9—2所示。（9-7）11111111500001117100111014011011060101101131010101500111001211001004001101111110001130101010101010010210010019011000111111000800000000监督元信息元监督元信息元码字序号码字序号表9—2（7，4）码的码字表不难看出，上述（7，4）线性分组码的最小码距d0=3，它能纠正一个错误或检测两个错误。二、监督矩阵Ｈ和生成矩阵Ｇ式（9-7）所述（7，4）码的3个监督方程式可以改写为这组线性方程可用矩阵形式表示为并简记为其中，AＴ是A的转置，０Ｔ是O=〔000〕的转置，ＨＴ是H的转置。（9-11）

H称为监督矩阵，一旦H给定，信息位和监督位之间的关系也就确定了，H为r×n阶矩阵，H矩阵每行之间是彼此线性无关的。式（9-11）所示的H矩阵可分成两部分。（9-10）HAT＝０T或AHＴ＝０（9-12）其中，P为r×k阶矩阵，Ir为r×r阶单位矩阵，可以写成H=〔PIr〕形式的监督矩阵称为典型监督矩阵。HAT=OT说明H矩阵与码字的转置乘积必为零，可以采用来作为判断接收码字A是否出错的依据。=〔PIr〕

若把（9-7）补充为下列方程（9-13）并改写为矩阵形式（9-14）即（9-15）两边求转置，得其中（9-16）称为生成矩阵，由G和信息码组就可以产生全部码字。G为k×r阶矩阵，各行也是线性无关的。生成矩阵也可以分两部分，即(9-17)其中（9-18）Q为k×r阶矩阵，Ik

为k阶单位阵，可以写成式（9-17）形式的G

矩阵，称为典型生成矩阵。非典型形式的生成矩阵经过简单的行运算也一定可以化为典型生成矩阵形式。G=[IkQ]

三、伴随式（校正子）S

设发送码组，在传输过程中可能发生误码。接收码组B=[bn-1，bn-2…b1，b0]，则收发码组之差定义为错误图样E，也称为误差矢量，即

E=B-A

（9-19）其中，且（9-20）式（9-19）也可写作B=A+E

（9-21）令S=BHT，S称为伴随式或校正子，利用AHT=0，得

（9-22）

由此可见，伴随式S与错误图样E之间有确定的线性变换关系。接收端译码器的任务就是从伴随式确定错误图样，然后从接收到的码字中减去错误图样。上述（7，4）线性分组码的伴随式与错误图样的对应关系如表9-3所示。S=BHT=（A+E）HT=EHT

00000101010001110111011100000000000001000001000001000001000001000001000001000000/b0b1b2b3b4b5b601234567s2

s1

s0e6

e5

e4

e3e2e1

e0SE错误码位序号表9-3（7，4）码S与E的对应关系从表9-3中可以看出，伴随式S的2r形式分别代表A码无错和2r

-1种有错的图样。

汉明码是汉明（Hamming）于1949年提出的能够纠正单个随机错误的线性分组码。它有如下参数：码长：n=2r-1信息位：k=2r-1-r监督位：n-k=r,r是不小于3的任意正整数。最小距离：d0=3上述的（7，4）线性分组码就是一个汉明码。汉明码的码率为R=k/n=(n-r)/n=1-r/n(9-23）若码长n很长，则R接近1，所以汉明码是一类高效码。

第四节循环码

循环码（CyclicCode）是一类重要的线性分组码，它除了具有线性码的一般性质外，还具有循环性，即循环码许用码组集合中任一码字循环移位所得的码字仍为该码组集合中的一个码字。循环码的两个最引人注目的特点是：可以用反馈线性移位寄存器很容易地实现其编码和伴随式计算由于循环码有许多固有的代数结构，从而可以找到各种简单实用的译码方法。

目前发现的许多线性分组码都与循环码密切相关。由于循环码具有众多的良好性质，所以它在理论和实用中都是十分重要的。表9-4中给出一种（7，3）循环码全部码字。在代数理论中，为了便于计算，常用码多项式表示码字。（n，k）循环码的码字，其码多项式（以降幂顺序排列）为(9-24)如表9-4中第4号码字可用多项式

表示。

0000000001110101001110111010100111010100111101001111010001234567

码字序号表9-4（7，3)循环码T(x)=an-1xn-1+an-2xn-2+???+a1x+a0

T4(x)=x6+x3+x2+x

T7(x)=x6+x5+x2+1

第7号码字可用多项式

表示。

一、生成多项式及生成矩阵

如果一种码的所有码多项式都是多项式g(x)的倍式，则称g(x)为该码的生成多项式。在(n，k)循环码中，任意码多项式A(x)都是最低次码多项式的倍式。如表9-4的（7，3）循环码中，（9-25）其它码多项式都是g(x)倍式，即

g(x)=T1(x)=x4+x3+x2+1

T0(x)=0·g(x)T2(x)=(x+1)·g(x)T3(x)=x·g(x)…T7(x)=x2·g(x)0000000001110101001110111010100111010100111101001111010001234567

码字序号因此，循环码中次数最低的多项式（全0码字除外）就是生成多项式g(x)。可以证明，g(x)是常数项为1的r=n-k次多项式，是

xn+1

的因式。循环码的生成矩阵常用多项式的形式来表示，即其中

（9-26）(9-27)g(x)=xr+gr-1xr-1+…g1x+1

例如（7，3）循环码，n=7，k=3，r=4，其生成多项式及生成矩阵分别为即

g(x)=T1(x)=x4+x3+x2+1二、监督多项式及监督矩阵为了便于对循环编译码，通常还定义监督多项式，令其中，g(x)是常数项为1的r次多项式，即生成多项式；h(x)是常数项为1的k次多项式，称为监督多项式。同理可得监督矩阵H（9-29）（9-28）其中称为h(x)的逆多项式。

（9-30）例如（7，3）循环码，

则g(x)=x4+x3+x2+1

三、编码方法和电路

在编码时，首先要根据给定的(n，k)值选定生成多项g(x)，即应在xn+1的因式中选一个r=n-k次多项式作为g(x)。设编码前的信息多项式m(x)为（9-31）

m(x)的最高幂次为k-1。循环码中的所有码多项式都可被g(x)整除，根据这条原则，就可以对给定的信息进行编码。用xr（即xn-k）乘m(x)，得到xr·m(x)的次数小于n。用g(x)去除

xr·m(x)

，得到余式R(x)，R(x)的次数必小于g(x)的次数，即小于(n-k)。将此余式加于信息位之后作为监督位，即将R(x)与xr.m(x)相加，得到的多项式必为一码多项式，因为它必能被g(x)整除，且商的次数不大于(k-1)。m(x)=a1+a2x+a3x2+…+akxk-1

因此循环码的码多项式可表示为（9-32）其中xr·m(x)

代表信息位，

R(x)是xr·m(x)与g(x)相除得到的余式，代表监督位。编码电路的主体是生成多项式构成的除法电路，再加上适当的控制电路组成。g(x)=x4+x3+x2+1时，（7，3）循环码的编码电路如图9-2所示。

图9-2（7，3）循环码的编码电路T(x)=xr·m(x)+R(x)

g(x)的次数等于移位寄存器的级数；g(x)的x0、x1、x2、…、xr

的非零系数对应移位寄存的反馈抽头。首先，移位寄存器清零，3位信息元输入时，门1断开，门2接通，直接输出信息元。第3次移位脉冲到来时将除法电路运算所得的余数存入移位寄存器。第4－7次移位时，门2断开，门1接通，输出监督元。具体编码过程如表9-5所示，此时输入信息元110。10010100001000010000断开接通00004567/11000010111011001接通断开/1100123输出移位寄存器D0D1D2D3门2门1输入移位次序表9-5（7，3）循环码的编码过程四、译码方法和电路

接收端译码的目的是检错和纠错。由于任一码多项式T(x)都应能被生成多项式g(x)整除，所以在收端可以将接收码组R(x)用生成多项式去除。当传输中未发生错误时，接收码组和发送码组相同，即T(x)=R(x)，故接收码组R(x)必定能被g(x)整除。若码组在传输中发生错误，则R(x)≠T(x)，R(x)除以g(x)时除不尽而有余项，所以，可以用余项是否为零来判别码组中有无误码。在接收端为纠错而采用的译码方法自然比检错时复杂。同样，为了能够纠错，要求每个可纠正的错误图样必须与一个特定余式有一一对应关系。图9-3为（7，3）循环码的译码电路。图9-3（7，3）循环码译码电路解码器的核心是一个除法电路和缓冲移位寄存器，这里的除法电路与发送端编码器中的除法电路相同。译码电路的具体纠错过程这里不再详述。五、CRC码

CRC是英文名称CyclicRedundancyCheck的缩写，意为循环冗余校验。前面的分析已经表明，循环码的检错能力是很强的，而CRC码便是一种广泛用于检错的循环码。CCITT所推荐的，并在高速数据链路控制规程（HDLC）及X.25协议中所采用的CRC码是一种（n,n-16）的循环码。它的最小距离为4，生成多项式为此码能检测长度不大于16的所有突发错误，所有奇数个和2个独立错误以及其它大量错误图样。这种码的编码电路和检错电路也都很简单。g(x)=x16+x12+x5+1

循环冗余校验码（CRC码）在移动通信中也获得了广泛的应用，例如在美国D-AMPS和日本PDC数字蜂窝移动通信系统中，对于数字话音和控制信号的无线传输所采用的误差保护技术之一就应用了CRC码。

例如在日本的PDC系统中，就采用了如下几种CRC码：1）对数字话音振中44个最敏感的有效比特进行7位CRC计算。此CRC生成多项式为2）8位CRC码，其生成多项式为3）CCITT建议的16位CRC码。上述第②和第③项的CRC码用于控制信好的检错。g(x)=x7+x6+x5+x4+1g(x)=x8+x7+x4+x3+x+1

FEC系统中除了应用分组码（BlockCode）外，还广泛使用卷积码（ConvolutionalCode）。在同等码率和相似的纠错能力下，卷积码的实现往往比分组码要简单，因此在FEC系统中，将越来越多地应用卷积码。一、基本概念

卷积码又称连环码，是1955年提出来的一种纠错码，它和分组码有明显的区别。（n，k）线性分组码中，本组r=n–k个监督元仅与本组k个信息元有关，与其它各组无关，也就是说分组码编码器本身并无记忆性。卷积码则不同，每个(n，k)码段（也称子码，通常较短）内的n个码元不仅与该码段内的信息元有关，而且与前面m段的信息无限元有关。通常称m为编码存储。卷积码常用符号(n，k，m)表示。第五节卷积码图9-4是（2，1，2）卷积码的编码器。它由移位寄存器、模二加法器及开关电路组成。图9-4卷积码（2，1，2）编码器

起始状态，各级移位寄存器清零，即S1S2S3为000。S1等于当前输入数据，而移位寄存器状态S2S3存储以前的数据，输出码字C由下式确定（9-33）

当输入数据D=[11010]时，输出码字可以计算出来，具体计算过程如表9-6所示，另外，为了保证全部数据通过寄存器，还必须在数据位后加3个0。

从上述的计算可知，每1位数据，影响（m+1）个输出子码，称（m+1）为编码约束度。每个子码有n个码元，在卷积码中有约束关系的最大码长度则为（m+1）n，称为编码约束长度。（2，1，2）卷积码的编码约束度为3，约束长度为6。aacbcdba状态0000111000010111C1C20000100110110100S3S200001011S1表9-6（2，1，2）编码器的工作过程二、卷积码的描述

卷积码同样也可以用矩阵的方法描述，但较抽象。因此，我们采用图解的方法直观描述其编码过程。常用的图解法有3种方法：树图、状态图和格图。1．树图

树图描述的是在任何数据序列输入时，码字所有可能的输出。对应于图9-4所示的（2，1，2）卷积码的编码电路，可以画出其树图如图9-5所示。图9-5（2，1，2）码的树图以S1S2S3为000作为起点，用a、b、c和d表示出S3S2的4种可能状态：00、01、10和11。若第一位数据S1=0，输出C1C2=00，从起点通过上支路到达状态a，即S3S2=00；若S1=1，输出C1C2=11，从起点通过下支路到达状态b，即S3S2=01；依次类推，可得整个树图。输入不同的信息序列，编码器就走不同的路径，输出不同的码序列。例如当输入数据为[11010]时，其路径如图9-5中虚线所示，并得到输出码序列为[11010100…]，与表9-6的结果一致。2．状态图

除了用树图表示编码器的工作过程外，还可以用状态图来描述。图9-6就是该（2，1，2）卷积码编码器的状态图。在图中有4个节点a、b、c、d，同样分别表示S3S2的4种可能状态。每个节点有两条线离开该节点，实线表示输入数据为0，虚线表示输入数据为1，线旁的数字即为输出码字。图9-6（2，1，2）卷积码的状态图3．格图

格图也称网络或篱笆图，它由状态图在时间上展开而得到，如图9-7所示。图中画出所有可能数据输入时，状态转移的全部可能轨迹，实线表示数据为0，虚线表示数据为1，线旁数字为输出码字，节点表示状态。

以上的3种卷积码的描述方法，不但有助于求解输出码字，了解编码工作过程，而且对研究解码方法也很有用。图9-7（2，1，2）卷积码的格图三、卷积码的译码

卷积码的译码可分为代数译码和概率译码两大类。代数译码是利用生成矩阵和监督矩阵来译码，最主要的方法是大数逻辑译码。概率译码比较实用的有两种：维特比译码和序列译码。目前，概率译码已成为卷积码最主要的译码方法。本节我们将简要讨论维特比译码和序列译码。1．维特比译码

维特比译码，它是一种最大似然译码算法。最大似然译码算法的基本思路是，把接收码字与所有可能的码字比较，选择一种码距最小的码字作为解码输出。由于接收序列通常很长，所以维特比译码对最大似然译码做了简化，即它把接收码字分段累接处理，每接收一段码字，计算、比较一次，保留码距最小的路径，直至译完整个序列。现以上述（2，1，2）卷积码为例说明维特比译码过程。设发端的信息数据D=[11010000]，由编码器输出的码字C=[1101010010110000]，收端接收的码序列B=[0101011010010010]，有4位码元（带下划线）差错。下面参照图9-7的格状图说明译码过程。

如图9-8所示，先选前3个码作为标准，对到达第3级的4个节点的8条路径进行比较，逐步算出每条路径与接收码字之间的累计码距。累计码距分别用括号内的数字标出，对照后保留一条到达该节点的码距较小的路径作为幸存路径。再将当前节点移到第4条级，计算、比较、保留幸存路径，直至最后得到到达终点的一条幸存路径，即为解码路径，如图9-8中实线所示。根据该路径，得到解码结果。图9-8维特比译码格图序列译码

当卷积码参量m很大时，可以采用序列译码法。其过程如下：译码先从码树的起始节点开始，把接收到的第一个子码的n个码元与自始节点出发的两条分支按照最小汉明距离进行比较，沿着差异最小的分支走向第二个节点。在第二个节点上，译码器仍以同样原理到达下一个节点，以此类推，最后得到一条路径。若接收码组有错，则自某节点开始，译码器就一直在不正确的路径中行进，译码也一直错误。因此，译码有一个门限，当接收码元与译码器所走的路径上的码元之间的差异总数超过门限值时，译码器判定有错，并且返回试走另一分支。经数次返回找出一条正确的路径，最后译码输出。当该门限值很小时，序列译码的性能接近最大似然译码，尽管译码时每一次搜索的计算量和所需存储容量不大，但是其频繁的返回则要求更大的计算量