基于Altera MegaCore实现FFT的方法

0 引 言

FFT(快速傅里叶变换)是计算离散傅里叶变换(DFT)的高效算法，它把计算N 点DFT 的乘法运算量从N2 次下降到N/2log2N 次。FFT 的出现对数字信号处理的发展起着至关重要的作用，它可应用于傅里叶变换所能涉及的任何领域，为广泛应用数学方法处理数字信号开辟了新局面[ 1 ] 。

传统的FFT 实现方法是通过软件(软件编程)和硬件(专用芯片ASIC)这两种方法来实现，而近年来，FPGA 发展十分迅速，这给FFT 设计提供了一个新思路[2]。为了更好地满足设计人员的需要，各大公司相继推出了I P 模块，本文提出了一种采用Altera 公司的IP Core FFT MegaCore来实现FFT 的简单方法。

1 FFT MegaCore核的性能

Altera 公司的FFT MegaCore 是一个高性能、高参数化的快速傅里叶变换处理器，可以高效的完成FFT 和IFFT 运算，支持的器件系列包括Stratix Ⅱ、StratixGX、StratixⅡGX、Stratix、Cyclone、CycloneⅡ以及CycloneⅢ等，采用基2/4频域抽取(DIF)FFT算法，运算长度从64 到16384，使用嵌入式内存，系统最大时钟频率大于300MHz。FFT 处理器可以设置两种不同的引擎结构：四输出和单输出，结构图如图1 和图2 所示[3]。

为了增加F F T 兆核函数的总吞吐量，也可以在一个FFT 兆核函数变量中使用多个并行引擎。复取样数据X[k，m]从内部存储器并行读出并由变换开关(SW)重新排序，排序后的取样数据由基4 处理器处理并得到复数输出G [ k ，m]，由于基4 按频率抽选(DIF)分解方法固有的数字特点，在蝶形处理器[ 4 ]输出上仅需要3 个复数乘法器完成3 次乘旋转因子( 有一个因子为1 ，不需要乘) 计算。这种实现结构在一个单时钟周期内计算所有四个基4 蝶形复数输出。同时，为了辨别取样数据的最大动态范围，四个输出由块浮点单元(BFPU)并行估计，丢弃适当的最低位(LSB)，在写入内部存储器之前对复数值进行四舍五入并行重新排序。

若要求转换时间尽量小，四输出是最佳选择;若要求资源尽量少，单输出比较合适。FFT 处理器支持3 种I/O 数据流结构：连续型、缓冲突发型、突发型。连续型允许在处理过程中连续输入数据;缓冲突发型与连续型相比，占用内存资源较小，但这是以减少平均吞吐量为代价的;突发型与缓冲突发型类似，但占用内存资源更少，也是以减少平均吞吐量为代价的。

图1 FFT处理器四输出引擎结构

图2 FFT处理器单输出引擎结构

2 整体方案

整体方案设计框图如图3 所示。输入缓冲器和输出缓冲器分别存储预处理数据和F F T 变换结果，F F T 运算器负责F F T 运算;控制器为输入缓冲器和输出缓冲器提供读写地址和控制运算时序及缓冲器的读写操作。下面重点介绍FFT 运算器的实现。

图3 整体方案设计框图