《串行FFT递归算法蝶式递归计算原理求傅里叶变换》由会员分享，可在线阅读，更多相关《串行FFT递归算法蝶式递归计算原理求傅里叶变换（18页珍藏版）》请在金锄头文库上搜索。
1、串行FFT递归算法（蝶式递归计算原理）求傅里叶变换摘要FFT，即为快速傅氏变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。设x(n)为N项的复数序列，由DFT变换，任一X（m）的计算都需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），那么求出N项复数序列的X（m）,即N点DFT变
2、换大约就需要N2次运算。当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变换就只需要Nlog(2)(N)次的
3、运算，N在1024点时，运算量仅有10240次，是先前的直接算法的1%，点数越多，运算量的节约就越大，这就是FFT的优越性。关键字：FFT 蝶式计算 傅里叶变换 / 目录一题目与要求11.1题目1二设计算法、算法原理12.1算法原理与设计12.2设计步骤2三算法描述、设计流程43.1算法描述43.2流程图5四源程序代码与运行结果74.1源程序代码74.2运行结果12五算法分析、优缺点135.1算法分析135.2优缺点14六总结15七参考文献16一题目与要求1.1题目对给定的，利用串行FFT递归算法（蝶式递归计算原理）计算其傅里叶变换的结果。1.2要求利用串行递归与蝶式递归原理，对给定的向量求解
4、傅里叶变换的结果。二设计算法、算法原理2.1算法原理与设计蝶式递归计算原理：令 为n/2次单位元根，则有 ，将b向量的偶数项 和奇数项 分别记 为 和 。注意推导中反复使用： 。图2.1 公式图形2.2设计步骤对于以上的分析可画出如图 2.2所示的离散傅里叶变换递归计算流图。图2.3就是一个按此递归方法计算的n=8的FFT蝶式计算图。FFT的蝶式递归计算图（有计算原理推出）：图2.2 递归计算流图特别的，的FFT蝶式计算图（展开的）：图2.3 蝶式计算图按输入元素展开，前面将输出序列之元素 按其偶下标（）和（）展开，导出 和递归计算式，按此构造出了如图1所示的FFT递归计算流程图。事实上，我们
5、也可以将输入序列之元素按其偶下标（） 和几下标（）展开，则导出另一种形式的FFT递归计算式 。三算法描述、设计流程3.1算法描述SISD上的FFT分治递归算法：输入: a=(a0,a1,an-1); 输出: B=(b0,b1,bn-1) Procedure RFFT(a,b) begin if n=1 then b0=a0 else (1)RFFT(a0,a2,an-2, u0,u1,un/2-1) (2)RFFT(a1,a3,an-1, v0,v1,vn/2-1) (3)z=1 (4)for j=0 to n-1 do (4.1)bj=uj mod n/2+zvj mod n/2 (4.2)
6、z=z endfor endifend 注: (1)算法时间复杂度t(n)=2t(n/2)+O(n) t(n)=O(nlogn)n=8的FFT蝶式计算图:图3.1 FFT蝶式计算图n=6的FFT递归计算流程图:图3.2 FFT递归计算流程图3.2流程图开始计算出前size_x/2个exp(-j*2*k/size_x)个值，即W的值输入序列对应值（例如5+j3，输入5 3）输入序列长度size_x飞级数i=？级数i加1是 输出fft结果序列结束 否 该级该组起始下标j=？计算出该级需要的W的个数l 是 否该级该组元素序数k=？组起始下标加2*lK加1 是Xj+k Xj+klXj+k+l*W(si
7、ze_x/2/l)*k Xj+k+l -1 否四源程序代码与运行结果4.1源程序代码/*FFT*/#include /整个程序输入和输出利用同一个空间xN，节约空间#include #include #define N 1000 /定义输入或者输出空间的最大长度typedefstructdouble real;doubleimg;complex; /定义复数型变量的结构体void fft(); /快速傅里叶变换函数声明void initW(); /计算W(0)W(size_x-1)的值函数声明void change(); /码元位置倒置函数函数声明void add(complex,comple
8、x,complex *); /*复数加法*/void mul(complex,complex,complex *); /*复数乘法*/void sub(complex,complex,complex *); /*复数减法*/void divi(complex,complex,complex *); /*复数除法*/void output(); /*输出结果*/complex xN,*W; /*输出序列的值*/intsize_x=0; /*输入序列的长度，只限2的N次方*/double PI; /pi的值int main()inti;system(cls);PI=atan(1)*4;printf
9、(Please input the size of x:n); /*输入序列的长度*/scanf(%d,&size_x);printf(Please input the data in xN:(such as:5 6)n);for(i=0;isize_x;i+) /*输入序列对应的值*/scanf(%lf %lf,&xi.real,&xi.img);initW(); /计算W(0)W(size_x-1)的值fft(); /利用fft快速算法进行DFT变化output(); /顺序输出size_x个fft的结果return 0;/*进行基-2 FFT运算,蝶形算法。这个算法的思路就是，先把计算过
10、程分为log(size_x)/log(2)-1级（用i控制级数）；然后把每一级蝶形单元分组（用j控制组的第一个元素起始下标）；最后算出某一级某一组每一个蝶形单元（用k控制个数，共l个）。*/voidfft()inti=0,j=0,k=0,l=0;complexup,down,product;change(); /实现对码位的倒置for(i=0;ilog(size_x)/log(2);i+) /循环算出fft的结果l=1i;for(j=0;jsize_x;j+=2*l)for(k=0;kl;k+) /算出第i级j组蝶形单元的结果 /算出j组中第k个蝶形单元mul(xj+k+l,W(size_x/2/l)*k,&product); /*size/2/l是该级W的相邻上标差，l是该级该组取的W总个数*/add(xj+k,product,&up);sub(xj+k,product,&down);xj+k=up; /up为蝶形单元右上方的值xj+k+l=down; /down为蝶形单元右下方的值void initW()
