1 引言

Size: px

Start display at page:

Download "1 引言"

潮谈暂费
5 years ago
Views:

1 第 36 卷第 17 期计算机工程 2010 年 9 月 V ol.36 No.17 Computer Engineering September 2010 工程应用技术与实现文章编号 : (2010) 文献标识码 :A 中图分类号 :TN764 超宽带系统中维特比译码器的设计与实现欧阳淦, 刘亮, 叶凡, 任俊彦 ( 复旦大学专用集成电路与系统国家重点实验室, 上海 ) 摘要 : 提出一种超宽带系统中的维特比译码器, 对混合幸存路径管理单元进行改进, 使其最高工作频率提升 25%, 译码延时减少 40 个时钟周期在 Xilinx Virtex-5 XC5VX330 FPGA 上的实现结果表明, 该维特比译码器能在 240 MHz 的时钟频率下正确工作并行使用 2 个该译码器, 可对系统中所有 8 种速率的数据译码关键词 : 超宽带 ; 维特比算法 ; 混合幸存路径管理 Design and Implementation of Viterbi Decoder for Ultra-WideBand System OUYANG Gan, IU iang, YE Fan, REN Jun-yan (State Key ab of ASIC & System, Fudan University, Shanghai ) Abstract This paper focuses on the design of Viterbi decoder for the Ultra-WideBand(UWB) wireless system. It improves the hybrid survivor path management unit in the decoder, promoting its imum operating speed by 25% and reduces its decoding latency by 40 clocks. The implementation result on the Xilinx Virtex-5 XC5VX330 FPGA shows the Viterbi decoder this paper presents can work correctly at 240 MHz. The data transmitted at all the eight kinds of speed can be decoded by using two slices of such Viterbi decoder in parallel. Key words Ultra-WideBand(UWB); Viterbi algorithm; hybrid survivor path management 1 概述超宽带 (Ultra-WideBand, UWB) 是一种高速短距离无线通信技术, 能在 2 m~10 m 的范围内以 53.3 Mb/s~480 Mb/s 的速率传输数据, 具有较大的技术潜力和广阔的商用前景 MB-OFDM 方案是超宽带的一种实现方案, 被采纳为 EMCA 368 标准 [1] 为了提高通信系统的抗干扰能力, 使发送的信息可靠地在接收端重现, 现代通信系统几乎都采用前向纠错编解码技术 MB-OFDM 方案采用约束长度 K 为 7 码率 R 为 1/3 的卷积码作为前向纠错编码, 并推荐使用维特比 (Viterbi) 算法对其解码 MB-OFDM UWB 系统的数据传输率高卷积码的约束长度大, 给系统中的维特比译码器的设计带来了较大的挑战维特比译码器一般由分支度量单元 (BMU) 加比选择单元 (ACSU) 和幸存路径管理单元 (SMU) 组成 ACSU 一般是整个译码器关键延时路径所在, 高速维特比译码器常采用超前 ( 主要是 radix-4) 结构 [2] [3] 比特级流水线结构或将 ACSU 替换为 CSAU [4], 以提高译码器的吞吐率本文设计的维特比译码器就采用了 CSAU SMU 有 2 种传统的实现方法 : 寄存器交换 (RE) 和回溯 (TB) RE 实现简单并能够每个时钟输出一个译码值但如果卷积编码器的约束长度大,RE 需要大量的寄存器和数据选择器实现, 并且这些寄存器和数据选择器在每个时钟都可能翻转, 面积和功耗都很大 TB 采用集成度很高的 RAM 实现, 虽然能够较大程度减少面积和功耗, 但译码延时较大, 并且不能保证每个周期都能输出一个译码值, 从而制约了译码器的吞吐率混合幸存路径管理结构结合了 RE 和 TB 的优点, 在降低译码器面积和功耗以及提升吞吐率之间取得了较好的 260 平衡 [5] 然而由于 MB-OFDM UWB 的维特比译码器状态数高达 64, 若采用混合幸存管理方法, 则 SMU 的最高工作频率相对于 CSAU 的最高工作频率要低 23%, 而且译码延时高达 105 个时钟周期为进一步提高译码器的工作频率, 并降低译码延时, 本文设计一种改进的混合幸存路径管理结构采用这种改进结构能够使译码器最高工作频率提升 25%, 并将译码延时减少 40 个时钟周期, 所做改进仅仅会增加少量硬件开销并略微地降低译码性能 2 维特比算法维特比算法实际上是一种最大似然译码算法, 即通过寻找最接近于接收序列的发送码字序列实现译码卷积编码器本质上是一个有限状态机, 而编码过程则会在一个网格图中产生一条状态转移序列因此, 维特比算法就可以在网格图中寻找最可能与接收序列对应的编码器的状态转移序列, 从而找到编码前的信息并实现译码对于每一个输入到维特比译码器的待译码符号,BMU 会计算它与每一个可能的发送码字之间的相近程度, 即分支度量这样, 网格图中的每个可能的状态转移分支都会有一个对应的分支度量一系列连续的状态转移分支构成一条状态基金项目 : 国家科技重大专项基金资助项目新一代宽带无线移动通信网 (2009ZX ) 作者简介 : 欧阳淦 (1986-), 男, 硕士研究生, 主研方向 : 无线通信系统信道编解码器的 VSI 实现 ; 刘亮, 博士研究生 ; 叶凡, 讲师 ; 任俊彦, 教授博士生导师收稿日期 : jyren@fudan.edu.cn

