用fpga实现fft算法

《用fpga实现fft算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、用FPGA实现FFT算法

2、第1内容显示中引言　　DFT(DiscreteFourierTransformation)是数字信号分析与处理如图形、语音及图像等领域的重要变换工具，直接计算DFT的计算量与变换区间长度N的平方成正比。当N较大时，因计算量太大，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。快速傅立叶变换(FastFourierTransformation，简称FFT)使DFT运算效率提高1～2个数量级。其原因是当N较大时，对DFT进行了基4和基2分解运算。FFT算法除了必需的数据存储器ram和旋转因子rom外，仍需较复杂的运算和控制电路单元，即使现在,实

3、现长点数的FFT仍然是很困难。本文提出的FFT实现算法是基于FPGA之上的，算法完成对一个序列的FFT计算，完全由脉冲触发，外部只输入一脉冲头和输入数据，便可以得到该脉冲头作为起始标志的N点FFT输出结果。由于使用了双ram，该算法是流型(Pipelined)的，可以连续计算N点复数输入FFT，即输入可以是分段N点连续复数数据流。采用DIF(DecimationInFrequency)-FFT和DIT(DecimationInTime)-FFT对于算法本身来说是无关紧要的，因为两种情况下只是存储器的读写地址有所变动而已，不影响算法的结构和流程，也不会对算法复杂度有何影响。算

4、法实现的可以是基2/4混合基FFT，也可以是纯基4FFT和纯基2FFT运算。傅立叶变换和逆变换对于变换长度为N的序列x(n)其傅立叶变换可以表示如下：　　　　　NnkX(k)=DFT[x(n)]=Σx(n)表中存储的是N点旋转因子表。控制模块产生所有的控制信号，存储器1和2的读写地址、写使能、运算模块的启动信号及因子表的读地址等信号。当然对于运算模块为基16/8复用模块时，控制模块就需要产生模式选择信号，如对于运算模块是基4/2模块时，该信号就决定了内部运算模块是进行基4运算还是基2运算。存储器1作为当前输入标志对应输入N点数据的缓冲器，存储器2作为中间结果存储器，用于存储

5、运算模块计算出的各Pass的结果。在图中的各种地址、使能和数据的紧密配合下，经过一定延时后输出计算结果及其对应指示标志。图2只是一定点或浮点的FFT实现模块，如果是块浮点运算，则必须加入一个数据因子控制器，控制每遍运算过程中的数据大小，并根据各个Pass的乘性因子之和的大小，对最终输出进行大小控制，以保证每段FFT运算输出增益一致。　　外部输入为N点数据段流和启动信号(N点之间如无间隔，则每N数据点输入一脉冲信号)，一方面，外部数据存入存储器1中，同时通过控制模块的控制，读出存储器1中的前段N点数据和Rom表中的因子及相关控制信号送入运算核心模块进行各个Pass的运算，每个

6、Pass的输出都存入存储器2中，最后一个Pass的计算结果存入存储器2中，并在下一个启动头到来后，输出计算结果。对图2的实现，除去运算模块，关键是各个Pass数据因子读写地址及控制信号的配合。速度、资源和精度　　假定输入数据的速率为fin，则每数据的持续时间T=1/fin，运算模块的计算时钟频率为fa，对于N(N=2p，p即为Pass数目)点FFT计算时延与Pass数目直接相关。如果使用基2运算不考虑控制开销，纯粹的计算时延为td=p×N×T×fin/fa。显然在fa>p×fin时，在N点内可完成FFT运算。否则不能完成，即不能实现流型的变换。这在N很大且输入数据速率

7、较高时以FPGA实现几乎是不可能的，而且内部计算时钟过高容易导致电路的工作不稳定。设基2时的最小可流型工作运算频率为fa0，则使用基4实现流型的变换，计算时钟fa=fa0就可以。而使用基8时计算时钟fa=fa0便可完成，基16时为fa0的1/4。上面所讨论的是纯基运算，当N不为4的幂次方时(如N=2048=16×16×8，运算模块为基16/8复用模块)，而又希望使用较低倍的时钟完成运算时，图2中的运算模块必然包括基4/2复用模块(即基16/8复用模块)，这也就是前面提到复用模块的主要用意。由上面的分析可以得出结论，如果计算使用的基越大，完成速度越快。　　但是，使用基16/8

8、模块所使用的逻辑资源要比基4/2模块多将近一倍，这是因为基16/8复用模块是以基4模块和基4/2复用模块构建而成。当然，可以直接实现基16/8复用模块，但用FPGA很难解决复杂度和成本问题。另外，如果流型运算间隔比N点数据长度长一倍以上，可以考虑在较低的计算时钟下使用基2运算模块实现流型FFT。　　运算结果的精度直接与计算过程中数据和因子位数(浮点算法)相关，如果中间计算的位数、存储数据位数和Rom表中的位数越大，输出精度就越大。当然，位数增大后逻辑运算资源和存储资源都会直线上升。浮点、块浮点和定点FFT　　根据运