DSP卷积码的维特比译码的分析与实现要点

编号：

《DSP技术与应用》课程论文卷积码的维特比译码的分析与实现

论文作者姓名：______ ______

作者学号：___ ______

所在学院：

所学专业：_____ ___

导师姓名职称：__ _

论文完成时间： _

目录

摘要： (1)

0 前言 (2)

1 理论基础 (2)

1.1信道理论基础 (2)

1.2差错控制技术 (3)

1.3纠错编码 (4)

1.4线性分组码 (5)

2 卷积码编码 (7)

2.1 卷积码概要 (7)

2.2 卷积码编码器 (8)

2.3卷积码的图解表示 (8)

2.4 卷积码的解析表示 (11)

3 卷积码的译码 (14)

3.1 维特比译码 (15)

3.2 代数译码 (17)

3.3 门限译码 (18)

4 维特比译码器实现 (18)

4.1 TMS320C54 系列DSP概述 (18)

4.2 Viterbi译码器的DSP实现 (19)

4.3 实现结果 (21)

5 结论 (21)

参考文献 (22)

II

卷积码的维特比译码的分析与实现

摘要：

针对数据传输过程中的误码问题，本文论述了提高数据传输质量的一些编码及译码的实现问题。自P.Elias 首次提出卷积码编码以来，这一编码技术至今仍显示出强大的生命力。在与分组码同样的码率R 和设备复杂性的条件下，无论从理论上还是从实际上均己证明卷积码的性能至少不比分组码差，且实现最佳和准最佳译码也较分组码容易。目前，卷积码已广泛应用在无线通信标准中，其维特比译码则利用码树的重复性结构，对最大似然译码算法进行了简化。本文所做的主要工作：

首先对信道编码技术进行了研究，根据信道中可能出现的噪声等问题对卷积码编码方法进行了主要阐释。

其次，对卷积码维特比译码器的实现算法进行了研究，完成了译码器的软件设计。

最后，结合实例，采用DSP芯片实现卷积码的维特比译码算法的仿真和运行。

关键词：

卷积码维特比译码DSP

Convolutional codes and Viterbi decoding analysis and

realization

Zhang Yi-Fei

(School of Physics and Electronics, Henan University, Henan Kaifeng 475004, China)

Abstract:

Considering the error bit problem during data transmission,this thesis discussed some codings and decoders,aiming at enhancing transmission performance. From P.Elias first gave the concept of convolutional code, it has show its’ great advantage. Under the same condition and the same rate of block code, the performance of convolutional code is better than block code, and it’s easier to implement the best decoding.Convolutional codes have been widely used in wireless communication standards, the Viterbi decoding using the repetitive structure of the code tree, the maximum likelihood decoding algorithm has been simplified. Major work done in this article: First, the channel coding techniques have been studied, the main interpretation of the convolutional code encoding method according to the channel may be noise and other issues.

Secondly, the convolutional code Viterbi decoder algorithm has been studied, the software design of the decoder.

Finally, with examples, simulation and operation of the DSP chip convolutional codes, Viterbi decoding algorithm.

1

Key words:

convolutional code Vltebri decoder DSP

0 前言

随着数据处理、计算机通信、卫星通信以及高速数据通信网的飞速发展，用户对数据传输的可靠性提出了越来越高的要求，因此如何在保证数据传输速率的前提下，提高传输数据的可靠性，就成为一个迫切需要解决的问题。数字信号在传输过程中不可避免的要受到干扰的影响，因而信息数据会发生误码。

严重时会干扰系统的正常工作。根据干扰对数据传输影响的不同干扰可分为随机干扰和突发干扰。其中，电子热噪声产生的干扰可以看作是随机的高斯白噪声，它对信道主要的影响是产生码元的随机错误。脉冲干扰和同频干扰对信道的影响会产生码元的突发错误，如连续出现多个。或多个I。其他干扰如衰落和多径干扰对信道同时产生随机和突发错误两种影响。

要提高系统数据传输的可靠性，可以在分析其来源的基础上，尽可能对各干扰源采取对应措施使之减小干扰，同时可以改善信道性能，增加接收端的信噪比或是采用抗干扰能力强的调制解调方式。在上述条件己确定时，针对某一特定的通信系统，应分析信道干扰产生的主要原因，有针对性的应用纠错或检错编码以及相应的技术如反馈重传等来提高传输数据可靠性的方法，即在数据传输时进行差错控制。

目前，信道编码的应用几乎遍及数据通信的各个方面，关于信道编码的理论和应用研究也有了新的发展。

1 理论基础

1.1信道理论基础

通信的目的是传输信息。通信系统一般由信源，信道，信宿组成。信道是一种物理媒质，用来将来自发送设备的信号传送到接收端。信道既给信号以通路，也会对信号产生各种干扰和噪声。数字信号在传输的过程中，由于信道传输特性不理想以及加性噪声的影响，导致信号波形失真，接收端会不可避免地产生错误判决。

按照加性干扰引起的错码分布规律的不同，信道可以分为三类，即随机信道、突发信道和混合信道。在随机信道中，错码的出现是随机的，而且错码之间是独立统计的。例如，由高斯白噪声引起的错码就具有这种性质。在突发信道中，错

2

码是成串集中出现的，即在一些短促的时间段内会出现大量错码，而在这些短促的时间段之间存在较长的无错码区间。这种成串出现的错码成为突发错码。产生突发错码的主要原因之一是脉冲干扰，例如电火花产生的干扰。信道中的衰落现象也是产生突发错码的另一个主要原因。既存在随机错码又存在突发错码的信道，成为混合信道。

1.2差错控制技术

针对传输信道的不理想，为提高数字传输可靠性就要考虑到差错控制措施了。它的基本思想是通过对信息序列作某种变换，在信息序列中插入若干由发送信息序列生成，但又不是发送者发出的监督码元，使原来的信息序列产生某种相关性，在接收端就可以利用这种相关性来检查并纠正信息序列在传输中所产生的差错。随着差错控制技术的完善和集成电子技术的发展，这项技术不仅已成功地应用于各种通信系统，而且在计算机，磁记录与存储中的使用也日益广泛。

针对不同类型的信道，差错控制技术主要分为以下四种。

（1）前向纠错（FEC）

发送端对信息码元进行编码处理，使发送的码组具有纠错能力。接收端收到这些码序列之后，通过译码能自动发现并纠正传输中出现的错误。这种方法不需要反向信道，特别适合于只能提供单向信道的场合。由于接收端能自动纠错，不会因为发送端反复重发而延误时间，系统实时性好。这种差错控制方式的主要特点是设备较为复杂。

（2）检错重发（ARQ）

发送端经编码后发出能够检错的码组，接收端收到后如果检测出错误，则通过反向信道通知发送端重发，直至接收端确认收到正确信息为止。所谓检测出错误，是指发现某个或某些接收码元有错，但不一定知道错码的准确位置。这种方式也需要使用反向信道，而且实时性较差。常见的检错重发系统有三种：停发等候重发、返回重发和选择重发。

（3）反馈校验（IRQ）

接收端将收到的信息码元原封不动地转发回发送端，并与发送的码元相比较。如果发现错误，发送端再进行重发。这种方法的原理和设备都比较简单，无需检错和纠错编译系统，但要使用反向信道。由于每个信息码元至少要被传送两次，所以传输效率低，实时性差。

（4）混合纠错（HEC）

3

混合纠错方式是前向纠错方式和检错重发方式的结合。发送端经过编码后发出的码组不但能够检测错误还具有一定的纠错能力。如果接收端收到的码组错误较少，则自动进行纠错；如果错误太多，超出了码的纠错能力但尚未能检测时，接收端通过反向信道请求发送端重发一遍。

1.3纠错编码

差错控制编码，有时也称为信道编码或纠错编码。不同的编码方法，有不同的检错或纠错能力。有的编码方法只能检错，不能纠错。一般说来，付出的代价越大，检（纠）错的能力越强。这里所说的代价，通常用冗余度表示。

1.3.1纠错编码类型

差错控制系统中使用的信道编码种类很多，分类的方式也很多。

（1）根据差错控制编码的功能，可以把信道编码分为检错码，纠错码和纠删码。检错码只能检测错误；纠错码可以纠正错误；纠删码兼具纠错和检错能力，在发现不可纠正的错误时，可以发出错误指示或将其删除。

