卷积码的维特比译码

矩阵表示当m=2,A0=(l 1)T, A1=(O 1)T, A2=(l 1)T 时, 如前3个输入为110,则前6个输出为111010AAn-1 An-20 0A)2M ( m ()+ m j D + m 2 D」+ •…C (D) = c()+ c ] D+ c 2 Q + --------C⑺(£))二c Oy +c Iy D + c2y£)2+ …J = l,2,・・・，〃o状态图表示法以两个D触发器的组合值为状态，如D1D2,描述从当前状态在不同的输入时的输出及将到达的状态，每个分支上的标注为yly2, 表示当前的输出。

(2,1,2)码状态图（2丄2）截断篱状图（2儿2）码编码电路码编码电路解析对¥用建口）表示常数乘法 先霧［器，共有（m+l ）*n<5个,（i=l,2，・・・，k;j=l ，2,…由入 到纟小）。

g （ij ）=l 时常三每绅租與出”“木玮后去右與的峋成,#模2加法器是将与其相关的$器。

占 一 7L 乂一上丄_、丄，土E 体不仅 丕与开关K 在每一节拍中’、 : 移动n 次，每一次输® 入信息元而输出凸元。

接线。

输出码子c 是: ■1信息元 输入1^411ft犬态累加距离译出序列：00 0接受100001序列f 1011011100 A0011(X)0000译码结果分析1100000011 5 :10时间to—tl七2七3t4t 消息序列m0001发送序列U0000001101接收序列R1010000111译码序列C0|o0111101 L01\的路径返回全零状态并完成译码。

图例:输入比讐510说明:醴曲是进入屛编码器的序列，flilll 是编码器输出，是经信道传输后的译码器输入，隸烤」是译码器输出。

白色码子是编码器清零的冗余信息，沁o 窗是发生番滾的比特位。

七61111,653状态图生成过程9 0 ® 0=10状态。

请简述卷积码译码的维特比算法
卷积码译码的维特比算法是一种概率译码方法，通过计算接收序列的每个可能的发送序列的概率，然后选择具有最大概率的发送序列作为译码输出。

具体步骤如下：
1. 计算每个时刻每个状态下的分支度量。

2. 对于每个时刻，计算每个状态下的部分路径和。

3. 将部分路径和与该时刻的接收路径进行比较，计算汉明码距离。

4. 选择具有最小汉明码距离的状态作为幸存路径。

5. 将幸存路径的最后一个时刻作为输出，并删除所有其他路径。

6. 重复步骤3-5，直到所有接收序列都被译码。

该算法的核心思想是“加、比、选”，即先将每个时刻每个状态下的分支度量进行累积，然后比较每个时刻每个状态下的部分路径和，选择具有最小汉明码距离的状态作为幸存路径。

通过重复执行这些步骤，最终得到译码输出。

编号：《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芯片实现卷积码的维特比译码算法的仿真和运行。

关键词：卷积码维特比译码DSPConvolutional codes and Viterbi decoding analysis andrealizationZhang 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.1Key words:convolutional code Vltebri decoder DSP0 前言随着数据处理、计算机通信、卫星通信以及高速数据通信网的飞速发展，用户对数据传输的可靠性提出了越来越高的要求，因此如何在保证数据传输速率的前提下，提高传输数据的可靠性，就成为一个迫切需要解决的问题。

卷积编码和Viterbi译码摘要本文的目的是向读者介绍了前向纠错技术的卷积编码和Viterbi译码。

前向纠错的目的（FEC）的是改善增加了一些精心设计的冗余信息，正在通过信道传输数据的通道容量。

在添加这种冗余信息的过程称为信道编码。

卷积编码和分组编码是两个主要的渠道形式编码。

简介前向纠错的目的（FEC）的是改善增加了一些精心设计的冗余信息，正在通过信道传输数据的通道容量。

在添加这种冗余信息的过程称为信道编码。

