《快速抽取傅里叶变换》由会员分享，可在线阅读，更多相关《快速抽取傅里叶变换（10页珍藏版）》请在金锄头文库上搜索。
1、西安电子科技大学课程论文 数字图像处理快速抽取傅里叶变换班级：070821作者：董文凯学号：07082001时间：2011-06-30快速抽取傅里叶变换实验要求：编写基 2 时间抽取快速傅里叶变换算法程序，用快速傅里叶变换计算下列两个序列 。其中 的线性卷积，比较nxnx21,cos0,12.N当 时快速傅里叶变换方法与用卷积定义法求卷积4,863,5104N的计算速度。实验内容：1.基 2 时间抽取 FFT 的推导过程：1.1 基本原理：设序列点数为 , 若不满足，认为加 0 使之达到要求。设旋转因子为2LN，快速抽取傅里叶变换将 的序列expnkNWjkn 2LN按 的奇偶分为两组： ，其
2、0,1. 12;xrxrr中 。则有：/r10nkNnDFTxW10NkkNnn为 偶 数 为 奇 数122210rrrx1122120022NrkrkkNNNrrxX式中， 和 分别是 和 的 的 DFT,1Xk1n/另外， 的取值范围是： ,./又利用 /2/2rNrkW可得 121/1 2/2100NrkrkNrxxW考虑到 /N及前半部分 ，1X,.可得后半部分 /12kXkXN1.2 复杂度分析：对任一次迭代，共有 对结点，因此共需 次复数加法和 次复/2 /2N数乘法；因此 次迭代的总计算量为：复数加法次数 ，复数乘法r 2logr次数为 ；算法复杂度为 。21/logN2logO
3、2.算法流程：2.1 蝶形运算信号流图：蝶形运算符号见图 1，以 2 点、4 点和 8 点为例表示出蝶形信号流程图如图2、图 3 和图 4 所示。图 1 蝶形运算符号图 2 两点蝶形信号流图图 3 四点蝶形信号流图图 4 八点蝶形信号流图2.2 算法流程图：图 5 基 2 时间抽取 FFT 算法流程图其中倒序部分算法流程见图 6。图 6 倒序部分算法流程实验结果及分析：将序列 和 基 2 时间抽取 FFT 进行变换得1()cos()xn2xn当N=4 时计算结果分别为：X1 =0.5839 - 0.4697i -0.9665 - 0.0000i 0.5839 + 0.4697i 6.1342
4、+ 0.0000iX2 =1.4142 - 0.7321i -1.3178 - 0.0000i 1.4142 + 0.7321i 4.1463 + 0.0000i当N=8 时计算结果分别为：X1 =Columns 1 through 512.0848 + 0.9318i 4.1977 - 2.9399i -1.3322 - 3.7609i -3.6975 -0.0000i -1.3322 + 3.7609iColumns 6 through 84.1977 + 2.9399i 12.0848 - 0.9318i 29.4783 + 0.0000iX2 =Columns 1 through 52
5、.5554 + 2.2279i 1.8637 - 1.1417i -0.4848 - 1.7721i -1.7502 -0.0000i -0.4848 + 1.7721iColumns 6 through 8当N=16 时计算结果分别为：X1 =1.0e+002 *Columns 1 through 50.2394 + 0.3432i 0.2346 + 0.0775i 0.0883 + 0.0001i 0.0680 -0.0619i 0.0178 - 0.0796iColumns 6 through 10-0.0276 - 0.0692i -0.0585 - 0.0396i -0.0694 -
6、 0.0000i -0.0585 +0.0396i -0.0276 + 0.0692iColumns 11 through 150.0178 + 0.0796i 0.0680 + 0.0619i 0.0883 - 0.0001i 0.2346 -0.0775i 0.2394 - 0.3432iColumn 161.2072 + 0.0000iX2 =Columns 1 through 52.5675 + 8.1495i 3.9564 + 2.8984i 3.6344 + 0.0469i 2.4751 -1.7258i 0.8794 - 2.5275iColumns 6 through 10-0
7、.7271 - 2.3729i -1.9126 - 1.4172i -2.3489 - 0.0000i -1.9126 +1.4172i -0.7271 + 2.3729iColumns 11 through 150.8794 + 2.5275i 2.4751 + 1.7258i 3.6344 - 0.0469i 3.9564 -2.8984i 2.5675 - 8.1495iColumn 1640.4692 + 0.0000i当N=32 时计算结果分别为：X1 =1.0e+002 *Columns 1 through 50.4796 + 1.5601i 0.4611 + 0.6776i 0.
8、4309 + 0.3421i 0.3898 +0.1453i 0.3210 - 0.1252iColumns 6 through 100.2888 - 0.0429i 0.2270 - 0.1145i 0.1635 - 0.1585i 0.1001 -0.1824i 0.0393 - 0.1893iColumns 11 through 15-0.0167 - 0.1815i -0.0658 - 0.1610i -0.1061 - 0.1302i -0.1360 -0.0913i -0.1545 - 0.0470iColumns 16 through 20-0.1607 - 0.0000i -0
9、.1545 + 0.0470i -0.1360 + 0.0913i -0.1061 +0.1302i -0.0658 + 0.1610iColumns 21 through 25-0.0167 + 0.1815i 0.0393 + 0.1893i 0.1001 + 0.1824i 0.1635 +0.1585i 0.2270 + 0.1145iColumns 26 through 300.2888 + 0.0429i 0.3210 + 0.1252i 0.3898 - 0.1453i 0.4309 -0.3421i 0.4611 - 0.6776iColumns 31 through 320.
10、4796 - 1.5601i 4.9659 + 0.0000iX2 =1.0e+002 *Columns 1 through 50.0093 + 0.2309i 0.0474 + 0.1182i 0.0576 + 0.0689i 0.0595 +0.0379i 0.0569 + 0.0152iColumns 6 through 100.0512 - 0.0022i 0.0431 - 0.0157i 0.0332 - 0.0255i 0.0223 -0.0320i 0.0108 - 0.0351iColumns 11 through 15-0.0004 - 0.0351i -0.0107 - 0
11、.0321i -0.0195 - 0.0266i -0.0262 -0.0189i -0.0304 - 0.0098iColumns 16 through 20-0.0319 - 0.0000i -0.0304 + 0.0098i -0.0262 + 0.0189i -0.0195 +0.0266i -0.0107 + 0.0321iColumns 21 through 25-0.0004 + 0.0351i 0.0108 + 0.0351i 0.0223 + 0.0320i 0.0332 +0.0255i 0.0431 + 0.0157iColumns 26 through 300.0512
12、 + 0.0022i 0.0569 - 0.0152i 0.0595 - 0.0379i 0.0576 -0.0689i 0.0474 - 0.1182iColumns 31 through 320.0093 - 0.2309i 1.1765 + 0.0000i当N=64、256、 512、1024 时的计算结果分别省略不求。结果分析：当N 远远大于1 时用基2FFT 方法计算比用一般卷积定义法求卷积的计算速度要快许多，因为快速傅里叶变换计算量远比卷积定义法求卷积的计算量少。近似下降一半。附录：源程序FFT.h#pragma once#ifndef FFT_H#define FFT_H#inc
13、lude #include using namespace std;#define pi 3.141592class FFTprivate:void changeOrder(double* xr,double* xi,int n);public:FFT(void);void FFT_1D(double* ctxr,double* ctxi,double* cfxr,double* cfxi,int len);void rFFT_1D(double* ctxr,double* cfxr,double* cfxi,int len);void IFFT_1D(double* cfxr,double*
14、 cfxi,double* ctxr,double* ctxi,int len);void rIFFT_1D(double* cfxr,double* cfxi,double* ctxr,int len);FFT(void);#endifFFT.cpp#include .fft.hFFT:FFT()/倒序实现/xr 实部，xi 虚部，n 为 2的幂/void FFT:changeOrder(double *xr,double *xi,int n)double temp;int k;int lh=n/2;int j=lh;int n1=n-2;for(int i=1;i=k)j=j-k;k=(i
15、nt)(k/2+0.5);j=j+k;/复数 FFT/ctxr和 ctxi的长度为 len/cfxr和 cfxi的长度为 2的幂/void FFT:FFT_1D(double *ctxr,double *ctxi,double *cfxr,double *cfxi,int len) int m=ceil(log(double)len)/log(2.0);int l,b,j,p,k;double rkb,ikb;int n=1#include FFT.husing namespace std;void main()double xr10=1,2,3,4,5,6,7,8,9,10; /实部double xi10=0,0,0,0,0,0,0,0,0,0; /虚部double *cxr,*cxi;cxr=new double16;cxi=new double16;FFT f;f.rFFT_1D(xr,cxr,cxi,10);for(int i=0;i16;i+)coutcxri+jcxii;coutendl;coutendl; double *fxr,*fxi