（2）根据信息码元与附加监督码元之间的关系，可以分为线性码和非线性码。若信息码元与监督码元之间的关系是线性的，即满足一组线性方程，称为线性码；反之，两者若不满足线性关系，则称为非线性码。

（3）根据信息码元与监督码元之间的约束方式，可以分为分组码和卷积码。在分组码中，编码后的码元序列没n位为一组，其中k个是信息码元，r个是附加的监督码元，r=n-k,通常记为（n,k）.分组码的监督码元只与本码组的信息码元有关，它又可分为循环码和非循环码。卷积码则不同，虽然编码后的序列也划分为码组，但监督码元不仅与本码组的信息码元有关，还与前面几个码组有约束关系。

（4）根据信息码元在编码前后是否保持原来的形式不变，可以分为系统码和非系统码。在编码后的码组中，信息码元和监督码元通常都有确定的位置，一般信息码元集中在码组的前k位，而监督码元位于后r位。如果编码前后信息码元保持原样不变，则称为系统码；反之称为非系统码。系统码的性能与非系统码大致相同，但是在某些卷积码中非系统码的性能优于系统码。系统码的编码和译码相对比较简单，因此得到了广泛的应用。

1.3.2常用纠错编码

卷积码和线性分组码是现代数字通信中运用最多、最久、最基本的两种纠错码，从技术的角度看，一个通信系统采用什么样的纠错码，应考虑以下几个方面:

4

5 纠错能力（编码增益）、编码效率、编译码开销（复杂度或可实现性）、编译码延时（实时性）等。

1.4线性分组码

所谓线性分组码，是指信息码元和监督码元之间的关系可以用一组线性方程来表示的分组码。线性码的概念建立在代数学群论的基础上，因此又称群码。

分组码一般用符号（n,k ）表示，其中n 是码组的总位数，又称为码组的长度，k 是码组中信息码元的数目，n-k=r 为码组中的监督码元数目，或称监督位数目。

图1.4.1

在分组码中，吧码组中“1”的个数称为码组的重量，简称码重。把两个码组中对应位上数字不同的位数称为码组的距离，简称码距。码距又称汉明距离。我们把编码中各个码组之间距离的最小值称为最小码距（0d ）。

一种编码的最小码距0d 的大小直接关系着这种编码的检错和纠错能力：

（1）为检测e 个错码，要求最小码距：01d e ≥+

（2）为了纠正t 个错码，要求最小码距：021d t ≥+

（3）为纠正t 个错码，同时检测e 个错码，要求最小码距：01d e t ≥++ 奇偶监督码就是一种简单的线性分组码，例如在偶校验是，它的信息码元11...n a a -和监督码元0a 满足以下线性关系：

()120...0mod2n n a a a --+++=（1.4.1）

上式表示采用偶校验时的监督关系，称为监督方程式。接收时为了检查传输过程中是否出现错误，需要将所有码元的模2加再计算一遍，即：

120...n n s a a a --=+++ （1.4.2）

式中，s 被称为校正子或伴随式。如果s=0表示接收码组正确；如果s=1表

6

示出现误码。由于只有1位监督码元，随意只能表示有错和无错两种情况，而不能指出错码的位置。

如果有r 个监督位，就有r 个监督方程式，这是校正子则有2r

中组合，其中

1种表示没有错码，其余21r -种组合可以用来指示1位错码的21r -个可能位置。对于码长为n ，信息码元数为k 的分组码（n,k ）来说，如果希望用r=n-k 个监督位构造出r 个监督方程来指示1位错码的n 种可能位置，从而能纠正错误，则要求

21r n -≥或21r k r ≥++（1.4.3）

下面通过一个例子来具体说明如何构造这种线性分组码。设分组码（n,k ）中k=4，若要能纠正1位错码，要求监督码元数3r ≥。现取r=3，则n=k+r=7。我们用6543210a a a a a a a 表示这7个码元，其中210a a a 是监督位。设1s ，2s 和3s 分别表示与3个监督方程式对应的校正子，而且123s s s 构成的校正子码组与误码位置的关系如下表

由上表推出，1s ，2s 和3s 与7个码元6543210a a a a a a a 的逻辑关系式分别为

16542

2653136430

s a a a a s a a a a s a a a a =+++=+++=+++ （1.4.5）

编码时使用的监督方程式对应123s s s =000的无误码情况，即

6542653164300

00

a a a a a a a a a a a a +++=+++=+++= （1.4.6）

利用以上方程，可以得到计算监督码元2a ，1a 和0a 的关系式分别为

7 2654

16530643

a a a a a a a a a a a a =++=++=++ （1.4.7）

信息码元给定之后，直接按上式求出对应的监督码元，可得到（7,4）码的16个准用码组如表

接收端收到每个码组后，计算1s ，3s 和3s ，按照123s s s 的值确定有无误码以及误码的位置，比予以纠正。例如接收码组为“1101011”时，123s s s =001，由表

1.4.1可知在位置0a 上出现误码，正确码组应该是“1101010”。可以看出，这种

（7,4）码的最小码距min 3d =，

它能纠正1位错误或检测两位错误。错误数再多，则无法检测或出现错纠。

2 卷积码编码

2.1 卷积码概要

卷积码是1955年由麻省理工学院的伊利亚斯（P.Elias ）提出来的，它与前面讨论的分组码不同，属于非分组码。通常，为了达到一定的纠/检错能力和编码效率，分组码的码长较大。由于编译码时必须把整个码组存储起来，因此处理产生的延时随码长的增加而线性增大。而卷积码的信息码元个数k 和码长n 通常较小，故延时小，特别适合于以串行形式传输信息的场合。与分组码相比，不仅与k 个信息码元有关，而且与前面N-1段的信息码元有关。

2.2 卷积码编码器

图2.2.1

卷积码编码器的一般形式如图2.2.1所示，它包括:一个由N段组成的输入移位寄存器，每段有k级，共Nk位寄存器；一组n个模2和相加器；一个由n 级组成的输出移位寄存器。对应于每段k个比特的输入序列，输出n个比特。由图可知，n个输出比特不但与当前的k个输入比特有关，而且与以前的困一1k)个输入信息比特有关。整个编码过程可以看成是输入信息序列与由移位寄存器和模2和连接方式所决定的另一个序列的卷积，卷积码积由此得名。通常把N称为约束长度。常把卷积码记作n(，k，N)，它的编码效率为R=k/n。

2.3卷积码的图解表示

下面以图2.3.1所示(2，1，3)卷积编码器为例加以说明。

图2.3.1

8

9 2.3.1树状图

对于图2.3.1所示的(2，1，3)卷积码编码电路，其树状图如2.3.2所示。这里，分别用abc 和d 表示寄存器1m ，2m 的4种状态:00，01，10，和11，作为树状图中每条支路的节点。以全零状态a 为起点，当地第1位信息10b =时，输出码元1200c c =，寄存器保持状态a 不变，对应图中从起点出发的上支路;当11b =时，输出码元1211c c =，寄存器则转移到状态b ，对应图中的下支路;然后再分别以这两条支路的终节点a 和b 作为处理下一位输入信息2b 的起点，从而得到4条支路。以此类推，可以得到整个树状图。显然，对于第i 个输入信息比特，途中将会出现2i

条支路。单从第4位信息开始，树状图的上半部和下半部完全相同，这意味着此时的输出码元已和第1位信息无关，由此可以看出把卷积码的约束长度定义为N

一1的意义。

图2.3.2

2.3.2 网格图

利用树状图中观察到的重复性，把其中相同状态的节点合并到一起，可以得到一种更为紧凑的图形，即网格图。这种图仍由节点和支路组成，4行节点分别表示.a，b，c，d4种状态;支路则代表了状态之间的转移关系，其中实线支路代表输入信号为“0”，虚线支路代表输入信息为“1”，支路上标注的码元为当前输

2k N-种状态，从第N节开始图形同样会出现重复。出。一般情况下，网格图应有(1)

图2.3.3

2.3.3状态图

取出已经达到稳定状态的一节网络，便得到图3一5()a形式的状态图。如果再把相同的当前状态和下一状态重叠起来，就得到图3一5b()形式的状态转移图。

