第 18卷 Vo1．18 第 8期 No．8 电子设 计工 程 Electronic Design Engineering 2010年 8月 Aug．2010 基于 FPGA 的卷积 编译码 器 的设计 与实现 刘 杨 ．章 敏 (桂 林 电 子 科技 大 学 广 西 桂 林 541004) 摘 要 ：为 了解 决 传 统 的 维特 比译 码 器结 构 复 杂 、译 码 速 度 慢 、消耗 资 源 大的 问题 ，提 出一 种 新 型 的 适 用 于 FPGA特 点 ， 路 径 存 储 与 译 码 输 出 并行 工作 ，同 步存 储 路 径 矢量 和 状 态 矢 量 的译 码 器设 计 方 案 。该设 计 方 案 通 过 在 ISE9．2i中仿 真 验 证 ．译 码 结 果 正 确 ，得 到 编 码 前 的 原 始码 元 ，速 度 显 著提 高 ，译 码 器复 杂 程 度 明 显 降低 。并 在 实际 的软 件 无 线 电通 信 系统 中信 道 编 解码 部 分 得 到 应 用 ．性 能 优 良。 关 键 词 ：卷 积 码 ；维特 比 ；FPGA；软 件 无 线 电 (SDR) 中图 分 类 号 ：TN92 文 献 标 识 码 ：A 文 章 编 号 ：1674—6236(201O)08—0l68—03 Design and implem entation of convolutional codec based on FPGA LIU rang，ZHANG Min (Guilin University ofElectronic Technology，Guilin 541004，China) Abstract：In order to solve the traditional viterbi decoder’S problem such as complex structures， slow decoding， big consumption resources．this paper presented a novel decoder design approach，which is applied FPGA features，the path storage and decoding the output worked in parallel，and the stored path vector and state vector synchronized．The design simulation is proved by ISE9．2i．The decoding results were correct．the decoder could get the source code element，the speed increased and the decoder complexity simplified．In the actual software—defined radio communication system 。the encoding and decoding part of channel is applied to excellent performance． Key words：convolutional code；viterbi decoder；FPGA；software—defined radio(SDR) 卷 积 码 是 Elias在 1955年最 早 提 出的 ，稍 后 ，Wozencraft 效 率 ．m 为 约 束 长 度 。卷 积码 编 码 原 理 如 图 1所 示 。 在 1957年 提 出 了一 种 有 效译 码 方 法 ，即序 列 译 码 。Massey在 1963年 提 出 了一 种性 能稍 差 ，但 比较 实 用 的 门 限 译 码 方 法 ， 由 于这 一 实 用 性 进 展使 卷积 码 从 理 论 走 向 实用 。而 后 Viterbi 在 1967年 提 出 了最 大似 然译 码 法 ，该 方 法 对 存 储 器 级 数 较 图 1 卷 积 码 编 码 器 原 理 图 小 卷 积 码 的译 码 很 容 易实 现 ，并 具 有 效 率 高 、速度 快 、译 码 器 Fig．1 Principle diagram of convolutional encoder 简 单 等 特 点 ．人 们 后 来 称 其 为 维 特 比算 法 或 维 特 比译 码 ，广 泛 应 用 于 现 代 通 信 中 。本 文 主 要 论 述 了基 于 Xilinx公 司 的 FPGA的 卷 积 编码 器 及 相 应 的维 特 比译 码 器 的研 究 ．并 在 幸 存 路 径 存 储 与译 码 输 出判 决 方 面提 出 了 改进 算 法 ，从 而 使 译 码 器 结 构 得 到 简 化 。 1 卷 积 码 的 编 码原 理 与 实现 卷 积 码 是 一 种 重 要 的 前 向 纠错 编 码 FEC，用 (n，k，m)表 示 ．分 组码 不 同 ．其 监 督 元 与 本 组 的信 息 元 和 前 若 干 组 的 信 息 元 有 关 。这 种 编 码 的 纠 错 能力 强 ，不 仅 可 纠 正随 机 差 错 ，而 且 可 纠 正突 发 差 错 。卷 积 码 根 据 需 要 ，有 不 同 的 结 构 及 相 应 的 纠错 能力 ．但 都 有 类 似 的编 码 规 律 。卷 积 码 的 编 码 器 是 一 个 具 有 k个 输 入 位 (端 )、n个 输 出位 (端 )，m 级 移 位 寄存 器 的 有 限状 态记 忆 系 统 ．通 常 称 为时 序 网络 。其 中 R=k／n为 编码 收 稿 日期 ：2010—03—02 稿 件 编 号 ：201003010 卷 积 编 码 充 分 利 用 各 组 信 息 元 之 间 的相 关 性 ，在 误 码 率 和 复 杂 度相 同 的情 况 下性 能优 于分 组 码 ，并 且 最 佳 译 码 更 易 实 现 ．因 此 在 通 信 系 统 中得 到 广 泛 应 用 。 但 是 卷 积 码 没 有 严 格 的代 数结 构 ．尚未 找 到 严 密 的 数 学 手 段 将 纠 错 性 能 与码 的 构 成 有 规 律 地 联 系 起 来 ， 目前 大 都 采 用 计 算 机 搜 索 好 码 。 通 常 是 (2，1，3)卷 积 码 ，本 文 以 生 成 多 项 式 G=(11l，101)的 (2，1，3)卷 积 码 为 例 介 绍 设计 和实 现 过 程 。 设 初 始 状 态 为 SO编 码 为 00，根 据 生 成 矩 阵 分 别带 入输 入 0和输 入 1时 得 到 下一 个 状 态 和相 应 输 出 。依 次 代 入 ，可 得 到如 图 2所 示 的状 态 图 。 描 述 卷 积 码 的方 法 主要 有 两 类 IlJ：图解 表 示 和 解 析 表 示 。 上 文提 到 的生 成 多 项 式 G=(111，101)即是 解 析 表 示 。卷 积码 的 图解 表示 又 可 分 为 树状 图 、网 格 图 和 状 态 图 3种 。下 面介 绍 常 用 的树 状 图 表 示 (网格 图 表 示 将 在 译 码 部 分 介 绍 )。在 图 2所 示 的卷 积 编 码 树 状 图 中 。假 设 移 位 寄存 器 的 起 始状 态 作 者 简 介 ：刘 杨 (1984一 )，男 ，江 西 九 江人 ，硕 士研 究 生 。研 究 方 向 ：通 信 与 信 息 系统 。 - 168- 

