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的理论基础。
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ号：24596024