2k N-种可能状态(节点)，每个节点会引出2“条支显然，状态图也应该有(1)

路，

同时也会有2k条来自其他节点或本节点的支路到达。

10

11

图2.3.4

2.4 卷积码的解析表示

2.4.1 生成多项式

我们可以用延时算子D 构成的多项式来表示卷积编码器中各级移存器与模2加之间的连接关系。如果某级寄存器与模2加项链，对应的系数为1；反之则为0.以上述卷积码为例，图2.3.1所示的编码器结构可以用以下两式描述：

()()2

12211G D D D G D D =++=+(2.4.1)

其中，变量D 的幂次等于该级寄存器相对于时间起点的单位延时数。在卷积码中，通常把表示移位寄存器与模2加连接关系的多项式称为生成多项式。有时还可以用二进制或八进制的生成序列来表示生成多项式，即

()()()

()()()2112221111711015G D D D g G D D g =++?===+?==（2.4.2）

同理，也可以用延时算子D 的多项式来表示编码器的输入和输出序列。例如，输入序列“110111”可以表示为

()3451...b D D D D D =+++++(2.4.3)

其中，变量D 的幂次等于该级寄存器相对于时间起点的单位延时数，时间起点则通常选在第一位比特上。

卷积编码器的输出序列可以根据生成多项式和输入信息序列的乘积算出。例如，输入序列为“110111”时，可得输出序列的D 算子多项式为

12

()()()

()()1123455711...1...

c D G D b D D D D D D D D D =?=+++++++=+++(2.4.4)

()()()

()()22234524611...1...

c D G D b D D D D D D D D D D =?=++++++=+++++(2.4.5)

由此，输出序列

()()()11,11,21,322,12,22,31,12,11,22,21,32,3,,,...100001...

,,,...111010...

,,,,,,...110101000110...c c c c c c c c c c c c c c c ======（2.4.6）

2.4.2 生成矩阵

卷积码不是分组码，但是从生成多项式的描述可以看出，它仍属于线性码，同样可由生成矩阵G 或监督矩阵H 所完全确定。

仍以上述卷积码为例，设编码器的起始状态为全零，则输出序列{}

1,2,,i i c c c =与输入信息序列{}i b 之间的关系如下所示：

1,11

2,111,2212,221,33212,3311,122,2i i i i i i i c b c b c b b c b c b b b c b b c b b b c b b ---=??=??=+?=?

?=++??=+??????=++?

?=+??????

（2.4.7） 写成矩阵形式为

13 ()()1,12,11,22,21,2,12111011001110110000111011............111011...1110...11......i i i c c c c c c b b b ?? ? ? ? ?= ? ? ? ? ???

（2.4.8）

所以，该码的生成矩阵G 就是上式最右边的矩阵

111011001110110000111011111011...1110...11......G ?? ? ? ? ?= ? ? ? ? ???

（2.4.9）

可以看出，生成矩阵G 是一个半无限矩阵，每一行的结构相同，只是下一行比上一行向右移动了2位，而且前3行就已代表了卷积码的全部特征，故得截短生成矩阵

'111011001110000011G ?? ?= ? ???

(2.4.10)

生成矩阵和生成多项式之间存在确定的关系。式（2.4.2）中已经给出了卷积码的生成序列为

()()

()()12311111

232222111101g g g g g g g g ====（2.4.11）

比较式（2.4.9）和（2.4.11），可以发现两者之间的关系为

14

112233121212112233121212112223121212123123123............g g g g g g g g g g g g G g g g g g g G G G G G G G G G ?? ?

?= ? ? ??

??? ? ?= ? ???(2.4.12)

其中，每个子矩阵(1,2,3)i G i =由一行两列组成，即

()()()112233112212312,,G g g G g g G g g ===

推广到一般情况，对于（n,k,N ）卷积码，如果其生成序列的一般表达式为

()12,,,,,......l N i j i j i j i j i j g g g g g =（2.4.13）

其中，1,2,...,;1,2,...,i k j n ==。那么对应的生成矩阵一般形式为

121212..................N N N G G G G G G G G G G ?? ? ?= ? ???

(2.4.14) 其中，(1,2,...,)l G l N =为k 行n 列子矩阵，即

1,11,21,2,12,22,,1,2,.........l l l n l l l n l l l l k k k n g g g g g g G g g g ?? ? ?= ? ? ???

（2.4.15） 卷积码的解析和图解表示方法各有特点。用延时算子和生成序列表示卷积码的生成多项式最为方便；网格图则在分析卷积码的译码算法时非常有用；状态图表明卷积码编码器是一种有限状态的马尔科夫过程，因而可以用信号流图理论来分析卷积码的结构及其性能。

3 卷积码的译码

卷积码的译码方式可以分为两大类：代数译码和概率译码。代数译码时利用编码本身的代数结构进行解码，不考虑信道的统计特性。大数逻辑译码，又称门

15 限译码，是卷积码代数译码的最主要的一种方式。大数逻辑译码对于约束长度较短的卷积码最为有效，而且设备较简单。概率译码（又称最大似然译码）则是基于信道的统计特性和卷积码的特点进行计算。首先由沃曾克拉夫特针对无记忆信道提出的序贯译码就是概率译码方式之一；另一种概率译码方式是维特比算法。当妈的约束长度较短时，它比序贯译码算法的效率更高，速度更快，目前得到广泛的应用。

3.1 维特比译码

维特比译码算法是由维特比在 1967 年提出的，其实质是最大似然译码，但利用了编码网格图的特殊结构，从而降低了计算的复杂性，与完全比较译码相比，它的优点是使得译码器的复杂性不再是码字序列中所含码元数的函数。该算法包括计算网格图上在时刻i t 到达各个状态的路径和接收序列之间的相似度，或者说距离。维特比算法考虑的是，去除不可能成为最大似然选择对象的网格图上的路径，即，如果有两条路径到达同一状态，则具有最佳量度的路径被选中，成为幸存路径。对所有状态都将进行这样的选路操作，译码器不断在网格图上深入，通过去除可能性最小的路径实现判决。较早地抛弃不可能的路径降低了译码器的复杂性。Omura 在 1969 年证明了维特比算法实际上就是最大似然算法。注意，选择最优路径可以表述为选择具有最大似然量度的码字，或者选择具有最小距离的码字。

维特比（Viterbi ）卷积译码步骤及其特点：接收一段，比较、计算一段，尽早舍弃非最佳路径。

（1）丢弃网格图上不可能成为最大似然选择对象的路径；

（2）如果有两条路径到达同一状态，则具有最佳度量的路径被选中，称为幸存路径（surviving path ）；

（3）最佳度量采用汉明距离。

对于（2，1，3）的卷积码来说，设输入码序列 M 为：

()12,,...,,...,,0,0,...,0i l M m m m m =

其中i m 是k 个比特的输入码字，信息序列的周期长度为L ×k ，0代表k 个比特的0，附加在有用的信息码字之后，(K-1)组共有（K-1) ×k 个0，使译码器归到全零状态。

加0的目的：使信息序列能分帧传输，接收序列也能分帧译码。

译码器网格图如下

图3.1.1

译码步骤为：从状态 a 开始，对于某一时间单位t=

t，(j=1，2，…)，计

j

算进入每一个状态的部分路径与接收码字Z 之间的度量（距离）；j 增加1，计算此时刻进入各状态的部分路径度量，并挑选出一条度量值最佳的路径，作为幸存路径；如果j

幸存路径选择如下图：

16

图3.1.2

通过路径合并，可以保证路径数不会超过状态数。在每次删减之后，都只有4 条路径。随着周期性的加入0 比特，可以使路径逐渐减少，最后得到一条译码路径。

3.2 代数译码

代数译码是从码字本身的代数结构出发，不考虑信道统计特性，在每次的计算循环之内，可全部译出一个码的支路。

在信道传输中码字产生了错误，如果错误图样是已知的，则一定满足R C E

=+.(R为接收码元序列，C为发送码元序列，E为误码序列)根据码元信息位与监督位的关系，一个接收的码字有没有错误可以用监督矩阵H来检验，，R、

C、E之间有如下关系式

17

18

()T

T T T HR H C E HC HE =+=+(3.2.1)

