通 信 原 理 指导教师:杨建国 指导教师:杨建国 二零零七年十一月 二零零八年三月.

Presentation on theme: "通 信 原 理 指导教师:杨建国 指导教师:杨建国 二零零七年十一月 二零零八年三月."— Presentation transcript:

1 通 信 原 理 指导教师:杨建国 指导教师:杨建国 二零零七年十一月 二零零八年三月

2 第十章 差错控制编码 10.1 概述 10.2 检错与纠错原理 10.3 简单分组码 10.4 线性分组码 10.5 循环码
第十章 差错控制编码 10.1 概述 10.2 检错与纠错原理 10.3 简单分组码 10.4 线性分组码 10.5 循环码 10.6 卷积码

3 10.1 概 述 信源编码与信道编码 在数字通信中，根据不同的目的，编码可分为信源编码和信道编码。信源编码是为了提高数字信号的有效性以及为了使模拟信号数字化而采取的编码。信道编码是为了降低误码率， 提高数字通信的可靠性而采取的编码。 数字信号在传输过程中，加性噪声、码间串扰等都会产生误码。为了提高系统的抗干扰性能，可以加大发射功率，降低接收设备本身的噪声，以及合理选择调制、解调方法等。此外，还可以采用信道编码技术。

4 差错控制方式 　　常用的差错控制方式有三种：检错重发、前向纠错和混合纠错。它们的系统构成如图10－1所示, 图中有斜线的方框图表示在该端检出错误。

5 图10-1 差错控制方式的系统构成

6 1. 检错重发方式 检错重发又称自动请求重传方式，记作ARQ(Automatic Repeat Request)。 由发端送出能够发现错误的码，由收端判决传输中无错误产生，如果发现错误，则通过反向信道把这一判决结果反馈给发端，然后，发端把收端认为错误的信息再次重发，从而达到正确传输的目的。其特点是需要反馈信道，译码设备简单，对突发错误和信道干扰较严重时有效， 但实时性差，主要在计算机数据通信中得到应用。

7 2. 前向纠错方式 前向纠错方式记作FEC(Forword ErrorCorrection)。发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。其特点是单向传输，实时性好，但译码设备较复杂。

8 3. 混合纠错方式 混合纠错方式记作HEC(Hybrid ErrorCorrection)是FEC和ARQ方式的结合。发端发送具有自动纠错同时又具有检错能力的码。收端收到码后，检查差错情况，如果错误在码的纠错能力范围以内，则自动纠错，如果超过了码的纠错能力， 但能检测出来，则经过反馈信道请求发端重发。这种方式具有自动纠错和检错重发的优点，可达到较低的误码率，因此， 近年来得到广泛应用。

9 另外，按照噪声或干扰的变化规律，可把信道分为三类：随机信道、突发信道和混合信道。恒参高斯白噪声信道是典型的随机信道，其中差错的出现是随机的，而且错误之间是统计独立的。具有脉冲干扰的信道是典型的突发信道， 错误是成串成群出现的，即在短时间内出现大量错误。短波信道和对流层散射信道是混合信道的典型例子，随机错误和成串错误都占有相当比例。对于不同类型的信道，应采用不同的差错控制方式。

10 10.2　检错与纠错原理 10.2.1纠错码的分类 (1) 根据纠错码各码组信息元和监督元的函数关系，可分为线性码和非线性码。如果函数关系是线性的，即满足一组线性方程式，则称为线性码，否则为非线性码。 (2) 根据上述关系涉及的范围，可分为分组码和卷积码。分组码的各码元仅与本组的信息元有关；卷积码中的码元不仅与本组的信息元有关， 而且还与前面若干组的信息元有关。 (3) 根据码的用途，可分为检错码和纠错码。检错码以检错为目的，不一定能纠错；而纠错码以纠错为目的，一定能检错。

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

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

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

14 码的最小距离d0直接关系着码的检错和纠错能力；任一(n,k)分组码，若要在码字内:
(1) 检测e个随机错误，则要求码的最小距离d0≥e+1; (2) 纠正t个随机错误， 则要求码的最小距离d0≥2t+1; (3) 纠正t个同时检测e(≥t)个随机错误，则要求码的最小距离d0≥t+e+1。

