基于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 整体方案设计框图

3 FFT运算器的实现

FFT 运算器采用FFT MegaCore 实现，用Quartus Ⅱ仿真软件设计时产生的FFT MegaCore 模块图如图4 所示[5]。这里采用器件为Altera 公司的Stratix 系列，变化域长度设置为6 4 ，数据量精度为2 4 b i t ，旋转因子量化精度为24bit。引擎结构可以选四输出，I/O数据流结构选连续型[3]。在工程中，设计者也可以根据实际情况选择其他的参数设置。

图4 FFT MegaCore模块

在F P G A 硬件设计中，一个乘法器占用的资源要远大于一个加法器占用的资源，而该模块主要是完成复数乘法运算，我们则可以通过数学变换减少乘法器的数量。例如两个复数a+jb 和c+jd 的乘积结果e+jf，其中e=ac-bd，f=ad+bc，变换得e=(a+b)c-b(c+d)，f=(a+b)c-a(c-d)，可以看出实际上是增加三个加法器来减少一个乘法器。

FFT MegaCore 端口定义如下。

clk:输入，FFT 系统时钟信号;

reset:输入，FFT高有效同步复位信号，低时FFT工作;

master_sink_dav:输入，指示主接收器数据有效信号;

master_sink_sop:输入，输入数据包起始位置指示信号;

inv_i:输入，转换方向控制信号，低有效时做FFT，高有效时做IFFT;

data_real_in[23..0]:输入，输入实部数据;

data_imag_in[23..0]:输入，输入虚部数据;

master_source_dav：输入，指示FFT 模块收到的数据是否有效;

master_sink_ena：输出，指示数据是否写入输入缓存中;

fft_real_out[23..0]：输出，输出实部数据;

fft_imag_out[23..0]：输出，输出虚部数据;

master_source_ena：输出，指示输出数据是否有效;

master_source_sop：输出，输出数据包起始位置指示信号;

master_source_eop：输出，输出数据包结束位置指示信号;

exponent_out[5..0]：输出，每一个数据输出时的一个比例因子，用来保持数据精度和内部最大信噪比。工作流程:系统复位后，数据源将master_sink_dav 置位，表示有数据等待输入;作为回应FFT Core 将master_sink_ena 置位，表示可以接收数据;数据源加在第一个复数数据，同时master_sink_sop 置位，表示输入数据包起始位置;下一个时钟，master_sink_sop 被清零，输入数据按顺序加入，输入数据达到设置值时，系统启动FFT 运算。通过inv_i 信号的置位和清零可以改变单个数据包的FFT 转换方向，inv_i必须与master_sink_sop严格同步。当FFT转换结束时master_source_ena置位，输出运算结果;在输出过程中master_source_sop和master_source_eop信号被置位，表示输出数据包的起始位置和结束位置;e x p o n e n t_out 为比例因子，是IP Core 通过每一次参数的设定自动计算出来的，对于每个数据包来讲，它产生的e x p o n e n t_out 的值是不同的。

4 结 论

本文介绍了一种采用Altera 公司的FFT MegaCore 实现快速傅里叶变换的方法，该方法非常简单，能进一层次简化开发的流程，缩短工程开发周期，节约成本，因此在实际工程中是一种很好的应用。