一种维特比译码改进算法的研究

JournalofTelemetry,Tracking,andCommandVol.27,№.1January2006

一种维特比译码改进算法的研究

刘国芳,　程乃平

(装备指挥技术学院　　北京　101416)

摘　要:介绍传统维特比译码算法的基本原理;根据卷积编码的原理,结合(2,1,7)卷积码的子网表,提出一种维特比译码的改进算法,仿真结果表明,改进算法是可行的;最后通过数据分析,得出该算法与传统的译码算法相比具有存储量小、译码延迟短的优点。该算法同样适用于其它的卷积编码。关键词:卷积码;　维待比译码;　译码算法中图分类号:TN911.21　　文献标识码:A　　文章编号:CN11-1780(2006)01-0030-03

前　言

为了提高系统传输的质量,克服数据传输错误,一般采用差错控制编码,卷积编码是一种很好的纠错

编码方法。它满足线性叠加原理,且子生成元不随时间变化;与之相应的维特比算法是加性高斯白噪声信

[1]

道下卷积码的最优译码算法。

维特比译码算法是1967年Viterbi提出的一种译卷积码的最大似然译码算法。在码的约束度较小时,它的译码效率较高、速度较快,因此广泛应用于数传系统,特别是卫星通信系统中。传统的维特比算法中的回溯算法采用通用的存储器作为存储主体,存储幸存路径的格状连接关系,通过读写存储器来完成数据的写入和回溯输出。但其译码延时较长。针对此,本文提出(2,1,7)卷积编码的维特比译码回溯算法的改进算法,该算法克服了传统算法的不足,有效地减少了存储器的存储空间,缩短了译码延迟。

1　传统的维特比译码算法的基本原理

[2,3]

维特比算法可用网格图来表示,它是一个时间序列的状态图。图1是一个简单的表示两个状态的状态转移网格图。在n-1时刻,两个可能状态x0、x1根据输入的信息可能转移到n时刻的两个状态0x、1x。维特比算法就是通过在网格图中寻找最小路径度量值来判决最大似然状态序列,幸存路径存储就是存储具有最小路径度量值的信息。在传统的算法中,幸存路径存储器的组织采用类似指针的方法,将幸存路径分成前序状态的幸存路径和指向前序状态的指针两部分。在幸存路径存储器写满后要进行截尾译码,截尾译码的过程就是找出当前时刻n的所有状态中具有最小路径度量值的状态,这个状态对应的路径就是最大似然路径,然后根据存储的指针找到其n-1时刻的前序状态,再根据该状态存储的指针找到其n-2时刻的前序状态,直到找到起始状态为止,它所存储的信息即为译码输出。在该算法中,幸存路径存储器所存储的内容既包括路径的信息,又包括前序状态的指针,因而需要大量的存储空间。同时,每输出一个译码结果需要回溯整个译码深度(即读L次存储器),因而降低了译码速度。

图1　两状态转移网格图

2　改进的维特比译码算法

(2,1,7)卷积码有27-1个状态,根据其编码原理,可以得出当旧状态输入分别为0和1时对应的输

出新状态和输出值,将旧状态与新状态以及输入输出值制成表1所示的(2,1,7)卷积码的子网表。表1

　收稿日期:2005204212　　收修改稿日期:2005207208

© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net

第27卷第1期刘国芳等,一种维特比译码改进算法的研究・31・

只给出前八个状态和最后两个状态的对应表1　(2,1,7)卷积码的子网表值。最后一列称为Tab表,共有64个不同的输入0输入1

状态序号旧状态

新状态输出新状态输出状态,其结构为旧状态1(6bit)+输出(2bit)

00000000000000010000011+旧状态2(6bit)+输出(2bit)。如表2所

10000010000001110000000

示。完整的(2,1,7)卷积码Tab表为:Tab=[131,896,1414,1669,2187,2952,3470,3725,5008,4243,5781,5526,7064,6299,7837,7582,9120,8355,9893,9638,11176,10411,11949,11694,12467,13232,13750,14005,14523,15288,15806,16061,17089,16834,18372,17607,19145,18890,20428,19663]

234567000010000011000100000101000110000111000001000001000010000010000011000011011000110110

100001100001100010100010100011100011

100111001001

Tab表131896141416692187295234703725

…62

62

…111110

111111

…011111

011111

…11

00

…111111

111111

…00

11

…32764

31999

该算法的基本步骤如下:①将存储器按状态数分成相应的存储单元,每单元的位数

表2　Tab表结构图

由译码深度决定,并对每个单元按状态排序。

　　　旧状态1(6bit)　输出(2bit)　旧状态2(6bit)　　输出(2bit)

每一个状态当前的数值由其前一状态和该状