2 转移路径, 而这一系列转移分支的分支度量的和就是这条路径的路径度量路径度量由 ACSU 累加对于网格图中的每一状态,ACSU 会比较汇集到该状态的 2 条路径的路径度量, 选择并保留其中路径度量较大的那条路径作为该状态的幸存路径当前时刻所有状态的幸存路径中, 路径度量最大的那条幸存路径称为该时刻的最终幸存路径 SMU 会保存当前时刻之前一段时间内 ACSU 输入的选择结果 ( 判决信息 ), 并沿着该时刻的最终幸存路径回溯, 推断出对应的编码器的状态转移序列, 从而实现译码 MB-OFDM 采用的约束长度 K 为 7, 码率 R 为 1/3 的卷积码, 并且通过有规律地去掉某些编码后的比特形成所谓的凿孔码后再进行传输这样整个系统的码率或者说传输效率就能提高去掉的比特不能为维特比译码器提供任何有用信息, 故而较高的码率也意味着较低的译码性能表 1 列出了 MB-OFDM UWB 所有 8 种传输速率相应调制方式和卷积码的码率表 1 8 种传输速率对应的调制方式和码率速率 /(Mb s -1 ) 调制方式码率 53.3 QPSK 1/3 80 QPSK 1/ QPSK 1/3 160 QPSK 1/2 200 QPSK 5/8 320 DCM 1/2 400 DCM 5/8 480 DCM 3/4 3 维特比译码器的 VSI 实现 3.1 BMU 对于 AWGN 信道, 某一时刻 t 某条分支的分支度量计算如下 : BM( b0bb 1 2) = ( I0 S0) + ( I1 S1) + ( I2 S2) 其中,b 0 b 1 b 2 为这条分支对应的二进制码字而 S i 与 b i 对应, 当 b i 为 1 时,S i 为 +A; 当 b i 为 0 时,S i 为 -A I 0 I 1 I 2 是解调器提供给维特比译码器的 8 段量化信息, 对于同一时刻的所有分支度量, 它们的值是相等的于是分支度量可表示为 BM ( b0b1b 2) = I0sign( S0) + I1sign( S1) + I2sign( S2) 其中,sign(S i ) 为 S i 的符号, 用 +1 和 -1 表示考虑到打孔码,8 段量化信息需要用 4 bit 表示为 {-7, -5, -3, -1, 1, 3, 5, 7}, 而对于打孔位置, 译码器将对应的 I 0 I 1 I 2 均为 4'b0000 因此,BMU 可以简单地用 8 组加法器实现, 每组加法器的输入为 3 个 4 bit 数据 3.2 CSAU 与 ACS 结构 ( 这里仅考虑普通的 radix-2 结构 ) 相比,CSA 结构的关键路径减少了一级比较器相比于 ACS 结构,CSA 结构能以增加将近 1 倍面积的代价将吞吐率提高约 40%( 对于 8 状态的维特比译码器 ) [4] 根据后面提到的仿真结果,CSAU 的延时与改进后的 SMU 的延时接近, 因此, 本文所设计的译码器也采用 CSAU 无论是 ACSU 还是 CSAU, 设计时候都必须考虑路径度量不断累加而产生的溢出对于 radix-2 的 ACSU 以及 CSAU, 只要路径度量的位宽 Γ bits 满足下式 : Γbits lb( Δ + λ ) + 1, Δ = λ lbn 则累加器的溢出将不影响路径度量之间的相对大小, 也就不会影响解码结果其中, λ 为分支度量的最大值 ;N 为译码器的状态数 ; Δ 为路径度量的最大值在本译码器中, λ =21, N=64, Δ =126, 因此 CSAU 中路径度量用 9 bit 表示就能防止溢出考虑到 BMU 输入给 CSAU 的分支度量可能为负数,CSAU 需要采用 10 bit 的加法器和比较器才能防止溢出 3.3 SMU 采用 TB 实现 SMU 时,RAM 被划分为 3 个部分 : 入块, 合并块以及译码块, 如图 1 所示判决信息译码块 D 最终幸存路径合并块入块 D 回溯入图 1 基于 TB 方法的 SMU 实现维特比译码器有个重要的性质, 即不论从哪个状态出发并沿着该状态的幸存路径回溯, 当回溯长度超过 5K 时, 这些幸存路径有很大的概率汇聚成同一条路径, 也就是最终幸存路径因此, 合并块的深度一般需要大于 5K 当合并块满级后开始从任意状态出发执行回溯操作, 同时入块也开始入判决信息但是当回溯 D 级后, 入块也刚刚满, 此时须停止入判决信息直至回溯进行到译码块的最左边因此,TB 法并不能做到每个时钟都输出一个译码值, 吞吐率也受到较大限制采用 RE 实现 SMU 要直观很多, 仅仅需要将寄存器和数据选择器按照卷积编码器网格图连接起来 [4] 这些寄存器都采用同一时钟控制, 每一时钟能够输出一个译码值因此维特比译码器的吞吐率就等于这个时钟的频率寄存器和数据选择器 ( 归一化为 1 bit 的寄存器和 1 bit 的 2 选 1 数据选择器 ) 的数目可以根据下式确定 : K -1 寄存器数目 = 数据选择器数目 = 2, 5K 在 MB-OFDM 中,K=7, 于是寄存器和数据选择器的数目都将高达个这对维特比译码器的面积和功耗都相当不利混合幸存路径管理方法包括预回溯 (Pretrace-back) 和前向追溯 (Trace-forward)2 种不同的实现方法 [5] 预回溯当 K 较大时较难设计, 因此, 本文采用相对简单的前向追溯结构采用前向追溯法实现 SMU 时, 同样将 RAM 划分为入块合并块和译码块, 如图 2 所示, 不过此时 3 个部分的深度相同判决信息译码块最终幸存路径回溯合并块入块图 2 基于前向追溯法的 SMU 实现入前向追溯与 TB 不同的是, 前向追溯法在入判决信息的同时执行前向追溯操作前向追溯操作由用寄存器和数据选择器组 261

