1. FFT(Fast Fourier Transformation),即为快速傅里叶变换,是离散傅里叶变换的快速算法,它是根据离散傅里叶变换的奇、偶、虚、实等特性,对离散傅里叶变换的算法进行改进获得的。
2.FFT算法的基本原理
FFT算法是把长序列的DFT逐次分解为较短序列的DFT。
按照抽取方式的不同可分为DIT-FFT(按时间抽取)和DIF-FFT(按频率抽取)算法。按蝶形运算的构成不同可分为基2,基4,基8,以及任意因子的类型。
3本次程序的基本过程
我们这次所研究的是数字信号处理中的FFT算法,我们这次所用的数字信号是复数类型的。
(1)所以首先,我们先定义了一个复数结构体,因为是进行复数的运算,我们又相继定义复数的加减乘运算的函数。
(2)紧接着,我们定义了进行FFT计算的fft()快速傅里叶变换函数initW() 初始化变换核函数即旋转因子的计算,change() 变址函数,output()输出傅里叶变换的结果的函数。
(3)定义主函数,并调用定义好的相关子函数,利用fft()中的蝶形运算以及change()函数来完成从时间域上选取的DIT-FFT。