15 3. 编码效率 用差错控制编码提高通信系统的可靠性， 是以降低有效性为代价换来的。我们定义编码效率R来衡量有效性: 其中, k是信息元的个数，n为码长。 对纠错码的基本要求是: 检错和纠错能力尽量强； 编码效率尽量高；编码规律尽量简单。 际中要根据具体指标要求， 保证有一定纠、 检错能力和编码效率，并且易于实现。 （10-1）

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

17 设码字A=［an-1,an-2,…,a1,a0］，对偶监督码有
(10-2) 奇监督码情况相似， 只是码组中“1”的数目为奇数， 即满足条件 (10-3) 而检错能力与偶监督码相同。 奇偶监督码的编码效率R为

18 10.3.2　水平奇偶监督码 为了提高奇偶监督码的检错能力，特别是克服其不能检测突发错误的缺点，可以将经过奇偶监督的码元序列按行排成方阵，每行为一组奇偶监督码，如表10-1所示。发送时按 列的顺序传输，接收时仍将码元序列还原为发送时的方阵形式，然后按行进行奇偶校验。

19 表10-1水平奇偶监督码

20 行列监督码 奇偶监督码不能发现偶数个错误。为了改善这种情况，引入行列监督码。这种码不仅对水平(行)方向的码元，而且对垂直(列)方向的码元实施奇偶监督。这种码既可以逐行传输，也可以逐列传输。一般地，L×M个信息元附加L+M+1个监督元，组成(LM+L+M+1,LM)行列监督码的一个码字(L+1行，M+1列)。图 是(66,50)行列监督码的一个码字。 这种码具有较强的检测能力，适于检测突发错误，还可用于纠错。

21 表10-2 (66,50)行列监督码

22 10.3.4群计数码 把信息码元中“1”的个数用二进制数字表示，并作为监督码元放在信息码元的后面，这样构成的码称为群计数码。例如，一码组的信息码元为 ，其中“1”的个数为5，用二进制数字表示为“101”，将它作为监督码元附加在信息码元之后，即传输的码组为 101。群计数码有较强的检错能力，除了同时出现码组中“1”变“0”和“0”变“1”的成对错误外，它能纠正所有形式的错误。

23 恒比码 码字中 1 的数目与 0 的数目保持恒定比例的码称为恒比码。 由于恒比码中，每个码组均含有相同数目的 1 和 0，因此恒比码又称等重码，定 1 码。这种码在检测时，只要计算接收码元中 1 的数目是否正确，就知道有无错误。  目前我国电传通信中普遍采用 3∶2 码，又称“5 中取 3”的恒比码，即每个码组的长度为 5，其中 3 个“1”。这时可能编成的不同码组数目等于从 5 中取 3 的组合数 10，这 10 个许用码组恰好可表示 10 个阿拉伯数字，如表 所示。而每个汉字又是以四位十进制数来代表的。实践证明，采用这种码后，我国汉字电报的差错率大为降低。

24 表 ∶2 恒比码

25 10.4 线 性 分 组 码 10.4.1基本概念 在(n,k)分组码中，若每一个监督元都是码组中某些信息元按模二加而得到的，即监督元是按线性关系相加而得到的，则称为线性分组码。或者说，可用线性方程组表述码规律性的分组码称为线性分组码。线性分组码是一类重要的纠错码，应用很广泛。现以（7，3）分组码为例说明线性分组码的意义和特点。

26 现以(7,4)分组码为例来说明线性分组码的特点。设其码字为A=［a6 a5 a4 a3 a2 a1 a0］，其中前 4 位是信息元，后 3 位是监督元， 可用下列线性方程组来描述该分组码，产生监督元。
(10-４)

27 表10-4（7，3）分组码的八个码字

28 　　我们可以把(n，k)线性分组码看成一个n维线性空间，每一个码字就是这个空间的一个矢量。n维线性空间长度为n的码组共有2n个，但线性分组码的码字共有2k个，k<n。显然，这2k个分组码构成了n维线性空间的K维线性子空间，它是线性分组码的许用码组，剩余的空间构成的码组是禁用码组。

