基于FPGA的FFT/IFFT处理器的实现

冬1988

1 引言

8 z& e: w+ @* i, L高速实时数字信号处理对系统性能要求很高，因此，几乎所有的通用DSP都难以实现这一要求。可编程逻辑器件允许设计人员利用并行处理技术实现高速信号处理算法，并且只需单个器件就能实现期望的性能。在数据通信这样的应用中，常常需要进行高速、大规模的FFT及其逆变换IFFT运算。当通用的DSP无法达到速度要求时，唯一的选择是增加处理器的数目，或采用定制门阵列产品。现在，随着微电子技术的发展，采用现场可编程门阵列（FPGA）进行数字信号处理发展迅速。采用现场可编程器件不仅加速了产品上市时间，还可满足现在和下一代便携式设计所需要的成本、性能、尺寸等方面的要求，并提供系统级支持。本文研究了基于FPGA的FFT及其逆变换IFFT处理器的硬件电路实现方法。在系统时钟频率为100MHz时，1024点复位FFT的计算时间只需要10μs左右。
+ x4 R& q' Z& k* I( X
$ v2 H8 D, S; ~! x7 ^5 w2 基4 FFT/IFFT算法
3 h9 Z. v- h% k' T9 K
序列x(n),n=0,...,N-1的离散傅里叶变换为：
5 D  ?8 [. k8 ]8 M7 m5 X- P) X

