维特比viterbi算法在C55x+DSP中的实现

基于Viterbi 算法的GMSK 信号解调方法的研究摘要：高斯最小频移键控（GMSK ）具有振幅恒定、相位连续、带宽窄、带外衰减大和对邻近信道干扰小的特点。

维特比算法是用来寻找最优路径上观察值所属的类别，本文重点研究了GMSK 信号的维特比相干解调算法—基于最大似然函数检测（MLSD ）的Viterbi 相干解调，通过信号状态的具体表示及路径度量的计算，运用MA TLAB 仿真绘制出了信号在不同信噪比下的误码率曲线，总结得出改算法具有良好的抗噪性和抗多径性能。

关键字：高斯最小频移键控；Viterbi 算法；最大似然函数检测；误码率一、引言GMSK 高斯滤波的最小频移键控调制，它是在MSK 调制的基础上发展起来的。

MSK 最小频移键控是调制指数为1/2的二进制CPFSK 连续相位频移键控。

MSK 信号的包络恒定、相位连续，且相位在一个码元周期内变化2。

虽然MSK 的功率谱密度在主瓣外衰减较快，但是仍不能满足移动通信对带外衰减的严格要求，为了使信号的功率谱密度更紧凑，带外辐射更小，频带利用率更高，于是在MSK 调制的基础上提出了GMSK 调制方式，即在MSK 调制之前加上一个高斯前置滤波器，从而改善了信号的功率谱特性，缩小带宽，减少带外辐射小和邻近信道干扰，加快带外衰减，使之能达到带外衰减在60dB 以上的通信要求。

GMSK 调制在移动通信领域得到了广泛的应用，成为了数字通信中很有优势的一种调制方式，GMSK 已经在美国蜂窝数字分组数据系统和欧洲全球通系统中得到应用。

目前GMSK 信号的解调方法有很多。

差分解调，主要指一比特差分解调和二比特差分解调，算法原理简单，但是在多径信道的环境下其误码率都比较高。

因为GMSK 调制具有非线性的特点，具有判决反馈或没有反馈的MMSE 相干检测方法是GMSK 系统的次优解调方法，而基于维特比算法的最大似然函数检测是GMSK 系统的最佳接收机，是一种有发展前景的解调方法。

1 引言卷积码的概率码最早始于1961年由Wozencraft提出的序列译码，这是第一个实用的概率译码方法，1963年Fano对序列译码进行改进，提出Fano算法，从而推动了序列译码的实际应用。

1967年Viterbi提出了另一种概率译码算法:Viterbi算法，它是一种最大似然译码算法。

在码的约束比较小时，它比序列译码算法效率更高、速度更快，译码器也较简单。

因而自Viterbi算法提出以来，无论在理论上还是实践上都得到了极其迅速的发展，并广泛应用于各种数据传输系统，特别是卫星通信系统中。

1.1 卷积码的发展卷积码是深度空间通信系统和无线通信系统中常用的一种编码。

卷积码与分组码不同，它的本码组的校验元不仅与本组的信息元有关，而且还与以前各时刻输入至编码器的信息组有关。

在编码过程中，卷积码充分利用了各码字间的相关性，而且它的信息元和校验元也比分组码小，在与分组码同样的码率R和设备复杂性条件下，无论从理论上还是从实践上都证明卷积码的性能至少不比分组码差；而且卷积码在实现最佳译码也较分组码容易。

所以从信道编码定理来看，卷积码是一种非常有前途的码类。

在IS-95.CDMA的无线数字蜂窝标滩中都采用了卷积码；在第三代无线通信系统的蜂窝结构中所采用的Turbo码，也是源自卷积码。

卷积码是由伊利亚斯（P.Elias）发明的一种非分组码。

通常它更适用于前向纠错，因为对于许多实际情况它的性能优于分组码，而且运算简单。

卷积码是一种线性树码，由于该码的输出序列是输入序列和编码器的冲击响应的离散时间卷积，故名卷积码。

其一般结构包括：一个由N段组成的输入移位寄存器，每段k个，共Nk个移位寄存器、一组n个模2和相加器，一个由n级组成的输出移位寄存器。

对应于每段k个比特的输入序列，输出n个比特。

卷积码常记为（n,k,N-1），当k等于1时，N-1就是寄存器的个数。

卷积编码器是由记忆的，即一组信息码元的校验码元不但取决于本组信息元，而且还与前m=N-1组信息码元有关。

