c语言写的fft程序 C语言编写FFT程序.pdf

DSP 课程作业

用 C 语言编写 FFT 程序

1，快速傅里叶变换 FFT 简介

快速傅氏变换 (FFT)，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、

偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并

没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说

是进了一大步。

我们假设 x (n)为 N 项的复数序列，由DFT 变换，任一 X (m)的计算都需要 N 次复

数乘法和 N-1 次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复

数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次 “运算”(四

次实数乘法和四次实数加法)，那么求出N 项复数序列的X (m),即N 点 DFT 变换大约就

需要 N^2 次运算。当 N 1024 点甚至更多的时候，需要 N2 1048576 次运算，在 FFT 中，

利用 WN 的周期性和对称性，把一个 N 项序列 (设 N 2k,k 为正整数)，分为两个 N/2 项的

子序列，每个 N/2 点 DFT 变换需要 (N/2)2 次运算，再用 N 次运算把两个 N/2 点的 DFT

变换组合成一个N 点的DFT 变换。这样变换以后，总的运算次数就变成N+2(N/2)2 N+N2/2。

继续上面的例子，N 1024 时，总的运算次数就变成了 525312 次，节省了大约 50%的运算

量。而如果我们将这种 “一分为二”的思想不断进行下去，直到分成两两一组的DFT 运

算单元，那么 N 点的 DFT 变换就只需要 Nlog2N 次的运算，N 在 1024 点时，运算量仅有

10240 次，是先前的直接算法的 1%，点数越多，运算量的节约就越大，这就是 FFT 的优

越性。

2，FFT 算法的基本原理

FFT 算法的基本思想：利用 DFT 系数的特性，合并 DFT 运算中的某些项，吧长序列的

DFT—>短序列的DFT，从而减少其运算量。

FFT 算 法 分 类 : 时 间 抽 选 法 DIT: Decimation-In-Time ； 频 率 抽 选 法 DIF :

Decimation-In-Frequency

按时间抽选的基-2FFT 算法

1、算法原理

设序列点数 N 2L，L 为整数。

若不满足，则补零。N 为 2 的整数幂的 FFT 算法称基-2FFT 算法。将序列 x (n)按 n

的奇偶分成两组： x 2r x r N

  1  r 0,1,..., 1

2

x 2r1 x r

  2  

则 x (n)的DFT: N1 nk N1 nk N1 nk

X k x n W x n W  x n W

     N    N    N

n 0 n 0 n 0

N 1 N 1

2 2

2r1k

2rk  

x 2r W  x 2r1 W

   N    N

r 0 r 0