基2FFT原理

FFT前置知识

FT和DFT

傅里叶变换FT（fourier transform）用于将时域信号

和频域信号

之间变换，公式如下所示：

对于计算机系统中，无法处理连续的过程，因此离散化为离散傅里叶变换DFT（Discrete Fourier Transform）：

取

，可将DFT改写为以下公式：

DFT改进（削减计算量）

首先分析原始公式的计算量，取一个8点DFT算法，对于一个点：

• 需要复数乘法N次，每次复数乘法由四次实数乘法和两次实数加法实现
• 需要复数加法N-1次，每次复数加法由两次实数加法构成

因此，对于一个点，需要实数乘法共4N次，实数加法共（2N-2+2N）=4N-2次。削减计算量的主要重点在

上，使用欧拉公式有：

考虑

的情况，有以下公式：

同理有

，因此以一个4点DFT为例，有以下公式：

可减少所需要的复数乘法的次数，进而减少对应的实数乘法和加法的数量

FFT

基2FFT

基2FFT指点数为

的FFT变换，取

的FFT变换如下所示：

将一个N点的FFT分解为两个FFT，一个为奇数项的FFT，另一个为偶数项的FFT。对于

而言，考虑以下变化：

带入上式，有以下：

取

和

分别是两个长度为

的FFT运算，有：

上述有

，考虑后半段结果，有：

同理有

，因此当

时，考虑

的周期性，有：

综上所述对于一个N点的FFT运算，有

其中，

为对偶数序列的

点FFT；

为对应奇数序列的

点FFT。该操作将一个N点FFT分解为两个

点的FFT。

蝶形运算

蝶形运算为一个二输入二输出的运算，公式如下所示：

其中

为两个输入；

为两个输出；W为权值，均为复数。蝶形运算可以用于映射基2FFT，首先考虑2点FFT，两点FFT公式如下所示：

因此可以使用一个蝶形运算实现，权值为

，现考虑一个4点FFT，首先将其分解为2个两点FFT，分解的公式为

分解步骤也可以用蝶形运算实现，因此整体运算如下图所示：

fft4.png

更多点数的FFT可以类似的进行，即不断分解为长度为一半的奇偶序列的FFT变换分层实现。