3 成的前向追溯单元执行, 这些寄存器和数据选择器同样按照卷积编码器的网格图连接起来连续执行 m 次前向追溯后, m 个时钟周期前的所有状态的幸存路径信息保存在前向追溯单元的寄存器中这样, 开始执行回溯操作时, 译码块最右边的幸存状态已知, 即最终幸存路径的起始点已知这就意味着可以直接从译码块开始回溯并译码因此, 入判决信息与回溯译码同步进行, 译码器的吞吐率也就能提高到译码器的时钟频率 3.4 前向追溯法的具体实现回溯操作实质上就是根据地址指针读取 RAM 中第 n 时刻的信息并用这个信息更新地址指针, 再根据新地址指针读取 RAM 中第 n-1 时刻的信息而如果采用前向追溯结构, 寻找回溯起点时, 需要从前向追溯单元中读出地址指针这 2 个操作是 SMU 中的延时最大的 2 个操作, 且都可能比 CSA 操作的延时大表 2 给出了在 Xilinx Virtex-5 XC5VX330 FPGA 上这 4 种操作的延时比较 ( 综合结果 ) 表 2 不同操作的延时比较操作名称最小延时 /ns 最高频率 /MHz CSA ACS 回溯找回溯起点可见,CSA 结构比 ACS 大约快 33% 而回溯以及寻找回溯起点操作相比于 CSA 操作分别慢 19% 和 23% 分析综合结果发现, 回溯以及寻找回溯起点操作中最大的延时是 64 选 1 数据选择器产生的而且 SMU 的译码延时高达 35 3=105 个时钟周期针对这个问题, 本文设计了一种改进的混合幸存路径管理结构, 在增加少量硬件资源的代价下, 较大程度地降低了译码延时并提高了译码器的最高工作频率如图 3 所示这种改进结构主要增加了 2 个前向追溯单元, 即增加了 768 个寄存器和数据选择器而所使用的 RAM 则由 3 片的 RAM 变成 5 片的 RAM(Mem0~Mem4) 硬件资源的开销并无较大的增加时钟周期 0 13 Mem0 Mem1 Mem2 Mem3 Mem4 Mem0 Mem1 TFU0 Mem2 Mem3 Mem4 前向追溯 26 Mem0 Mem1 TFU0 Mem2 TFU1 Mem3 Mem4 前向追溯 39 Mem0 Mem1 TFU0 Mem2 TFU1 Mem3 TFU2 Mem 寻找回溯起点 2 clocks 2 clocks 前向追溯 Memory TFU TFU Mem0 Mem2 Mem3 Mem 读译码寻找回溯起点 2 clocks 2 clocks 图 3 改进的 SMU 结构 TFU2 前向追溯改进的 SMU 工作原理如下 :SMU 刚刚开始工作时, 判决信息入 Mem0, 由于卷积编码器的最初状态为 0, 此时无需执行前向追溯当 Mem0 完 13 组判决信息后, 判决信息开始入 Mem1, 此时 TFU0 开始执行前向追溯当 Mem1 完 13 组判决信息后, 判决信息开始入 Mem2,TFU0 停止工作, 而 TFU1 开始执行前向追溯当 Mem2 完 13 组判决信息后, 判决信息开始入 Mem3, 此时 TFU1 停止工作, 而 TFU2 开始执行前向追溯当 8 组判决信息入 Mem3 时, 开始寻找回溯起点 : 将 TFU2 的第 0 组 6 bit 寄存器值作为地址指针 addr_p; 用 2 个时钟周期完成 64 选 1 操作 ( 每个周期都完成 1 次 8 选 1 操作 ), 从 TFU1 中读取第 addr_p 组 6 bit 寄存器值作为第 1 次更新后的地址指针 addr_p'; 紧接着的 2 个时钟周期完成 64 选 1 操作, 从 TFU0 读取第 addr_p' 组 6 bit 寄存器值作为第 2 次更新后的地址, 也就是所要寻找的最终幸存路径的起始地址指针 TB_P 整个寻找 TB_P 的过程共需要 5 个时钟周期, 寻找到 TB_P 的同时 Mem3 也刚刚完 13 组判决信息 Mem3 入第 13 组判决信息的同时, 回溯操作也开始执行首先用 1 个时钟周期从 5 个 RAM 的输出结果中选择出 Mem0 的输出结果 Data_ out( 此时刻同时产生 TB_P) 然后依据下式更新回溯指针 : TB_P'[5 : 0] = {TB_P[4 : 0],TB_data} TB_data = Data_out[TB_P] 可以发现, 新的回溯指针 TB_P' 的高 3 位是旧的回溯指针的中间 3 位 TB_P[4:2] Data_out 可看成连续的 8 段, 每段 8 bit 于是可以在 Mem4 入第 1 组判决信息的同一周期, 根据 TB_P 的高 3 位 TB_P[5:3] 选择其中 1 段 8 bit 数据 ; 此周期同时读出新的 Data_out' 再接下来的 1 个时钟周期根据延时 1 个周期后的 TB_P[2:0] 从这段 8 bit 数据中选择 1 bit 的 TB_data 并用它获取新的回溯指针 TB_P', 此周期同时根据 TB_P[4:2] 选择 Data_out' 中的 1 段 8bit 数据再接下来的 1 个时钟周期可根据 TB_P'[2:0] 从这段 8 bit 数据中选择 1 bit 并用它再次更新回溯指针这样便实现了流水线操作, 每个周期都能产生一个回溯指针, 而回溯指针的最高位就是译码值回溯过程中, 每个周期仅仅有一个 8 选 1 操作, 延时比 64 选 1 操作小很多综合结果表明, 采用改进的结构,SMU 的最高工作频率可达 408 MHz, 接近 CSAU 的最高工作频率通过上面的描述可以发现, 改进的结构每一时刻也只有 1 个前向追溯单元执行前向追溯操作, 继承了普通结构低功耗的优点并且, 采用这种改进的结构, SMU 的译码延时可以减少到 13 5=65 个时钟周期在改进的结构中, 合并块的深度为 34 级图 4 和图 5 的仿真结果表明, 合并块深度减少 1 级对仅仅会在码率较高且采用 DCM 调制时, 会略微地降低译码性能其中, 信噪比为 E b /N o 因此, 采用改进的混合幸存路径管理结构, 维特比译码器的译码性能的损失很小误码率合并块深度为 34 合并块深度为 35 R=5/8 R=1/2 R=1/ 信噪比 /db 262

