基于fpga的fft算法

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

1、基于FPGA的可扩展高速FFT处理器的设计与实现来源：电讯技术　作者：刘晓明　时间：2007-07-12　发布人:卢春妙　　本文提出了基于FPGA实现傅里叶变换点数可灵活扩展的流水线FFT处理器的结构设计以及各功能模块的算法实现，包括高组合数FFT算法的流水线实现结构、级间混序读/写RAM地址规律、短点数FFT阵列处理结构以及补码实现CORDIC算法的流水线结构等。利用FPGA实现的各功能模块组装了64点FFT处理器。从其计算性能可知，在输入数据速率为20MHz时，利用此结构实现的FFT处理器计算1024点

2、FFT的运算时间约为52μs。　　一、引言 　　DFT(离散傅里叶变换)作为将信号从时域转换到频域的基本运算，在各种数字信号处理中起着核心作用，其快速算法FFT(快速傅里叶变换)在无线通信、语音识别、图像处理和频谱分析等领域有着广泛的应用。用大规模集成电路FPGA(现场可编程门阵列)来实现FFT算法时，需要重点考虑的不再是算法运算量，而是算法的复杂性、规整性和模块化，因为算法的简单性和规整性将更适合大规模集成，更方便于版图设计，而算法的模块化更有利于FFT处理器的灵活扩展。　　组合数FFT算法和CORDIC

3、(坐标旋转数字计算机)算法结合起来，在计算长点数、可扩展FFT时具有较大的优越性［1，2］。而面向高速、大容量数据流的FFT的实时处理，可以通过VLSI(超大规模集成电路)器件的并行处理或多级流水线处理等来达到。特别是多级流水线处理的FFT结构使得基于FPGA器件的FFT处理器完成不同点数的FFT计算时可以通过增减模块级数很容易地实现。二、组合数N=r1r2点混合基FFT原理　　　　计算N点DFT：　　式中k=0，1，…，N-1。　　若N=r1r2的组合数，可将n(n＜N)表示为 　　式(2)的意义在于，计

4、算组合数N=r1r2点DFT，等价于先求出r2组r1点的DFT，其结果经过对应旋转因子的相位旋转后，再计算r1组r2点的DFT。实际应用中，DFT往往用它的快速算法FFT实现，因而式(2)中的r1点DFT和r2点DFT都用r1点FFT和r2点FFT实现。三、可扩展FFT处理器实现结构 　　根据式(2)的FFT算法原理设计FFT处理器的可扩展结构如图1所示。 　　采用流水线模块化级联结构，把FFT处理器划分成短点数FFT、级间混序RAM和相位旋转等功能模块，设计的各功能模块可以重复利用，通过复用或增减各功

5、能模块可以灵活改变FFT处理器的计算规模，而且不增加设计量。在图1结构中，当Li＝1时，就演变成了基2FFT；当Li＝2时，就演变成了基4FFT；同理，当Li≠Lj时，就演变成了高组合数的混合基FFT。1.短点数FFT阵列结构 　　－Tukey算法结构实现时，有大量的复数乘法实际上转化为加减运算，所以用阵列结构实现不但具有速度快的优点，而且所用器件资源也减少很多，通过对阵列结构短点数FFT进行时分复用，可以提高运算单元的使用效率。2.相位旋转运算单元　　　　实现短点数FFT级间相位旋转，采用ROM存储旋转因

6、子与数据复乘的传统方法，不仅涉及乘法运算，而且会消耗大量存储器资源。　　　　利用CORDIC算法实现组合数FFT级间数据的相位旋转，把乘法转化成加减法运算，适合FPGA的大规模集成。可以设计出统一结构的CORDIC处理器模块，重复利用于不同级间实现相位旋转，而且其控制逻辑非常简单。　　　　(1)CORDIC算法原理　　　　复数P=x+jy旋转角度θ得到Q的表达式： 　　如果旋转角度θ可以分解成n个小角度φi之和，即： 　　公式:　　(2)CORDIC处理器结构设计　　　　本文提出了一种流水线CORDIC处理

7、器结构的解决方案。实现式子(4)的迭代运算时采用补码移位和补码加减运算，可以减少大量求补运算，其迭代结构如图2所示。　　前者在于左移补零的位数的不同，这样，只需要改变n0k0的放大倍数(改变左移低位补零的位数)，就可以把同一方向向量功能模块级联到图1FFT处理器的不同级间来计算CORDIC处理器的MSBi，这就大大地减小了重复设计，其迭代结构如图3所示。3.RAM结构及其级间数据混序用流水线读/写RAM地址发生器的设计　　　　设计的RAM，每个存储单元为32bit，高16位为复数的实部，低16位为复数的虚部

8、。输入输出数据接口用RAM设计为乒乓结构，用两块相同的RAM交替读出或交替写入数据，这样就放宽了对I/O操作速度的要求，使得外围电路可以不必工作于FPGA系统时钟。　　级与级之间数据混序用RAM设计为读/写RAM，对RAM同一存储单元用两个时钟完成一次读/写操作，即用流水线读/写同一块RAM来实现级与级之间的数据混序。此结构取代了用两块RAM完成数据混序的乒乓结构的传统方法，不涉及存储器之间的读写切换，控制逻辑非