29 10.4.2汉明(Hamming)码 　　汉明码是一种用来纠正单个错误的线性分组码，已作为差错控制码广泛用于数字通信和数据存储系统中。 　　一般来说，若码长为n，信息位为k，则监督元为r=n-k。如果求用r个监督位构造出r个监督方程能纠正一位或一位以上错误的线性码，则必须有 2r-1≥n （10-5） 现以(n,k)汉明码为例来说明线性分组码的特点。

30 　　在前面讨论奇偶监督码时，如考虑偶监督，则用式（10-2）作为监督方程，而在接收端译码时，实际是按下式计算的：
(10-6) 若S=0，就认为无错；若S=1，就认为有错，我们称上式为监督方程，S校正子（校验子），又称伴随式。如果增加一位监督元，就可以写出两个监督方程，计算出两个校正子S1和S2。S1S2为00时，表示无错；S1S2为01、10、11时，指示3种不同的错误图样。由此可见，若有r位监督元，就可以构成r个监督方程，计算得到的校正子有r位，可用来指示2r-1种不同的错误图样，r位校正子为全零时，表示无错。

31 　　设分组码中信息位k=4，又假设该码能纠正一位错码，这时d0≥3，要满足2r-1≥n，取r≤3时，当r=3时，n=k+r=7，这样就构成了（7，4）汉明码。这里用A=［a6 a5 a4 a3 a2 a1 a0］表示码字，其中前4位是信息元，后3位是监督元，用S1，S2，S3表示由3个监督方程得到的3个校正子。3个校正子S1，S2，S3指示23-1种不同的错误图样，校正子与错码位置的对应关系如表10-5所示。 　　

32 表10-5 校正子与错码位置的对应关系

33 　　由表10-5可知，校正子S1为1的错码位置为a2，a4，a5，a6；校正子S2为1的错码位置为a1，a3，a5，a6；校正子S3为1的错码位置为a0，a3，a4，a6。这样，我们可以写出3个监督方程，即 （10-7） （10-8） （10-9）

34 　在发送端编码时，a6，a5，a4，a3为信息元，由传输的信息决定；而监督元a2，a1，a0则由监督方程（10-7），（10-8），（10-9）来决定，当3个校正子S1，S2，S3均为0时，编码组中无错码发生，于是有下列方程组 （10-10）

35 由上式可以求得监督元a2，a1，a0为 （10-11） 已知信息元a6，a5，a4，a3，就可以直接由上式计算出监督元a2，a1，a0。由此得到（7，4）汉明码的16个许用码组如表10-6所示。

36 表10-6　(7,4)汉明码的16个许用码组

37 　在接收端收到每组码后，按监督方程（10-7），（10-8），（10-9）计算出S1，S2和S3，如不全为0，则可按表10-5确定误码的位置，然后加以纠正。
　　汉明码有较高的编码效率，其编码效率为 　

38 监督矩阵 　　不难看出，上述(7，4)码的最小码距d0=3，它能纠正一个错误或检测两个错误。将式(10-10)所述(7,4)汉明码的3个监督方程式可以改写成线性方程组如下 (10-12)

39 这组线性方程可用矩阵形式表示为 (10-13)   并简记为 (10-14)

40 其中，AT是A的转置，0T是0=［0 0 0］的转置，HT是H的转置。
(10-15) H称为监督矩阵，一旦H给定，信息位和监督位之间的关系也就确定了。H为r×n阶矩阵，H矩阵每行之间是彼此线性无关的。式(10-7)所示的H矩阵可分成两部分

41 (10-16) 其中,P为r×k阶矩阵，Ir为r×r阶单位矩阵。可以写成H=［P Ir］形式的矩阵称为典型监督矩阵。 HAT=0T，说明H矩阵与码字的转置乘积必为零，可以用来作为判断接收码字A是否出错的依据。

42 生成矩阵 若把监督方程补充为下列方程 (10-17)

