MI Shuo-ling
摘要: (2,1,7)卷积 码 作 为 差 错 控 制 手 段 在 卫 星 通 讯 领 域 得 到 了 广 泛 应 用 。 本 文 研 究 并 实 现 了 一 种 软 件 方 式 的 基 于(2,1,7)卷 积 编 码 的 维 特 比 译 码 (Viterbi) 解 决 方 案 , 测 试 结 果 表 明 , 该 方 案 能 够 使 得 误 码 率 为 10-3 量 级 的 数 据 经 译 码 处 理 后 误 码 率 降 低 到 10-6, 可 以 满 足 维 特 比 译 码 应 用 需 求 。 关键词: 卷积码; Viterbi 译码; 蝶形运算 中图分类号: TP311.1 文献标识码: A
体汉明距离矩阵
定义如下:
应的输出
,并把
清空。
5、程序流程图
程序流程图如图 3 所示。
图 3 程序流程图
3.2 结果验证
在验证该维特比译码方案的性能时, 对多个不同的原始文
件进行测试。 这些原始文件都包含 107 个信息码元,首先对原始
文 件 进 行(2,1,7)卷 积 编 码,然 后 加 噪 声 处 理 以 后 进 行 维 特 比 译
码,最后对原始文件和维特比译码文件进行误码比较,从而统计
原始误码率和相应的维特比译码误码率。需要注意的是,噪声处
理是在卷积码文件中随机的修改固定个数的信息码元, 所以在
技 两 次测 验 中,即使 是 相 同的 原 始 误码 个 数,因为 其 误 码的 同。 表格 1 中给出测试过
路 径,减 少 传 统 的 回 溯 阶 段 。 本 文 所 述 算 法 已 经 应 用 于 单 位 科 研
项目中,稍加修改,可广泛应用于通讯等领域。
本文创新点: 使用两个路径度量寄存器,在蝶形运算模块采
用乒乓操作运算,有效简化蝶形运算。 同时,采用路径存储器及
时记录幸存路径,减少译码输出阶段的回溯时间。
5 结论
本文 的 创新 点 为:针 对 Ad hoc 接 入 网 中 Jelger 算 法 存 在 的 一些不足,引进了网关负载平衡的概念对原算法进行了改进,以 减少其网关切换次数。通过实验证明该改进算法与原算法相比, 能够降低节点平均网关切换次数,有效地平衡网关负载,可解决 因为最小跳数算法引起频繁切换网关和大量移动节点选择同 一网关而造成的负载过高等问题。 本文研究结果对于工业控 制、民用等各个方面的无线局域网接入技术的发展具有一定的 参考价值。 参考文献 [1] 郑少仁, 王海涛, 赵志峰等. Ad hoc 网络 [M]. 人民邮电出版 社, 2005.
术 程 中 得 到 的 平 均 数 据 , 从 表 格 1 中 可 以 看 到 原 始 误 码 率 在
10-3 数 量 级 时 , 维 特 比 译 码 误 码 率 达 到 10-6, 达 到 了 维 特 比
译码的目的。
创
表格 1 维特比译码前后误码率统计情况
新
假设理论输出码元比特为 ,接收到的信息码元比特为
,那么分支度量的计算公式就是:
。
3、加 -比 较 -选 择 (ACS)的 蝶 形 计 算
所谓“加”是指计算路径距离累加值。 维特比网格图中有 64
个 状 态,分 别 有 两 条 路 径 进 入 每 个 状 态 i,分 别 计 算 这 两 条 路 径
的分支度量值为
。 两条路径与相应的分支度量值相加
然后“比较”
图 2 维特比译码基本结构图
米朔灵: 硕士研究生
3.1 程序结构设计
- 110 - 360元 / 年 邮局订阅号：82-946
《现场总线技术应用 200 例》
您的论文得到两院院士关注
网络与通信
根据维特比译码原理, 一个完整的维特比译码软件包括以
下几个部分:信元输入、分支度量计算、ACS 蝶形计算、选取 最 佳
, 开辟两个数组来辅助乒乓操作
计算。 初始化为
,
其中 MAX 是 的近似值。
(2)译码深度 L,是指单次循环中处理信元的长度。 根据维特
比 译 码 截 断 定 理,译 码 深 度 最 小 为 5~10 倍 的 m,本 程 序 动 态 改
变译码深度,较理想译码深度为 L=48。
(3) 两个输出信息比特寄存器
this kind of Viterbi decoding algorithm is able to decrease the bit error rate from 10 -3 to 10 -6 and thus it can be used for error
技 control.
Key words: convolutional code; Viterbi decoding; Butterfly compute
路径和译码输出。 在一个译码周期内,读取输入信息码元后,计
算输入信息码元与各个可能输出码的分支度量值, 然后对每个
状态蝶形计算,最后选取幸存路径并译码输出。基本结构图如图
2 所示:
软件实现具体步骤如下:
1、程序初始化
在程序设计中需要首先确定三个重要参数路径度量器、译
码深度和输出信息寄存器。
(1)两 个 存 储 路 径 度 量 值 的 路 径 度 量 器
前路径度量值,避免单次循环后对 preDistance 的频繁更新。
4、输出译码信元
当输入码组超过译码深度时,开始产生译码输出,它是通过
比较 64 条幸存路径,选取其中具有最小距离的一条作 为 最 佳译
码路径, 然后输出该路径对应的路径寄存器中的相应的信息比
特,作为译码输出比特。 采用
记录
幸存路径,不需要回溯输出,只需要将与
有关。 卷积码的通用表示方式为(n,k,m),其中 k 表示在每个时间
单位, 输入编码器的信息码元个数;n 表示编码器 针对 k 个 输 入
的 输 出 码 元 个 数 ;m 则 表 示 编 码 约 束 长 度 。 本 文 将 重 点 讨 论
(2,1,7) 卷 积 码 ,(2,1,7) 卷 积 码 的 生 成 多 项 式 为 (171,133), 包 括 6
4.2 仿真结果分析 首先对两个算法 分别 进 行 了 900s 的 仿 真,统计 节 点 的平 均 网关切换次数,如图 3 所示。
图 3 节点的平均网关切换次数 我们可以看出,与原算法中网关切换次数相比,由于对网关 切换的条件做出了一定的限制, 改进算法中节点切换网关的次 数 有了 明 显 地减 少 。 在 原算 法 中 平均 每 个 节点 发 生 约 50 多 次 网 关 切 换,而 改 进 算 法 中 只 有 约 18 次,网 关 频 繁 切 换 的 问 题 得 到了较大改善。 接着又仿真了节点以 0~60 之 间 的多 个 不 同速 率 发 送 CBR 分组的情况,如图 4、图 5 所示。
网络与通信
文 章 编 号 :1008-0570(2010)12-3-0110-02
《微计算机信息》(管控一体化 )2010 年第 26 卷第 12-3 期
(2,1,7)维特比译码软件实现方法研究
Software Implementation of (2,1,7) Viterbi Decoding
(中国科学院研究生院) 米 朔 灵
但是硬件方式的解决方案使用受限, 必须要有与之配套的物理 然路径的支路,最后得到一条接近实际路径的幸存路径。维特比
接口。因此,深入研究方便使用的软件方式的维特比译码算法很 译码器有以下几个特点:
有必要。
1.(n,k,m)卷 积 码 共 有
个状态,因而一般的维特比译码
2 卷积码编 码和 Viterbi 译码
Abstract: The (2,1,7) convolutional code, as the recommended standard by CCSDS, has been applied widely in the field of com-
munication. This paper presents a software implementation of Viterbi decoding for (2,1,7) convolutional code. The result shows that
的最小值对
4 总结
本文 介 绍了 一 种(2,1,7)卷积 码 维 特比 译 码 算法 的 软 件 实 现
方案。维特比译码是一个动态编程的过程,其中“加-比较-选择”
模 块 是 核 心 模 块,该 方 案 在 “加-比 较 -选 择 ”模 块 中 引 入 乒 乓 操
作计算, 并使用输出信息比特寄存器及时记录译码过程中幸存
,
存储每个状态幸存路径的输出信息比特。 初始化为 null 矩阵。
2、计算分支度量
分支度量指的是输入信息码元和卷积编码各个可能输出
码元的距离。 一般有采用欧氏距离计算的软判决和采用汉明距
离计算的硬判决,在硬件设计中,软判决较硬判决优
。但
是,在软件设计中,分别采用软判决和硬判决的分支度量计算的
本质一样。故采用了实现较为简单的硬判决计算分支度量值,具
参考文献
[1]刘国锦,王济生等.卷积码的 Viterbi 高速译码方案[J].微计算机
信息.2009,6-2:p243-245
[2]王新梅,肖国镇.纠错码-原理与方法[M].西安电子科技大学出
版社.1991
[3]张宗橙. 编码理论-算法、结构和应用[M].人民邮电出版社.2009
[4]刘少阳,邹永.(2,1,7)卷积编码及其维特比译码算法的软件实
会因为存储量太大而难以实用化。根据维特比译码截断定理,译
图 1 (2,1,7)卷积编码状态转移示意图 2.1 卷积编码
码深度一般为 5~10 倍的 m.
3 Viterbi 译码的软 件实现
卷 积 码 是 Elise 于 1955 年 提 出 的 一 种 按 比 特 编 码 的 技 术,