文档库 最新最全的文档下载
当前位置:文档库 › 列表 Viterbi 译码算法及其应用

列表 Viterbi 译码算法及其应用

列表 Viterbi 译码算法及其应用
列表 Viterbi 译码算法及其应用

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所示,并假设译码器确知网格图的初始状态。 图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倍的译码延迟。 图2幸存路径选择 在译码过程的每—步,到达每个状态的可能路径总有两条,通过比较路径量度舍弃其中一条。图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.wendangku.net/doc/9318291471.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,故冲激响应至

Viterbi译码器研究目的意义及现状

Viterbi译码器研究目的意义及现状Viterbi译码器研究目的意义及现状 1研究的目的和意义 由于卷积码的优良性能,被广泛的应用于深空通信,卫星通信和2G及3G移动通信中,卷积码有三种译码方法:门限译码,门限译码,概率译码和Viterbi 算法,其中Viterbi算法是一种基于网格图的最大似然译码算法,是卷积码的最佳译码方式,具有效率高、速度快等优点。Viterbi译码充分发挥了卷积码的特点,使译码错误概率达到最小,在码的约束度较小时,它具有译码算法效率高,速度快,译码器也简单的特点。 FPGA(Field,Programmable Gate Array),即现场可编程门阵列,它是在PAL、GAL、CPLD等可编程器件的基础上进一步发展的产物。它是作为专用集成电路(ASIC)领域中的一种半定制电路而出现的,既解决了定制电路的不足,又克服了原有可编程器件门电路数有限的缺点。 同时在FPGA的基础上实现Viterbi译码器,迎合了当前FPGA迅猛发展的趋势。把相对成熟的技术应用到某些特定领域如通讯,视频,信息处理等等开发出满足行业需要并能被行业客户接受的产品这方面主要是FPGA技术和专业技术的结合问题,另外还有就是与专业客户的界面问题产品设计还包括专业工具类产品及民用产品,前者重点在性能,后者对价格敏感产品设计以实现产品功能为主要目的,FPGA技术是一个实现手段在这个领域,FPGA因为具备接口,控制,功能IP,内嵌CPU等特点有条件实现一个构造简单,固化程度高,功能全面的系统产品设计将是FPGA技术应用最广大的市场,具有极大的爆发性的需求空间产品设计对技术人员的要求比较高,路途也比较漫长不过现在整个行业正处在组建“首发团队”的状态,只要加入,前途光明产品设计是一种职业发展方向定位,不是简单的爱好就能

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译码算法

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

卷积编码和Viterbi译码

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

Viterbi译码器的优化设计

基金项目:华为研究基金资助项目 收稿日期:1999-10-18; 定稿日期:2000-01-05 第30卷第3期2000年6月 微电子学M icroelectronics V o l .30,№3Jun .2000 文章编号:1004-3365(2000)03-0168-04 Viterbi 译码器的优化设计 秦 东,肖 斌,李志勇,周 汀 (复旦大学 专用集成电路与系统国家重点实验室,上海 200433)   摘 要: Viter bi 译码器中的大容量、宽带宽存储器限制了译码器的速度和系统的功耗,合理地组织这个存储器是提高译码器速度,降低系统功耗的关键。从电路系统角度分析了Viterbi 译码器的结构,提出了一种优化设计方案。 关键词: 专用集成电路;Viter bi 译码器;存储器管理;卷积编码中图分类号: T N492文献标识码: A   Optimized Architectural Design of Viterbi Decoders QIN Dong ,XIAO Bin ,LI Zhi -yong ,ZHOU T ing (S tate K e y L ab .o f AS I C &Systems ,Fud an Univ ersity ,S hang hai 200433,China )   Abstract : T he need o f V iter bi deco der s for lar ge mem or y w ith w ide bandw idth limits the speed o f the deco der and it consum es mo st po w er o f t he w hole sy stem.So ,pr oper manag ement o f the m em or y is the key t o get a hig h-speed and low -po wer V iter bi deco der.An o ptimized a rchitectur al desig n o f V iter bi deco der is descr ibed in the paper . Key words : A SIC;V it erbi decoder;M emor y m anag ement;Co nvolutio nal encoder EEACC : 1265  1 引 言 卷积编码和Viterbi 译码是一种有效的前向纠错方法,广泛应用在深空通信、卫星通信和移动通信中[1]。Viterbi 译码算法是用于卷积码译码的一种最大似然译码算法,其复杂性随约束长度的增长呈指数增长。在当前的某些应用中,对Viterbi 译码器提出了更高的性能要求,往往采用长约束长度的卷积码,使译码需要大容量宽带宽的存储器,降低译码器的速度,增加功耗。在一些文章里提出了改进的Viterbi 算法 [2,3] ,虽然可以减小存储器容量,但译码 器性能会下降。本文从电路系统角度分析了Viterbi 译码器的结构,提出了一种结构优化设计方法,并用这种优化结构实现了一个用于无线多媒体通信中的Viterbi 译码器。 2 V iterbi 译码器系统结构 Viterbi 算法是一种估计一个有限状态过程中 状态序列的最优算法。以下简单介绍Viterbi 算法的基本概念和系统结构,包括一些符号和术语。 卷积编码器的简单结构如图1所示。输入信息符号m i 是M 进制的,编码得到的数据c i 是当前符号m i 和前k 个存储在移位寄存器中的符号的函数。得到c i 后,移位寄存器在时钟作用下移位,状态由(m i -1,m i -2,…,m i -k )变成(m i ,m i -1,…,m i -k +1)。卷积码的约束长度就是k +1。 图1 卷积编码器