43 可改写为矩阵形式 (10-18) 即 (10-19)

44 变换为 其中, (10-20) 称为生成矩阵，由G和信息组就可以产生全部码字。G为k×n阶矩阵，各行也是线性无关的。生成矩阵也可以分为两部分，即 (10-21)

45 其中 (10-22) Q为k×r阶矩阵,Ik为k阶单位阵。可以写成式(10-13)形式的G矩阵，称为典型生成矩阵。非典型形式的矩阵经过运算也一定可以化为典型矩阵形式。

46 校正子和检错 设发送码组A=［an-1,an-2,…,a1,a0］，在传输过程中可能发生误码。接收码组B=［bn-1,bn-2,…,b1,b0］，则收发码组之差定义为错误图样E， 也称为误差矢量， 即 (10 -23) 其中E=［en-1,en-2,…,e1,e0］，且 当bi=ai (10 -24) 当bi≠ai

47 式(10-23)也可写作 (10-25) 令S=BHT，称为伴随式或校正子。 (10-26) 由此可见，伴随式S与错误图样E之间有确定的线性变换关系。接收端译码器的任务就是从伴随式确定错误图样，然后从接收到的码字中减去错误图样。

48 表10-7 (7,4)码S与E的对应关系

49 Ai+Ai= A0 10.4.6线性分组码的性质 线性分组码是一种群码，对于模二加运算，其性质满足以下几条：
　　线性分组码是一种群码，对于模二加运算，其性质满足以下几条： 　　(1)有封闭性。所谓封闭性是指群码中任意两个许用码组之和仍为一许用码组，这种性质也称为自闭率。 　　(2)有零码。所有信息元和监督元均为零的码组，称为零码，即A0=［00…0］。任一码组与零码相运算其值不变，即 Ai+Ai= A0

50 A2+A3=A3+A2 d0=Wmin(Ai) Ai∈ [n,k],i≠ 0 (4)满足结合律。即
（A1+A2）+A3=A1+（A2+A3） (5)满足交换律。即 A2+A3=A3+A2 　　(6)最小码距等于线性分组码中非全零码组的最小重量。线性分组码的封闭性表明，码组集中任意两个码组模二相加所得的码组一定在该码组集中，因而两个码组之间的距离必是另一码组的重量。所以，码的最小距离也就是码的最小重量，即 d0=Wmin(Ai) 　 Ai∈ [n,k],i≠ 0

51 （1）d(A1，A2)≤W(A1)+W(A2); （2）d(A1，A2)+d(A2，A3)≥d(A1，A3);
线性分组码还具有以下特点: （1）d(A1，A2)≤W(A1)+W(A2); （2）d(A1，A2)+d(A2，A3)≥d(A1，A3); 　（3）码字的重量全部为偶数，或者奇数重量的码字数等于偶数重量的码字数。

52 10.5　循环码 10.5.1循环特性 循环码的前k位为信息码，后r位为监督码元，它除了具有线性码的一般性质外，还具有循环性，即循环码组中任一码组循环移位所得的码组仍为一个许用码组。表10-8中给出了一种(7,3)循环码的全部码组。 在代数理论中，为了便于计算，常用码多项式表示码字。 (n,k)循环码的码字，其码多项式(以降幂顺序排列)为 (10-27)

53 表10-8 (7,3)循环码的全部

54 A4(x)=4•x4+4•x4+4•x4+1•x3+0•x2+1•x+1•x0 =x6+x3+x+1
表10-8中第4组码字可用多项式表示为 A4(x)=4•x4+4•x4+4•x4+1•x3+0•x2+1•x+1•x0 =x6+x3+x+1 在循环码中，若A(x)是一个长为n的许用码组，则xi•A(x)在按模xn+1运算下，也是一个许用码组。也就是说：一个长为n的(n，k)分组码，它必定是按模xn+1运算的一个余式。

55 10.5.2生成多项式与生成矩阵 　如果一种码的所有码多项式都是多项式g(x)的倍式，则称g(x)为该码的生成多项式。在(n,k)循环码中，任意一个码多项式A(x)都是最低次码多项式的倍式。 　　因此，循环码中次数最低的多项式(全0码字除外)就是生成多项式g(x)。可以证明，g(x)是常数项为1的r=n-k次多项式，是xn+1的一个因式。