Viterbi算法Viterbi算法是一种动态规划算法，用来寻找由观测信息产生(Observed Event)的最可能隐状态序列(Viterbi路径)，这种方法通常用在隐马尔可夫模型中。

向前算法是一个类似的算法，用来计算一串观测事件发生的概率。

这些算法都属于信息论的范畴。

这个算法做一连串的假设。

首先，观测事件和隐事件必须处于序列中。

这个序列通常是关于时间的。

第二，这两个序列需要对应，一个观测事件的实例必须与一个隐事件相关联。

第三，计算在特定时间点t的最可能隐序列必须只依赖于位于t的观测事件，和t-1处的最可能序列。

这些假设在一阶隐马尔可夫模型中都要被满足。

Viterbi路径和Viterbi算法同时遵循寻找单一最可能观测解释的相关动态规划算法。

例如，在统计分析中的动态规划算法能应用于寻找一个字符串的单个最相似上下文无关推导，即“Viterbi推导”。

Viterbi算法是由Andrew Viterbi 在1967年提出的，是一种用于有噪声的数据链路中错误纠正的模型，并广泛应用在卷积码的解码中，例如CDMA/GSM数字蜂窝，拨号调制解调器，卫星通信，深空通信和802.11无线局域网等。

现在也广泛的应用在语言理解，关键词匹配，计算机语言学，生物信息学等。

例如，在语音理解中，听觉信号被认为是观测事件的序列，文字串被认为是“潜在的原因”。

Viterbi算法能够找到对应听觉信号的最可能文字序列。

概要前面提到的假设可以被如下概括。

Viterbi算法在一个状态机的假设上做操作。

也就是说，在任何时间系统被抽象为一些状态。

这些状态是有限的，尽管很大。

每个状态被表示为一个节点。

多个状态的序列(路径)往往都能产生同一个给定的状态，但其中只有一条是最可能产生这个状态的，被称作“生存路径”。

这是一个最基础的假设，因为这个算法会检测所有的可能路径并只保留一个最可能的路径。

这种策略并不需要计算所有的路径，只需要一个状态一个路径而已。

维特⽐算法（Viterbi）及python实现样例维特⽐算法（Viterbi）维特⽐算法维特⽐算法shiyizhong 动态规划算法⽤于最可能产⽣观测时间序列的-维特⽐路径-隐含状态序列，特别是在马尔可夫信息源上下⽂和隐马尔科夫模型中。

术语“维特⽐路径”和“维特⽐算法”也被⽤于寻找观察结果最有可能解释的相关dongtai 规划算法。

例如在统计句法分析中动态规划可以被⽤于发现最有可能的上下⽂⽆关的派⽣的字符串，有时被称为“维特⽐分析”。

利⽤动态规划寻找最短路径动态规划是运筹学的⼀个分⽀，是求解决策过程最优化的数学⽅法，通常情况下应⽤于最优化的问题，这类问题⼀般有很多可⾏的解，每个解有⼀个值，⽽我们希望从中找到最优的答案。

在计算机科学领域，应⽤动态规划的思想解决的最基本的⼀个问题就是：寻找有向⽆环图（篱笆⽹络）当中两个点之间的最短路径（实际应⽤于地图导航、语⾳识别、分词、机器翻译等等）下⾯举⼀个⽐较简单的例⼦做说明：求S到E的最短路径，如下图（各点之间距离不相同）：我们知道，要找到S到E之间最短路径，最容易想到的⽅法就是穷举法。

也就是把所有可能的路径都例举出来。

从S⾛向A层共有4种⾛法，从A层⾛向B层⼜有4种⾛法，从B层⾛向C层⼜有4种⾛法，然后C层⾛向E点只有⼀种选择。

所以最终我们穷举出了4*4*4=64种可能。

显然，这种⽅法必定可⾏，但在实际的应⽤当中，对于数量及其庞⼤的节点数和边数的图，其计算复杂度也将会变得⾮常⼤，⽽计算效率也会随之降低。

因此，这⾥选择适⽤⼀种基于动态规划的⽅式来寻找最佳路径。

所谓动态规划。

其核⼼就是“动态”的概念，把⼤的问题细分为多个⼩的问题，基于每⼀步的结果再去寻找下⼀步的策略，通过每⼀步⾛过之后的局部最优去寻找全局最优，这样解释⽐较抽象，下⾯直接⽤回刚刚的例⼦说明。