4 4 图 4 合并块深度对译码性能的影响 (QPSK 调制 ) 误码率信噪比 /db 合并块深度为 34 合并块深度为 35 R=3/4 R=5/8 R=1/ 图 5 合并块深度对译码性能的影响 (DCM 调制 ) 维特比译码器的 FPGA 实现结果 Xilinx Virtex-5 XC5VX330 FPGA 的实现结果表明, 该译码器能在 240 MHz 的时钟频率下正确工作对 53.3 Mb/s~ 200 Mb/s 之间的 5 种传输速率, 可以仅使用其中 1 个维特比译码器 ; 而对于 320 Mb/s 400 Mb/s 以及 480 Mb/s 这 3 种传输速率, 可并行使用 2 个这样的维特比译码器, 从而使整个译码器能灵活地对系统中所有 8 种传输速率的数据进行译码实现整个译码器所需的 XC5VX330 FPGA 资源使用情况如表 3 所示表 3 译码器的硬件资源使用情况硬件资源名称使用数总数使用率 /(%) Slice Registers Slice UTs Slice U T-Flip Flop pairs Block RAM BUFGs 结束语本文针对 MB-OFDM UWB 中的维特比译码器设计了一个改进的混合幸存路径管理结构, 它保留了普通的混合幸存路径管理结构低功耗每周期输出一个译码值的优点同时, 它将普通结构中延时最大的 64 选 1 操作巧妙地拆分成 2 个 8 选 1 操作, 并分别在 1 个周期完成采用改进的结构,SMU 的最高工作频率能够提升 25%, 译码延时可以减少 40 个时钟周期而且, 这种改进思想同样适用于其他约束长度较大吞吐率要求较高的维特比译码器参考文献 [1] ECMA High Rate Ultra Wideband PHY and MAC Standard[S] [2] Black P J, Meng T H Y. A 140-Mb/s, 32-state, Radix-4 Viterbi Decoder[J]. IEEE Journal of Solid-State Circuits, 1992, 27(12): [3] Yeung A K, Rabaey J M. A 210 Mb/s Radix-4 bit-level Pipelined Viterbi Decoder[C]//Proc. of ISSCC 95. San Francisco, USA: IEEE Press, 1995: [4] Yeo E, Augsburger S A, Davis W T, et al. A 500-Mb/s Soft-output Viterbi Decoder[J]. IEEE Journal of Solid-State Circuits, 2003, 38(7): [5] Black P J, Meng T H Y. Hybrid Survivor Path Architectures for Viterbi Decoders[C]//Proc. of ICASSP 93. Minnesota, USA: [s. n.], 1993: 编辑金胡考 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ( 上接第 259 页 ) 送数据包成功, 并释放了该数据包对象的使用权之后, 才可以重新获得使用权 USB 通信线程检测到数据包对象队列非空时, 开始发送数据, 发送完毕后释放该数据包对象 4.3 消息包接收模块机制消息包接收模块维护一个消息字队列, 队列的每个元素称为消息字, 包含一个消息码及其对应的处理函数应用程序向 USB 通信线程注册消息包处理函数的过程就是向消息字队列插入一个元素的过程同理, 当应用程序不再需要接收该消息包时, 可以注销其消息包处理函数消息包接收模块在接收到一个消息包时遍历消息字队列, 查找具有相同消息码的消息字, 执行对应的处理函数如果该消息包是一个尚未注册的消息包, 则丢弃该包 4.4 数据包接收模块机制数据包接收模块的实现机制与数据包发送模块的实现机制相似, 数据包接收模块维护一个数据包对象队列等待接收数据的应用程序向接收模块插入一个等待接收的数据包对象 ; 当数据包接收模块接收到一个相同数据包标志码的数据包对象时, 将 FPGA 中双口 RAM 数据复制到数据包对象中所指明的数据存储空间接收完毕后,USB 接收模块释放该数据包对象, 代表数据包已接收完毕, 应用程序就可以使用其中的数据 4.5 PC 主机程序设计 PC 主机上需要开发一个 USB 通信模块, 负责与 DSP 中的 USB 通信线程通信主机 USB 通信模块的设计和实现原理与 DSP 端的 USB 通信管理线程相同 5 结束语本文实现了 ADSP-TS201 DSP 的扩展 USB 通信接口, 该接口扩展方法也可用于为其他处理器扩展 USB 接口在 USB 通信接口的硬件基础上, 该 USB 通信管理线程不仅提高了 USB 通信资源的利用率, 而且屏蔽了硬件实现细节, 为应用程序提供了简易的控制接口, 方便用户使用参考文献 [1] 刘小军, 刘栋斌. 基于 EZ-USB 的 CCD 信号采集系统 [J]. 计算机工程, 2009, 35(14): [2] Visual DSP Kernel(VDK) User s Guide[Z]. Analog Devices Inc., [3] ADSP TS201S TigerSHARC Embedded Processor[Z]. Analog Devices Inc., [4] EZ-USB FX2PTM USB Microcontroller High-speed USB Peripheral Controller[Z]. Cypress Semiconductor Inc., [5] EZ-USB Technical Reference Manual[Z]. Cypress Semiconductor Inc., 编辑张正兴 263

5 1

第卷第期年月半导体学报! " # $%&'%' $!&' #% #$1 /#1 $'! / ?/ ?/ / 3 0,?/ ) * +!!! '!,!! -. & ' $! '! 4% %&1)/1(7%&)03 (% )

第卷第期年月半导体学报! # $%&'%' $!&' #% #$1 /#1 $'! / ?/ ?/ / 3 0,?/ ) * +!!! '!,!! -. & ' $! '! 4% %&1)/1(7%&)03 (% ) 第卷第期年月!"# $%&'%' $!&'#%#$1/#1 $'! /18103 2?/03101?/18103 /3 0,?/0301.13 )*+!!! '!,!! -.&' $!'! 4%%&1)/1(7%&)03(%)%&,%*(1&0)%$-0*,%30)17*1*)0(+1(1+&1*+*),)1; &113(%44(10&.0701&0-&00*/)%;()1%-1+%&0)0*1*)%