因为C 是一个码字，所以有0T T HC =，则T T HR HE =。令T T S HE =或

T S EH =，称S 为伴随式或校验子。

当0T S EH ==时，则[]R C ∈判无错。

当0T S EH =≠时，则[]R C ?判有错。

因此可以利用伴随式S 的内容对接收序列进行检错和纠错。伴随式与信道所产生的错误图样有关，而与发送的是哪一个码字无关。任何一个错误图样都可由公式(3.2.1)算出相应的伴随式。译码器的任务就是根据伴随式来确定错误图样，得到最可能发送的码字C=R+E 。适用于代数译码的卷积码是具有快检特性的系统卷积码。代数译码方法很多，且各有特点和使用场合，常用的有门限译码法。

3.3 门限译码

对分组码适用的门限译码、或大数逻辑译码也可适用于卷积码。因此卷积码的门限译码与分组码的门限译码是完全相同的。门限译码可以用比较简单的设备获得1至3dB 的编码增益。

卷积码的门限译码基于正交一致校验和的概念。任何伴随比特或伴随比特的和可以表示成一致校验和。若接收序列是一码字，则信道错误序列也是码字，所有伴随比特，因而所有校验比特的和必为0，否则某些校验和将不为零。选择码生成式时将一组J 个正交估计{}k A 进行简单的大数表决，并由此解出判断一个差错符号的一致校验方程式，一个或更多的伴随式符号相加，可以得到估计{}k A 。门限译码相对于卷积码的概率译码来说其对给定的信息组的最终判决只根据接

收组的一个约束长度作出。 4 维特比译码器实现

4.1 TMS320C54 系列DSP 概述

C54 系列 DSP 具有很高的操作灵活性和速度。它具有先进的修正哈佛结构（一条程序总线、三条数据总线、和四条地址总线）、专门硬件逻辑的 CPU 、片内存储器、片内外设和专用的指令集、将 C54 系列 DSP 的 CPU 和片内存储器与外设配置组合在一起的螺旋结构，使它可满足电子市场众多领域的应用要求。C54 系列 DSP 具有以下优点：

维特比译码程序

(n,k,N)卷积码的维特比译码算法实现#include #define t_src 0 #define t_des 1 #define t_len 2 #define t_flag 3 #define t_in 4 using namespace std; intmyn=0; intstalen=0; int myg1[10]={0}; int myg2[10]={0}; int stan0[256][2]={0};//输入0时个状态的输出 int stan1[256][2]={0};//输入1时各状态的输出intstachn[256][2]={0};//状态装换表 int path[256][100]={0};//存储路径 intcalpath[256]={0};//存储路径长度 intmyin[24]; //一次处理12次 intmyout[200]; // intmyoutsym=0; intpthsym; intoutfull=0; //决定是否输出 int table1[8]={1,2,4,8,16,32,64,128}; voidchartobits(char ch,int *bits); charbitstochar(int *bits); intcalluj(int a1,int a2,int b1,int b2); voidinitpath(void); voidselpath(int a1,int a2); voidwridata(void); voidviterbit(void); voidwritdataedn(void); voidcreatsta(void); voidmyinput(void); int main(){ myinput(); creatsta(); viterbit(); } voidmyinput(void){ inti,j; cout<<"输入编码的约束长度N:(3>myn;

DSP卷积码的维特比译码的分析与实现

编号： 《DSP技术与应用》课程论文卷积码的维特比译码的分析与实现 论文作者姓名：______ ______ 作者学号：___ ______ 所在学院： 所学专业：_____ ___ 导师姓名职称：__ _ 论文完成时间： _

目录 摘要： (1) 0 前言 (2) 1 理论基础 (2) 1.1信道理论基础 (2) 1.2差错控制技术 (3) 1.3纠错编码 (4) 1.4线性分组码 (5) 2 卷积码编码 (7) 2.1 卷积码概要 (7) 2.2 卷积码编码器 (8) 2.3卷积码的图解表示 (8) 2.4 卷积码的解析表示 (11) 3 卷积码的译码 (14) 3.1 维特比译码 (15) 3.2 代数译码 (17) 3.3 门限译码 (18) 4 维特比译码器实现 (18) 4.1 TMS320C54 系列DSP概述 (18) 4.2 Viterbi译码器的DSP实现 (19) 4.3 实现结果 (21) 5 结论 (21) 参考文献 (22) II

卷积码的维特比译码的分析与实现 摘要： 针对数据传输过程中的误码问题，本文论述了提高数据传输质量的一些编码及译码的实现问题。自P.Elias 首次提出卷积码编码以来，这一编码技术至今仍显示出强大的生命力。在与分组码同样的码率R 和设备复杂性的条件下，无论从理论上还是从实际上均己证明卷积码的性能至少不比分组码差，且实现最佳和准最佳译码也较分组码容易。目前，卷积码已广泛应用在无线通信标准中，其维特比译码则利用码树的重复性结构，对最大似然译码算法进行了简化。本文所做的主要工作： 首先对信道编码技术进行了研究，根据信道中可能出现的噪声等问题对卷积码编码方法进行了主要阐释。 其次，对卷积码维特比译码器的实现算法进行了研究，完成了译码器的软件设计。 最后，结合实例，采用DSP芯片实现卷积码的维特比译码算法的仿真和运行。 关键词： 卷积码维特比译码DSP Convolutional codes and Viterbi decoding analysis and realization Zhang Yi-Fei (School of Physics and Electronics, Henan University, Henan Kaifeng 475004, China) Abstract: Considering the error bit problem during data transmission,this thesis discussed some codings and decoders,aiming at enhancing transmission performance. From P.Elias first gave the concept of convolutional code, it has show its’ great advantage. Under the same condition and the same rate of block code, the performance of convolutional code is better than block code, and it’s easier to implement the best decoding.Convolutional codes have been widely used in wireless communication standards, the V iterbi decoding using the repetitive structure of the code tree, the maximum likelihood decoding algorithm has been simplified. Major work done in this article: First, the channel coding techniques have been studied, the main interpretation of the convolutional code encoding method according to the channel may be noise and other issues. Secondly, the convolutional code V iterbi decoder algorithm has been studied, the software design of the decoder. Finally, with examples, simulation and operation of the DSP chip convolutional codes, Viterbi decoding algorithm. 1

卷积码编码和维特比译码

卷积码编码维特比译码实验设计报告 SUN 一、实验目的 掌握卷积码编码和维特比译码的基本原理，利用了卷积码的特性, 运用网格图和回溯以得到译码输出。 二、实验原理 1.卷积码是由连续输入的信息序列得到连续输出的已编码序列。其编码器将k个信息码元编为n个码元时，这n个码元不仅与当前段的k个信息有关，而且与前面的（m-1）段信息有关（m为编码的约束长度）。 2.一般地，最小距离d表明了卷积码在连续m段以内的距离特性，该码可以在m个连续码流内纠正(d-1)/2个错误。卷积码的纠错能力不仅与约束长度有关，还与采用的译码方式有关。 3. 维特比译码算法基本原理是将接收到的信号序列和所有可能的发送信号序列比较，选择其中汉明距离最小的序列认为是当前发送序列。卷积码的Viterbi 译码是根据接收码字序列寻找编码时通过网格图最佳路径的过程,找到最佳路径即完成了译码过程,并可以纠正接收码字中的错误比特。 4.所谓“最佳”, 是指最大后验条件概率:P( C/ R) = max [ P ( Cj/ R) ] , 一般来说, 信道模型并不使用后验条件概率,因此利用Beyes 公式、根据信道特性出结论:max[ P ( Cj/ R) ]与max[ P ( R/ Cj) ]等价。考虑到在系统实现中往往采用对数形式的运算,以求降低运算量,并且为求运算值为整数加入了修正因子a1 、a2 。令M ( R/ Cj) = log[ P ( R/ Cj) ] =Σa1 (log[ P( Rm/ Cmj ) ] + a2) 。其中, M 是组成序列的码字的个数。因此寻找最佳路径, 就变成寻找最大M( R/ Cj) , M( R/ Cj) 称为Cj 的分支路径量度,含义为发送Cj 而接收码元为R的似然度。 5.卷积码的viterbi译码是根据接收码字序列寻找编码时通过网格图最佳路径的过程，找到最佳路径即完成了译码过程并可以纠正接收码字中的错误比特。 三、实验代码 #include<> #include "" #define N 7 #include "" #include <> #include<> #define randomize() srand((unsigned)time(NULL)) encode( unsigned int *symbols, /*编码输出*/ unsigned int *data, /*编码输入*/ unsigned int nbytes, /*nbytes=n/16,n为实际输入码字的数目*/ unsigned int startstate /*定义初始化状态*/

