兰海洋，林晓焕

（西安工程大学 电子信息学院，陕西 西安 710048）

0 引言

19世纪20年代，法国工程师傅里叶（Fourier）指出：任意一个周期函数都可以分解为无穷多个不同频率正弦信号的和，这即是傅里叶级数[1]，求解傅里叶系数的过程就是傅里叶变换。傅里叶变换的应用非常广泛，主要的领域有：物理学、电子类学科、数论、组合数学、信号处理、概率论、统计学、密码学、声学、光学、海洋学、结构动力学等[2]。快速傅里叶变换（FFT）是离散傅里叶变换（DFT）的一种快速算法。一般采用 ROM 的方法来实现FFT，其速度不能满足实时性的要求[3]，这里采用移位存储器的方法来存储旋转因子，大大地提高了FFT的运算速度。

1 算法原理

设长度为N的有限序列x(n)的DFT为：

设序列x(n)的长度N(N=2M,M为任意整数)按N的奇偶性把x(n)分解为两个N/2点的子序列：

则x(n)的N点DFT为：

由于

所以

式中，G(k)和H(k)分别为 g(m)和 h(m)的 N/2点 DFT，表达式如下：

由于G(k)和H(k)均以N/2为周期，考虑到对称性，有,X(k)就可表达式为：

这样就将N点的DFT分解为两个N/2点的DFT以及上面两式的运算，使DFT运算量减少，将每个N/2点的DFT分解为两个N/4点的DFT，由于N是2 的正整数次幂，还可以继续分下去，直到分解为2点的DFT为止，这种运算可用图1的流图表示，称为蝶形运算符。当N=8时[5]，整个信号的流图如图2所示。

图1 蝶形运算符

图2 8点FFT蝶形运算示意

2 电路过程原理

2.1 FFT的总体设计

FFT设计主要由以下部分组成：蝶形运算单元，地址产生单元，功能切换单元，存储单元，浮点单元和时序控制元。各模块功能如下：

蝶形运算单元采用DIT方式完成FFT的蝶形运算，双口RAM1和 RAM2作为存储器，从RAM1中读出数据存入RAM2中，或从RAM2中读出数据存入RAM1中。……