fft算法，什么是FFT

本文目录一览

1，什么是FFT
2，求FFT公式或算法
3，FFT与图像最大互相关算法
4，关于示波器中 FFT 算法的问题
5，什么是FFT算法DSP是什么
6，基于cuda的一维快速傅里叶fft算法

1，什么是FFT

快速傅里叶变换，是计算机算傅里叶变换的常用方法。　FFT（Fast Fourier Transformation），即为快速傅氏变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的 FFT算法图发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。

什么是FFT

2，求FFT公式或算法

二维FFT相当于对行和列分别进行一维FFT运算。具体的实现办法如下：先对各行逐一进行一维FFT，然后再对变换后的新矩阵的各列逐一进行一维FFT。相应的伪代码如下所示： for (int i=0; i

在这里有： http://blog.21ic.com/user1/4123/archives/2007/38294.html

求FFT公式或算法

3，FFT与图像最大互相关算法

图像互相关算法就是计算两幅图像相关系数的方法，常用于图像匹配。例如同一目标物，被拍了两张照片，要把两张照片“对齐",可以给出不同的对位，计算相关系数，相关系数最大的对位就是最佳对齐。相关系数计算和褶积计算可以用到傅里叶变换。FFT 是快速傅里叶变换。FFT 要求离散点为 2 的整次方点，例如1024，2048....,它利用系数的对称性，省去大量计算时间。关于图像匹配互相关算法，网上好像很多。FFT 是老技术，程序也能找到。（随便找了一篇）图像匹配最大互相关算法的专用ASIC硬件实现方式研究见参考资料。

FFT与图像最大互相关算法

4，关于示波器中 FFT 算法的问题

FFT=fast fourior transform. 这是一种方便于计算机计算的快速傅里叶变换还有一种是DFT 但是因为其complexity=N^2>>FFT=NlogN 因此不被计算机算法采用紫色的是上面方波在频域里的对应值（spectrum）我们知道方波可以用傅里叶级数表示成无穷多个正弦函数的和f(t)=a∑sin(kπt)/k(大致表示不是精确的)因此频域里也是sin(wt)的叠加也就形成了显示的图案因为FFT是按一定采样率采样的因此频域里应该是周期函数但是由于DFT所取的点数限制还有取点数N*1/f(采样时间)不等于方波的周期使得函数有所谓的sidelobe 因此使得不是显示中不是完美的impulse. 周期特征也不明显而在FFT(DFT)里取点数会影响在频域里的分辨率点数取的越多频域的分辨率就越高显示就越会像一个impulse

5，什么是FFT算法DSP是什么

FFT是快速傅里叶变换（ Fast Fourier Transform ） DSP是数字信号处理（ Digital Signal Processing ）

1、蝶形算法：有关蝶形算法的介绍和思想大家百度或者Google一下就很容易找到，这里只是说一下要注意的地方。蝶形算法中有这样一个有趣的规则：若输入信号的顺序为自然顺序，那么输出信号的顺序就为倒位序（算法参见4）顺序。 2、二维FFT的变换顺序：首先进行行变换，对变换后的结果再进行列变换。 3、关于二维FFT运算后的结果按照公式运算出的结果中，能量大部分分集中在四个角，如果我们想要能量集中在中间，我们需要成一个欧拉数，其实也简单，你可以在输入信号时做一个简单的变换，如下描述：设i，j为输入信号的坐标，那么输入信号可表示为x(i, j)，若(i + j) % 2 == 0 则取源信号为输入信号，否则取源信号的相反数为输入信号，即 -x(i, j)。运算出来的结果中，能量就集中在中间位置了。 4、关于倒位序算法倒位序：就是将数字的各个尾反过来排序后得到的数字后的顺序，举个例子吧如我们的输入8个信号，我们只需要三个位就可以描述着写信号的下标，比如1 = 001B， 2 = 010B等等，那么1的倒位后为100B = 4， 010B = 2，依此类推，这就是倒位序，最后生成的新的顺序就是排序后的结果，这个结果有一个特点，那就是把偶数和奇数分开，这也就是FFT的理论基础。

6，基于cuda的一维快速傅里叶fft算法

CUFFT库说明有，很清楚的，下面代码赋值给data就可以了#define NX 256#define BATCH 10cufftHandle plan;cufftComplex *data;cudaMalloc((void**)&data, sizeof(cufftComplex)*NX*BATCH);if (cudaGetLastError() != cudaSuccess)fprintf(stderr, "Cuda error: Failed to allocate\n");return;}if (cufftPlan1d(&plan, NX, CUFFT_C2C, BATCH) != CUFFT_SUCCESS)fprintf(stderr, "CUFFT error: Plan creation failed");return;}.../* Note:* Identical pointers to input and output arrays implies in-placetransformation*/if (cufftExecC2C(plan, data, data, CUFFT_FORWARD) != CUFFT_SUCCESS)fprintf(stderr, "CUFFT error: ExecC2C Forward failed");return;}if (cufftExecC2C(plan, data, data, CUFFT_INVERSE) != CUFFT_SUCCESS)fprintf(stderr, "CUFFT error: ExecC2C Inverse failed");return;}