卷积编码和分组编码是两个主要的渠道形式编码。

卷积码串行数据操作，一次一个或数位。

分组码操作比较大（通常，多达几百个字节的情侣）消息块。

有很多有用的分组码和卷积多种，以及接收解码算法编码信息的DNA序列来恢复原来的各种数据。

卷积编码和Viterbi译码前向纠错技术，是一种特别适合于在其中一个已损坏的发射信号加性高斯白噪声（AWGN）的主要通道。

你能想到的AWGN信道的噪声，其电压分布也随着时间的推移，可以说是用高斯，或正常，统计分布特征，即一钟形曲线。

这个电压分布具有零均值和标准差这是一个信号与噪声比接收信号的信噪比（SNR）函数。

让我们承担起接收到的信号电平是固定的时刻。

这时如果信噪比高，噪声标准偏差小，反之亦然。

在数字通信，信噪比通常是衡量Eb /N的它代表噪声密度双面能源每比特除以之一。

卷积码通常是描述使用两个参数：码率和约束长度。

码率k/n，是表示为比特数为卷积编码器（十一）信道符号卷积编码器输出的编码器在给定的周期（N）的数量之比。

约束长度参数，钾，表示该卷积编码器的“长度”，即有多少K位阶段提供饲料的组合逻辑，产生输出符号。

K是密切相关的参数米，这表明有多少位的输入编码器周期被保留，用于编码后第一次在卷积编码器输入的出现。

的m参数可以被认为是编码器的记忆长度。

在本教程中，并在此示例的源代码，我集中精力率1 / 2卷积码。

Viterbi译码是一种两个卷积编码与解码，其他类型的算法类型的顺序解码。

卷积码的维特比译码原理及仿真摘 要 本课程设计主要解决对一个卷积码序列进行维特比(Viterbi)译码输出,并通过Matlab 软件进行设计与仿真，并进行误码率分析。

实验原理QPSK ：QPSK 是英文QuadraturePhaseShiftKeying 的缩略语简称，意为正交相移键控，是一种数字调制方式。

四相相移键控信号简称“QPSK ”。

它分为绝对相移和相对相移两种。

卷积码：又称连环码，是由伊莱亚斯(P.elias)于1955年提出来的一种非分组码。

积码将k 个信息比特编成n 个比特，但k 和n 通常很小，特别适合以串行形式进行传输，时延小。

卷积码是在一个滑动的数据比特序列上进行模2和操作，从而生成一个比特码流。

卷积码和分组码的根本区别在于，它不是把信息序列分组后再进行单独编码，而是由连续输入的信息序列得到连续输出的已编码序列。

卷积码具有误码纠错的能力，首先被引入卫星和太空的通信中。

NASA 标准（2，1，6）卷积码生成多项式为： 346134562()1()1g D D D D D g D D D D D=++++=++++其卷积编码器为：图1.1 K=7，码率为1/2的卷积码编码器维特比译码：采用概率译码的基本思想是：把已接收序列与所有可能的发送序列做比较，选择其中码距最小的一个序列作为发送序列。

如果接收到L 组信息比特，每个符号包括v 个比特。

接收到的Lv 比特序列与2L 条路径进行比较，汉明距离最近的那一条路径被选择为最有可能被传输的路劲。

当L 较大时，使得译码器难以实现。

维特比算法则对上述概率译码做了简化，以至成为了一种实用化的概率算法。

它并不是在网格图上一次比较所有可能的2kL 条路径(序列)，而是接收一段，计算和比较一段，选择一段最大似然可能的码段，从而达到整个码序列是一个最大似然值得序列。

