快速傅立叶变换 [英] fast fourier transform

问题描述

我正在为fft编写代码，用户将在其中输入样本数.我如何循环所有蝶形图，使其成为一个有效的程序.在蝶形图的每个阶段之间可以运行一个循环的共同因素是什么?

I was writing a code for fft where the user will input the number of samples. How do i loop all the butterfly diagrams so that it becomes an efficient program. what is the common factor between each stage of the butterfly diagram using which i can run a loop ???

推荐答案

周围有无数的FFT算法，网络上充满了对理论和算法的良好描述.为什么不先从网络搜索(google)开始，开发一些代码，然后在遇到问题时返回此处.

There are tons of FFT algorithms around and the web is full of good descriptions of the theory and the algorithms. Why don''t you start with a web search (google), develop some code, and come back here in case you run into problems.

我已经为第一阶段编写了代码蝴蝶:

i have written the code for the first stage butterfly which is :

for (k=0;k<m;k++)
{
    while (l    {
        if (k%2==0)
        INT[k]=input[l]+W[0]*input[l+m/2];
        else
        INT[k]=input[l]+W[m/2]*input[l+m/2];
        l=l+1;
     }
}

但是在接下来的阶段中，变量太多了，例如输入样本，输出样本，旋转因子.我面临的问题是我无法找到它们之间的关系，因此无法理解如何运行循环，因此整个过程蝴蝶可以解决.

but for the next stages there are too many variables like the input sample, the output sample,the twiddle factor.the problem i am facing is that i cant find a relation between them and hence cant understand how to run a loop so that the whole butterfly can be solved.

在Wiki上查找Cooley-Tukey算法，该算法具有简单，教学法"的C和C ++实现的链接:

http://en.wikipedia.org/wiki /Cooley％E2％80％93Tukey_FFT_algorithm#Pseudocode [ ^ ]

Cooley-Tukey一直被认为是FFT的经典之作.

Look up Cooley-Tukey algorithm on wiki, which has links to "simple, pedagogical" C and C++ implementations:

http://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm#Pseudocode[^]

Cooley-Tukey always was considered an FFT classic.

这篇关于快速傅立叶变换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！