Viterbi译码的Matlab实现

2010年12月（上） Viterbi 译码的Matlab 实现 张慧 （盐城卫生职业技术学院，江苏盐城 224006） ［摘要］本文主要介绍了Viterbi 译码是一种最大似然译码算法，是卷积编码的最佳译码算法。本文主要是以（2，1，2）卷积码为例，介 绍了Viterbi 译码的原理和过程，并用Matlab 进行仿真。［关键词］卷积码；Viterbi 译码 1卷积码的类型 卷积码的译码基本上可划分为两大类型：代数译码和概率译码，其中概率译码是实际中最常采用的卷积码译码方法。 2Viterbi 译码 Viterbi 译码是由Viterbi 在1967年提出的一种概率译码，其实质是最大似然译码，是卷积码的最佳译码算法。它利用编码网格图的特殊结构，降低了计算的复杂性。该算法考虑的是，去除不可能成为最大似然选择对象的网格图上的路径，即，如果有两条路径到达同一状态，则具有最佳量度的路径被选中，称为幸存路径（ surviving path ）。对所有状态都将进行这样的选路操作，译码器不断在网格图上深入，通过去除可能性最小的路径实现判决。较早地抛弃不可能的路径降低了译码器的复杂性。 为了更具体的理解Viterbi 译码的过程，我们以（2，1，2）卷积码为例，为简化讨论，假设信道为BSC 信道。译码过程的前几步如下：假定输入数据序列m ，码字U ，接收序列Z ，如图1所示，并假设译码器确知网格图的初始状态。 图１ 时刻t 1接收到的码元是11，从状态00出发只有两种状态转移方向，00和10，如图a 所示。状态转换的分支量度是2；状态转换的分支径量度是0。时刻t 2从每个状态出发都有两种可能的分支，如图b 所示。这些分支的累积量度标识为状态量度┎a ，┎b ，┎c ，┎d ，与各自的结束状态相对应。同样地，图c 中时刻t 3从每个状态出发都有两个分支，因此，时刻时到达每个状态的路径都有两条，这两条路径中，累积路径量度较大的将被舍弃。如果这两条路径的路径量度恰好相等，则任意舍弃其中一条路径。到各个状态的幸存路径如图d 所示。译码过程进行到此时，时刻t 1和t 2之间仅有一条幸存路径，称为公共支（com-mon stem ）。因此这时译码器可以判决时刻t 1和t 2之间的状态转移是00→10；因为这个状态转移是由输入比特1产生的，所以译码器输出1作为第一位译码比特。由此可以看出，用实线表示输入比特0，虚线表示输入比特1，可以为幸存路径译码带来很大的便利。注意，只有当路径量度计算进行到网格图较深处时，才产生第一位译码比特。在典型的译码器实现中，这代表了大约是约束长度5倍的译码延迟。 图２幸存路径选择 在译码过程的每—步，到达每个状态的可能路径总有两条，通过比较路径量度舍弃其中一条。图e 给出了译码过程的下一步：在时刻t 5到达各个状态的路径都有两条，其中一条被舍弃；图f 是时刻t 5的幸存路径。注意，此例中尚不能对第二位输入数据比特做出判决，因为在时刻t 2离开状态10的路径仍为两条。图g 中的时刻t 6同样有路径合并，图h 是时刻t 6的幸存路径，可见编码器输出的第二位译码比特是1，对应了时刻t 2和t 3之间的幸存路径。译码器在网格图上继续上述过程，通过不断舍弃路径直至仅剩一条，来对输入数据比特做出判决。 网格图的删减（通过路径的合并）确保了路径数不会超过状态数。对于此例的情况，可证明在图b 、d 、f 、h 中，每次删减后都只有4条路径。而对于未使用维特比算法的最大似然序列彻底比较法，其可能路径数（代表可能序列数）是序列长度的指数函数。对于分支字长为L 的二进制码字序列，共有2L 种可能的序列。下面我们用Matlab 函数viterbi （G,k,channel_output ）来产生输入序列经Viterbi 译码器得到的输出序列，并将结果与输入卷积码编码器的信息序列进行比较。在这里，G ＝g ，k=k0，channel_output=output 。用Matlab 函数得到的译码输出为10011100110000111，这与我们经过理论分析得出的结果是一致的。 我们用subplot 函数将译码器最终的输出结果与（下转第261页） 250

Viterbi译码的MATLAB仿真研究

BUPT 卷积码编码及Viterbi译码 班级：07114 学号：070422 姓名：吴希龙 指导老师：彭岳星 邮箱：FusionBupt@https://www.doczj.com/doc/2e14332093.html,

1. 序言 卷积码最早于1955年由Elias 提出，稍后，1957年Wozencraft 提出了一种有效地译码方法即序列译码。1963年Massey 提出了一种性能稍差但是比较实用的门限译码方法，使得卷积码开始走向实用化。而后1967年Viterbi 提出了最大似然译码算法，它对存储级数较小的卷积码很容易实现，被称作Viterbi 译码算法，广泛的应用于现代通信中。 2. 卷积码编码及译码原理 2.1 卷积码编码原理 卷积码是一种性能优越的信道编码，它的编码器和解码器都比较易于实现，同时还具有较强的纠错能力，这使得它的使用越来越广泛。卷积码一般表示为(n,k,K)的形式，即将k 各信息比特编码为n 个比特的码组，K 为编码约束长度，说明编码过程中相互约束的码段个数。卷积码编码后的n 各码元不经与当前组的k 个信息比特有关，还与前K-1个输入组的信息比特有关。编码过程中相互关联的码元有K*n 个。R=k/n 是编码效率。编码效率和约束长度是衡量卷积码的两个重要参数。典型的卷积码一般选n,k 较小，但K 值可取较大(>10)，以获得简单而高性能的卷积码。 卷积码的编码描述方式有很多种：冲激响应描述法、生成矩阵描述法、多项式乘积描述法、状态图描述，树图描述，网格图描述等。 2.1.1 卷积码解析表示法 卷积码的解析表示发大致可以分为离散卷积法，生成矩阵法，码多项式法。下面以离散卷积为例进行说明。 卷积码的编码器一般比较简单，为一个具有k 个输入端，n 个输出端，m 级移位寄存器的有限状态有记忆系统。下图所示为(2,1,7)卷积码的编码器。 若输入序列为u =(u 0u 1u 2u 3……), 则对应两个码字序列c ①=(c 0①c 1①c 2①c 3①……)和c ②=(c 0②c 1②c 2②c 3② ……) 相应的编码方程可写为c ①=u ?g ①，c ②=u ?g ②，c=(c ①,c ②)。 “?” 符号表示卷积运算，g ①，g ②表示编码器的两个冲激响应，即编码器的输出可以由输入序列和编码器的两个冲击响应卷积而得到，故称为卷积码。这里的冲激响应指：当输入为[1 0 0 0 0 … … ]序列时，所观察到的两个输出序列值。由于上图K 值为7，故冲激响应至

一种卷积码维特比译码算法的软件实现

