快速傅立叶变换应用，FFT快速傅立叶变换的工作原理

很多朋友对快速傅立叶变换应用，FFT快速傅立叶变换的工作原理不是很了解，每日小编刚好整理了这方面的知识，今天就来带大家一探究竟。

FFT是一种计算DFT的快速算法，但它是基于复数的，所以在计算实DFT时需要转换成复数格式。下图显示了实DFT和虚DFT。实DFT是将时域中N个点的信号转换成频域中的两个(N/2 ^ 1)点，其中一个(N/2 ^ 1)点称为实部，另一个(N/2 ^ 1)点称为信号。

相比较而言，复数DFT将两个n点的时域信号转化为两个n点的频域信号。在时域和频域中，一个N点信号是实部，另一个N点信号是虚部。如果要计算N点实数的DFT，就要在时域上把这N点作为实部，在时域上把N个0点作为虚部。我们可以通过FFT计算这样一个复信号的DFT，得到两个N点的频域信号，一个N点是实部，另一个N点是虚部。在这两个N点信号中，0到N/2点是要计算的N点实数的DFT频域。

对于实DFT来说，它的频域也是一个离散的周期信号，它的周期是N个点，从0到N/2点，1-N到-1点都是对称的，从下图可以看到。图中的坐标不是用n来表示，而是用采样频率的一部分来表示。所以如果用FFT逆变换计算实时域，就必须满足上图的对称性。FFT是如何工作的？

FFT的计算可以分为三步：首先将一个n点时域信号分成n个1点时域信号，然后对这n个1点时域信号进行频域计算得到n个频域点，再将这n个频域点按照一定的顺序相加得到我们需要的频谱。在这里，每个点都代表一个复数，它有一个实部和一个虚部。信号分解的第一步是按照以下规则进行的：可以看出是按照比特反转的顺序进行分解的。

第二步，计算每个点的频谱：这一步很简单，因为一个点在一个时域的频谱的值就是它本身，所以这一步不需要做什么，但是要明白，这N个点此时不是时域信号，而是频域信号。

第三步，将这N个频域信号合并，这是最麻烦的一步。与前面的时域分解相反，将两个1点频域信号变为一个2点频域信号，然后将两个2点频域信号变为一个4点频域信号，直到结束。下面介绍如何将两个4点频域信号变成一个8点频域信号。

首先复制一个4点频域信号，这样可以稀释时域信号，复制另一个4点频域信号，但是复制前需要乘以正弦函数，这样对稀释后的时域信号进行平移，然后将两个频域信号相加，如下图所示。这样做的目的是为了在时域分解中使用这种交错分解的方法。下面是一个基本运算，叫蝴蝶运算，把两个1点复数变成一个2点复数。

FFT运算的流程图运算速度比较如果用相关法计算DFT:如果用FFT法计算DFT:但是，FFT的速度可以更快。比如用基数4或者基数8，可以用4点或者8点计算，而不是2点，这样可以提高速度。FFT对于DSP就像晶体管对于电子学一样。每个人都知道如何使用它们，但只有少数人真正了解它们的原理。事实就是如此。你只需要知道如何使用它。

以上知识分享希望能够帮助到大家！