用FPGA实现FFT算法(图)
——
加入技术交流群
dft(discrete fourier transformation)是数字信号分析与处理如图形、语音及图像等领域的重要变换工具，直
接计算dft的计算量与变换区间长度n的平方成正比。当n较大时，因计算量太大，直接用dft算法进行谱分析和信号的实时处理是不切实际的。快速傅立叶变换(fast fourier transformation，简称fft)使dft运算效率提高1～2个数量级。其原因是当n较大时，对dft进行了基4和基2分解运算。fft算法除了必需的数据存储器ram和旋转因子rom外，仍需较复杂的运算和控制电路单元，即使现在,实现长点数的fft仍然是很困难。本文提出的fft实现算法是基于fpga之上的，算法完成对一个序列的fft计算，完全由脉冲触发，外部只输入一脉冲头和输入数据，便可以得到该脉冲头作为起始标志的n点fft输出结果。由于使用了双ram，该算法是流型(pipelined)的，可以连续计算n点复数输入fft，即输入可以是分段n点连续复数数据流。采用dif(decimation in frequency)-fft和dit(decimation in time)-fft对于算法本身来说是无关紧要的，因为两种情况下只是存储器的读写地址有所变动而已，不影响算法的结构和流程，也不会对算法复杂度有何影响。算法实现的可以是基2/4混合基fft，也可以是纯基4fft和纯基2fft运算。
傅立叶变换和逆变换
对于变换长度为n的序列x(n)其傅立叶变换可以表示如下：
n
nk
式（１）
其中，w=exp(-2π/n)。
当点数n较大时，必须对式(1)进行基4/基2分解，以短点数实现长点数的变换。而idft的实现在dft的基础上就显得较为简单了：
式（２）由式(2)可以看出，在fft运算模块的基础上，只需将输入序列进行取共轭后再进行fft运算，输出结果再取一次共轭便实现了对输入序列的idft运算，因子1/n对于不同的数据表示格式具体实现时的处理方式是不一样的。idft在fft的基础上输入和输出均有一次共轭操作，但它们共用一个内核，仍然是十分方便的。
基4和基2
基4和基2运算流图及信号之间的运算关系如图1所示：
（a）基４蝶形算法
（b）基２蝶形算法
以基4为例，令a=r0+j
评论