viterbi译码算法C++实现

Viterbi译码算法c++语言实现所对应的结构如下图所示: 已知接收序列y=-1,3,3-1,3,试求输入序列x=?用代码实现 所写函数包含两部分一个cpp一个h文件 Main.cpp如下所示: #include"decode.h" void main() { int re[]={-1,3,3,-1,3}; Decode vb; cout<<"trellis图是:"<

cout<<"输入的x序列是:"< #include usingnamespace std; class Decode { public:

void gettrellis(); void getpe(int a,int b1,int b2,int b3); void v(int *re,int n); void get_pre(int now,int *pre); int getcurrent(int j,int i,int in); int min_path(int a,int b); int get_out(int pre,int next); private: int trellis[4][4],s_number,multi1,multi2,multi3; struct get_path { int pre; int out; }; }; /* 函数名称:getpe() 作用:作为构造类创建对象的时候进行传参,其中第一个参数a 代表的是存储器个数,第二个参数代表的是所看到的从左到右,输入,存储器,存储器所乘的系数,将这三个参数传给类的对象*/ void Decode::getpe(int a,int b1,int b2,int b3)

Viterbi译码的FPGA免回溯实现

Viterbi 译码的FPGA 免回溯实现 王栋良,秦建存 (中国电子科技集团公司第54研究所,河北石家庄050081) 摘 要 卷积码在多种通信领域中广泛应用,Viterbi 译码是对卷积码的一种最大似然译码算法。随着卷积码约束度的增加,并行维特比译码所需的硬件资源呈指数增长,限制其硬件实现。介绍了一种串行译码结构的FPG A 实现方案,在保证性能译码的前提下有效地节省资源。同时提出了充分利用FPG A 的RAM 存储单元的免回溯Viterbi 解码实现算法,减少了译码时延,这种算法在串行和并行译码中都可以应用。 关键词 卷积码;Viterbi 译码;免回溯;FPG A 中图分类号 T N911.22 文献标识码 A 文章编号 1003-3106(2007)04-0027-02 A Implementation of a N on 2backtracking Viterbi Decoding Algorithm in FPGA W ANG D ong 2liang ,QI N Jian 2cun (The 54th Research Institude o f CETC ,Shijiazhuang Hebei 050081,China ) Abstract C onv olutional coding has been widely used in many communication fields ,and Viterbi decoding alg orithm is a maximum likelihood alg orithm for the conv olutional code.The hardware res ource required for parallel Viterbi decoding shows an exponential increase with the increase of constraint length of conv olutional code ,which limits its hardware im plementation.In this paper ,a FPG A im plementation of a serial Viterbi decoding architecture is presented ,which saves hardware res ource without per formance deterioration.Meanwhile ,a non 2backtracking s olution of Viterbi decoding alg orithm using the RAM units of FPG A is provided in the paper.The s olution can reduce the delay of decoding ,and can be im plemented in both serial decoding and parallel decoding. K ey w ords converlutional code ;viterbi decoding ;non 2backtracking ;FPG A 收稿日期:2006212225 0 引言 卷积码因其良好的纠错能力在多种通信领域中得到了广泛的应用。目前,对卷积码的解码一般使用Viterbi 译码算法。Viterbi 译码算法是一种最大似然译码算法,其解决方案是:对各编码状态只保留一个距离最小的幸存路径供下一次比较运算使用,其核心运算即对不同路径度量之间的加比选操作。 当译码进行一段时间之后,即到达一定译码深度后,通过回溯算法可以读出幸存路径即解码输出。这种方案的译码时延随着回溯深度的增大而增大。免回溯实现充分利用了FPG A 中的存储单元,将幸存路径和距离即时存储,待需要译码输出时读出即可,这种方案的译码时延较小。以(2,1,7)卷积码为例介绍了串行结构的Vterbi 译码方案以及免回溯方案的实现,该卷积码的生成多项式为(171,133),这种码型的应用非常广泛。 1 卷积码编码简介 通常称一个卷积码为(n ,k ,m )型卷积码,其中 n 是指编码输出的比特数;k 是指输入的信息比特数;m 为卷积编码的深度。通常(n ,k ,m )就是由m -1位移位寄存器和一些组合逻辑构成。所谓寄存器的状态是由这m -1个寄存器所确定的。但是在FPG A 的实现中,为了保持整个编码模块的输入输出同步性,在输入位增加了一个寄存器。图1是(2,1,7)卷积编码器的一种结构 。 图1 (2,1,6)卷积编码器结构图1中的(2,1,7)卷积编码器由1个7位移位寄存器和2个异或运算单元组成。每次当1个新的信息比特 到来,就把移位寄 信号与信息处理 2007年无线电工程第37卷第4期27

相关文档