如下图：⾸先，我们假设S到E之间存在⼀条最短路径（红⾊），且这条路径经过C2点，那么我们便⼀定能够确定从S到C2的64条（4*4*4=64）⼦路经当中，该⼦路经⼀定最短。

第9章Viterbi译码及其实现Viterbi译码是一种使用动态规划算法来解码卷积码的方法，它通过寻找最有可能的路径来恢复被编码的数据。

在这篇文章中，我们将介绍Viterbi译码的基本原理以及如何实现它。

1. Viterbi译码原理：Viterbi译码是一种基于有向无环图（DAG）的动态规划算法。

它的基本思想是在每一个时刻，选取最有可能的路径来解码出当前的数据。

具体来说，它会使用一个状态转移图来表示每个时刻的状态以及状态之间的转移。

每个状态表示接收到的一串码元，其中可能包含错误。

在Viterbi译码中，我们需要确定的是在给定的时刻，以及所有之前的时刻，哪个状态是最有可能接收到当前的码元。

为了实现这一点，我们需要每个时刻的状态转移图以及每个状态接收到正确码元的概率。

通过比较不同路径的概率，我们可以选择最有可能的路径。

2. Viterbi译码实现：Viterbi译码可以通过以下步骤实现：1）初始化：在初始时刻，我们首先需要将所有状态的概率初始化为1，并将每个状态的前一个状态设置为初始状态。

这样做是为了确保在选择路径时考虑所有可能的路径。

2）递推计算：从初始时刻开始，我们根据每个状态接收到的码元和切换到下一个状态的概率，更新每个状态的概率以及前一个状态。

具体来说，我们可以使用以下公式进行计算：当前状态概率=当前状态接收到的码元概率*前一个状态概率*切换到当前状态的概率3）路径选择：一旦计算出所有状态的概率，我们可以比较不同路径的概率，选择最有可能的路径。

具体来说，我们可以从最后一个时刻的状态开始，根据每个状态的概率选择前一个状态，直到回到初始状态。

4）结果恢复：一旦选择了最有可能的路径，我们可以根据这条路径中每个状态接收到的码元恢复原始数据。

通过以上步骤，我们可以使用Viterbi译码来解码卷积码并恢复原始数据。

总结：Viterbi译码是一种有效的卷积码译码方法，它使用了动态规划算法来选择最有可能的路径。

维特比算法在C55x DSP中的实现
蒋国荣;郑建宏
【期刊名称】《重庆邮电大学学报（自然科学版）》
【年(卷),期】2001(013)003
【摘要】讨论了维特比算法(VA)及其改进的软输出维特比算法(SOVA)在C55x DSP中的实现问题介绍了C55x的功能特点,并阐明它们在维特比算法三个主要步骤的运用.定量分析了维特比译码算法对C55xDSP的MIPS资源的消耗,为有关开发提供了参考依据.
【总页数】4页(P61-64)
【作者】蒋国荣;郑建宏
【作者单位】重庆邮电学院移动通信工程研究中心;重庆邮电学院移动通信工程研究中心
【正文语种】中文
【中图分类】TN911.72
【相关文献】
1.对基于C55x系列DSP在基带信号处理当中的应用与实现探析 [J], 陈聪秀
2.C55x系列DSP在基带信号处理中的应用与实现 [J], 丁晶;杨家玮;刘勤
3.C55x系列DSP在基带信号处理中的应用与实现 [J], 王文钦;查光明;蔡竟业
4.C55x系列DSP在基带信号处理中的应用与实现 [J], 丁晶;杨家玮;刘勤
5.定点DSP C55X实现浮点相关运算 [J], 孙兴邦;刘亮;夏志忠
因版权原因，仅展示原文概要，查看原文内容请购买。

3G测试系统中的Viterbi译码及其DSP实现及优化来源：EDN电子设计技术| 发表于：2007年07月10日本文相关DataSheet：TMS320C54X TMS320C55X TMS320C55x摘要介绍了一种用于测试TD-SCDMA手机终端测试平台中的关键技术——Viterbi译码。

研究用约束度K=9的卷积编码和最大似然Viterbi译码的差错控制方案，在Viterbi译码算法中，提出了原位运算度量、保存路径转移过程和循环存取幸存路径等方法，能有效地减少存储量、降低功耗，使得K=9的Viterbi译码算法可在CCS集成环境平台和TMS320C55X DSP芯片上实现，其性能指标符合3G PP通信协议标准要求，文中给出了适用于DSP编程的算法，给出了DSP 具体实现，同时给出了硬件的仿真结果。