56 循环码的生成矩阵常用多项式的形式来表示：
(10-28) 其中, (10-29)

57 g(x)=A2(x)=x4+x2+x+1 例如(7,3)循环码，n=7, k=3, r=4, 其生成多项式及生成矩阵分别为 即
（10-30） （10-31）

58 A=MG 将上式变换为典型的生成矩阵（将矩阵中第一行与第三行模二相加后取代第一行），可得到 （10-32）
将信息元与生成矩阵相乘就可以得到全部码组，即 A=MG (10-33)

59 (10-34) 由此可见，任一循环码A(x)都是g(x)的倍数，即都可以被g(x)整除，而且任一次数不大于（k-1）的多项式乘g(x)都是码多项式。

60 A(x)=xn-k·m(x)+[xn-k·m(x)]'
公式(10-34)实际上可以表示为 A(x)=m(x) g(x) 其中，m(x)为信息组多项式，其最高次数为k-1。一般而言，知道m(x)和g(x)就可以生成全部码字。但是由式(10-34)直接产生的码字并非系统码，因为信息元和监督元没有分开。只有使用典型生成矩阵并按照式(10-33)得出的码字才是系统码，或者运用代数算法求出系统循环码。由于循环码的所有码多项式都是g(x)的倍数，且最高次数为n-1，因此系统循环码多项式可以表示为 A(x)=xn-k·m(x)+[xn-k·m(x)]' (10-35)

61 xn+1=(x+1)(x3+x2+1)(x3+x+1)
上述(7,3)循环码的生成多项式g(x)是xn+1的一个n-k=4的一个因式，因为 xn+1=(x+1)(x3+x2+1)(x3+x+1) 所以n-k=4的因式有两个： (x+1) (x3+x2+1)=x4+x2+x+1 （10-36） (x+1) (x3+x+1)= x4+x3+x2+1 （10-37)

62 　　以上两式都可以作为码生成多项式g(x)。选用的生成多项式不同，产生的循环码的码组也不同。这里的(7,3)循环码对应的码生成多项式g(x)是式（10-36），所产生的循环码就是表10-8列出的码。

63 监督多项式及监督矩阵 为了便于对循环码编译码，通常还定义监督多项式， 令 (10-38) 其中g(x)是常数项为 1 的r次多项式，是生成多项式；h(x)是常数项为 1 的k次多项式，称为监督多项式。同理，可得监督矩阵H (10-39)

64 其中 (10-24) 是h(x)的逆多项式。例如(7，3)循环码， 则

65 即

66 编码方法 在编码时，首先要根据给定的(n,k)值选定生成多项式g(x)，即应在xn+1的因式中选一r=n-k次多项式作为g(x)。设编码前的信息多项式m(x)为 (10-25)

67 m(x)的最高幂次为k-1。循环码中的所有码多项式都可被g(x)整除，根据这条原则，就可以对给定的信息进行编码。用xr乘m(x)，得到xr·m(x)的次数小于n。用g(x)去除xr·m(x)，得到余式R(x), R(x)的次数必小于g(x)的次数，即小于(n-k)。将此余式加于信息位之后作为监督位，即将R(x)与xrm(x)相加， 得到的多项式必为一码多项式，因为它必能被g(x)整除，且商的次数不大于(k-1)。循环码的码多项式可表示为 (10-41) 其中，xr·m(x)代表信息位，R(x)是xr·m(x)与g(x)相除得到的余式，代表监督位。

68 编码电路的主体由生成多项式构成的除法电路， 再加上适当的控制电路组成。g(x)=x4+x3+x2+1 时，(7,3)循环码的编码电路如图 10-2所示。
图 10-2(7,3)循环码编码电路