一种卷积码维特比译码算法的软件实现Ξ 张海勇1)　刘文予1)　芦东昕2)　吴　畏2) (华中科技大学电子与信息工程系1)　武汉　430074) (中兴通讯股份有限公司2)　深圳　518057) 摘 要 提出了数字通信系统中一种卷积码译码的软件实现方案,该方案应用软件技术实现了卷积码维特比译码器功能,在程序实现中充分利用了卷积码的特性,运用蝶形运算,周期性的回溯以得到译码输出。在程序设计上采用了一些宏定义等处理方法,可以提升运算速度,是一种软件方法的前向纠错编码技术。 关键词:卷积码　维特比译码算法　蝶形运算　回溯 中图分类号:TP31 A Soft w are Implementation of Viterbi Decoding Algorithm Zhang H aiyong1)　Liu Wenyu1)　Lu Dongxin2)　Wu Wei2) (Dept.of Electronics&Information Engineering1),HUST,Wuhan430074) (ZTE Corporation2),Shenzhen518057) Abstract:A software implementation of a channel coding technology is presented,which realizes the functions of convolution2 al coding and Viterbi decoding.According to convolutional codes feature,this software uses butterfly algorithm which is defined as a macro,periodically traces back to get the decoding output,we also use some other methods in the program,can speed up the al2 gorithm,which belongs to a forward error correction coding technology. K ey w ords:convolutional code,Viterbi decoding algorithm,butterfly algorithm,trace back Class number:TP31 卷积码是由伊莱亚斯(Elias)于1954年首先提出来的。它充分利用了各组之间的相关性,本组的信息元不但决定本组的监督元,而且也参与决定以后若干组的监督元。同时在译码过程中,不但从该时刻所收到的码组中提取译码信息,而且还利用以后若干时刻内所收到的码组来提取有关信息。无论从理论上还是实际上均已证明其性能不差于分组码。在一些采用了前向纠错的系统里,如GS M/CDM A通信系统、卫星与空间通信系统里广泛采用了卷积码[1]。 卷积码译码器的设计是由高性能的复杂译码器开始的,如最初的序列译码,随着译码约束长度的增加,译码错误概率可达到非常小。后来慢慢地向低性能的简单译码器演化,对不太长的约束长度,维特比(V iterbi)算法是非常实用的。维特比算法是一种最大似然的译码方法。当编码约束度不太大(小于等于10)或者误码率要求不太高(约10-5)时[2],它的设备比较简单,用硬件译码计算速度很快。本文将给出一种用软件实现卷积码维特比译码算法的设计方法,针对译码中计算量最多的蝶形运算,采用宏定义的方式,并在计算度量长度时采用双数组计算,能够加快译码计算速度。 1　卷积码编码器的参数分析 卷积码把信源输出的信息序列以每段k0个码元进行分段,通过编码器输出长为n0的一个码段,该段(n0-k0)个校验元不仅与本段信息元有关,还与其前面m段信息元有关。卷积码可以用(n0,k0,K)表示,其中(K=m+1)为约束长度,串联的移位寄存器的数目以m表示,一个信息 Ξ收到本文时间:2004年12月2日

Viterbi译码程序代码

译码主要部分 #include"stdafx.h" //#define DEBUG void deci2bin(int d, int size, int *b); int bin2deci(int *b, int size); int nxt_stat(int current_state, int input, int *memory_contents); void init_quantizer(void); void init_adaptive_quant(float es_ovr_n0); int soft_quant(float channel_symbol); int soft_metric(int data, int guess); int quantizer_table[256]; void sdvd(int g[2][K], float es_ovr_n0, long channel_length, float*channel_output_vector, int *decoder_output_matrix) { int i, j, l, ll; //循环控制变量 long t; //时间 int memory_contents[K]; //记录输入内容 int input[TWOTOTHEM][TWOTOTHEM]; //对当前状态以及下一个状态映射 int output[TWOTOTHEM][2]; //卷积码编码输出矩阵 int nextstate[TWOTOTHEM][2]; //下一个状态矩阵 int accum_err_metric[TWOTOTHEM][2]; //误差累计矩阵 int state_history[TWOTOTHEM][K * 5 + 1]; //历史状态表 int state_sequence[K * 5 + 1]; //状态序列 int *channel_output_matrix; //信道输出序列 int binary_output[2]; int branch_output[2]; //0或者1的输出分支 int m, n, number_of_states, depth_of_trellis, step, branch_metric, sh_ptr, sh_col, x, xx, h, hh, next_state, last_stop; n = 2; //1/2为卷积码传输数据的码率 m = K - 1;//寄存器个数 number_of_states = (int)pow(2.0, m);//状态个数number of states = 2^(K - 1) = 2^m depth_of_trellis = K * 5; for (i = 0; i < number_of_states; i++)

卷积码的维特比译码原理及仿真

卷积码的维特比译码原理及仿真 摘 要 本课程设计主要解决对一个卷积码序列进行维特比(Viterbi)译码输出,并通过Matlab 软件进行设计与仿真，并进行误码率分析。 实验原理 QPSK ：QPSK 是英文QuadraturePhaseShiftKeying 的缩略语简称， 意为正交相移键控，是一种数字调制方式。四相相移键控信号简称“QPSK ”。它分为绝对相移和相对相移两种。 卷积码：又称连环码，是由伊莱亚斯(P.elias)于1955年提出来的一种非分组码。积码将k 个信息比特编成n 个比特，但k 和n 通常很小，特别适合以串行形式进行传输，时延小。卷积码是在一个滑动的数据比特序列上进行模2和操作，从而生成一个比特码流。卷积码和分组码的根本区别在于，它不是把信息序列分组后再进行单独编码，而是由连续输入的信息序列得到连续输出的已编码序列。卷积码具有误码纠错的能力，首先被引入卫星和太空的通信中。NASA 标准（2，1，6）卷积码生成多项式为： 346 1345 6 2()1()1g D D D D D g D D D D D =++++=++++ 其卷积编码器为： 输入序列 + + 输出c1 输出c2 图1.1 K=7，码率为1/2的卷积码编码器

维特比译码：采用概率译码的基本思想是：把已接收序列与所有可能的发送序列做比较，选择其中码距最小的一个序列作为发送序列。如果接收到L 组信息比特，每个符号包括v 个比特。接收到的Lv 比特序列与2L 条路径进行比较，汉明距离最近的那一条路径被选择为最有可能被传输的路劲。当L 较大时，使得译码器难以实现。维特比算法则对上述概率译码做了简化，以至成为了一种实用化的概率算法。它并不是在网格图上一次比较所有可能的2kL 条路径(序列)，而是接收一段，计算和比较一段，选择一段最大似然可能的码段，从而达到整个码序列是一个最大似然值得序列。 下面以图2.1的(2，1，3)卷积码编码器所编出的码为例，来说明维特比解码的方法和运作过程。为了能说明解码过程，这里给出该码的状态图，如图2.2所 示。维特比译码需要利用图来说明移码过程。根据卷积码画网格的方法，我们可以画出该码的网格图，如图2.3所示。该图设接收到的序列长度为8，所以画8个时间单位，图中分别标以0至7。这里设编码器从a 状态开始运作。该网格图的每一条路径都对应着不同的输入信息序列。由于所有可能输入信息序列共有2kL 个，因而网格图中所有可能的路径也为2L 条。这里节点a=00，b=10，c=01，d=11。 m j m j-1 m j-2 输出序列 m 1,m 2,…m j ,… y 1j y 2j 输入序列 00 a d 10 c b 11 00 11 01 01 10 图2.1 (2,1,3)卷积码编码器 图2.2 (2,1,3)卷积码状态图

卷积码编码和维特比译码的原理、性能与仿真分析

卷积码编码和维特比译码的原理、性能与仿真分析 1.引言 卷积码的编码器是由一个有k位输入、n位输出，且具有m位移位寄存器构成的有限状态的有记忆系统，通常称它为时序网络。编码器的整体约束长度为v,是所有k个移位寄存器的长度之和。具有这样的编码器的卷积码称作[n,k,v]卷积码。对于一个（n,1,v）编码器，约束长度v等于存储级数m.卷积码是由k个信息比特编码成n（n>k）比特的码组，编码出的n比特码组值不仅与当前码字中的k个信息比特值有关，而且与其前面v个码组中的v*k个信息比特值有关。 卷积码有三种译码方式：序列译码、门限译码和概率译码。其中，概率译码根据最大似然译码原理在所有可能路径中求取与接收路径最相似的一条路径，具有最佳的纠错性能，维特比译码是概率译码中极重要的一种方式。 序列译码和门限译码则不一定能找出与接收路径最相似的一条路径。不同于维特比译码，门限译码与序列译码所需的计算量是可变的且对于给定信息分组的最终判决仅仅基于（m+1）个接收分组，而不是基于整个接收序列。 与维特比译码所使用的对数似然量度不同，序列译码所使用的量度为Fano量度。在接收序列受扰严重的情况下，序列译码的计算量大于维特比译码所需的固定计算量，虽然序列译码要求的平均计算次数通常小于维特比译码。在采用并行处理的情况下，维特比译码的速度会优于序列译码。在同样码率和存储级数的条件下，门限译码的性能比维特比译码低大约3dB. 维特比译码的数据输出方式有硬判决及软判决两种方式，本文选取生成多项式为561,753的（2,1,8）卷积码对硬判决的性能进行分析，并依据维特比译码的原理以及卷积码的特性，对卷积码编码和维特比译码过程在加性高斯白噪声（AWGN）信道下进行仿真，并且根据仿真结果对维特比译码（硬判决）的结果进行分析。由于卷积码的生成可以看做一个马尔科夫过程，因此，不同状态间的转移概率对描述这个过程有极关键的作用。本文则基于MATLAB对不同状态间的转移概率进行求解，从而更准确地分析维特比译码的性能。仿

