《按时间抽选的基2-FFT算法 - 倒序算法》由会员分享，可在线阅读，更多相关《按时间抽选的基2-FFT算法 - 倒序算法（4页珍藏版）》请在金锄头文库上搜索。
1、按时间抽选的基按时间抽选的基 2-FFT 算法算法 - 倒序算法倒序算法我尝试自己编写一个 FFT 程序，首先要做的一个工作就是倒序。所谓倒序输入 顺序输出嘛我看了关于倒序的一个介绍。一个 2n 的序列 经过排序最后的得到的倒序 实际就是二进制的倒读过来。原来很简单，但是看它介绍的编程思路很难看懂。我观察了下 一个 8 个数的序列 比如：0 1 2 3 4 5 6 7-0 4 2 6 1 5 3 7 再找一个 16 个的例子也是一样 倒序后的数 相互对称的数字相加都是同一个数字大小再二分法 就可以发现这样的规律可以递推下去，所以这个就激起我想用递归的方法来实现倒序，因为它的规模可以缩小。终于克
2、服了恐惧心理，克服了懒惰习惯。一步步地完成了 FFT 算法 从倒序算法 到 FFT 的实现 参考了一些资料 还翻出了数字信号处理书。有一些用到的小函数还没有贴出来 贴代码了：void Base2TimeFFT(Complex * orign_result,Complex * l_result, int M,int Isign = 1)/1 mean fft -1 mean ifftif (!(Isign = 1 | Isign = -1 )/判断输入是否规范return ;Isign = -1 * Isign; /为了后来运算思路清晰 int Nsample = (int) Pow(2,M);
3、/倒序 int i, j;int *inverse_sort;inverse_sort = new intNsample;for (i = 0 ; i Nsample ; i+)inverse_sorti = i;InverseSort(inverse_sort,M);for (i = 0; i Nsample ; i+)l_resulti = orign_result(inverse_sorti);delete inverse_sort;/计算旋转因子Complex *spinelement;spinelement = new ComplexNsample / 2;/用到的旋转因子只有一半d
4、ouble N2pi = PI * 2 / Nsample;for (i = 0; i Nsample / 2;i+)spinelementi.m_real = cos(N2pi * i);spinelementi.m_img = Isign * sin(N2pi * i);int spinstep;/这个参数代表了该级运算的旋转因子的个数/同时也代表了 碟性的跨度/运算循环开始int L ;int spin;int temp;Complex temp_save1,temp_save2;for (L = 1; L = M;L+) /第 L 级运算temp = (int) Pow(2 , L);
5、spinstep = (int) Pow(2,L-1);for (j = 0; j spinstep;j+)spin = (int) (j * Pow(2,(M - L);for (i = j ; i = (Nsample - 1); i+= temp)temp_save1 = (l_resulti +(l_resulti + spinstep * spinelementspin);temp_save2 = ( l_resulti - (l_resulti + spinstep * spinelementspin);l_resulti = temp_save1;l_resulti + spinstep = temp_save2;delete spinelement; if (Isign = 1)/如果是 IFFT 还要归一化 isign 已经在前面反号了的for (i = 0 ; i Nsample;i+)l_resulti /= Nsample;
