【摘要】：FFT是DFT的快速算法，它在确定DFT的系数时，使所要求的乘法及加法次数减少。FFT算法的实质就是把一个长数据序列x，经多次分选抽取，最终分割成n/2个，每个有两个数据的序列做DFT计算，并分别算出分割后比较短的子序列的频谱；然后按一定的规则组合，即可得到整个序列x的频谱。这样，只需对只有两项的“序列”求DFT；然后应用式逐步“合并”；最终可求得原序列{x}的DFT。
FFT是DFT的快速算法，它在确定DFT的系数时，使所要求的乘法及加法次数减少。FFT的算法有很多种，其中大多数已编制了程序，从而使应用于数字频谱分析、滤波器模拟及相关领域的计算技术产生了较大的发展。
在按照式（5-2）的DFT直接计算X（k）值时，对于N个X（k）中的每一个必须做N次x（n）乘以e-j2πkn/N。所以共有N2次复数乘法运算，而且还要做N（N-1）次复数相加的运算。其计算工作量直接与N的大小有关，当N较大时，计算工作量将急剧增加。
FFT算法的实质就是把一个长数据序列x（n），经多次分选抽取，最终分割成n/2个，每个有两个数据的序列做DFT计算，并分别算出分割后比较短的子序列的频谱；然后按一定的规则组合，即可得到整个序列x（n）的频谱。
例如：有一数据序列{x（n）}，n=0，1，2，…，N-1，如图5-7所示（N=8）。将序列{x（n）}按偶数项和奇数项，经一次抽取组合成两个较短的半序列{y（n）}和{z（n）}，其中
则它们与X（k）的关系为(www.xing528.com)
式（5-10）表明，原序列{x（n）}的DFT能直接根据两个半序列的DFT计算出来。
如果原序列{x（n）}的总项数N=2p，则可以把它分割成两个半序列，半序列{y（n）}和{z（n）}又可以分成4个1/4序列；然后再分成8个1/8序列，直到最后每个序列只剩下两项为止。这样，只需对只有两项的“序列”求DFT；然后应用式（5-10）逐步“合并”；最终可求得原序列{x（n）}的DFT。按FFT算法逻辑步骤，编好程序用计算机进行计算。
图5-7 原始序列{x（n）}及其半序列{y（n）}、{z（n）}
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
