DAB系统中2048点FFT的FPGA实现*

     摘要：针对DAB模式I下的系统参数，本文介绍了OFDM调制中2048点FFT的FPGA实现技术关键点，包括蝶形运算的设计，数据存储地址的产生，旋转因子及其存储地址的产生。同时介绍了块浮点结构实现FFT的方法。
     关键词：FFT；基2；块浮点；蝶形运算；FPGA

     引言
      数字声音广播（DAB）是继AM/FM之后的第三代广播体系。1991年，EUREKA-147被国际标准化组织（ISO）选定为数字音频广播国际标准。DAB的目标在于使人们在任何时候任何地方都能通过简便的接收机接收到CD质量的数字声音信号，并享受它提供的各种附加服务。2006年5月10日，我国国家广播电视总局发布了《30MHz~3000MHz地面数字声音广播系统技术规范》，现已有多家公司在进行DAB接收机的研发，期望在2008年能够上市。
本文介绍了用于DAB调制系统的2048点快速傅里叶变换（FFT）的FPGA设计方法及实现。

     DAB调制系统中的FFT
      DAB采用的调制技术为正交频分复用（OFDM），OFDM是一种复用技术也是一种多载波调制技术，它的采用使DAB具有抗噪声、抗干扰、抗电波传播衰落、更适合高速移动接收的特点。
      目前我国的数字声音广播发展还处于起步阶段，尚没有成熟完善的基于DAB的OFDM调制/解调的硬件实现。中国传媒大学承担863子课题《数字音频广播应用示范系统》研究，对广播台站DAB前端系统硬件实现进行了探索，其中调制设备采用了DSP+FPGA架构实现信道编码、时间频率交织、OFDM调制和非线性校正功能，提供了支持单频网的基于E1和ASI的ETI接口及直接连接III波段与L波段发射机的射频适配接口。本设计所实现的FFT处理器是该项目中OFDM调制系统的核心模块。
      DAB标准中的参数直接影响移动无线电信道中的频率选择性和时间选择性，由于作为无线信道时间选择性的尺度—多普勒带宽取决于行车速度和无线电波的频率，因此，不同的应用和不同的频率范围也就决定了不同的参数，DAB系统确定了四种不同的工作模式。针对DAB标准模式I中OFDM调制需要载波总数为1536，本文介绍了2048点FFT的FPGA实现技术关键点。
      本文设计采用单存储器及单蝶形运算核的基2FFT有着较为优化的面积，同时以相对简单结构使得设计更易控制，有效减少开发时间。使用Altera公司CycloneII EP2C35F672C8芯片，消耗1321LEs，77Kbits Memory，8个内嵌9-bit乘法器。100MHz主频下，计算时间为230s，I/O时间40.96s，输入数据14bit，输出14bit，阶码5bit，信噪比达到67dB。

      时间抽取基2FFT算法
      FFT是离散傅里叶变换（DFT）的快速算法[1]，N点序列的DFT为：
，k=0，1，…，N-1 (1)
      按时间抽取基2FFT算法（Cooley-Tukey算法）利用系数的对称性、周期性和可约性，根据输入序列在时间上的奇偶，将N点DFT分解为2个N/2点DFT，每个N/2点DFT又可按照奇偶分解为两个N/4点DFT，直到分解为2点DFT。以8点FFT为例，其计算流图见图1。
图 1 按时间抽取8点FFT计算流图
      可见，Cooley-Tukey算法的基本单元是2点蝶形运算结构。如图2，该结构下某一级两个节点k和j的节点变量进行蝶型运算后，得到的结果为下一列k，j两节点的节点变量，而和其他节点变量无关，即原位运算。
图2 DIT蝶型运算结构
      Cooley-Tukey算法中，，可推导出蝶型单元运算方程[2]如下：
(2)
其中s表示序列所在级数，且

。

     FPGA系统结构
      为减小面积，本设计只有一个蝶型运算单元，通过迭代完成FFT运算。采用的是经典的基2多路延迟转换（R2MDC）[3] 及单存储器架构[4]，R2MDC结构将串行的输入数据通过延迟转换为两路并行数据进行运算，单存储器结构只对一个存储器进行数据读出及写回操作。为保证FFT处理精度同时又避免大大增加硬件结构的复杂度，采用块浮点运算。系统结构图如图3所示。
图3 2048点基2FFT处理器系统结构图
      图3显示了FFT处理器的各个模块之间的关系和基本的数据流向。运算数据存储在RAM 中，旋转因子存储在ROM中。控制信号控制IO模块是否接收或发送信号，同时控制地址产生器生成RAM和ROM的读写地址。每一级运算中，运算数据通过同样的定标规则确定数据格式后进入蝶形运算单元，此时相应的旋转因子也同时到达。蝶形运算结果存入RAM中。当前级蝶形运算结果经过溢出判断产生下一级运算数据的定标规则。
      另外，数据RAM和旋转因子ROM的设计、RAM读写地址生成方法、蝶型运算模块、块浮点运算的数据定标等都是设计中的难点，下面将对它们的设计和实现进行介绍。

     数据存储和旋转因子设计
      根据FFT原位运算[2]的特点，每一次蝶形运算的结果可存入蝶形输入数据所在存储器位置，RAM的存储单元数为N。
      旋转因子，其中r有N/2个取值（0，1，2……N/2-1），。
      电路实现时，旋转因子的实部虚部将存储在ROM中，利用对称性，只需存储前1/4周期的正余弦值，而后1/4周期值通过所存储值构造出来（负数以补码形式表示）。因为所需存储的正余弦值全是正数，因此位宽可以减少1bit符号位（为13bit）。ROM的大小为N/4字，每个字的高位存储sin值低位存储cos值。
      旋转因子后1/4周期值合成方法：①sinθ的后1/4周期值通过所存储的前1/4周期构成；②cosθ后1/4周期cosθ值由所存储的sinθ值取反加一得到。

     RAM和ROM读写地址产生及旋转因子合成
      由公式2可知，序列标号k和对应的就是RAM的读写地址。公式2表示每次从RAM中同时读出两个数据的地址分别为k和，若数据只存在一块N单元的双口RAM中，这两个数只能依次顺序读出。以Addr表示地址，两输入序列地址（标号）可统一为：
   (3)
