Viterbi译码（精选七篇）
Viterbi译码 篇1
关键词：Viterbi,现场可编程门阵列,加-比-选,度量截断
0引言
随着无线通信技术的飞速发展, 电磁环境日益恶化。为保证数据的可靠性, 现代数字通信系统对抗干扰能力提出了越来越高的要求。卷积码作为一种性能优越的前向纠错编码, 能够显著提高系统的抗随机噪声性能, 目前广泛应用于各大军事及民用无线通信系统之中。
Viterbi译码是卷积码最为重要的一种译码方法。相比其他译码方式, Viterbi译码在编码约束长度较小时, 译码效率更高、速度更快、性能更好, 尤为适合具有一定规模的IC芯片编程实现。本文所讨论的Viterbi译码器是以常用的 (2, 1, 5) 最佳非系统卷积码为例, 针对编译码基本原理和在现场可编程门阵列芯片 (FPGA) 中的实现方法进行了详细分析。
1卷积码编码原理
对于 (2, 1, 5) 最佳非系统卷积码而言, 编码原理如图1所示, 其中2为码长, 1为信息元大小, 5为编码约束长度。
按照编码器的不同状态进行逻辑组合, 将每比特信息元变成2 bit伪码并行输出。
2Viterbi译码核心思想
Viterbi译码算法的核心是“ACS” (Add-Compare-Select, 即“加-比-选”) , 按照最大似然概率准则向前不断延伸所有可能的最佳译码路径。Viterbi译码速度完全不受外界条件影响 (如随机噪声) 而仅仅与具体码型有关。
译码具体步骤如下:
① 计算进入状态转移网格图中各个分支路径的度量值, 其中分支路径度量为接收码元与网格中可能码元之间的欧式距离 (软判决下) 或汉明距离 (硬判决下) , 这里采用的是3 bit软判决下欧式距离;
② 把各分支度量同各自相应的前一时刻状态度量相加求和, 得到路径度量。在同一节点状态中, 比较各个分支的路径度量值, 舍去其中度量值大的路径, 保留度量值最小的路径作为幸存路径;
③ 当存储的幸存路径超过译码深度时, 则根据译码策略选择某一条路径逐一移位输出译码结果。
3Matlab仿真及译码深度选取
在Viterbi译码器中一个很重要的参量是译码深度。译码深度的大小关系到整个Viterbi译码器的性能。译码深度越小, Viterbi译码器资源开销少、译码延时小, 但引入较大的译码性能损失;译码深度越大, 译码性能损失越小, 但资源开销、译码延时均快速增长。图2为不同译码深度下, 针对 (2, 1, 5) 卷积码的Viterbi译码结果。
从图2中可以看出, 选择6倍编码约束长度即30为译码深度的最佳值。译码深度低于30时, 性能损失较严重;高于30时, 性能增长十分缓慢, 但所需的资源开销和译码延时明显。
4译码器FPGA设计及优化
为了提高译码速度, Viterbi译码器在FPGA芯片实现上采取全并行、寄存器交换方式, 实现原理如图3 (a) 所示, 其中包括BM (分支度量管理) 、ACS (加-比-选核心单元) 、PM (路径更新管理) 、SM (幸存路径管理) 和MC (路径度量监视/控制) 等模块。译码器EDA整体实现结构如图3 (b) 所示。
在全并行译码方式下, 对于 (2, 1, 5) 卷积码而言, 存在着16条幸存路径, 8个碟形运算单元用于路径度量寄存器两两比较交换。译码路径寄存器长度为30。全并行方式可以极大地提高译码速度。在每个时钟周期内, 8个碟形运算单元同时工作, 更新32条路径的度量值, 并2选1从中取出16条幸存路径存储起来。
由于全并行方式相对串行方式, 资源开销严重。因此, 在不牺牲译码速度的前提下, 需要尽量降低系统资源消耗。相对传统的Viterbi译码设计, 本文采取的改进策略如下:
① 对于路径度量的计算, 采用查找表的方式, 将所有分支度量的可能值存入RAM中, 通过地址总线 (将接收码元与可能码元的异或值作为地址) 来读取分支度量值 (欧式距离) 。欧氏距离需要乘方和开方运算, 单独用FPGA实现十分繁琐, 采用查找表方式能够有效减少FPGA的运算压力;
② 同时为了避免路径度量寄存器超过上限值溢出的潜在隐患, 采取了度量截断的策略, 如图3 (b) 所示。即每当监视的某一路径度量值达到上限的3/4大小时, 给出路径度量寄存器近满警告, 接着将各个路径度量寄存器最高位置0 (即原度量值减去上限值的1/2) , 之后警告解除。这样就能仅存储较小的路径度量值、占用较低的资源, 来获得最佳的译码效果;
③ 在编码器端要求尾比特归零, 即要求使编码器最后返回4′b0000状态。这样, 接收端的Viterbi译码器只需始终按照第1条路径而不是从16条幸存路径中选取路径度量值最小的最佳路径 (时刻在变化) 进行移位输出即可。该方法大大减少了每次挑选最优路径的冗余计算量和资源开销。
表1为本文采用的改进型全并行Viterbi译码方法与Altera QuartusⅡ 7.1开发环境所集成的Viterbi IP Core (同样是全并行方式) 在CycloneⅡEP2C35 FPGA芯片上利用Synplyfy pro 9.4工具综合后的资源消耗对比。
在表1中, 可以看出采用查找表方式、度量截断以及尾比特归零策略的全并行Viterbi译码器能够有效控制资源消耗, 在速度和资源占用上获得很好的平衡。
5实验仿真及结果分析
基于译码设计方法, 在Modelsim 6.1f仿真环境中进行了RTL行为级功能验证。利用Verilog HDL编写好的Viterbi译码模块作为待测模块。顶层测试文件利用PN序列发生器产生的一连串随机数, 经过 (2, 1, 5) 卷积编码和量化后, 调用Viterbi译码模块进行测试并与延时后的原PN序列作对比。仿真示意波形如图4所示。
从图中可以看出, 由于译码深度为30, 译码过程滞后30个时钟周期便能输出正确的译码结果和译码有效标志位, 始终无误码出现。
6结束语
本文提出的Viterbi译码方法能够充分发挥FPGA并行处理速度优势。并且能在不牺牲运算速度的前提下, 大大降低了芯片资源消耗, 在性能和资源方面均衡发展。该Viterbi译码方法尤适用于对运算速度要求高、对资源占用较为敏感的高速数字通信系统之中。
参考文献
[1]WICKER S B.Error Control Systemsfor Digital Communication and Storage[M].NewJersey:Prentice-Hall, 1995:290-332.
[2]LINS, COSTELLO D J.Error Control Coding:Fundamentals and Applications[M].London:Prentice-Hall, 1983:315-349.
[3]LOU H L.Implementing the Viterbi Algorithm:Fundamental and Realtime Issues for Processor Designers[J].IEEE Signal Processing Magazine, 1995 (9) :42-52.
[4]CHAN M H, LEE W T, LIN M C, et al.IC Design of an Adaptive Viterbi Decoder[J].IEEE Transactions on Consumer Electronics, 1996, 42 (1) :52-62.
Viterbi译码 篇2
在长期演进(LTE)系统中,为了获得正确无误的数据传输,采用了差错控制编码技术。咬尾卷积编码和Viterbi译码就是一种有效的前向纠错方法,它具有一定的克服突发错误的能力。与传统的卷积码[1]相比,咬尾卷积码没有结尾清零比特,编码时使用码块的最后m个信息比特来初始化编码寄存器,使编码器的初始状态和结束状态相同,从而可以提高编码效率,节约带宽资源。Viterbi译码算法是由Viterbi于1967年提出的一种最大似然译码算法,通过计算累计码距,在相应卷积码网格图上寻找最大似然路径,再根据这条路径所通过的延时器状态来重构发送序列。
数字信号处理器(DSP)具有精度高、灵活性好、可靠性高、时分复用和易于大规模集成等优点,得到了广泛的应用。在现代通信系统中,它占据着非常重要的地位,可以说在通信系统中越来越多的功能部件都是采用DSP技术实现的。本文研究了一种适用于时分-长期演进(TD-LTE)综合测试仪表系统的最优的Viterbi译码算法,并重点介绍了其在TI 公司DSP芯片TMS320C64x上的实现。
1 TD-LTE系统中的咬尾卷积码
LTE作为准4G技术,以正交频分复用(OFDM)和多输入多输出(MIMO)技术为基础,下行采用OFDM多址技术,上行采用单载波频分多址(SC-FDMA)技术,在20 MHz频谱带宽下能够提供下行100 Mbit/s、上行50 Mbit/s的峰值速率。
LTE TDD (亦称TD-LTE)系统采用的是结构为(3,1,7)的咬尾卷积编码方案[2],如图1所示,它使用码块的最后6 bit信息来初始化6个编码移位寄存器,使编码器的初始状态和结束状态相同。
2 Viterbi译码算法的仿真与选择
与传统的Viterbi译码不同,咬尾卷积码的Vit-erbi译码不知道编码器的初始状态和结束状态,因此,译码难度增加。目前咬尾卷积码Viterbi译码算法主要有循环维特比译码算法(CVA)和环绕维特比译码算法(WAVA)。通过研究分析可知,在众多的算法研究文献中,文献[3]提及的一种M比特重复循环维特比译码算法(N+M-CVA)可以说是后来很多改进算法的基础;文献[4]提出了一种有界距离循环维特比译码算法(BDD-CVA),这种算法通常只需将码块部分重复就可得到最终的译码结果,其优点是译码计算复杂度较低;WAVA[5]通常要将码块重复多次才会得到最终的译码输出,其优点是误比特率相对降低了,但译码计算复杂度却相应增加了。在所有的Viterbi译码算法中,最大似然维特比译码算法 (ML-VA)的误比特率是最低的,但是由于其惊人的译码计算复杂度,导致其几乎很难用于实际系统中。图2、图3为以上各种译码算法的误比特率仿真比较,码块大小分别为40和150 bit。其中L次迭代环绕维特比译码算法(L-WAVA)是在WAVA基础上稍加改进得到的。
从图中可以看出不管码块的大小如何,L-WAVA的译码误比特率都最接近ML算法。作为仪表系统的开发,系统对精度的要求比一般的终端系统更高,同时考虑到系统硬件配置也比一般的终端产品好很多的情况,系统最终采用了译码性能最优的L-WAVA算法,其算法描述如下:
(1) 初始化所有路径度量值为0,对码块执行VA译码算法,第1次迭代结束后找出具有最大度量的路径,回溯,检查首末状态是否相同,相同则译码输出,译码结束;否则,进入下一步。
(2) 在第i (i>1)次迭代开始时,用第i-1次迭代结束时的状态度量信息初始化第i次迭代的初始状态度量,并继续进行VA译码算法;迭代结束时,选择最优路径回溯到初始时刻(0时刻),比较第1次迭代到第i次迭代各次迭代首末状态是否相同,只要其中有一个相同,则译码输出对应迭代的码块,否则进行第i+1次迭代,直到达到最大迭代次数L。
(3) 若在第L次迭代做完VA译码算法后没有发现任何一次迭代首末状态相同,则译码输出第[L/2]+1次迭代的译码数据,将其作为最终的译码输出。
实验表明,本系统中L取值为3最为合适,既可使译码误比特率足够低,又不至于使译码延迟过大。可在保证系统高精度性能的前提下,尽可能地优化系统对其他资源的消耗,从而使整个系统性能最优。
3 Viterbi算法的DSP实现
3.1 硬件简介
TMS320C6000系列DSP是TI公司1997年2月推向市场的高性能DSP,综合了目前DSP性价比高、功耗低等优点。TMS320C64x系列在TMS320C6000 DSP芯片中处于领先水平,它不但提高了时钟频率,而且在体系结构上采用了VelociTI超长指令字(VLIW)结构[6]。片内有8个独立功能单元的内核,每个周期可以并行执行8条32 bit指令,最大峰值速度4 800 MI/s,2组共64个32 bit通用寄存器,32 bit 寻址范围,支持8/16/32/40位的数据访问,片内集成大容量静态随机存取存储器(SRAM),最大可达8 Mbit。由于具有出色的运算能力、高效的指令集、大容量的片内存储器和大范围的寻址能力,该系列特别适用于无线基站、测试仪表等对运算能力和存储量有高要求的应用场合。
3.2 Viterbi译码算法处理流程
Viterbi算法根据可能的状态转移进行译码,状态转移可用网格图表示。Viterbi译码过程就是根据接收的数据符号,按最大似然译码准则找出编码器在网格图上所走的路径,其处理过程如图4所示。由图4可以看出Viterbi算法的主要实现过程可分为4大部分:分支度量计算、加比选、幸存路径存储和回溯译码输出。
3.3 Viterbi译码算法程序实现
3.3.1 程序初始化
(1) 定义一个路径度量表state_metric[64][2],初始化清零。为了防止溢处,表中每个单元内存大小分配一个字(32 bit),在VA译码加比选的过程中交替更新为当前时刻的累积度量,如偶时刻时第2列为被更新的度量,奇时刻时第1列为被更新的度量,这样在加比选结束时根据时刻的奇偶性即可判断最终的路径度量存储的位置,从而查找出最优路径的末状态。
(2) 定义一个幸存路径状态表survivor_state[64][3*K],K为码块的长度,此表用于存储在整个译码过程中记录的所有可能的幸存状态,因为状态值的范围为0～63,所以表中每个单元内存大小分配一个字节(8 bit)即可,一个字节为TMS320C64x芯片可直接访问的最小数据单元。
(3) 定义一个幸存路径状态序列表state_sequence[3*K],与(2)同理,表中每个单元内存大小分配一个字节(8 bit)即可,回溯时将最优路径的各个状态存储到此表中,最后判断各码块首末状态是否相同,从而判断是否有译码输出,结束译码。
(4) 定义一个输出码字常量表output_table[32], 由于输出码字的范围为0～7(8进制),因此,为了便于访问,表中每个单元内存大小分配一个字节(8 bit),用于存储j状态在输入比特0时的输出码字,以便计算各状态的分支度量。
3.3.2 度量值更新计算
Viterbi算法的运算时间大部分消耗在距离量度的更新上,每一个符号间隔期间,距离量度需更新一次,因此优化度量值的计算是降低整个译码过程时间消耗的关键,整个实现方法的优劣性也都集中体现在此度量更新计算过程中。此过程可以分为以下4个方面:
(1) 分支度量简化。Viterbi译码的分支度量计算分为硬判决和软判决两种,硬判决用汉明距离表示,软判决用欧氏距离表示。由于在误比特性能方面软判决比硬判决优2 dB[7],因此本系统采用软判决方法来计算分支度量。设符号间分支度量用BM表示,根据欧氏距离计算公式有
(2) 软比特量化。在接收端采用软解调,使得接收数据在译码器的输入端量化为3 bit,量化范围为-4～3,即将0量化为3,1量化为-4;将网格输出码字进行映射,0映射为+1,1映射为-1,这样在计算分支度量时就将乘法简化为加减法,减少了运算量,提高了运算速度。如接收到的码字为(-4,+3,+3),网格输出码字为(1,0,1),则分支度量为-(-4)+(+3)-(+3)=+4。
(3) 蝶形运算。根据卷积编码的性质,状态转移具有图5所示的蝶形结构。图5表明连续的两个状态有相同的转移状态,各状态输入比特0与输入比特1有相反的分支度量,且j状态与j+1状态对称,其中j应满足j mod 2=0。因此,利用此对称性,在计算分支度量时只需计算状态j在输入比特0时的分支度量G1,则输入比特1时的分支度量为-G1,j+1状态在输入比特0和1的分支度量分别为-G1和G1,-G1可通过‘NEG’指令将G1取反得到。这样,每次计算一个分支度量就等于计算了两个状态、4个输入比特的分支度量,计算量降低了3/4。
(4) 比较选择、保存最大累积度量和最优状态。将j和j+1状态的累积度量与各自到达状态(j+1)/2的分支度量相加,得到(j+1)/2处的两个累积度量,进行比较,将大的度量值存储到state_metric,并将其相应的状态j或j+1存储到幸存路径survivor_state中;到达状态(j+1)/2+32的处理方法相同。
3.3.3 路径回溯
(1) 确定末状态。
在加比选操作完成了一次迭代后,根据算法此时应回溯一次。首先查看当前时刻的奇偶性,如果为奇时刻,则在state_metric[64][2]的第1列中查找最大度量值和其对应的状态,并将此状态作为回溯首状态,亦即最优路径的末状态;如果为偶时刻,则在state_metric[64][2]的第2列中查找。
(2) 根据末状态回溯。
将末状态存储到state_sequence中的对应位置,其值指示的为前一时刻survivor_state中的幸存状态的位置,依次向前回溯,取出最优路径的各状态存储到状态序列state_sequence中。
(3) 译码输出。
在回溯完毕后,检查state_sequence中各次迭代的首末状态是否有相同。如果有相同,则译码输出相应码块的数据,将其作为最终的译码输出数据;如果没有相同,但是迭代次数达到了3次,则译码输出第2个码块的数据。译码输出实现方法如下:若(下一状态-当前状态≫1)>0则输出1,否则输出0。
4 性能分析
在DSP软件实现中,通过指令并行,尽量优化程序[8]循环体,减少或消除程序中的“NOP”指令,在码块大小为50 bit时,通过在CCS3.3上仿真运行程序,在理想信道情况下,整个译码过程耗时47 993个指令周期,此时因为输入数据没有错误,译码程序只迭代一次就得到了正确的译码输出;在信道条件极差的情况下,译码程序需迭代3次才能译码输出,此时译码耗时为142 545个指令周期。TMS320C64x芯片的主频一般为1 GHz,一个指令周期耗时为1 ns,因此本文中的DSP实现可达到约350.75～1 041.7 kbit/s的译码速率,且误比特率相当低,满足系统的译码要求。
5 结束语
文章从理论仿真出发,根据TD-LTE系统特性,通过仿真比较为系统选择了一种最优的Viterbi译码算法,并在TMS320C64x芯片上实现了这种算法。重点讲述了Viterbi算法在DSP中的实现方法,程序运行结果表明,本算法具有较低的译码误比特率和较高的译码速率,能够满足LTE系统的需要,具有可行性和高效性。
摘要：文章基于长期演进(LTE)系统的咬尾卷积码,通过对多种Viterbi译码算法的仿真比较,为时分长期演进(TD-LTE)测试系统选择了一种最优的Viterbi译码算法,并在TMS320C64x数字信号处理器(DSP)中实现了这种算法。提出了一些具体的软件优化策略和技巧,对加比选蝶形运算进行了大量简化。通过译码程序在CCS3.3中的运行结果,验证了该算法及优化策略和技巧的可行性和有效性。
关键词：长期演进,Viterbi译码,软判决,数字信号处理器实现
参考文献
[1]张宗橙.纠错编码原理和应用[M].北京:电子工业出版社,2003.150-198.
[2]3GPP TS 36.212 v8.7.0-2009.Multiplexing andchannel coding(Release 8)[S].
[3]CoxAn Richard V,Sundberg Carl-Erik W.An Effici-cent Adaptive Circular Viterbi Algorithm for Decodinggeneraliized Tailbiting convolutional Codes[J].IEEETransactions on Communications,1994,43(1):57-68.
[4]Anderson John B,HladikStephen M.An Optimal Cir-cular Viterbi Decoder for the Bounded Distance Criteri-on[J].IEEE Transactions on Communications,2002,50(11):1 736-1 742.
[5]Shao Rose Y,Lin Shu,Fossorier Marc P C.Two De-coding Algorithms for Tailbiting Codes[J].IEEETransactions on Communications,2003,51(10):1 658-1 665.
[6]Texas Instruments Incorporated.TMS320C64x/C64x+DSP CPU and Instruction Set Reference Guide[EB/OL].http://www.ti.com.cn,2008.
[7]张力军,张宗橙,郑宝玉,等(译),Proakis John G(著).数字通信(第四版)[M].北京:电子工业出版社,2003.340-371.
Viterbi译码 篇3
Viterbi译码算法是由Viterbi在1967年首先提出的一种针对卷积编码的一种最大似然译码算法。它的译码思想不是在网格图上依次比较所有的可能路径, 而是接收一段,计算、比较一段,保留最有可能的路径,从而达到整个码序列是一个最大似然序列。由于它在码的约束比较小时,算法效率高、速度快,译码器也较简单,所以在约束长度小于10的情况下被广泛使用。这种算法在实现时由于DSP(Digital Signal Processor,数字信号处理器)的储存特点,度量值累加后可能会产生溢出,导致译码错误,所以必须对不断累加的度量值进行处理使它在保持在适当的范围内。本文基于TI(Texas Instrument,德州仪器)公司的CCS集成环境平台和TMS320C55X芯片实现Viterbi译码,其对应的卷积编码约束长度为5,编码速率1/2。下面首先介绍分支度量的计算方法,再分析各种防溢出的措施。
1 分支度量的计算方法
在进行译码时,Viterbi译码器每收到一个符号就进行状态转移。Viterbi译码算法必须计算前一个状态到各个新状态的分支度量值。当采用硬判决输入时,分支度量值可用汉明距离表示;若用软判决输入时,采用欧氏距离来计算。对于编码速率为R=1/C的卷积码来说, 欧氏距离:
T=undefined[SDn+Gn(j)]2
其中SDn为接收序列,Gn(j)为网格图上每个路径状态的期望输入值,j是路径指示值,C为编码速率的倒数,将上式展开得:
undefined
对于所有分支来说,SDundefined和Gn(j)2的值都是一样的,只是一个常数,在进行各路径度量值比较时,可以不考虑。这样就有简化的分支度量值:
undefined
省去上式前面的负号,则在分支比较时取最大值。对于编码速率1/2的卷积码,它的分之度量即为:
T=SD0G0(j)+SD1G1(j)
Gn(j)用双极性表示,即0用+1表示,1用-1表示。根据此公式和如图1(a)和(b)所示的碟型结构可以推导出每一步的度量值变化规律为:若接受到的数据也是双极性的,则当SD0和G0(j)相等,SD1和G1(j)相等时度量值加2;若他们中有一个不相等,则度量值不变;若两个都不相等,则度量值减2。
2 度量值防溢出的方法
首先看不对度量值采取防溢出措施得到的结果,如图2所示。图为误码率几乎为0的情况下最大似然路径的度量值累加情况,图中Y轴为度量值,X轴为归一化的时间节点,每个时间结点代表一次状态转移。可以看到,经过每个节点度量值都要增加2,即在不采取任何措施的情况下,度量值将以斜率2无限增长。因为DSP的累加器ACX的长度是有限的,所以如果储存的度量值超过了累加器的储存范围就会产生溢出错误,这种错误将会严重影响之后译码过程,造成译码错误。因此,必须采取措施来防止溢出,一般来说,防溢出的方法必须满足以下两个条件:
① 能够抑制度量值的无限增长趋势。
② 影响要均衡,不能破坏各条路径度量值的相对大小信息,否则将影响加比选结果,造成译码错误。
可以用某种附加算法使所有度量值在原来基础上定期降低,以延缓甚至停止其增长趋势。有3种方法可以满足以上条件,他们分别是定期移位法,减最小值法和减固定值法。下面依次介绍这3种方法及其性能。
(1)定期移位法
定期移位法是对度量值周期性地右移,等效于对所有度量值周期性的除以一个常数。通过对最大似然路径的度量值分析得出,其增长规律呈线性。若将使度量值在线性增长基础上再以幂级数阶段性缩减,这种相反作用的结果将使得度量值最终趋于稳定。若以k个时间节点为周期,对度量值进行1比特移位处理,经过一定移位周期之后,线性增长与移位缩减达到平衡,度量值将到达固定峰值Ttop,并停止增长。容易推得Ttop的表达式为:
Ttop=2k*2-1
度量值达到固定峰值需要一定时间,其表达式为:M=2+log2k,单位为移位周期。
图3为约束长度为5,以16个时间节点为周期,即k=16,使用定期移位处理后得到的最大似然路径的度量值仿真曲线。由图3中看出,经过M=2+log216=6个移位周期后,度量值到达稳定峰值Ttop=2*16*2-1=63。
在DSP实现中使用此方法,所有的度量值最多使用6个2进制位即可保存。使用此方法的整个译码过程使用了53881个机器周期(本文的所有测试结果都是基于译码器输出234个比特序列的译码程序,由于程序本身加入了大量附加程序,所以机器周期仅用于比较各算法执行周期的相对长短,并不代表程序的本身的译码效率)。
表1显示了对于不同k值使用此方法所得到的参数:
和另外两种方法对比,由表1可以看出定期移位法是一种比较节省储存空间和执行时间的算法。但它是一种会损失度量值精度的算法,它体现在两个方面:一是数据在右移时采取直接丢弃最低位的方法,即如果两个度量值为30和31,移位后都为15。二是当前计算出的度量值与之前的已经累加的度量值并不处于同一个数量级,而是2的指数关系。所以如果在误码率较高的信道中使用这种方法可能会导致译码错误。
(2)减最小值法
减最小值法即对所有度量值都周期性减去前一步的所有状态度量值中的最小值,以达到抑制度量值的无限增长趋势。此方法是基于Viterbi译码的这样一个特性,即对于码率为1/2,约束度为p的卷积码的硬判决译码,在每一步的度量的最大值与最小值的差不超过2(p-1)。由此得出使用此方法得到的最大似然路径的度量值的最大值Ttop的表达式:
Ttop=2(p-1+k)
图4为约束长度为5,以16个时间节点为周期,将最大似然路径的度量值进行定期移位处理后得到的仿真曲线。图中Ttop=42,这是因为度量值的起点是从2开始的。可以使用6位2进制储存空间进行储存。由图4可以验证最大度量和最小度量之间的差值都是2(p-1)=8。由于需要比较出最小值,所以此方法所需的机器周期较多,为56484。
表2给出当p=5时,对于不同的k使用此方法所得到的参数:
从表2可以看出减最小值法也是一种节省储存空间的算法,且它不像定期移位法那样会有度量值精度的损失,但它需要有更长的处理时间
(3)减固定值法
以上两种方法都可以保证所有的度量值为正,如果利用DSP以补码来保存负数的特点,就可以保存负的度量值,这样就可以不作比较,周期性地直接对所有度量值减去一个固定值,只要这个值能够抑制度量值的无限增长趋势即可。因为每一步度量值的最大值与最小值的差不超过2(p-1),因此本方法也可以抑制度量值的负方向的无限增长。若以k个时间节点为周期,这个值可以取为2k。则处理后的最大似然路径的度量值Ttop=2k。
图5为约束长度为5,以16个时间节点为周期,将最大似然路径的度量值进行减固定值处理后得到的仿真曲线。图中Ttop=32,因为非最大似然路径中的度量值会出现负值,所以必须用储存单元的最大位数来保存补码。TMS320C55X系列采用字储存的方式,所以需要用16位2进制数来保存。此方法由于省去了比较和移位,所以只用了53540个机器周期。表3给出了对于不同k值使用此方法得到的参数。
减固定值法没有度量值的精度损失,且使用的机器周期是3中算法中最少的,但需要的储存空间也是最多的。
3 结束语
由以上分析可以看出3种方法各有其特点:从译码性能上来说,由于定期移位法会损失精度,所以在误码率较大的信道中一般不采用这种方法,但若在误码率低的信道中使用此方法,将对节省时间和空间起到很好的效果。从机器周期上说,减最小值法的机器周期最长,所以一般用在芯片速度快或对实时处理要求不高的场合,可以达到节省存储空间的目的。从存储空间上来说,减固定值法使用固定长度的储存空间,对内存空间的占用大,但它实现简单,机器周期短,可以用于对实时处理要求较高的场合,以空间换时间。
以上3种方法都有一个共同的特点,即使用的存储空间越多,机器周期就越小。这是时间和空间的基本矛盾,实际应用中应权衡各种因素,多实验,以达到最佳的译码效果。
参考文献
[1]张宗橙.纠错编码原理和应用[M].电子工业出版社,2003.
[2]Viterbi A.Very rowrate convolution codes for maximumtheoretical performance of spread spectrum multiple-access systems[J].IEEE Transactions on Selected Areas in Communication,1990(4):641-649.
[3]申敏,邓矣兵,郑建宏,等.DSP原理及其在移动通信中的应用[M].人民邮电出版社,2001.
[4]陈源,江修富.Viterbi算法的关键问题研究及DSP实现[M].2005.
Viterbi译码 篇4
Viterbi译码算法是针对卷积码的性能最好的译码算法,TI公司的55系列DSP芯片兼容54系列DSP芯片,而且具有功耗更低、运算速率更高等特点,广泛地应用于现代数字通信系统中。目前现有的文献中,对怎样用C语言编程实现Viterbi译码算法论述不多。文献[1,2,3]等用汇编语言编写,可读性较差,文献[4,5,6]仅仅给出了程序的简化流程图及部分函数的介绍,并没有对Viterbi算法的纠错性能进行详细验证。本文针对常用的(2,1,7)卷积码,设计实现了一种全并行的连续译码的Viterbi算法,硬判决译码,在VC++6.0上开发,再移植到CCS平台上运行,采用文件读写操作的方法进行纠错性能验证。仿真实验结果表明其纠错性能完全达到甚至优于理论上Viterbi译码算法纠错性能的极限。
1 Viterbi译码算法的原理及程序流程
Viterbi译码程序由以下模块组成:文件读、写操作模块,BMU模块,ACS模块,ACS迭代计算模块,最小状态值计算模块,回溯模块和ram读写模块等,每个模块用相应的函数实现。状态数S=64,回溯深度tblen=42,采用4个数组存储4个ram块的译码结果,分别为Pre_ram[48]用于存储前48时刻的译码结果,ram1[42]、ram2[42]和ram3[42]分别循环存储接下来每42时刻的译码结果,实现连续译码。N为进入(2,1,7)编码器的比特数。
1.1 头文件定义
为节省篇幅,没有全部列出来。
1.2 Viterbi译码算法程序流程
具体的译码流程如图1所示。
2 各功能模块的函数设计
2.1 File读操作模块
函数void File_Read(uint y0[N],uint y1[N])完成此功能,y0[N]和y1[N]是输入Viterbi译码器的输入待译码数据。
2.2 BMU模块
函数void Bmu(uint y0,uint y1,uint b[N1])完成此功能,b[4]是一个1行4列的数组,用于返回输入值{y0,y1}与00,01,10,11的汉明距离。实际编程时,用指针p指向b[4]。
2.3 前6个时刻SM值计算模块的设计
函数void Pre_ACS(uint y0,uint y1,uint ACS_SM[N2],uint b[],uint i)完成此功能,ACS_SM[N2]是每一时刻对应的S0-S63的SM值,因为ACS_SM[N2]要保持上一时刻的计算结果,所以数组ACS_SM[N2]为static(静态)数组。i为时刻数,i=0-5。
2.4 ACS模块的设计
函数void ACS(uint SM1,uint BM1,uint SM2,uint BM2,uint data[2]),SM1和SM2是路径度量值,BM1和BM2是分支度量值。data[2]是一个1行2列的数组,这里设定,如果SM1+BM1≥SM2+BM2,data[0]= SM2+BM2,data[1]=1;如果SM1+BM1<SM2+BM2,data[0]= SM1+BM1,data[1]=0。
2.5 ACS迭代运算模块的设计
函数void ACS_diedai(uint y0,uint y1,uint ACS_SM[N2],uint xingcun[N2])完成此功能,用指针p1和p2分别指向数组ACS_SM[64]和xingcun[64]),用于返回每次计算更新后64个状态的SM值和幸存值,为防止溢出,如果64个状态的SM值都大于8,则所有的SM值都减去8。
2.6 最小值所在状态模块的设计
函数uint Small_State(uint ACS_SM[N2])实现的功能:在输入某时刻63个状态的SM值时,输出最小SM值所在的状态值。该状态值用于回溯计算的状态起始处。
2.7 状态回溯模块的设计
函数void State_Huisu(uint Min_State,uint xingcun[N2],uint state[2])实现的功能:在给出某一状态及某时刻该状态的幸存值计算预译码值和下一时刻的状态。
2.8 ram_Pre回溯模块的设计
函数void Pre_ram_Huisu(uint Huisu_State_pre[N3+1],uint Xingcun_Pre[N3][N2],uint Yima_Pre[N4])完成此功能。该函数实现的功能是对ram_Pre模块通过回溯得到预译码值。预译码值存入数组Yima_Pre[6]- Yima_Pre[47]中,与实际的译码结果顺序相反。
2.9 前6个时刻状态回溯计算模块
函数void Pre_Start_Huisu(uint Start_State,uint Yima_Pre[N4])完成此功能, Start_State= Huisu_State_pre[0],用这个值计算t=0-5时刻的预译码值,存入Yima_Pre[0]-Yima_Pre[5]。
2.10 ram回溯模块的设计
函数void ram_Huisu(uint Huisu_State[N3+1],uint Xingcun[N3][N2],uint Yima[N3])用于完成此功能。Huisu_State[42+1],是一个1行43列的数组,存放每一回溯时刻的状态值,Xingcun[N3][N2]是一个42行64列的二维数组,存储用于回溯的42个时刻每一时刻的幸存值。Yima[42]用于存放每一时刻的预译码值,该函数可以被ram1,ram2,ram3调用。
2.11 File写操作模块
函数void File_Write(uint yima[N])用于把数组yima[N]写入yima_out.txt文件中,用来与Yuanbianma.txt文件进行误码率计算。
3 纠错性能测试
对设计的Viterbi译码器C程序纠错性能的测试,采用的方法见文献[7]:进入(2,1,7)编码器的比特数N=20 000个,可动态更改。同时把数据写入到Yuanbianma.txt文档中保存。编码后比特数为2*N=40 000个,再在Matlab中对编码数据加扰码,然后把有扰码的数据写入到y0.txt文档和y1.txt文档中。C程序读入数据到数组y0[N]和y1[N]。
程序运行完成后,译码数组yima[N]的值写入到yima_out.txt文件中。最后把yima_out.txt中的数据导入到Matlab中,计算误比特率。误码形式是以100个比特为一组,编码后每100个比特随机错5位、6位、7位、8位和9位等,还有一种错误形式是对编码数据加高斯白噪声,比较不同信噪比(SNR)条件下的误比特率(BER)。
由图2和图3的曲线可以看出,本文用C语言设计的Viterbi译码器程序,其纠错性能不仅完全达到理论上vitdec()函数纠错性能的极限,而且其纠错性能甚至优于理论算法的纠错性能。
4 结束语
针对卷积码的Viterbi译码算法,本文用C语言进行了各功能函数的设计,给出了完整的程序流程图,并采用大容量编译码数据对Viterbi译码程序进行纠错性能的测试。仿真实验结果表明,本文设计的Viterbi译码程序完全达到甚至优于Viterbi理论算法的纠错性能。采用C语言设计,平台移植性好,程序可读性好。因此,本文设计的Viterbi译码程序具有较好的实际应用价值。
摘要：为了在DSP中实现Viterbi译码,用C语言编程实现了一种全并行连续译码的Viterbi译码算法。其各功能模块用函数设计,纠错性能的测试和验证采用文件读写的方法,便于处理大容量的编译码数据,且能容易地修改错误的形式。仿真测试结果表明,该Viterbi译码算法的纠错性能完全达到甚至优于Viterbi理论算法纠错性能的极限,采用C语言设计,程序可读性好,且便于在不同系列DSP平台之间移植。
关键词：Viterbi译码算法,文件读写操作,C语言编程,纠错性能验证
参考文献
[1]吴莉莉.刘益成.用TMS320C54X实现Viterbi译码器[J].单片机与嵌入式系统应用,2004,4(4):19-21.
[2]董鹏,张锁熊,田迎举.数字卫星通信中的Viterbi算法及DSP实现[J].现代电子技术,2003,2(5):31-33.
[3]吕圣洁,李小文,张传达.适用于TD-SCDMA系统的Viterbi译码及其DSP实现[J].微计算机信息,2008,24(4):166-168.
[4]孙延鹏,赵雪莹,博海玲.基于DSP的Viterbi译码器的实现[J].沈阳航空工业学报,2004,21(4):82-84.
[5]刘少阳,邹永.(2,1,7)卷积编码及其维特比译码算法的软件实现[J].信息与电子工程,2006,4(6):467-469.
[6]赵冰.卷积编码及基于DSP的Viterbi译码器设计[J].信息与控制,2002,31(5):473-476.
Viterbi译码 篇5
传统的Viterbi译码器主要包括支路度量单元(BMU)、加比选单元(ACSU)以及幸存路径存储单元(SMU)。其中SMU根据各状态的幸存路径得出译码信息,其实现方法有两种:寄存器交换法(RE)和追踪回溯法(TB)。传统的寄存器交换法需要在译码过程中不断进行寄存器交换存取操作,对于约束长度较大、状态数较多的情况,硬件功耗较大;而追踪回溯法无需进行复杂的寄存器交换,每一个译码时刻只需变动少量RAM,实现功耗较小。因此关于追踪回溯法的Viterbi译码器研究甚广[1,2,3]。但是TB方法的译码延时约为RE方法的4倍[4],无法满足对实时性要求高的无线通信系统(如无线局域网)的性能要求。
基于对译码性能、功耗以及延时的考虑,提出一种新型的指针反馈式低功耗Viterbi译码器。该译码器采用新的译码单元取代SMU,利用译码路径从初始状态0开始的特点,通过每一时刻通过不断更新的唯一状态译码指针,结合加比选单元输出的状态译码信息,指示出当前时刻的译码路径状态走向,并输出当前译码结果。FPGA实现结果表明,对于(2,1,7)卷积译码延时只为2个时钟周期,实时性好。此外,该方法实现的译码器比传统的追踪回溯法译码器功耗降低60%,并且实现较好的译码性能。
1 指针反馈式Viterbi译码基本原理
传统的Viterbi译码按照最大似然估计原则,通过计算每一时刻可能的路径值,最终找出一条最大似然路径作为译码输出路径。
本文提出的指针反馈式Viterbi译码利用传统译码器每次译码从初始状态0开始的特点,并且在译码过程中,使前一时刻某状态只与当前时刻另一状态存在一对一指向关系,从而在每一时刻确定译码路径。与此同时,通过状态指针不断更新当前时刻译码路径上的状态,实时输出译码结果。但是这种方法在遇到输入序列某区域存在较多错码情况时,很有可能选错译码路径而导致大面积译码错误。为了克服上述缺点,卷积编码器必须做出简单调整:当编码L(L≥4)次后,重新复位输入,使译码重新从状态0开始,从而有效阻隔输入错码引起的译码错误的扩散。在信噪比较高的情况下,该译码器能够在功耗、延时以及性能上得到保证。
为了更好地说明所提出的Viterbi译码器算法,现以约束长度K=3、编码率r=1/2生成多项式g0=1118,g1=1018,并且以L=10的卷积编码器对数据(01011101001000)进行编码得到(00,11,10,00,01,10,01,00,10,11,11,10,11,00),并经过噪声干扰,对该组噪声数据进行软判决处理,其译码过程如图1所示。根据状态转移关系,状态0或状态2可能指向下一时刻的状态0或状态1。当t=1时,状态0与状态1幸存路径均源于t=0时的状态0,为了使相邻时刻状态转移不出现分叉情况,此时需要对状态0和状态1更新后的累计路径距离进行最小值比较,较小的一方状态指向不变,结果从t=0到t=1,状态0指向状态0。而原本状态0指向状态1的情况,改变成状态2指向状态1(即图中虚线表示),从而实现相邻两时刻之间状态转移的单一指向性。为了演示方便,图1中只给出t≤4时改进后各状态幸存路径情况。另外,从图中看出译码路径每时刻经过的译码状态的最低位(最低位以下划线标示)与此刻译码比特相同,因此可以采用状态指针的方法将其初始化为状态0,每一时刻译出的码比特反馈更新状态指针,进行实时译码追踪。此外,由于L=10,在t=10时,状态重新复位到状态0,使译码器重新从状态0出发以实现连续译码。
2 指针反馈式Viterbi译码器整体设计
指针反馈式Viterbi译码器整体结果如图2所示,其中包括支路度量单元(BMU)、改进型加比选单元(MACSU)以及指针反馈追踪(PFPT)模块。本文基于802.11a/n,K=7,r=1/2,g0=1338,g1=1718卷积编码,采用4比特软判决对译码器进行硬件设计及实现。
2.1 支路度量单元(BMU)
支路度量单元负责将接收到的编码数据与参考数据进行各状态支路距离计算。理论上在进行软判决处理时,支路距离采用欧氏距离计算方法。但是传统的欧氏距离需要进行开根号与平方操作,因此硬件实现消耗资源高。本文给出一种改良的距离计算方法,数据量化范围从0~15共15个区间,与参考文献[5]提出的14个区间量化相比,计算精度上升。各支路距离的表达式为:
其中,BM00,BM01,BM10,BM11表示各状态转移时所有可能出现的支路距离情况。由式(1)看出,各支路距离计算只需通过简单的将输入软数据进行取反和加法的操作,硬件消耗资源少。图3为BMU的硬件实现图。
2.2 改进型加比选单元(MACSU)
MACSU由(2K-1)/2(即32)个改进型蝶状加比选基本单元MACS组成,其中每个MACS包含传统的加比选操作。译码过程中,MACS输入与输出状态转移关系如图4所示。其中St-1(i)表示t-1时刻第i个状态。由图可知,在t-1时刻状态i和状态j均有可能跳转到t时刻状态p和状态q。
在硬件实现时,每个MACS单元结构如图5所示。其中,PMt-1(i)表示t-1时刻状态i的累计路径距离,PMt(p)表示t时刻状态p更新的累计路径距离,BM(i,p)表示由状态i转移到状态p时对应的支路度量距离。因此,根据传统加比选操作,状态p和状态q更新的累计路径距离可以表示为:
并且状态p和状态q的最小路径输出判决位表示为:
其中sign{x}表示取x符号位,即最高有效位。由于式(4)和式(5)中传统判决位表示时会出现状态分叉情况,即状态p和状态q均源于状态i或状态j,此时D(p)和D(q)输出值相等。但是对于本文提出的译码器,上述的分叉情况是不允许的。因此在原来加比选操作的基础上,当出现上述分叉情况时(假设状态p和状态q均源于状态i),为了使状态i单向指向其中一种状态,需要再对状态p和状态q的更新累计路径距离PMt(p)和PMt(q)进行最小值比较,若PMt(p)
在式(6)和式(7)的基础上需要加上判决算法,即:如果D(p)堠D(q)≡1,则D(p)和D(q)均不变;否则D(p)=0,D(q)=1(若△BM<0),或D(p)=1,D(q)=0(若△BM≥0),即:D(p)=~sign{△BM},D(q)=sign{△BM}。
由式(6)和式(7)以及上述判决算法看出,只需对△PM和△BM进行简单的加减法以及取符号位,即可实现状态间一一指向关系,硬件实现复杂度低,并且延时少。实现时,每一时刻MACS输出的各状态更新的累计路径距离反馈给下一时刻MACS的输入端进行叠加计算,并且将各状态记录当前判决比特输出至下一模块中。
2.3 指针反馈追踪模块(PFPT)
PFPT模块通过状态指针储存的译码状态结合从MACSU输出的64位判决比特进行状态64选1的操作,最终在每一时刻输出译码结果,并且将译码比特反馈更新状态指针,用于下一时刻译码路径状态的选取。另外,每进行第1节中提及的L次译码时,状态指针复位至状态0(008)。
3 FPGA实现结果及译码器性能分析
指针反馈式Viterbi译码器对于约束长度大(K≥7)、译码状态数较多的情况,其功耗以及性能效果明显。对第2节中所述的硬件设计进行FPGA实现,并且对多种Viterbi译码器进行功耗等参数比较。其结果如表1和表2所示。
由表2看出,在相同CMOS工艺情况下,指针反馈式Viterbi译码器与参考文献[6]和参考文献[7]相比,实现功耗最低;而在相同编码条件下,本文实现的算法功耗比参考文献[6]功耗至少降低60%。
另外,将卷积编码数据经过加性高斯白噪声信道后,对噪声数据进行指针反馈式Viterbi译码,其仿真结果与理想无编码情况作误比特率(BER)及信噪比(SNR)对比。其结果如图6所示,当SNR在6d B附近时,BER约为10-4;而当SNR≥7.2 d B时,BER=0。因此,该译码器在较高SNR时性能较好。
本文提出了一种指针反馈式Viterbi译码器,该译码器依靠初始译码状态从状态0开始的特点,相邻两时刻各状态进行单向一对一转移关系,并在每时刻通过不断更新的状态指针寻找译码路径上的状态,同时输出译码结果。算法仿真以及FPGA和CMOS综合结果表明,该Viterbi译码器在信噪比较高时有良好的译码性能,同时功耗相对一般译码器减少60%,硬件实现资源低,译码延时少,因此适合于无线局域网和移动通信等系统硬件实现。
摘要：为了满足复杂的无线通信系统功耗以及性能要求,提出并设计了一种指针反馈式Viterbi译码器。该译码器使相邻时刻的各状态转移满足单向一对一指向关系,并根据传统译码器初始译码状态从状态0延伸的特点,通过每一时刻不断更新的状态指针指向当前时刻译码路径状态,同时输出译码结果。算法仿真以及FPGA和CMOS综合结果表明,该译码器功耗降低60%,译码延时小,并且在信噪比较高的情况下有很好的译码性能,特别适用于约束长度大、译码状态数多的情况。
关键词：低功耗,Viterbi译码器,FPGA,指针反馈式
参考文献
[1]童琦,何洪路,吴明森.基于FPGA的高速并行Viterbi译码器的设计与实现[J].电子技术应用,2007,33(1):30-32.
[2]LIN D J,LIN C C,CHEN C L,et al.A low-power Viterbi decoder based on scarce state transition and variable truncation length[C].International Symp.on VLSI Design,automation and test,2007:1-4.
[3]AMEEN S Y,Al-JAMMAS M H,ALENEZI A S.FPGA implementation of modified architecture for adaptive Viterbidecoder[C].Electronics,Communications and Photonics Conference(SIECPC),2011:1-9.
[4]朱永旭,吴斌,周玉梅,等.适用于IEEE802.11n的高速低功耗Viterbi译码器的设计[J].微电子学与计算机,2010,27(7):10-14.
[5]El-DIB D A,ELMASRY M I.Memoryless Viterbi decoder[J].IEEE Trans.on Circuits and System-II,2005,52(12):826-830.
[6]LIN C C,SHIH Y H,CHANG H C,et al.Design of a power-reduction Viterbi decoder for WLAN application[J].IEEE Trans.on Circuits and System-I,2005,52(6):1148-1156.
Viterbi译码 篇6
在现代通信系统中,前向纠错编码(FEC)得到了广泛的应用。其中,卷积编码是应用最广泛的一种。卷积码与分组码不同,它的本码组的校验元不仅与本组的信息元有关,而且还与以前各时刻输入至编码器的信息组有关。在编码过程中,卷积码充分利用了各码字间的相关性, 在相似的纠错能力下,低码率的卷积码编/译码设备往往比分组码简单,因而被广泛地应用于前向纠错系统中。Viterbi译码算法是卷积码中的一种最大似然译码算法,在码的约束度较小时,它的译码算法效率很高,速度很快,译码器也比较简单,因而自提出以来,无论在理论上还是实践上都得到了迅速的发展,在卫星通信、深空通信、行星探测、DVD 及某些要求具有不等差错保护(UEP)的领域也有着十分重要的应用。本文所讨论的Viterbi译码器是采用国际上卫星通信和其它通信系统中常用的(2,1,7)卷积码,生成多项式为G=(171,133)。
1 Viterbi译码原理
Viterbi译码是卷积码的一种最大似然译码算法。它把接收序列与所有可能路径中最相似的一条路径作为译码输出,具体步骤如下:
(1) 计算进入每一状态的各个分支路径的度量(称为分支度量),其中分支度量定义为接收码元与可能码元之间的欧几里得距离(软判决)或汉明距离(硬判决)。
(2) 把各分支度量同各自相应的前一时刻状态度量相加求和,得到路径度量。在每个状态中,从到达这一状态的路径度量里选出并保留最小者作为当前时刻的状态度量。同时保留与之相应的路径作为幸存路径。
(3)在各状态的幸存路径中选出状态度量最小的一条,顺此回溯,得到译码输出。
上述步骤(1),步骤(2)通常称之为加比选运算(ACS),步骤(3)为回溯(Traceback)。
2 Viterbi译码器的总体设计框图
根据Viterbi译码原理得到Viterbi译码器的总体设计框图如图1所示。
译码器的设计思想是:由ACS单元输出幸存路径信息,根据它可以获得译码信息序列,有Register Exchange和TB(TraceBack)两种方案,采用TB方案,可以减少功耗。其中ACS单元的路径度量存储要做好防溢出处理,每路径度量存储占8B,TB方案采用截尾译码法,并且分两路同时进行回溯,回溯深度64周期,因为有64个状态信息,所以回溯所需幸存路径信息占4kB。
3 分支度量计算模块(BMU)
分支度量计算模块计算输入信号对卷积编码各个可能输出信号的距离值。它的输入信号是前端解调输出的信号,卷积编码的可能输出信号为00,01,10和11。分支度量计算模块根据输入信号状态计算并输出4路分支度量值。本设计度量采用汉明距离,为硬判决;本设计采用的输入信号为基于解扩后的信息,对于任一2bit输入信号Datain(10…),应以(Datain[0]-c0)+(Datain[1]-c1)(其中c0,c1取值为1或0)作为分支度量值。
4 加/比/选(ACS)
通过观察(2,1,7)卷积码的状态图,得出各个状态之间有如下的ACS碟形单元关系:如图2所示。
图2是j-1到j时刻的碟形单元框图,可以看出j-1时刻,两状态矢量差值32,j时刻两状态矢量差1,从j-1时刻到j时刻的状态也有关系。例如Sk(j-1)=(000000)2时,则Sk+32(j-1)=(100000)2,对应Sm(j)=(000000)2和Sm+1(j)=(000001)2,到j时刻状态矢量上分支路径信息记为0,下分支路径信息记为1。对于Sm(j)状态,两分支度量加上各自j-1时刻的路径度量,取最小值更新Sm(j)状态的路径度量值,并且记下相应的幸存路径信息,由于采用的是回溯法进行幸存路径的存储,所以这时记下的幸存路径信息是蝶形单元中进入Sm(j)状态的两个分支的上支还是下支。如果是上支度量值加上j-1时刻的路径度量小于下分支度量值加上j-1时刻的路径度量则存储0,如果是上支度量值加上j-1时刻的路径度量大于下分支度量值加上j-1时刻的路径度量则存储1。对于Sm+1(j)状态同前,其他的碟形单元结构类似,只是对应的状态不同。
所以本设计对于译码器的ACS的设计就是要设计32个并行的ACS碟形单元。每个碟型单元都相同。
5 路径度量归一化
在加/比/选模块中,为了防止溢出,当每一个路径度量值都大于等于所选择的特定值时,在下一个处理周期,所有的路径度量值都减去这个特定值,以实现路径度量值的归一化。在本设计中,选择4作为特定值。若所有的路径度量值都大于或等于4时,进行归一化操作,从所有的路径度量值中减去4,要实现归一化设计,在电路实现上还需要一个与4进行比较的电路,其比较结果产生归一化标志smallflagl和smallflag2。在每一步的路径度量的归一化操作将可靠保证具有最小量度的路径度量值不受路径度量的比特数的影响。
6 回溯单元
近年来随着大规模集成电路工艺水平的提高,人们在维特比算法及其硬件实现的研究方面做了大量的工作。作为维特比译码器三大组成模块之一的幸存路径存储(SMU)和输出单元的设计实现也成了近年来科研人员讨论的热点。SMU的2种传统实现方法是寄存器交换法RE(registerexchenge)与回索TB(traceback)。寄存器交换法采用专用寄存器作为存储主体,存储的是路径上的信号信息,利用数据在寄存器阵列中的不断交换实现信息的译码。其优点是存储单元少、译码延时短、输入/输出端固定,缺点则是内连关系过于复杂,不适于大状态译码器的FPGA实现。而回索法则采用通用的RAM作为存储主体,存储的是幸存路径的格状连接关系,通过读写RAM来完成数据的写入和回索输出。其优点是内连关系简单、规则,缺点是译码延时较长(是RE法的3～4倍)。本设计采用回溯法。
回溯单元最重要的一点是要寄存当前回溯状态,并且每次回溯起始时需要选择最小路径度量对应的状态为当前回溯状态,回溯方案定为每T/2(T=64)间隔进行回溯,回溯的状态寄存器只需要4个单元,每单元7bit,另外译码输出需要一个32bit的寄存器。
图3是某一回溯单元框图,其他回溯单元结构相同。图中所示回溯状态寄存器共6bit。6表示最高位,1表示最低位,回溯时相当于对回溯状态寄存器右移,最高位写入幸存路径信息。实现时只需要将寄存器的输出连接到对应位的输入即可,几乎不考虑占用的组合逻辑资源。
原理介绍:假如回溯单元寄存器中当前的状态是Sm(j),表示当前的时刻是j,状态是m写成2进制是(D6D5D4D3D2D1),假设此时刻写入到回溯单元寄存器的幸存路径信息是0,也就是说是碟形单元的上分支Sk(j-1)到达Sm(j),则可以回溯到j-1时刻的当前状态是(0D6D5D4D3D2),也就是k=(0D6D5D4D3D2)。且D6被写入译码输出的32位移位寄存器中等待输出。以此依次回溯,当回溯64列时,就在卷积编码的网格图中找到一条最短的路径,就可以进行32位译码信息的输出。
7 回溯单元的硬件实现
回溯的硬件实现是本设计方案的重点,本节着重说明。回溯过程共有4块32x64bitRAM, Viterbi译码TraceBack框图中有两个计数器,其中模32加法计数器产生RAM的写地址Addr1,模32减法计数器产生TB(TraceBack)过程RAM的读地址Addr2,两地址由外循环模4计数器产生的Ctrl信号,选通做为RAM的实际读写地址。同时,RAM的读写控制信号也由外循环模4计数器产生的Ctrl信号经过一个译码器产生。回溯过程开始时,一共有2块RAM同时参与回溯,一块RAM被写入幸存路径信息,所以此回溯方案同时使用了3块RAM,这就需要对RAM的片选使能信号进行编码,使得每次仅有3块RAM工作,进一步减少电路功耗。RAM片选使能信号可以由模32减法计数器的当前值为基础编码产生。为了讲解方便,把RAM从左到右按字编码,共有128字,编成128列,Viterbi译码开始时,先要经过64时钟周期,幸存路径信息写入到前2块RAM中,同时,第64周期最小路径度量值对应的状态值会写入第2块RAM对应的当前状态寄存器中,回溯开始,随后,回溯单元将根据当前回溯状态和当前回溯状态对应的幸存路径信息回溯到前一状态,依次类推。再经过32时钟周期,回溯到32列时,第96列处将开始第二个回溯过程,回溯方法同前。又经过32个时钟周期,第一回溯过程回溯到1列,第二回溯过程回溯到64列,第128列将启动第三回溯过程,回溯方法同前。同时,回溯的结果信息位在回溯到32列时已经开始串行移入到32bit的移位寄存器中了,此时可以并行输出32bit的回溯结果,第一回溯过程结束,再过一个周期,幸存路径信息则开始写入第1列中。
图4中块RAM的输出对应一个64选1的Mux,它的输出还要经过一个2选1的Mux,然后选通到回溯单元,4个当前状态寄存器的输出也进入回溯单元,回溯单元通过一个简单的移位操作,回溯到下一个状态。回溯的输出和最小路径度量对应的状态经过一个2选1的Mux写入到当前状态寄存器中,最后是译码输出,当前状态寄存器的最低位共4bit通过一个4选1的Mux写入到32bit移位寄存器中,每32时钟周期一次输出32bit回溯信息结果。
8 结束语
卷积编码和Viterbi译码是一种有效的前向纠错方法, 广泛应用在深空通信、卫星通信和移动通信中。Viterbi译码算法的复杂性随约束长度的增长呈指数增长。本文介绍了一种Viterbi译码器的设计方法,主要内容就是幸存路径的存储器的组织和管理, 这种结构很容易用FPGA实现。用这种结构实现了一个约束长度为7,码率为1/2的卷积码的Viterbi译码器。这种约束条件的卷积码和Viterbi译码器被用在卫星通信中。由于采用全并行结构的ACS,所以可以达到很高的译码速度。同时采用回溯的方法,所以有128的时钟中期的延迟。
摘要：卷积码在通信系统中得到了极为广泛的应用。其中约束长度K=7,码率为1/2和1/3的Odenwalder卷积码己经成为商业卫星通信系统中的标准编码方法。提出了一种(2,1,7)卷积码Viterbi译码器的设计方案,该译码器采用全并行结构的加/比/选模块和回溯法以提高译码速度,重点介绍了幸存路径存储与交换单元的设计与实现。
关键词：卷积码,Viterbi译码器,FPGA
参考文献
[1]王新梅.纠错码与差错控制[M].北京:人民邮电出版社,1989.
[2]秦东,肖斌,李志勇,等.Viterbi译码器的优化设计[J].微电子学,2000,30(3).
[3]付永庆,孙晓岩,李福昌.实现Viterbi译码器幸存路径存储及译码输出的一种新方法[J].应用科技,2003,30(3).
Viterbi译码 篇7
在无线通信中,由于信道的噪声和畸变,会对传输的信息引入失真和信号判决错误,因此需要使用信道编译码来降低误码率。卷积编码和Viterbi译码是广泛使用的信道编译码技术,具有一定的克服突发错误的能力,可以降低信道的误码率,带来很高的编码增益。因而卷积编码和Viterbi译码也是目前无线通信中的重要组成部分。
1 卷积编码器
典型的(n,k,m)卷积编码器是指输入位数为k,输出位数为n,约束长度为m的卷积码编码器,其编码速率为k/n。802.11b协议中采用(2,1,6)结构的卷积编码,其生成多项式为[133,175],码率R=1/2,约束长度为6。卷积编码器原理框图如图1所示。根据(2,1,6)卷积编码器原理框图,用寄存器和异或电路很容易实现(2,1,6)卷积编码器的设计。
2 Viterbi译码器
Viterbi译码的基本思想就是利用编码网格图,在其中搜索一条路径,使其最接近实际路径,搜索到的这条路径称为幸存路径。因此Viterbi译码算法实际上就是最大似然译码,它是逐步去除网格图上不可能成为最大似然路径者来搜索幸存路径。对于(2,1,6)卷积码,采用Viterbi译码算法,共有64种状态,在每一个译码时刻都有2条路径到达同一状态。在这2条路径中,将累积度量最小的一条保留下来,而将另一条路径淘汰。
Viterbi译码器一般包括:分支度量生成模块、加比选模块、幸存信息存储模块和回溯判决模块。该设计采用软判决译码,对输入码字进行3比特8电平量化;为了减小译码时延,采用截短译码,根据文献[3],回溯深度大于5倍约束长度时,对译码没有影响,本设计回溯深度取为40。
2.1 分支度量生成模块
分支度量生成模块主要完成计算接收码字与估计码字之间的汉明距离。汉明距离的计算方法为:
式中,BM00、BM01、BM10、BM11分别是期望码字为00、01、10、11时的分支度量值;r0、r1为接收码字的上下支路。(2,1,6)卷积码共有64个状态,对于全并行结构,每一时刻要计算128个分支度量值。通过分析可知任意一个状态的输出期望码字只可能是00、01、10、11这4个中的一个,并且每一时刻各个状态的接收序列是相同的,所有状态的分支度量值也只有4种可能。
2.2 加比选模块
加比选模块是Viterbi译码器中最为核心的模块,加比选单元通过把前一状态的路径度量值和当前输入信号的分支度量值相加,即可得到该分支的路径度量值,然后比较不同分支路径度量值的大小并选择出最小的度量值,即可更新该状态的度量值,同时输出状态转移信息。加比选单元的运算可以按照状态转移图的蝶形运算进行,蝶形运算结构原理图如图2所示。
式中,Si、Sj为状态;PMi、PMj为路径度量值;BMi0、BMi1、BMj0、BMj1为分支度量值,各个蝶形单元存在如下规律:对于第i个蝶形单元,起始状态j=i+32,结束状态p=2*i,q=2*i+1。路径度量之间的关系为:
在完成路径度量值的更新后,加比选单元同时输出p、q的状态转移信息。对于状态p而言,“0”代表走的是上支路(从状态i转移而来),“1”代表走的是下支路(从状态j转移而来)。根据蝶形运算结构给出蝶形运算的实现电路框图如图3所示。
(2,1,6)卷积码共有64个状态,相应的有32个这样的蝶形运算单元,每一时刻所有的64个状态都进行着“加比选”操作,并行输出64个状态的路径度量值和路径转移信息。
2.3 溢出控制处理
由于每接收到一个码元,所有的状态都要进行一次“加比选”操作,随着接收码元的增多,路径度量值的累加就可能存在溢出问题,所以对路径度量值要进行溢出控制。每一步所计算的状态度量值存在以下关系:
对于(2,1,6)卷积码,在软判决中BMmax=14,BMmin=0,路径度量最大值和最小值之间的最大差值为84,用8比特存储路径度量值,将其最高位作为溢出标志位,设定一个门限值128,如果最小的路径度量值都大于128,此时最大的路径度量值也不会超过212(128+84),该值也没有超过255。当所有路径度量值的最高位都为1时,通过将该标志位置0的方法,等同于减去了数值128,这种方法可以省去用于归一化的减法器,节省了硬件资源。
2.4 路径度量的比较处理
当译码器工作到一定的译码深度后(该译码器的译码深度为40),要将所有状态的路径度量值进行比较,通过比较找出路径度量值最小的状态序号,然后将这个序号送给回溯判决模块作为译码判决的起始状态使用。路径度量值比较的功能就是尽快地完成64路输入路径度量值的比较,此处使用比较树,共分为6级比较结构,即先两两比较,然后将结果再两两比较,直到比较出最小值,并记录下最小值的序号。
2.5 幸存信息存储模块
幸存信息存储单元的作用是存储加比选运算中产生的判决比特,通过这些判决比特可以得到所有状态的幸存路径,选择其中一个状态的幸存路径输出就可以得到译码结果。
幸存信息的存储可以用乒乓RAM来实现:将数据先存入一个RAM,在对其进行读取的同时将后面的数据存入另一个RAM,这样乒乓读写,可对数据进行连续处理,减小了时延。该文的设计采用另外一种存储结构,如图4所示。
此结构是长度为n的RAM。数据读取过程如下:第1帧数据(长度等于回溯深度k=40)到来时,将其从地址0开始顺序存入RAM;第1帧数据存完后,从地址k-1开始倒序读出;同时,第2帧数据从地址n-1开始倒序存入RAM;当第2帧数据存完后,从地址n-k+1开始顺序读出;同时,第3帧数据从地址0开始顺序存入RAM;如此循环读写RAM。当读写时钟大小相等时,RAM的最小长度为nmin=k+1。
2.6 回溯判决
回溯是通过对幸存信息的处理来得到译码结果的,幸存信息不是回溯路径和译码信息,而是状态转移信息。
用比较出的最小路径度量值的序号作为回溯的起始状态,根据幸存路径寄存器里存储的值进行判断,若是“0”,则是由上面状态转移过来;若是“1”,则是下面状态转移过来(如图2)。根据这些信息回溯到对应的前一状态。回溯节点逐级前移,从与之对应的幸存路径寄存器中获得路径转移信息;重复上述的转移过程,直到最后一级并输出译码结果。
3 仿真和硬件调试结果
利用Verilog HDL硬件描述语言对卷积编码和Viterbi译码进行仿真,具体做法为:用设计的(2,1,6)卷积编码器对一已知序列进行编码,输出对应的码字,然后对该输出码字进行加噪声处理,再送入Viterbi译码器进行译码,仿真波形如图5所示。
从仿真图中可以看出,译码器输出序列在经过一段延时后,与输入编码器的序列一致,说明该译码器能对受到干扰的信息进行正确译码,同时验证了设计的正确性。其中data_in表示输入编码器的数据; data_out为译码器输出数据。
最后,选择Cyclone II 系列EP2C5T144C8芯片,使用Quartus II软件中的逻辑分析仪进行了硬件调试,实际信号输出结果与图5一致,证明了该设计的正确性。
4 结束语
上述主要讨论了802.11b中卷积编码器和Viterbi译码器的FPGA设计实现方法,其中包括分支度量的计算、加比选模块的设计和回溯译码输出等。同时用Verilog HDL硬件描述语言对卷积编码器和Viterbi译码器的设计进行了仿真验证,最后在Cyclone II系列的EP2C5T144C8芯片下完成了硬件的调试。
参考文献
[1]IEEE STD802.11b-1999[S].
[2]王新梅,肖国镇.纠错码-原理与方法[M].西安:西安电子科技大学出版社,2001:443-452.
[3]晏坚,何元智.差错控制编码(第2版)[M].潘亚汉,译.北京:机械工业出版社,2007:341-361.
[5]王连成.基于FPGA的Viterbi译码器设计[J].电子元器件应用,2010,12(5):39-40.
[6]温学东.卷积编码及其Viterbi译码算法的FPGA实现[J].信息与电子工程,2005,2(3):176-178.
[7]张力军,张宗橙.数字通信(第4版)[M].郑宝玉,译.北京:电子工业出版社,2006:340-358.
【Viterbi译码】相关文章：
自动译码07-13
迭代译码算法07-16
LDPC译码09-04
解读《达·芬奇译码》07-01
LDPC译码器07-14
Turbo译码器08-05
二进制译码器05-08
数字译码显示电路心得体会05-27