69 g(x)的次数等于移位寄存器的级数；g(x)的x0,x1,x2, …、 xr的非零系数对应移位寄存器的反馈抽头。首先，移位寄存器清零，3 位信息元输入时，门1断开, 门2接通，直接输出信息元。第 3 次移位脉冲到来时将除法电路运算所得的余数存入移位寄存器。 第 4～7 次移位时，门2断开，门1接通，输出监督元。具体编码过程如表 10-5 所示， 此时输入信息元为 1 1 0。

70 表10-9 (7,3)循环码的编码过程

71 译码方法 接收端译码的目的是检错和纠错。 由于任一码多项式A(x)都应能被生成多项式g(x)整除，所以在接收端可以将接收码组B(x)用生成多项式去除。当传输中未发生错误时，接收码组和发送码组相同，即A(x)=B(x)，故接收码组B(x)必定能被g(x)整除。 若码组在传输中发生错误，则B(x)≠A(x)，B(x)除以g(x)时除不尽而有余项，所以，可以用余项是否为0来判别码组中有无误码。在接收端采用译码方法来纠错自然比检错更复杂。同样，为了能够纠错，要求每个可纠正的错误图样必须与一个特定余式有一一对应关系。

72 (a)循环码译码示意图；(b)(15,11)循环码译码电路
图10-3循环码译码电路 (a)循环码译码示意图；(b)(15,11)循环码译码电路

73 B(x)=bn-1xn-1+bn-1xn-1+…+b1x+b0 E(x)=en-1xn-1+en-1xn-1+…+e1x+e0
在接收端采用译码方法来纠错比检错复杂得多。同样，为了能够纠错，要求每个可纠正的错误图样必须与一个特定余式有一一对应关系。设接收的码组、错误图样及伴随式的多项式为 B(x)=bn-1xn-1+bn-1xn-1+…+b1x+b0 E(x)=en-1xn-1+en-1xn-1+…+e1x+e0 S(x)=sn-1xn-1+sn-1xn-1+…+s1x+s0 可以证明 S(x)=[B(x)]′=[E(x)]′ （10-42）

74 式中，［·］′就是B(x)或E(x)除以g(x)所得的余式。可见，在检错时，根据B(x)或E(x)除以g(x)所得的余式是否为0，可判断接收码组是否有错，S(x)=0时表明B(x)无错；S(x)≠0时表明B(x)有错。 　　用于纠错时，需要根据不同的非零S(x)指明不同的错误位置，从而纠正错误。伴随式S(x)的计算由除法电路来实现。利用式（10-42）可以求得（7，3）循环码单个错误的错型多项式E(x)与伴随式S(x)的对应关系，如表10-10所示。

75 表10-10（7，3）循环码E(x)与S(x)的对应关系

76 　　图10-4中，接收到的B(x)一方面送入七级缓存器，一方面送入g(x)除法电路计算伴随式S(x)。经七次移位后，七位码元全部送入缓存器，这时B(x)中的首位b6输出，同时g(x)除法电路也得到了伴随式S(x)（存放在四个除法电路的移存器里），若首位b6有错，则D1、D2、D3、D4的状态分别为0、1、1、1。经与门输出1（纠错信号）和缓存器模二加即可纠正b6的错误，同时该纠错信号也送到S(x)计算电路去清0。其纠错，即译码过程如表10－11所示（接收的码组是表10-4的A2，第一位出错变为“(1)010111）”。

77 图10-4单个错误出现在接收码组首位时的(7,3)循环码译码电路

78 表10-11　(7,3)循环码的译码过程

79 10.6 卷 积 码 10.6.1卷积码的概念 卷积码的编码器是由一个有k个输入位、n个输出位，且有m节移位寄存器构成的有限状态的有记忆系统，其原理图如图10-5所示。

80 图10-5卷积码的编码器原理图

81 图 10-6 是卷积码(2,1,2)的编码器。它由移位寄存器、 模二加法器及开关电路组成。
图10-6卷积码(2,1,2)的编码器原理图

82 　起始状态各级移位寄存器清零，即D1D2为00。u等于当前输入数据，而移位寄存器状态D1D2存储以前的数据，输出码字Ci由下式确定
当输入数据D=u1, u2,…，ui时，输出码字为(C1C2)1，(C1C2)2，…， (C1C2)i。