将的表达式代入得到：
  (4)
其中。因为是最内层循环，是最外层循环。可用bit累加器表示、和，的二进制表示为，则，，。
      因此RAM地址产生的规则可由下式5表示，地址产生方法随着级数s改变。
(5)
      系数中的r决定了ROM地址。r的求解有具体的数学推导。其硬件实现可描述为：将蝶形单元中的 值所表示的二进制数左移位，右补零得bit的R（r的二进制数）[2]。表示为：

      旋转因子中的r对应寻址范围是前1/2周期cos和sin的ROM地址,对应有效地址字长应为10bit。而ROM中存储的是前1/4周期的cos值和sin值，ROM地址字长为9bit。因此可以将转换后的地址低9bit做为读取ROM表的地址，而第10bit作为相位控制位输出，并作为选择器控制信号完成后续旋转因子的合成。旋转因子的硬件合成如图4所示。
图4 旋转因子由ROM存储值合成

     蝶形运算处理
      蝶形运算处理单元完成蝶形运算，可根据蝶形单元的运算方程设计RTL。将表达式代入公式2得：
　　　　　　 (6)
      将复数乘法部分展开，得：
　　　　(7)
      用4个乘法器，3个加法器，3个减法器可实现。由VerilogHDL代码完成寄存器传输级（RTL）设计，电路结构实现如图5。
图5 蝶形单元RTL结构图
      将较大的组合逻辑分解为较小的几块，中间插入触发器，这样可以提高电路的工作频率。这也是所谓“流水线”（pipelining）技术的基本原理，在蝶形运算模块中我们采用了两级流水的方式，其中乘法器插入一级流水。
      蝶形运算由三级乘加补码运算组成，为保证数据精度，乘法运算后数据位宽保持不变，加减法结果数据位宽增加1bit。蝶形输入数据为14bit的补码，输出为位宽16bit数据。

     块浮点数据处理
      FFT经过多级包含乘加的蝶形运算得到最终结果，也就是计算中将会有多级累加，例如2048点FFT有2*11级加法。采用定点结构，必须有足够的数据位宽以防止运算中可能出现的溢出以及保持一定的精度。采用浮点结构精度可得到保证，但相对需要消耗更多资源。而块浮点可以用相对较小的数据宽度获得较好的计算精度，是定点与浮点的折中，对节省硬件资源、提升系统性能指标以及提高系统主频有很大意义。
      块浮点结构中，每一级数据的小数点位置是统一的，在每级蝶形运算后统一定标，确定下一级参与运算的数据的小数点位置。每次进入蝶形单元的数据为纯小数，因此通过数据右移及指数增加来改变数据的标度。并不是每一级运算数据都会发生溢出，根据绝对值最大的数决定标度[5]。
      由蝶形单元结构可以看出，其中包含一级乘法，两级加/减法。小数相乘仍为小数，因此乘法结果数据宽度不必增加。小数加减可能增加1比特整数位，因此需将结果数据位宽增加1比特，两级加法结果应保留2比特整数位，防止溢出。
　　 可以设计Moore状态机来决定当前级蝶型运算数据的指数。状态机遍历当前级2048个蝶型运算结果实部和虚部后找出绝对值最大的数，根据其整数所占位宽决定下一级运算数据进入蝶形运算前应该取的有效位置以及指数，使进入蝶形运算的都是纯小数。数据处理流图由图3可见。

     结语
      本文介绍了FFT库利图基算法的FPGA实现方法。采用基2单蝶型运算核单存储器的架构，实现较为简单。分析了蝶型运算的结构，并介绍了便于硬件实现的快速产生RAM/ROM地址的方法，以及旋转因子的设计。同时，本文介绍了采用块浮点结构设计FFT的方法，使FFT有较高的精度及性能。

参考文献：
1. 胡广书，数字信号处理—理论、算法与实现，2版，清华大学出版社,2003.
2. 程佩青，数字信号处理教程，2版，清华大学出版社，2004.
3. Shousheng He,Mats Torkeleon. Design and Implementation of a 1024-point Pipeline FFT Processor. Proc. IEEE Custom Integer Circuits Conf.1998.
4. Bevan M. Baas.A Low-Power, High-Performance,1024-Point FFT Processor[J] IEEE JOURNAL OF SOLID-STATE CIRCUITS, VOL. 34
5. 万红星，高性能实时FFT处理器的ASIC设计与研究，北京理工大学，2006.