数字通信中卷积码Viterbi译码算法的研究及软件实现
赵胜男 朱晓明
(西安电子科技大学ISN国家重点实验室 西安 710071)
摘 要:介绍了数字通信系统中一种卷积码为特比译码的软件实现算法,在CCS环境实现了(2,1,7)卷积码Viterbi译码功能,在程序实现中充分利用了卷积码的特性,运用网格图和回溯以得到译码输出。关键词:卷积码 Viterbi译码 回溯中图分类号:TN91文献标识码:A文章编号:1673-0534(2007)09(a)-0152-02
1 引言
卷积码是Elise于1955年提出的一种按比特编码的技术,不同于分组码每次编出一组码它编出的码不仅和当前输入有关,也和前面时刻的输入相关。网格图(Trellis)经常用来描述卷积码的整个系统。Viterbi译码算法是由Viterbi于1967年提出的一种最大似然译码算法,通过计算累计码距,在相应卷积码图上寻找位移最大似然路径,再根据这条路径所通过的延时器状态,来重构发送序列。Viterbi译码分为硬判决和软判决和硬判决两种。在硬判决过程中信号之间的差别用汉明距离来表示,而在软判决中用欧氏距离来表示。
2 卷积编码
卷积码一般用(n,k,m)来表示,其中k表示在每个时间单位,送至编码器信息元个数;n表示编码器就送出相应的码元个数;m则表示了编码器的长度。卷积码具有纠错功能是因为编码输出和前面若干时刻的输入有关系。每一个输出码元通过当前输入码元和前面若干个码元运算得到。卷积码的纠错能力随m的增大而增大,差错率则随m的增大而降低。
下面以(2,1,7)卷积码为例,给出一些卷积码的特性图1为编码器结构图。该结构包括6个延时单元,所以编码器共64个状态,该码的生成多项式为(133,171)。设状态为若用10

进制表示,则可以记为;若用二进制表示,可以写成,。
因为

k=1,所以每个状态都可以通过两种

不同状态在输入相同的信息元后转移出来,同时在输入不同信息元后转移到另外两种不同状态,状态之间的转化关系是固定不变的。假
在输入信息元后转设状态
化为了状态

,可以得到i与

j间

的固定关系:

Viterbi译码实质上就是最大似然译码,它是逐步去除网格图上不可能成为最大似然路径着来搜索性出路径,由于(2,1,7)卷积码有64个状态,不易表述,所以这里用L=5时的(2,1,2)码的网格图来表述,见图2。
由图2可见,每一个状态有2个输入和2个输出分支,每个分支上有2个数字,表示第i个时刻编码输出。因而图中的,每一条路经都对应不同的输入信息序列。Viterbi算法的目的就是用最大似然算法得出最可能的一条支路。每一条支路由m段组成,m段对应m组输出码字,让它与接收到的码子比较分别算出码子间距,并相加求和。每一条支路都和接收码子做一个这样的运算,找出最小的一个,它所对应的支路既判决码子。3.2 Viterbi算法
Viterbi算法前后分为2部分:状态更新和回溯
(1)状态更新
①每个支路与接受码元的汉明距,选择较小的与状态表中相应的元素中的原有更新值相加,得到新的值。
②存储a.步骤中的信息,表明是从两个支路中的哪一个支路来的,以供回溯时候使用。
(2)回溯
对于L时刻的每一个状态,都对应一个回
溯表,记录了到达这个状态幸存路径的信息。当译码进行至一定深度时,每条幸存路径的前段分支已完全重合为一条路径,图4展示了这个Viterbi译码的这个特性。因此在足够多的时间间隔后可以比较状态表中的更新值,找到最小的以得到唯一直路。根据Viterbi译码截断定理,

译码深度最小为5~10倍的m。
图3 回溯网格图
3.3 Viterbi译码的实现
下面以(2,1,7)卷积码译码为例,介绍一下Viterbi译码的具体实现
3.3.1 程序初始化
(1)定义2个更新的回溯表:table[64][26][2] 里面存储每一状态的幸存路径的输出比特,初始化为-1
(2)定义2个路径比较寄存器:dmin[2][64]记录每一状态下的最小度量值,初始化为0
(3)回溯译码长度:这里定义为48。
如输入比特0,和转移为。根据这个关系,就可以很容易地确定状态的前后转移关系。
图

1 (2,1,7)编码器结构图

3 Viterbi译码
3.1 基本原理
由于编码的过程就是卷积码编码器状态之间不断跳转的过程,所以编码网格图完全描述了一个特定卷积码系统的特性。一旦我们确定了整个编码过程的状态转移过程,卷积码的输入就完全确定了。Viterbi译码解码就是基于马尔可夫链中状态转移的知识,利用编码网格图,在其中搜索一条路径使其接近实际路径,搜索到这条路经称为幸存路径。因此,
图2 (2,1,2)卷积码网格图(实线输入0,虚线输入

1)

(下转

154




页)
152
科技咨询导报 Science and Technology Consulting Herald
卷积码Viterbi译码算法的FPGA实现_信息与通信_工程科技_专业资料。希望对大家有...开发软件投入少、芯片价格不断降低,特别是对小批量、多品种 的产品需求,使 ...
卷积码Viterbi译码算法的F... 4页 20财富值 数字通信中卷积码Viterbi译...... 可采用循环移位 的方式, 避免重复读写; 在软件实现时如果采用指针的方式 技术...
动态规划:卷积码的Viterbi译码算法_计算机软件及应用_IT/计算机_专业资料。实现了(2,1,3)卷积码编码、经过白噪声有噪信道加噪、维特比译码解码。附java源代码及...
在卷积码研究方面,随着 Viterbi 算法的提出及序列译码算法 Fano 算法 的提出,也...这既可用硬件实现,也可用软件实现。前者主要用各 种数字电路,主要是采用大规模...
门限译码算法[4]曾 经是卷积码的第一种实用的译码方法。该算法虽然误码性能稍差但易于实现,使 卷积码在有线和无线信道的数据传输中得到了一些实际应用。 Viterbi...
卷积码Viterbi译码的优化与实现_信息与通信_工程科技_专业资料。卷积码的FPGA...3 V iterb i算法的 FPGA 实现 ( 2, 1 6) 卷积码 V iterb i译码器的...
计算机软件及应用卷积码编译码...卷积码编译码算法研究与实现 1 摘 要 在数字通信...网格图在卷积码的概率译码,特别是 Viterbi 译码中...
卷积码及其维特比译码算法的软件实现_信息与通信_工程科技_专业资料。第 37 ...Sof t ware Method of Implement Convolutional Code and Its Viterbi Decoding ...
卷积码的 V iterb i 译码算法 在数字移动通信中, 如何降低数据传输的误码率,...根据前述方案, 我们设计出 FPGA 的逻辑电路, 在 FPGA 的仿真软件 . W o ...
热门文档