这说明IFFT可以由FFT求出。因此，FFT和IFFT处理器可以用统一的硬件结构来实现。
0 G' L' e  O- S+ h, D0 o1 M- ^
: T! [* f, L9 Y, j对于FFT，设序列x(n)的长度为N=4p(p为整数)，则基4频率抽取蝶菜运算单元方程为：

3 FFT/IFFT的硬件实现
. E4 P! U$ L: Z
" F1 I! I6 x! F$ `# r我们采用Xilinx公司的Virtex-II系列FPGA来实现FFT/IFFT处理器。

3.1 蝶形运算单元结构
8 r1 h: ?" U0 R
+ p* f6 a+ l0 c6 W- `$ u基4频率抽取FFT计算一共包括了log4(N)级运算，其中，在每一级中包含了N/4个基4蝶形运算，蝶形运算器如图1所示。

Virtex-II系列FPGA有内嵌18bit×18bit补码乘法器以及大容量用户可配置RAM，非常适合做大规模算术运算。图1所示的蝶形运算器可以在一个时钟周期内完成一次基4蝶形运算。其中，操作数A、B、C、D存放在RAM中，三个18位放置因子W1、W2、W3存放在ROM中。由于运算结果可能会超过原数据，所以要进行量化移位[1][2]。
. F7 l7 I0 x5 n2 s; F; ~& {
3.2 并行运算结构
# {8 |( H6 A; z) ?5 H1 P) J
( n, C% g+ T* S6 Y& q  ]0 n* y5 h通用DSP的蝶算单元通常是从内存中顺序读入四个操作数A、B、C、D，因而计算速度受到了很大限制。而使用FPGA可充分利用并行计算技术在一个时钟周期内并行读取四个操作数，以便完成一次基4蝶形运算。我们采用四对RAM×2（分别存放实部和虚部）来存储蝶算中的操作数A、B、C、D。如图2所示，处理器在每个时钟周期从RAM中读出数据A、B、C、D送入蝶形运算器（图1）。运算结果AO、BO、CO、DO在下一个时钟周期写回原地址。

图2中的四对RAM×2的地址A0，A1，A2，A3分别对应公式（3）中的n,n+4p-s-1,n+2×4p-s-1,n+3×4p-s-1。A0，A1，A2，A3可以按下述方法产生：
设a,b为两个递减计数器，它们组成一个大的计数器Counter=a×4p-1+b。如图3所示。
2 m" T$ W% O1 p8 Q, Z2 N

ROTATEn(x,m)表示把x(n位二进制)循环左移m位。则图2中四个操作数地址为：
% z/ p! f# b% C7 U& f

式（4）中每个地址对应一个RAM×2的入口地址。设操作数地址A的四进制表达式为A=（Kp-1...K1K0）4。定义Mk为A的所有四进制位数和除以4的余数
; S* R, @6 y+ P

式（5）中，mod为求余运算。
8 u; t! @* N7 ~/ L2 w2 x$ v+ y4 p
可以证明地址A0，A1，A2，A3的Mk值互不相同，取值范围是0，1，2，3。因此我们采取如图2所示的并行存储结构：所有Mk=0的操作数都存放在RAMA中，Mk=1的操作数都存放在RAM B中，Mk=2的操作数都存放在RAM C中，Mk=3的操作数都存放在RAM D中。通过以上地址映射，我们可以在一个时钟周期并行读取四个操作数地址，完成蝶形运算。
# p7 g  G% C) v
( v- a( ?6 S" k3 L# X$ T3 g# D+ L3.3 放置因子的生成
, F4 l  ]  n8 a$ }- `: N/ K
, a* ?2 i7 t; o4 z7 G- Q. |* v1 G为了加快FFT/IFFT运算速度，我们采用查表的方式来得到放置因子W1，W2，W3（图1），我们采用3对ROM×2（实部和虚部）来存放复数W1，W2，W3，三个ROM的入口地址都为c。可以证明，把图3中的计数器b的低2(p-a-1)位都置为0所得到的值即为c的值。即：
/ o$ x2 E5 t4 g5 x+ k! W

3.4 FFT/IFFT芯片整体结构
4 G1 }3 S$ T8 a/ j/ {. p& V
5 Z; h4 ?: F- T* HFFT/IFFT芯片整体结构如图4所示。在式（2）中讨论过，我们可以用FFT来计算IFFT，只需要先求出输入序列的共轭X*(k)，然后进行正常的蝶形运算，在输出时再进行一次求共轭运算。所谓复位的共轭是对它的虚部取反，实部不变。因此，我们可以把处理器动态地配置成FFT或其逆变换IFFT。为了充分利用I/O带宽、连续地进行FFT/IFFT。为了充分利用I/O带宽、连续地进行FFT/IFFT。我们采用了乒乓缓冲存储结构，如图4所示。由于FFT/IFFT计算采用的是同址计算，每次蝶形运算结果要写回原地址中，所以，RAM X和RAM Y有输入和工作两种模式。这里，我们把RAM X和RAM Y配置成乒乓结构，当RAM X处于工作模式时，RAM Y处于输入状态。当一次64/256/1024点FFT/IFFT完成后，RAM X和RAM Y将自动切换到另一个状态。这样，输入序列就可以连续地输入到FFT/IFFT处理器中进行变换，以达到实时处理的要求。输出结果存放在RAM Z中，可以由用户读出。
& V+ b2 a* @2 V3 @  v* A
4 测试结果
- h4 C' s1 l" z* U8 m! Y$ B
8 f& {/ o8 V: P: f. x4 u这个电路采用Verilog HDL完成设计，采用Virtex-II XC2V250实现。使用Vilinx ISE4.2i完成整套流程，图5是部分仿真波形（modelsim+sdf）。在系统时钟为100MHz时，完成一次1024点复数FFT/IFFT需要12.8μs。相比之下，TI公司的TMS320C67（主频167MHz）需要120μs，AD公司的ADSP21160（主频100MHz）需要90μs。可见，基于FPGA的FFT/IFFT处理器由于其硬件上的并行性，速度远远快于一般的通用DSP。

5 结束语

3 `* Z! L: h! q3 E2 _FPGA具有成千上万的查找表和触发器，因此，FPGA平台可以利用更低的成本达到此通用DSP更快的速度。采用FPGA技术，还可以获得高性能，满足成本要求，并享有快速有效地对新设计进行优化的灵活性。针对这一特性，本文研制了一种基于并行算法的FFT/IFFT处理器，可以广泛应用在高速信号处理系统中。

swww2212

当通用的DSP无法达到速度要求时，唯一的选择是增加处理器的数目，或采用定制门阵列产品。