G1G0G′1G′0态的奇偶决定。②搜索Tab表的每一个状态,将输入值x0x1与G0G1、G′0G′1进行比较(将Tab表中的数据经过移位得G0G1、G′0G′1),得到分支码距,与旧的路径度量值相加得到新的路径度量值,每个状态得到了两个分支累加路径度量值,将这两个分支累加路径度量值进行比较,找出比较小的一条分支累加距离,并将这条分支保存。同时把这条分支对应的路径(包含译码信息)写到此状态的存储中,写入的同时,将此信息向左移位1次,在最低位写入1或者是0,当该节点为偶数时,向存储单元中最低位写入“0”,而当该节点为奇数时,向存储单元中最低位写入“1”。③当译码时刻达到一定深度时,判决出当前时刻的所有状态中具有最小路径度量值的状态,译码输出根据该状态数值读取幸存路径存储单元中相应数值的最高位作为译码结果输出。

3　仿真结果与分析

图2是维特比编译码过程。将仿真产生的随机序列(a)通过(2,1,7)卷积编码器,产生卷积码序列(b)并作为译码输入,通过改进算法译码后输出数据(c)。可见,图(c)与图(a)的输出码相同,表明了该算法能正确地译出输入数据。

图2　维特比编译码仿真图

© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net

・32・遥　测　遥　控2006年1月

4　改进算法与传统算法的比较

4.1　存储量

在传统算法中,幸存路径存储器中的内容既包括路径的信息,又包括前序状态的指针,因而在任一时

刻,每个状态都需要两位的存储空间,总的存储空间为

存储空间=回溯长度・状态数・每个状态所需的位数

对于m=7的(2,1,7)卷积码,设回溯长度为32,则传统算法所需的存储空间为

7-1

存储空间=32・2・2=4096bit在改进算法中,存储单元中只存入幸存路径的信息,因而任一时刻每个状态仅需一位存储空间,因此所需的存储空间为

存储空间=32・2・1=2048bit可见,改进算法比传统算法节省了一半的存储空间。4.2　延迟

传统的算法每产生一位译码输出就需要进行回溯,回溯长度等于译码深度,即每产生一位译码输出需要回溯L步,需要读L次存储器,因而译码延迟主要由回溯长度L决定。假设译码延迟为△,读存储器的

δ延迟为δ,回溯长度为L,则译码延迟为△=L・。在改进算法中,译码输出只需读出具有最小路径度量值的状态所对应的幸存路径存储单元中的最高位即可,无需向前回溯,因而读存储器的次数由L次减少至一

次,故译码延迟为△=δ。因此,改进算法译码延迟比传统算法减少了(L-1)δ。

7-1

5　结　论

综上所述,改进算法的优点是:每一个译码时刻只向存储单元中存入幸存路径的信息,在此存入的是当前时刻此状态中路径度量值译码的信息即输入信息,因而节省了存储空间;译码输出时,只需读出最小路径度量对应的存储器中数值的最高位,因而减少了读寄存器的次数,提高了译码速度,缩短了译码延迟;查表时采用循环寻址的方法,因而大大减少了程序段,缩短了程序运行时间。因此,该算法对于提高系统的性能起到了一定的作用。本文提出的改进算法是针对(2,1,7)卷积码而言的,对于其它的卷积码,只需改变其子网表,因此改进算法的译码原理同样也适用于其它的卷积码。

参考文献

[1]　王新梅,肖国镇.纠错码原理与方法[M]。西安:西安电子科技大学出版社,2001.

[2]　YasudaY,KashikiK,HirataY.HighRatePuncturedConvolutionalCodesforSoftDecisionViterbiDecoding[J]IEEE

Trans.onCom.,1984,(32):315～319

[3]　杜志秀.软判决维特比译码的研究与实现[D],北京:装备指挥技术学院,2000.

AnImprovedViterbiDecodingAlgorithm

LiuGuofang,　ChengNaiping

Abstract:TheprinciplesofconventionalViterbidecodingalgorithmareintroducedinthispaper.Basedonthecodingprincipleofconvolutionalcodesandthesubnetlistof(2,1,7)codes,animprovedViterbidecodingalgorithmisproposed.Theresultsofsimu2lationprovesthefeasibilityofthisalgorithm.Thedataanalysisshowsthatthememoryneedandthedecodingdelayarereducedobvi2ouslyafterusingthisalgorithm.Thisalgorithmisalsofeasibletootherconvolutionalcodes.

Keywords:Convolutionalcodes;　Viterbidecoding;　Decodingalgorithm

[作者简介]

刘国芳　1981年出生,硕士研究生,主要研究方向为扩频通信系统。程乃平　参见本期第38页。

© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net