0、引言随着TD-SCDMA产业化进程的日益明朗，3G之战还未吹号，硝烟味已弥漫了黎明前的市场。

这就要求尽快提供好的手机终端。

对手机终端的性能测试越显得迫在眉睫。

由于重邮信科3G研究院在TD方面有着很成熟的技术和经验，在此基础上我们不但推出了3G样机，而且致力于开发好的TD手机测试平台，本文所介绍的Viterbi译码方法是独具特色的TD测试平台中所用到的。

3GPP中TD-SCDMA系统采用了3种信道编码方案：卷积编码、Turbo编码和不编码。

不同类型的传输信道所使用的编码方案和编码效率是不同的。

本文介绍针对卷积编码的Viterbi译码方案。

针对DSP设计的特点，本文在不改变纠错性能的前提下提出了一系列的方法，如原位运算、保存转移、循环存取等，旨在将存储器的容量减到最小，将整体功耗降到最低。

1、Viterbi译码原理[1]Viterbi译码算法（简称VA算法）是由Viterbi在1967年首先提出的，它是一种针对卷积码的最大似然译码算法。

他不是在网格图上依次比较所有的可能路径，而是接受一段，计算、比较一段，保留最有可能的路径，从而达到整个码序列是一个最大似然序列。

DSP期末复习题及答案⼀、填空题（每空2分，共20分）1、在C语⾔和C55x汇编语⾔的混合程序设计中，C函数的参数和返回值传递到C55x的寄存器中。

在函数“long func(int *p1, int i2, int i3, int i4)”中，*p1传递到AR0寄存器，i2传递到T0寄存器，i4传递到AR1寄存器，返回值由AC0寄存器传递。

2、汇编语⾔“mov *AR0，AC0”使⽤的寻址⽅式是间接寻址模式，“mov #0x3，DPH”使⽤的寻址⽅式是直接寻址模式，“mov *(#0x011234)，T2”使⽤的寻址⽅式是绝对寻址模式。

3、指令执⾏前AC0的值是0012345678，那么汇编语句“AND #0x7f， AC0”，执⾏之后，AC0的值是0000000078。

4、C55x 的链接器命令⽂件中，SECTIONS命令的主要作⽤是告诉链接器如何将输⼊段组合成输出段，以及在存储器何处存放输出。

MEMORY命令的主要作⽤是定义⽬标系统的存储器配置图，包括对存储器各部分的命名，以及规定它们的起始地址和长度。

⼆、简述题（共40分）1、根据你的理解，试列举 DSP 芯⽚的特点？（5分）答：哈佛结构；多总线结构；指令系统的流⽔线操作；专⽤的硬件乘法器；特殊的DSP 指令；快速的指令周期；丰富的外设2、TMS320C55x 芯⽚的总线结构有何特点，主要包括哪些总线？它们的功能是什么？（6分）答：TMS320C55x DSP采⽤先进的哈佛结构并具有⼗⼆组总线，其独⽴的程序总线和数据总线允许同时读取指令和操作数，实现⾼度的并⾏操作。

采⽤各⾃分开的数据总线分别⽤于读数据和写数据，允许CPU在同⼀个机器周期内进⾏两次读操作数和⼀次写操作数。

独⽴的程序总线和数据总线允许CPU同时访问程序指令和数据。

包括12条总线，分别是：PAB和PB、BAB和BB、CAB和CB、DAB和DB、EAB和EB、FAB和FB。

3、DSP 为了降低功耗采取了哪些措施？（6分）答：双电压供电；多种⼯作模式4、TMS320C55x 的总存储空间为多少？可分为哪 3 类，它们的⼤⼩是多少？存储器空间的各⾃作⽤是什么？（6分）答：程序空间16M Byte；I/O空间64K Words；数据空间8M Words5、TMS320C55x有哪些寻址⽅式，它们是如何寻址的？试为每种寻址⽅式列举⼀条指令（6分）答：直接寻址模式，mov ＃K16，DP；间接寻址模式，mov *AR0，AC0；绝对寻址模式，mov *(#0x011234)，T2；MMR寻址模式，mov *abs16(＃AR2), T2；寄存器位寻址模式，btstp @30, AC1；圆形寻址模式。