83 　　从上述的计算可知，每 1 位数据，影响(m+1)个输出子码，称(m+1)为编码约束度。每个子码有n个码元，在卷积码中有约束关系的最大码元长度则为(m+1)·n, 称为编码约束长度。 (2,1,2)卷积码的编码约束度为 3， 约束长度为 6。

84 表 10-6 (2,1,2)编码器的工作过程

85 　　对于上述卷积码的解码方法可用图10-7来完成。设收到的码序列为，解码器输入端的电子开关按节拍将和分开并分别送上端和下端。3个移存器的节拍比码序列推迟一拍：当到达时，D1D2开始移位，D3保持原态不变；当到达时，D3开始移位，D1D2保持原态不变。移存器D1，D2和模2加电路1构成了与发端一样的编码器，从接收的码序列中计算出C2；模2加法器2与接收到的进行比较，如果两者相同则输出0，否则输出1，表明接收的码有错。移存器D3，与门和模2加法器3共同组成了判决输出电路，如果模2加法器2的输出S（教正子）为0，模2加法器3输出正确码组；如果S为1，表明接收的码有错，与门输出和模2加法器3将接收错码予以纠正，得到正确码组。

86 图10-7卷积码(2,1,2)解码器

87 卷积码的描述 　　1.树状图 　　树状图描述的是在任何数据序列输入时，码字所有可能的输出。有一个(2,1,2)卷积码的编码电路如图10-8所示，可以画出其树状图如图10-9所示。当输入码组为 时，编码器的工作过程如表10-12所示。

88 图10-8(2,1,2)卷积码的编码电路

89 图10-9(2,1,2)卷积码的树状图

90 表10-12 (2,1,2)编码器的工作过程

91 以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; 依次类推， 可得整个树图。输入不同的信息序列，编码器就走不同的路径， 输出不同的码序列。例如，当输入数据为［ ］时， 其路径如图10-10中虚线所示，并得到输出码序列为［ …］，与表 的结果一致。

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

93 图 10 –10 (2,1,2)码的状态图

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

95 图10-11(2,1,2)卷积码的网格图

96 卷积码的译码 1. 维特比译码 维特比译码是一种最大似然译码算法。 最大似然译码算法的基本思路是：把接收码字与所有可能的码字比较，选择一种码距最小的码字作为解码输出。 由于接收序列通常很长，所以维特比译码时最大似然译码做了简化， 即它把接收码字分段累接处理，每接收一段码字，计算、 比较一次， 保留码距最小的路径，直至译完整个序列。

97 现以上述(2，1，2)码为例说明维特比译码过程。 设发送端的信息数据D=［ ］，由编码器输出的码字C=［ ］，接收端接收的码序列B=［ ］，有4位码元差错。下面参照图 10-8 的格状图说明译码过程。 如图10-12所示，先选前 3 个码作为标准，对到达第 3 级的 4 个节点的 8 条路径进行比较， 逐步算出每条路径与接收码字之间的累计码距。累计码距分别用括号内的数字标出，对照后保留一条到达该节点的码距较小的路径作为幸存路径。再将当前节点移到第 4 级，计算、比较、保留幸存路径，直至最后得到到达终点的一条幸存路径，即为解码路径，如图 10-12中实线所示。 根据该路径， 得到解码结果。

98 图10-12维特比译码的网格图

99 2. 序列译码 当m很大时，可以采用序列译码法。 其过程如下： 译码先从码树的起始节点开始，把接收到的第一个子码的n个码元与自始节点出发的两条分支按照最小汉明距离进行比较， 沿着差异最小的分支走向第二个节点。在第二个节点上，译码器仍以同样原理到达下一个节点，以此类推，最后得到一条路径。若接收码组有错，则自某节点开始，译码器就一直在不正确的路径中行进，译码也一直错误。因此，译码器有一个门限值，当接收码元与译码器所走的路径上的码元之间的差异总数超过门限值时，译码器判定有错，并且返回试走另一分支。经数次返回找出一条正确的路径，最后译码输出。