实数DFT，复数DFT，FFT
FFT是计算DFT的快速算法，但是它是基于复数的，所以计算实数DFT的时候需要将其转换为复数的格局，下图展现了实数DFT和虚数DFT的情状，实数DFT将时域中N点信号转换成2个(N/2+1)点的频域信号，此中1个(N/2+1)点的信号称之为实部，另一个(N/2+1)点的信号称之为虚部，实部和虚部门别是正弦和余弦信号的幅度。
比拟较而言，复数DFT将2个N点的时域信号转换为2个N点的频域信号。时域和频域中，1个N点信号是实部，另1个N点信号是虚部。
假设要计算N点实数DFT，则将那个N个点做为时域中的实部，另取N个0点做为时域的虚部，用FFT计算如许一个复数信号的DFT得到2个N点的频域信号，1个N点是实部另1个N点是虚部，在那两个N点的信号中，从0到N/2个点就是须计算的N点实数的DFT频域。
关于实数DFT来说，就像前几章讲的那样，它的频域也是离散周期信号，其周期为N点，从0到N/2点和1-N到-1点具有对称性，那个你能够从下面一张图看出。图中坐标不是用N表达是用摘样频次的分数表达，假设你看不懂，请看前面几章。
所以你假设用FFT反变更计算的是实数时域，则要称心上图的对称性。
FFT若何工做
FFT的计算能够分为三步：起首将1个N点的时域信号分红N个1点的时域信号，然后计算那N个1点时域信号的频域，得到N个频域的点，然后将那个N个频域的点根据必然的挨次加起来，就得到了我们需要的频谱。那里每个点的意思是复数，都有实部和虚部。
第一步的信号合成根据下面的法例施行：
能够看出它是根据比特反转挨次来合成的。
第二步是计算每个点的频谱：
那一步很简单，因为一个时域的点的频谱的数值就是它本身，所以那一步什么也不需做，但需大白那时候N个点不是时域信号了，而是频域信号。
第三步是将那N个频域信号连系起来
那一步是最费事的一步。就是和前面时域合成的挨次相反，将2个1点的频域信号酿成1个2点的频域信号，再将2个2点的频域信号酿成1个4点的频域信号，不断到完毕。那里看下若何将2个4点的频域信号酿成1个8点的频域信号。
起首对1个4点的频域信号停止复造，如许能稀释时域信号，也对另1个4点的频域信号停止复造不外复造之前需要乘上正弦函数，如许得到的稀释时域信号时颠末了平移的，然后将那两个频域信号加起来，如下图所示。之所以那么做的目标是在时域合成的时候就是用那种交错的合成体例的。
以下是根本的运算，称为蝶形运算，它将2个1点的复数酿成1个2点的复数。
以下是FFT运算的流程图
运算速度比力
假设用相关办法计算DFT：
假设用FFT办法计算DFT：
FFT的速度还能更快
好比利用基4或者基8，如许不是2点一计算，而是4点或者8点一计算，能够进步速度。
FFT对DSP来说就像是晶体管对电子学来说，都是范畴的根底，每小我都晓得怎么利用它们，但是只要很少一部门实正领会它们的原理。
事实就是如许，你只要晓得怎么用就能够了。
- END -
700页PPT，讲解工业机器人手艺根底
机器人4大坐标系讲解，别在搞混了
人工智能导论（180页PPT分享）
机器进修的通俗讲解
带你进门智能造造手艺根底
200页PPT搞懂机器视觉及利用手艺
手艺大全：40种传感器原理、电路、实例
全面领会智能汽车传感器手艺
点击文末阅读原文下载材料《数据构造C语言版》