动态规划：卷积码的Viterbi译码算法

动态规划:卷积码的Vitｅrｂi译码算法 学院:网研院?姓名:ｘxx 学号：xxｘ一、动态规划原理 动态规划（dynamｉc programminｇ)是运筹学的一个分支,是求解决策过程(decｉsioｎ procｅsｓ）最优化的数学方法。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解，每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。 动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同,确定最优解的条件也互不相同,因而动态规划的设计方法对不同的问题,有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。 二、卷积码的Ｖｉterbi译码算法简介 在介绍维特比译码算法之前，首先了解一下卷积码编码，它常常与维特比译码结合使用。(2,１，3)卷积码编码器是最常见的卷积码编码器,在本次实验中也使用了(2,1，３)卷积码编码器,下面介绍它的原理。 （2,１,３)卷积码是把信源输出的信息序列，以1个码元为一段,通过编码器输出长为2的一段码段。该码段的值不仅与当前输入码元有关，而且也与其之前的２个输入码元有关。如下图所示,输出out1是输入、第一个编码器存储的值和第二个编码器存储的值逻辑加操作的结果，输出ouｔ２是输入和第二个编码器存储的值逻辑加操作的结果。 （２,1,３)卷积码编码器

卷积码的维特比译码

卷积码的维特比译码 卷积编码器自身具有网格结构，基于此结构我们给出两种译码算法：Viterbi 译码算法和BCJR 译码算法。基于某种准则，这两种算法都是最优的。1967 年，Viterbi 提出了卷积码的Viterbi 译码算法，后来Omura 证明Viterbi 译码算法等效于在加权图中寻找最优路径问题的一个动态规划（Dynamic Programming）解决方案，随后，Forney 证明它实际上是最大似然（ML，Maximum Likelihood）译码算法，即译码器选择输出的码字通常使接收序列的条件概率最大化。BCJR 算法是1974 年提出的，它实际上是最大后验概率（MAP，Maximum A Posteriori probability）译码算法。这两种算法的最优化目标略有不同：在MAP 译码算法中，信息比特错误概率是最小的，而在ML 译码算法中，码字错误概率是最小的，但两种译码算法的性能在本质上是相同的。由于Viterbi 算法实现更简单，因此在实际应用比较广泛，但在迭代译码应用中，例如逼近Shannon 限的Turbo 码，常使用BCJR 算法。另外，在迭代译码应用中，还有一种Viterbi 算法的变种：软输出Viterbi 算法（SOV A，Soft-Output Viterbi Algorithm），它是Hagenauer 和Hoeher 在1989 年提出的。 为了理解Viterbi 译码算法，我们需要将编码器状态图按时间展开（因为状态图不能反映出时间变化情况），即在每个时间单元用一个分隔开的状态图来表示。例如（3，1，2）非系统前馈编码器，其生成矩阵为： G(D)=[1+D1+D21+D+D2]（1）

数字通讯中的维特比译码和Turbo码

译码器在数字通信中的应用 摘要：译码器可以用来实现组合电路，也可以用来实现码制转换。译码器就是把种代码转换为另一种代码的电路。随着现代电子技术的发展，译码器作为最基本的电子元器件之一，已广泛应用于数字通信系统中。 关键词：译码器，数字通信，维特比译码，Turbo码 1 引言 在数字电路中，能够实现译码功能的逻辑部件称为译码器(Decod6r)。实际上，译码器就是把一种代码转换为另一种代码的电路。译码器是一种组合逻辑电路。它的输入代码的组合将在某一个输出端产生特定的信号。译码是编码的逆过程，在编码时，每一种二进制代码状态都赋予了特定的含义，即都表示了一个确定的信号或者对象。把代码状态的特定含义翻译出来的过程称为译码，实现译码操作的电路称为译码器，或者说译码器是将输入二进制代码的状态翻译成输出信号，以表示其原来含义的电路。实际上，译码器就是把种代码转换为另一种代码的电路。随着现代电子技术的发展，译码器作为最基本的电子元器件之一，其应用领域越来越广泛，尤其是数字通信中的应用。 2原理 （1）译码器的原理 译码器的原理：用来表示输入变量状态的译码器是一种二进制译码器，输入输出代码之间的关系可由真值表表示。n个输入代码就有2n个输入状态，因此译码器就有2n个输出和输入状态相对应。每个输出的特定电位状态表示输入代码的一种组合。 （2）数字通信系统 数字通信系统是利用数字信号来传递信息的通信系统。如下图所示，数字通信主要涉及信编码和译码，信道编码与译码，同步及加密等等。 通信系统中信道编码的目的是增强数字信号的抗干扰能力。接受端的信道译码器按相应的逆规则进行解码，从中发现错误或纠正错误，提高通信系统的可靠性。纠错编码的基本思想是：在编码过程中，通过给所传输的信息设置附加的校验位，即增加其冗余度，使原来无规律或规律性不强的一组信息具有某种相关性；接收信息时再依据这种相关性译码，使编码信息具有检测或纠错性能，而用来检测或纠错的冗余码被称为纠错码。 （3）差错控制

卷积编码和Viterbi译码

卷积编码和Viterbi译码 摘要 本文的目的是向读者介绍了前向纠错技术的卷积编码和Viterbi译码。前向纠错的目的（FEC）的是改善增加了一些精心设计的冗余信息，正在通过信道传输数据的通道容量。在添加这种冗余信息的过程称为信道编码。卷积编码和分组编码是两个主要的渠道形式编码。 简介 前向纠错的目的（FEC）的是改善增加了一些精心设计的冗余信息，正在通过信道传输数据的通道容量。在添加这种冗余信息的过程称为信道编码。卷积编码和分组编码是两个主要的渠道形式编码。卷积码串行数据操作，一次一个或数位。分组码操作比较大（通常，多达几百个字节的情侣）消息块。有很多有用的分组码和卷积多种，以及接收解码算法编码信息的DNA序列来恢复原来的各种数据。 卷积编码和Viterbi译码前向纠错技术，是一种特别适合于在其中一个已损坏的发射信号加性高斯白噪声（AWGN）的主要通道。你能想到的AWGN信道的噪声，其电压分布也随着时间的推移，可以说是用高斯，或正常，统计分布特征，即一钟形曲线。这个电压分布具有零均值和标准差这是一个信号与噪声比接收信号的信噪比（SNR）函数。让我们承担起接收到的信号电平是固定的时刻。这时如果信噪比高，噪声标 准偏差小，反之亦然。在数字通信，信噪比通常是衡量E b /N 的它代表噪声密度双面 能源每比特除以之一。 卷积码通常是描述使用两个参数：码率和约束长度。码率k/n，是表示为比特数为卷积编码器（十一）信道符号卷积编码器输出的编码器在给定的周期（N）的数量之比。约束长度参数，钾，表示该卷积编码器的“长度”，即有多少K位阶段提供饲料的组合逻辑，产生输出符号。 K是密切相关的参数米，这表明有多少位的输入编码器周期被保留，用于编码后第一次在卷积编码器输入的出现。的m参数可以被认为是编码器的记忆长度。在本教程中，并在此示例的源代码，我集中精力率1 / 2卷积码。 Viterbi译码是一种两个卷积编码与解码，其他类型的算法类型的顺序解码。序贯解码的优点，它可以执行得很好，长期约束卷积码的长度，但它有一个变量解码时间。