刘 杨 ，等 基 于 FPGA 的卷积 编译 码 器的设 计 与 实现 a o0 b 0I c 1O d 图 2 编 码 器 状 态 罔 Fig．2 State diagram of erlco~er 图 4 (2，1，3)卷 积 码 的 网格 图表 示 Fig．4 Trellis of(2，1，3)convolutional codes (2，l，3)卷 积 码 的情 况 ，因 此 k=l，假 设 起 始 状 态 为 全 0。 全 为 0，当第 1个 输 入 比特 为 0时 ，输 出 比特 为 O0；若 输 人 比 在 不 同 时 刻 对 于 同 一 节 点 的所 有 8个 状 态 ．分 别 计 算 以 特 为 1时 。则 输 出 比特 为 11。随 着 第 2个 比 特输 入 ，第 1个 比 其 为 终 点 的 2条 分 支 路 径 的 对 数 似 然 函 数 累 加 值 并 进 行 比 特 右 移 1位 ，此 时 输 出 比特 同时 受 当 前 输 入 比特 和第 1个 输 较 ，舍 弃 其 中 对 数 似 然 函 数 累 加 值 小 的 路 径 ，保 留 对 数 似 然 入 比特 的影 响 。第 3个 比 特输 入 时 ，第 1、2比 特 分 别 右 移 1 函 数 累 加 值 较 大 的路 径 ，并 将 此 路 径 称 为 剩 余 路 径 。 由此 可 位 ．同时 输 出 2个 由 这 3位 移 位 寄存 器存 储 内容 所 共 同 决 定 见 ，上 述 过 程 可 以 归 纳 为 “加 一比一选 ”算 法 ．经 过 “加 一比一选 ” 的 比 特 。 当第 4个 比特 输 入 时 ，第 1个 比特 移 出移 位 寄 存 器 电 路 以后 ，通 过 结 束 信 息 来 确 定 最 终 得 到 的 译 码 序 列 ，其 中 而消 失 。 移 位 过 程 可 能 产 生 的 各 种 序 列 如 图 3中 的 二 叉 树 。 每 到 来 一 个 结 束 信 息 时 ．只将 与 已知 发 送 信 息 相 符 的 那 条 支 路 保 留 ，以此 类 推 ，经 过 ^L1个 结 束 信 息 后 ，即 可 得 到 与 发 送 序 列 最 相 似 的译 码 路 径 。 3 译 码 器 设 计 与 实现 维 特 比译 码 器 包 括 4个 子 模 块 ，如 图 5所 示 。 图 3 (2，1，3)卷 积 码 的 树 状 图表 示 Fig．3 Tree diagram of(2,1，3)convolutional codes 图 5 维 特 比译 码 器 的总 体 框 架 Fig．5 Overall framework of veterbi decod er 2 Veterbi(维 特 比 )译 码 器 原 理 1)控 制 单 元 向 各 个 功 能 模 块 提 供 控 制 信 号 ，保 证 译 码 卷 积 码 的译 码 方 式 有 3种 ：Veterbi译 码 、门 限译 码 和 序 器 的 工 作 时 序 正 确 ，协 调 各 个 功 能模 块 从 而 促 使 整 个 译 码 器 列 译 码 。 其 中 维 特 比译 码 具 有最 佳 译 码 性 能 ，但 硬 件 实 现 相 的 正常 工 作 。 对 复杂 。veterbi算 法 是检 测离 散 马 儿 可 夫 过 程 有 限 状 态 序 列 2)路 径 度 量 和 “加 一比一选 单 元 ” 计 算 和 比较 每 条 支 路 的优 化 算 法 i41。在 数 字 通 信 系 统 中 ，前 向 纠 错 卷 积 码 编 码 和 维 的路 径 度 量 ．得 到 并 保 存 剩 余 路 径 提 供 给 回 溯 单 元 。 对 于 特 比译 码 用 来 提 高 系 统 性 能 ，应 用 广 泛 。 (2，1，3)卷 积码 ，译 码 深 度 D=5(m+1)=20，为保 证 存 储 单 元 和 维 特 比算 法 是 一 种 最 大 似 然 译 码 算 法 。它 不 是 在 网 格 图 回溯 单 元 同 时 并 行 工 作 ，存 储 单 元 为 2D(m十1)2 =l 280 bit。 上 一 次 比较 所 有 可 能 的 2条 完 整 路 径 ，而 是 接 收 ～ 段 ，计 算 比 较 一 段 ，选 择 一 段 最 有 可 能 的 码 段 ，从 而 达 到 整 个 码 序 列 3)回 溯 单 元 从 前 面 “加 一比一选 ”电 路 送 来 的 剩 余 路 径 中选 择 量 度 最 小 的剩 余 路 径 ，从 这 条 路 径 对 应 的状 态 开 始 向 是 一 个 有 最 大 似 然 函 数 的序 列 。其 基 本 原 理 是 ：以 断 续 的 接 前 寻 找 ，直 到 找 完 前 面 所 有 状 态 ．并 从 存 储 单 元 中 读 出 译 码 收码 流 为 基 础 ，逐 个 计 算 它 与 其 他 所 有 可 能 出 现 的 连 续 的 格 信 息 送 给 译 码 控 制 单 元 。 状 图 路 径 的 距 离 ，选 出 其 中概 率 最 大 的 一 条 作 为 译 码 输 出 。 4)译 码 控 制 单 元 将 回溯 单 元 送 来 的 译 码 序 列 反 转 顺 序 维 特 比 (Veterbi)译 码 算 法 是 基 于 卷 积 码 的 网 格 图 表 示 输 出 即为 所 要 输 出 的 正确 的接 收序 列 。其 中反 转 顺 序 的 操 作 中 路径 的 计 算 ，其 核 心 思 想 就 是 通 过 计 算 路 径 矢 量 进 而 寻 找 可 由 RAM 实 现 ，顺 序 写 入 倒 序 读 出 。 最 短 路 径 从 而 最 终 得 到 译 码 序 列 并 可 以 纠 正 传 输 过 程 中 的 错 误 码 字 。 图 4中给 出 (2，1，3)卷 积 码 的 网格 图表 示 l 。 4 译 码 器 设 计 中 改进 和优 化 算 法 图 4中 的 网 格 图 中共 有 2“ 种 状 态 ．每 个 状 态 (节 点 )有 本 文 采 取 状 态路 径 和 判 决 比特 同 时 存 储 ，在 表 示 状 态信 2^条 支 路 进 入 ，同 时也 有 2 条 支 路 引 出 。 由 于 本 文 讨 论 的 是 息 的 比 特 前 加 上 l位 判 决 比 特 来 表 示 相 应 状 态 的输 入 支 路 一 169- 

