DOC《快速Fourier变换原理及其应用实例》

快速Fourier变换原理及其应用实例 付玉林 (广西大学机械工程学院, 广西 南宁 530004) 摘要离散Fourier变换(简称DFT)为离散信号的分析从理论上提供了变换工具,但由于计算时间较长而难以实现,快速Fourier变换(简称FFT)则是一种减少计算时间的有效算法.

本文在对DFT计算量进行分析的基础上指出了FFT的实现途径与计算方法,针对FFT算法进行了程序设计并给出了应用实例. 关键词:Fourier;

FFT;

信号分析;

程序 中图分类号:TP311.1 文献标识码:A

1 FFT算法的基本原理 1.1 DFT的计算量 为了说明FFT算法的原理,首先研究DFT变换对计算所需工作量. 由离散傅立叶变换分析已知,DFT计算式为 将此二式写成矩阵形式: 可知,X(k) 与x(n)分别为N列的列矩阵,元素写作X(0),…,X(N-1);

以及x(0),…,x(N-1).而与(W=)分别为NN方阵,其中各元素分别以或表示.这两个方阵是对称矩阵,即 由矩阵式(1)可以看出,将x(n)与两两相乘再取和即可得到X(k).每计算一个X(k)值,需要进行N次复数相乘和(N-1)次复数相加,当计算X(0),X(1),…共N个X(k)值时,则需要次复数相乘,N(N-1)次复数相加.随着N值加大,运算工作量将迅速增大,因而所需的运算时间难以实现. 1.2 减少工作量的途径 由以上分析可知,在[W]于[x(n)]相乘过程中存在着不必要的重复计算,避免这些重复计算,则是简化运算的关键.经分析可以发现存在不必要的运算: 另外也存在可利用的特性: (1)、的周期性: (2)、的对称性: 经过简化之后,就可以使DFT运算过程大大简化. 1.3 基2FFT计算方法 基2FFT算法要求N为2的幂.设一个点序列x(n),采样点数,M是正整数(一般取

7、

8、

9、10等).基2算法的出发点是把N点DFT运算分解为两组N/2点的DFT运算,即把x(n)按n为偶数和n为奇数分解为两部分.即 式中,的下标N表示取N点DFT计算.若以符号2r表示偶数n,2r+1表示奇数n,r=0,1,2,…,(N/2-1),则 又因为 所以 其中 但是必须注意到,G(k)和H(k)只有N/2个点,k=0,1,2,…N/2-1,而X(k)却需要N个点,k=0,1,2…,N-1.如果以G(k)和H(k)表达全部X(k),可以利用G(k)和H(k)的周期性: 由此: K=0,1,2,…,N/2-1 此式即为实现FFT算法的基本公式.它的基本思想是用构成大序列的两个小序列的DFT计算大序列的DFT.

2 FFT算法的程序设计 2.1 程序设计流程图 (1)各参数初始化(有子程序input_initial(void)完成),本部分主要完成根据用户输入的M值,确定N,进而计算的实部wr与虚部wi的计算,其如图一所示. (图一) (2)倒序子程序原理及流程图 ①程序原理 对l=1,2,…,M计算;

记 逆排得 左移 m-1位得由此得 对计算 ②倒序程序流程图 (图二)

3 FFT应用实例 本程序所采用的验证实例为: F(t)=exp(-t) (图三) 3.1 FFT实例程序流程图 (图四) 3.2 程序源代码(Visual Stdio C++6.0环境下运行) #include #include #include #define pi 3.1415926 #define N0

32768 int M,N;

int jup[16],kup[16];

double wr[N0];

double wi[N0];

double A[2][N0];

void input_initial(void) { coutM;

N=1