维特比译码

维特比译码的介绍与仿真实现 维特比译码是将接收到的序列和所有可能的发送序列作比较，选择其中汉明距离最小的序列当作是现在的发送序列的一种算法。译码器从某个状态,例如从状态出发,每次向右延伸一个分支,并与接收数字相应分支进行比较,计算它们之间的距离，然后将计算所得距离加到被延伸路径的累积距离值中。对到达每个状态的各条路径的距离累积值进行比较，保留距离值最小的一条路径，称为幸存路径（当有两条以上取最小值时，可任取其中之一）。这种算法所保留的路径与接收序列之间的似然概率为最大，所以又称为最大似然译码。 所以，维特比译码的过程可以简单的理解为：接收端使用相同的网格图，从同一状态开始猜测发送端可能的编码序列，然后与接收到的码组比较，其中与接收到的码组最近的猜测序列即使为译码序列，也就是码距最小的序列。 设卷积码为(n, k, m) = (3, 1, 2)码,如下图：

那么对应的网格图为上图所示。 由网格图可见，沿路径每一级有4种状态a, b, c和d。每种状态只有两条路径可以到达。故4种状态共有8条到达路径。比较网格图中的这8条路径和接收序列之间的汉明距离。比较到达每个状态的两条路径的汉明距离，将距离小的一条路径保留，也就是幸存路径。这样，就剩下4条路径了。继续考察接收序列中的后继的比特，最后得出总的汉明距离最小的路径，也就是发送序列。 假设现在的发送信息位为1101 编码后的发送序列：111 110 010 100 001 011 000 接收序列：111 010 010 110 001 011 000 (红色为错码) 发送序列的约束长度为N = m + 1 ＝ 3 最后的幸存路径画出的网格图示于下图中，图中粗线路径是距汉明离最小（等于2）的路径。 在上例中卷积码的约束长度为N = 3，需要存储和计算8条路径的参量。由此可见，维特比算法的复杂度随约束长度N按指数形式2N增长。故维特比算法适合约束长度较小（N 10）的编码。 卷积码的维特比译码是根据接收码字序列寻找编码时通过网格图最佳路径的过程，找到最佳路径即完成了译码过程，并可以纠正接收码字中的错误比特。维特比译码算法步骤如下描述： 1)根据接收码符号R，计算出相应的分支量度值BM(R/ Cj),j = 1 、2； 2)进入某一状态的2 条分支量度BM (R/ Cj）与其前状态路径量度PM累加 求和；

卷积码中的维特比译码和序贯译码算法

卷积码是1955年由Elias 等人提出的，是一种非常有前途的编码方法。我们在一些资料上可以找到关于分组码的一些介绍，分组码的实现是将编码信息分组单独进行编码，因此无论是在编码还是译码的过程中不同码组之间的码元无关。卷积码和分组码的根本区别在于，它不是把信息序列分组后再进行单独编码，而是由连续输 入的信息序列得到连续输出的已编码序列。即进行分组编码时，其本组中的n-k 个校验元仅与本组的k 个信息元有关，而与其它各组信息无关；但在卷积码中，其编 码器将k 个信息码元编为n 个码元时，这n 个码元不仅与当前段的k 个信息有关，而且与前面的（m －1）段信息有关（m 为编码的约束长度）。同样，在卷积码译码过程中，不仅从此时刻收到的码组中提取译码信息，而且还要利用以前或以后各时刻收到的码组中提取有关信息。而且卷积码的纠错能力随约束长度的增加而增强，差错率则随着约束长度增加而呈指数下降 。卷积码(n,k,m) 主要用来纠随机错误，它的码元与前后码元有一定的约束关系，编码复杂度可用编码约束长度m*n 来表示。一般地，最小距离d 表明了卷积码在连续m 段以内的距离特性，该码可以在m 个连续码流内纠正(d-1)/2个错误。卷积码的纠错能力不仅与约束长度有关，还与采用的译码方式有关。总之，由于n ，k 较小，且利用了各组之间的相关性，在同样的码率和设备的复杂性条件下，无论理论上还是实践上都证明：卷积码的性能至少不比分组码差。 编码原理[回目录] 以二元码为例，编码器如图。输入信息序列为u ＝(u 0， u 1，…)，其多项式表示为u (x )＝u 0+u 1x ＋…＋u l x l ＋…。 编码器的连接可用多项式表示为g (1,1)(x )＝1+x +x 2和 g (1,2)(x )＝1+x 2，称为码的子生成多项式。它们的系数矢 量g (1,1)=(111)和g (1,2)=(101)称作码的子生成元。以子生成多项式为阵元构成的多项式矩阵G (x )＝ [g (1,1)(x ),g (1,2)(x )]，称为码的生成多项式矩阵。由生成元构成的半无限矩阵 称为码的生成矩阵。其中(11,10,11)是由g (1,1)和g (1,2)交叉连接构成。编码器输出序列为c ＝u ·G ，称为码序 列，其多项式表示为c (x )，它可看作是两个子码序列c (1)(x )和c (2)(x )经过合路开关S 合成的，其中c (1)(x )＝u (x )g (1,1)(x )和c (2)(x )＝u (x )g (1,2)(x ),它们分别是信息序列和相应子生成元的卷积，卷积码由此得名。 在一般情况下，输入信息序列经过一个时分开关被分成k 0个子序列,分别以u (x )表示,其中i =1，2,…k 0，即u (x )＝[ u (x ),…, u (x )]。编码器的结构由k 0×n 0阶生成多项式矩阵给定。输出码序列由n 0个子序列组成，即c (x )＝[ c (x ), c (x )，…，c (x )]，且c (x )=u (x )·G (x )。若m 是所有子生成多项式 g (x )中最高次式的次数，称这种码为(n 0，k 0，m ) 卷积码。 表示方法[回目录] 描述卷积码编码器过程的方法有很多，如矩阵法、多项式、码树和网格图等，这里我们主要介绍和卷积码编码器结构密切相关的多项式法，以及与卷积码译码密切相关的网格图法。 一种卷积码编码器 卷积码编码器

卷积码的编译码MATLAB程序

%survivor state是一个矩阵，它显T了通过网格的最优路径，这个矩阵通过一个单独的函数metric(x,y)给出。 %其中G是一个矩阵，它的任一行决定了从移位寄存器到模2加法器的连接方式.为生成矩阵%这里，我们做了一个简单的(2,1,7)卷积码编码器。 k=1; G=[1 0 1 1 0 1 1;1 1 1 1 0 0 1];%G1=133,G2=171 %以下3种输入序列，可任选一种% %input=[0 0 0 0 0 0 0];%全0输入 %input=[1 1 1 1 1 1 1];%全1输入 input=[round(rand(1,7)*1)];%随机系列输入，也可用 randint(1,7,[0 1]) figure;plot(input,'*r') %figure1：画图：目标input，红色（red，r），形状为* s=input; g1=G(1,:); g2=G(2,:); c1=conv(s,g1);%作卷积 %disp(c1); c2=conv(s,g2); %disp(c2); n=length(c1);%7位输入时n=13 c=zeros(1,2*n);%生成全0矩阵，1*26 %disp(c); for i=1:n c(2*i-1)=c1(i);c(2*i)=c2(i);%两个模2加法器分别输出卷积结果序列后，由旋转开关读取的结果（此时仅为卷积结果，非2进制0/1） end for i=1:2*n if(mod(c(i),2)==0)% mod(c(i),2)==0意思：c(i)除以2，余数为0 c(i)=0; else c(i)=1; end end output=c; channel_output=output;%输出矩阵 %disp(channel_output); figure;plot(output,'*b') %画图：目标：卷积码编码输出，蓝色（blue，b）* %————————————————以上为编码部分，以下为维特比译码———————————————— n=size(G,1);%取矩阵G的行数，故n=2。即得到输出端口，即2个模2加法器 %检验G的维数 if rem(size(G,2),k)~=0 %当矩阵G的列数不为k的整数倍时，rem为求余函数 error('Size of G and k do not agree')%报错 end if rem(size(channel_output,2),n)~=0 %当输出矩阵的列数不是输出端口n的整数倍时。（注：size(channel_output,2)=26，2个模2加法器合成的输出）