《电子设计 工程 }2010年 第 8期 的译 码 信 息 ，因 此 ，译 码 器 在 回 溯 时 就 可 直 接 输 出 判 决 比特 存 储 路 径 量 度 的 寄 存器 位宽 为 lb(2x3)=3。 作 为 译 码 器 的输 出 ，降 低 了译 码 器 的 判 决 难 度 ，节 省 了存 储 回溯 路 径 所 需 要 的 内存 ，从 而 降 低 了译 码 器 结 构 复 杂 性 。 5 验 证 仿 真 本 设 计 中 译 码 器 在计 算 所 有 状 态 的 路 径 量 度 的 同 时 进 本 设 计 采 用 Xilinx公 司 的 ISE 9．2i为 开 发平 台 ，选 用 的 行 路 径 存 储 ，从 而 大 大 提 高 了 译 码 速 度 。路 径 量 度 是 指 每 个 是 Xilinx Virtex 4 FPGA 为 开 发 芯 片用 于 设 计 和 验 证 所 提 出 状 态 的 2条 输 入 支 路 和 2条 输 出支 路 ，路 径 存 储 指 的 是 状 态 的 卷积 编码 和 维 特 比(Veterbi)译 码 算 法 。 存 储 以及 相 应 的译 码 判 决 比特 存 储 。该 结 构 的译 码器 对每 一 5．1 卷 积 编 码 器 个 状 态 都 具 有 独 立 的处 理 单 元 ，彼 此 互 补 影 响 ，并 行 工作 ，提 如 图 6所 示 ．clk为 时 钟 信 号 ，reset为 复 位 信 号 ，din为 输 高 了译 码 速 度 。对 于 (2，l，3)卷 积 码 ，一 个 时 钟 需 要 进 行 2x2x 2==-32次路 径 量 度 计 算 和 2 8次 4比特 存 储操 作 。充 分发 挥 了 FPGA 拥 有 大量 LCS和 RAM 的优 势 。 在 网格 图 中 ，随 着 状 态 的 改 变 ，每 个 状 态 的 输 出 支 路 的 路 径 量 度 逐 渐 增 加 ，造 成 存 储 资 源 压 力 增 大 ，设 计 中 在 每 次 进 行 路 径 量 度 计 算 时 ，将 该 状 态 的 量 度 值 与 上 次 剩 余 路 径 量 入 信 号 。out_l，out_2为 编 码 后 得 到 的 并行 码 字 序 列 。可 看 出 ： 输 入码 元 为 “1010101l1Oll 0001000110111l1l1l100… … ”经 过 编 码 得 到 编 码 结 果 为 “110100Ol00O10010101O00l0 1011o01101l1oo11101001O10l01O101Ol0lOn ”结 果 正 确 。 5．2 Verterbi译 码 器 Ve~erbi译 码 器 仿 真 波 形 如 图 7所 示 ，rev[h0]为 输 人 译 度 的 最 小 值 做 差 后 进 行 保 存 ，以 达 到 减 小 存 储 器 空 间 的 需 码 器 的 接 收 序 列 ，clk为 时 钟 信 号 ，rst为 复 位 信 号 ，enable为 求 。对 于编 码 效 率 为 1／2的卷 积 码 ，以 上差 值 最 大 不 超 过 2m， 使 能信 号 ，h_out为 译 码 器 输 出 序列 。 可 看 出 ：译 码输 出码 元 因此 ，路径量度的量化宽的为 lb(2m)。对于(2，l，3)卷积码 ， 为 “101010l110110001000l101lll1l11100… … ”，结果 正确 。 图 6 卷 积 编 码器 的仿 真 波 形 Fig．6 Simulation wavefolqll of eonvolutional eneoder 图 7 维 特 比译码 器 的仿 真 波 形 Fig．7 Simulation waveform of veterbi decoder 6 结 束语 [3]夏 宇 闻．Verilog~ 字 系统 设 计 教 程 【M】．北 京 ：北 京航 空航 天 大 学 出版社 。2003． 通过 对卷 积编 码 原 理 与 维特 比译 码算 法 的 深 入 研 究 ，在 【4]Viterbi A肛 r-for bounds ofconvolutional codes and an asymptoti— 理 解 传 统 实 现 方 法 的 基 础 上 提 出 适 合 FPGA存 储 器 和 独 立 cally optimum decoding algorithm [J]．IEEE Transations on 运 算 单 元 丰 富 的 特 点 的 优 化 算 法 ，有 效 地 提 高 了译 码 器 的 处 Information Theory，1967，13(2)：260—269． 理 速 度 ，简 化 了译 码 器 的复 杂 程 度 。 【5]Anderson J B，Offer E．Reduced·state sequence detection 参 考 文 献 ： with convolutional codes~]．IEEE Transactions on Information 【l】曹志 刚．现代 通信 原理 【M】．北 京 ：清华 大学 出版 社 ，1994． Theory，1994，40(3)：965-972． [21王新 梅 ，肖 国镇 ．纠 错 码 原 理 与 方 "：-A[MI．西安 ：西安 电 子 科 【6】Proakis J G，Salehi M．Digital communicati0ns【M】．北 京 ：电 技 大 学 出版 社 。1991． 一 l7O一 子 工 业 出版 社 ．2006．