. . . .
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(n)的 DFT:
1 / 11