下面以图2.1的(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 译码算法和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）图1 （a）（3，1，2）编码器（b）网格图（h＝5）假定信息序列长度为h＝5，则网格图包含有h＋m＋1＝8 个时间单元，用0 到h＋m＝7 来标识，如图1（b）所示。

假设编码器总是从全0 态S0 开始，又回到全0 态，前m＝2 个时间单元对应于编码器开始从S0“启程”，最后m＝2 个时间单元对应于向S0“返航”。

卷积码的维特比译码卷积编码器自身具有网格构造，基于此构造我们给出两种译码算法：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〕图1 〔a〕〔3，1，2〕编码器〔b〕网格图〔h＝5〕假定信息序列长度为h＝5，那么网格图包含有h＋m＋1＝8 个时间单元，用0 到h＋m＝7 来标识，如图1〔b〕所示。

假设编码器总是从全0 态S0 开始，又回到全0 态，前m＝2 个时间单元对应于编码器开始从S0“启程〞，最后m＝2 个时间单元对应于向S0“返航〞。

动态规划：卷积码的Viterbi译码算法学院：网研院姓名：xxx 学号：xxx 一、动态规划原理动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。

动态规划算法通常用于求解具有某种最优性质的问题。

在这类问题中，可能会有许多可行解，每一个解都对应于一个值，我们希望找到具有最优值的解。

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。

若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。

如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。

不象搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。

动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。

二、卷积码的Viterbi译码算法简介在介绍维特比译码算法之前，首先了解一下卷积码编码，它常常与维特比译码结合使用。

（2,1,3）卷积码编码器是最常见的卷积码编码器，在本次实验中也使用了（2,1,3）卷积码编码器，下面介绍它的原理。

（2,1,3）卷积码是把信源输出的信息序列，以1个码元为一段，通过编码器输出长为2的一段码段。

该码段的值不仅与当前输入码元有关，而且也与其之前的2个输入码元有关。

如下图所示，输出out1是输入、第一个编码器存储的值和第二个编码器存储的值逻辑加操作的结果，输出out2是输入和第二个编码器存储的值逻辑加操作的结果。

卷积码编码维特比译码实验设计报告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<stdio.h>#include "Conio.h"#define N 7#include "math.h"#include <stdlib.h>#include<time.h>#define randomize() srand((unsigned)time(NULL))encode(unsigned int *symbols, /*编码输出*/unsigned int *data, /*编码输入*/unsigned int nbytes, /*nbytes=n/16,n为实际输入码字的数目*/unsigned int startstate /*定义初始化状态*/)////////////////////////////////////////////////////////////////////////////卷积码编码///////////////////////////////////////////////////////////////////////////////{unsigned int j;unsigned int input,a1=0,a2=0,a3=0,a4=0,a5=0,a6=0;for(j=0;j<nbytes;j++){input=*data;data++;*symbols = input^a1^a2^a3^a6; //c1(171)symbols++;*symbols = input^a2^a3^a5^a6; //c2(133)symbols++;a2=a1;a1=input;}return 0;}int trandistance(int m, int state1, int state2)/*符号m与从state1到state2时输出符号的汉明距离,如果state1无法到state2则输出度量值为100*/{int c;int sym,sym1,sym2;sym1=((state2>>1)&1)^(state2&1)^(state1&1);sym2=((state2>>1)&1)^(state1&1);sym=(sym1<<1) | sym2;if ( ((state1&2)>>1)==(state2&1))c=((m&1)^(sym&1))+(((m>> 1)&1)^((sym >> 1)&1));elsec=10000;return(c);}int traninput(int a,int b) /*状态从a到b时输入卷积码的符号*/{int c;c=((b&2)>>1);return(c);}int tranoutput(int a,int b) /*状态从a到b时卷积码输出的符号*/{int c,s1,s2;s1=(a&1)^((a&2)>>1)^((b&2)>>1);s2=(a&1)^((b&2)>>1);c=(s1<<1)|s2;return(c);}////////////////////////////////////////////////////////////////////////////维特比译码///////////////////////////////////////////////////////////////////////////////void viterbi(int initialstate, /*定义解码器初始状态*/int *viterbiinput, /*解码器输入码字序列*/int *viterbioutput /*解码器输出码字序列*/){struct sta /*定义网格图中每一点为一个结构体,其元素包括*/ {int met; /*转移到此状态累计的度量值*/int value; /*输入符号*/struct sta *last; /*及指向前一个状态的指针*/};struct sta state[4][N];struct sta *g,*head;int i,j,p,q,t,r,u,l;for(i=0;i<4;i++) /* 初始化每个状态的度量值*/for(j=0;j<N;j++)state[i][j].met=0;for(l=0;l<4;l++){state[l][0].met=trandistance(*viterbiinput,initialstate,l);state[l][0].value=traninput(initialstate,l);state[l][0].last=NULL;}viterbiinput++; /*扩展第一步幸存路径*/for(t=1;t<N;t++){for(p=0;p<4;p++){state[p][t].met=state[0][t-1].met+trandistance(*viterbiinput,0,p);state[p][t].value=traninput(0,p);state[p][t].last=&state[0][t-1];for(q=0;q<4;q++){if(state[q][t-1].met+trandistance(*viterbiinput,q,p)<state[p][t].met){state[p][t].met=state[q][t-1].met+trandistance(*viterbiinput,q,p);state[p][t].value=traninput(q,p);state[p][t].last=&state[q][t-1];}}}viterbiinput++;} /*计算出剩余的幸存路径*/r=state[0][N-1].met; /*找出n步后度量值最小的状态准备回溯路由*/g=&state[0][N-1];for(u=N;u>0;u--) /*向前递归的找出最大似然路径*/{*(viterbioutput+(u-1))=g->value;g=g->last;}/* for(u=0;u<8;u++)*(viterbioutput+u)=state[u][2].met; */ /*此行程序可用于检测第n列的度量值*/}void decode(unsigned int *input, int *output,int n){int viterbiinput[100];int j;for(j=0;j<n+2;j++){viterbiinput[j]=(input[j*2]<<1)|input[j*2+1];}viterbi(0,viterbiinput,output);}void main(){unsigned intencodeinput[100],wrong[10]={0,0,0,0,0,0,0,0,0,0},encodeoutput[100];int n=5,i,m,j=0,decodeinput[100],decodeoutput[100];randomize();for(i=0; i<n; i++)encodeinput[i]=rand()%2;encodeinput[n]= encodeinput[n+1]=0;encode(encodeoutput,encodeinput,n+2,0);printf("the input of encoder is :\n"); //信息源输入的信息码（随机产生）for(i=0;i<n; i++)printf("%2d",encodeinput[i]);printf("\n");printf("the output of encoder is :\n"); //编码之后产生的卷积码for(i=0;i<(n+2)*2;i++){printf("%2d",encodeoutput[i]);if(i%20==19)printf("\n");}printf("\n");printf("please input the number of the wrong bit\n"); //信道传输收到干扰而产生的错误码scanf("%d",&m);printf("please input the positions of the wrong bit(0-9)\n");for(i=0;i<m;i++){scanf("%d",&wrong[m]);if(encodeoutput[wrong[m]]==0)encodeoutput[wrong[m]]=1;elseencodeoutput[wrong[m]]=0;}printf("the input of decoder is :\n");for(i=0;i<(n+2)*2;i++){printf("%2d",encodeoutput[i]);if(i%20==19)printf("\n");}printf("\n");decode(encodeoutput,decodeoutput,n+2);printf("the output of decoder is :\n");for(i=0;i<n;i++)printf("%2d",decodeoutput[i]);printf("\n");for(i=0;i<n;i++){if(encodeinput[i]!=decodeoutput[i])j++;}printf("the number of incorrect bit is:%d\n",j);}四、实验总结（1）了解实验原理，分析实验所占数组变量很重要，也是相对考虑较多的；（2）对于读写文件，通过本实验更加熟悉；（3）记录实验程序最佳路径是本实验的难点；。

卷积维特比译码c语言卷积码和维特比（Viterbi）译码是两种在通信系统中常用的编码和解码技术。

卷积码是一种线性分组码，它通过将输入信息序列与一组预定的约束条件进行卷积运算来生成编码序列。

而维特比译码是一种高效的解码算法，用于从接收到的信号中恢复出原始的编码序列。

下面是一个简单的C语言示例，演示了如何实现卷积编码和维特比译码。

请注意，这只是一个基本的示例，实际的实现可能会更复杂，并且需要更多的错误处理和优化。

c复制代码:#include <stdio.h>#include <stdlib.h>#define N 4#define K 2#define G 2// 卷积编码函数void convolutional_encode(int input[K], int code[N]) {int i, j;for (i = 0; i < N; i++) {code[i] = 0;}for (i = 0; i < K; i++) {code[i] = input[i];}for (i = K; i < N; i++) {code[i] = (code[i - 1] ^ code[i - 2]) & G;}}// 维特比译码函数void viterbi_decode(int received[N], int output[K]) {int branch_metric[N][2];int path_metric[N];int max_metric, new_max_metric;int max_path, new_max_path;int i, j, k;for (i = 0; i < N; i++) {path_metric[i] = abs(received[i] - 0); // 初始化路径度量branch_metric[i][0] = abs(received[i] - 0); // 初始化分支度量branch_metric[i][1] = abs(received[i] - G); // 初始化分支}for (i = 0; i < N; i++) {output[i] = 0; // 初始化输出序列}for (i = 0; i < N; i++) {if (branch_metric[i][0] > branch_metric[i][1]) {output[i] = 0; // 选择分支0作为当前的最优路径path_metric[i] = branch_metric[i][0]; // 更新路径度量} else {output[i] = 1; // 选择分支1作为当前的最优路径path_metric[i] = branch_metric[i][1]; // 更新路径度量}if (path_metric[i] > max_metric) {max_metric = path_metric[i]; // 记录最大路径度量max_path = i; // 记录最大路径度量对应的路径值} else if (path_metric[i] == max_metric) { // 如果当前路径度量与最大路径度量相等，则选择路径值较小的路径作为最优路径new_max_metric = path_metric[i]; // 记录新的最大路径度量new_max_path = i; // 记录新的最大路径度量对应的路} else if (path_metric[i] < max_metric && path_metric[i] > new_max_metric) { // 如果当前路径度量比新记录的最大路径度量要小，但是比之前的最大路径度量要大，则更新新的最大路径度量和对应的路径值new_max_metric = path_metric[i]; // 更新新的最大路径度量new_max_path = i; // 更新新的最大路径度量对应的路径值} else if (path_metric[i] < max_metric && path_metric[i] < new_max_metric) { // 如果当前路径度量比新记录的最大路径度量要小，但是比之前的最大路径度量要小，则更新新的最大路径度量和对应的路径值，同时更新最优路径为新记录的最大路径对应的路径值和对应的分支值new_max_metric = new_max_metric; // 更新新的最大路径度量不变new_max_path = i; // 更新新的最大路径度量对应的路径值为当前路径。

中国新通信2009.11卷积码及其Viterbi 算法的简介卷积码是1955年由Elias 提出，它与分组码不同，分组码是把k 个信息比特的序列编成n 个比特的码组，每个码组的n-k 个校验位仅与本码组k 个信息位有关，而与其他码组无关。

为了达到一定的纠错能力和编码效率，分组码的码组长度一般都比较大。

编译码时必须把整个信息码组存储起来，由此产生的译码延时随n 的增加而增加。

卷积码编码的一般结构如图1所示。

卷积码的概率译码最早始于1961年由Wozencraft 提出的序列译码，1963年由Fano 进行了改进，提出了Fano 算法。

1967年由Viterbi 提出了另外一种概率译码算法Viterbi 译码算法，它是一种最大似然译码算法，在码的约束度较小时，它比序列译码算法效率更高、速度更快，译码器也较简单。

因此，自Viterbi 译码算法提出以来，无论在理论上，还是在实践上都得到了极其迅速的发展。

Viterbi 算法并不等价于最大似然算法，但是，在一定的条件下，Viterbi 算法就是最大似然译码和最佳译码算法。

2Viterbi 算法的FPGA 实现2.1FPGA 的结构和特点随着半导体器件技术的快速发展，专用集成电陈健李广华（天津工业大学信息与通信工程学院天津300160）摘要本文根据卷积码编码的方式，和Viterbi 译码算法，认真分析了Viterbi 译码算法各部分的功能、特点。

采用硬件描述语言Verilog HDL ，编写了（2，1，7）卷积码的编译码程序，进行了Viterbi 译码器的FPGA 设计。

关键词卷积码Viterbi 算法现场可编程门阵列卷积码Vit e rb i 译码的FP GA 实现1k1n输出图1卷积码编码的一般结构图中国新通信经验与交流EXPERIENCE AND EXCHANGE53CHINA NEW TELECOMMUNICATIONS January 2009路（ASIC ）的设计技术也随之不断提高和进步，现场可编程门阵列（FPGA ）的出现使得系统级集成电路的设计开发成为可能，电子设计自动化（EDA ）技术正给整个电子设计领域带来一场新的革命。

卷积码－Viterbi译码卷积码在一个二进制分组码（n,k）当中，包含k个信息位，码组长度为n，每个码组的（n-k）个校验位仅与本码组的k个信息位有关，而与其它码组无关。

为了达到一定的纠错能力和编码效率（＝k/n），分组码的码组长度n通常都比较大。

编译码时必须把整个信息码组存储起来，由此产生的延时随着n的增加而线性增加。

为了减少这个延迟，人们提出了各种解决方案，其中卷积码就是一种较好的信道编码方式。

这种编码方式同样是把k个信息比特编成n个比特，但k和n通常很小，特别适宜于以串行形式传输信息，减小了编码延时。

与分组码不同，卷积码中编码后的n个码元不仅与当前段的k个信息有关，而且也与前面（N-1）段的信息有关，编码过程中相互关联的码元为nN个。

因此，这N时间内的码元数目nN通常被称为这种码的约束长度。

卷积码的纠错能力随着N 的增加而增大，在编码器复杂程度相同的情况下，卷段积码的性能优于分组码。

另一点不同的是：分组码有严格的代数结构，但卷积码至今尚未找到如此严密的数学手段，把纠错性能与码的结构十分有规律地联系起来，目前大都采用计算机来搜索好码。

下面通过一个例子来简要说明卷积码的编码工作原理。

正如前面已经指出的那样，卷积码编码器在一段时间内输出的n位码，不仅与本段时间内的k位信息位有关，而且还与前面m段规定时间内的信息位有关，这里的m＝N-1通常用（n，k，m）表示卷积码（注意：有些文献中也用（n，k，N）来表示卷积码）。

图1就是一个卷积码的编码器，该卷积码的n = 2，k = 1，m = 2，因此，它的约束长度nN = n×(m+1) = 2×3 = 6。

图1 （2，1，2）卷集码编码器在图1中，与为移位寄存器，它们的起始状态均为零。

、与、、之间的关系如下：（1）假如输入的信息为D = [11010]，为了使信息D全部通过移位寄存器，还必须在信息位后面加3个零。

表1列出了对信息D进行卷积编码时的状态。

卷积码编码和维特比译码的性能对比1.引言卷积码的编码器是由一个有k位输入、n位输出，且具有m位移位寄存器构成的有限状态的有记忆系统，通常称它为时序网络。

编码器的整体约束长度为v,是全部k个移位寄存器的长度之和。

具有这样的编码器的卷积码称作[n,k,v]卷积码。

对于一个（n,1,v）编码器，约束长度v等于存储级数m.卷积码是由k个信息比特编码成n（nk）比特的码组，编码出的n比特码组值不仅与当前码字中的k个信息比特值有关，而且与其前面v个码组中的v*k个信息比特值有关。

卷积码有三种译码方式：序列译码、门限译码和概率译码。

其中，概率译码依据最大似然译码原理在全部可能路径中求取与接收路径最相像的一条路径，具有最佳的纠错性能，维特比译码是概率译码中极重要的一种方式。

序列译码和门限译码则不肯定能找出与接收路径最相像的一条路径。

不同于维特比译码，门限译码与序列译码所需的计算量是可变的且对于给定信息分组的最终判决仅仅基于（m+1）个接收分组，而不是基于整个接收序列。

与维特比译码所使用的对数似然量度不同，序列译码所使用的量度为Fano量度。

在接收序列受扰严峻的状况下，序列译码的计算量大于维特比译码所需的固定计算量，虽然序列译码要求的平均计算次数通常小于维特比译码。

在采纳并行处理的状况下，维特比译码的速度会优于序列译码。

在同样码率和存储级数的条件下，门限译码的性能比维特比译码低大约3dB.维特比译码的数据输出方式有硬判决及软判决两种方式，本文选取生成多项式为561,753的（2,1,8）卷积码对硬判决的性能进行分析，并依据维特比译码的原理以及卷积码的特性，对卷积码编码和维特比译码过程在加性高斯白噪声（AWGN）信道下进行仿真，并且依据仿真结果对维特比译码（硬判决）的结果进行分析。

由于卷积码的生成可以看做一个马尔科夫过程，因此，不同状态间的转移概率对描述这个过程有极关键的作用。

本文则基于MATLAB对不同状态间的转移概率进行求解，从而更精确地分析维特比译码的性能。

卷积编码和Viterbi译码zcl.space目录1引言1 2编码1 3译码2 4回溯4 5回溯深度6 6软译码61引言1965年，Peter Elias发明卷积码。

1967年，Andrew J.Viterbi（高通的创始人之一）发明了一种高效的译码算法：Viterbi算法。

Viterbi译码器可能是当前应用最广泛的一种卷积译码器。

2005年，G.David Forney在南加州大学的Viterbi Conference上提到：每秒，全世界的Viterbi译码器恢复的的二进制比特数是1015。

今天，我们来看看viterbi译码器如何实现译码。

2编码译码之前，先看如何卷积编码。

描述卷积编码器的方法有很多，按照每种描述，我们都可以实现卷积编码。

以约束长度为3，码率为1/2，生成多项式为g0=[111],g1=[101]的卷积码为例，图1左侧给出了移位寄存器电路图表示，图1右侧的表格是左侧的等价描述，显然左侧的表示更直观，右侧的表述更具体。

图1:卷积编码器的两种描述：移位寄存器和输入输出状态表卷积编码器还有一种描述：篱笆图描述。

篱笆图让Viterbi译码过程生动了许多，我认为是一个很伟大的发明，其作用和法拉力用磁感线表示磁场的存在一样，让难以理解的抽象过程瞬间活灵活现。

另外，在Turbo码的译码分析过程中，篱笆图也发挥着非常重要的作用。

图1右侧的表格可以表示如图2所示。

图2:卷积编码器篱笆图描述通过对篱笆图2进行时间上的延展，给定输入，我们可以很容易获得输出。

假设输入为(010111001010001)2(2.1)则编码输出为(001110000110011111100010110011)2(2.2)输出的获得过程如图3所示。

值得注意的是，在图3中，t=16和t=17时刻依然有0输入。

这两个0的作用是冲洗编码器，使得编码器的状态归零。

这样做的好处是Viterbi译码器知道编码器的最后一个状态是零状态。