VC++的FFT快速傅里叶变换编程设计+流程图+源代码(11)
1．一致性。同一个模块内部的标识符命名要一致。例如，如果规定变量的首字母大写，用全部大写表示常量，那么整个模块内都应该这么写。
2．准确性。用词要准确，可以望文生义，避免概念模糊或形式相近的标识符。例如，定义Total表示合计要比随意用一个变量来表示要明确的多。myFun、temp等模糊概念的变量也要避免。
3．长度短，信息多。在保持准确性的前提性，要力争长度短、信息多。既用最短数目的字符数表示尽可能多的信息。例如，用Total表示合计，而不用TotalOfNumbers。
3.FFT算法介绍
3.1离散傅立叶变换
离散傅立叶变换（DFT）实现了信号首次在频域表示的离散化，使得频域也能够用计算机进行处理。并且这种DFT变换可以有多种实用的快速算法。使信号处理在时、频域的处理和转换均可离散化和快速化。
设序列x(n)长度为M，定义x(n)的N点DFT为
式中，N称为离散傅里叶变换区间长度，要求N ≥ M。为书写简单，令 ，因此通常将N点DFT表示为
定义X(k)的N点离散傅里叶逆变换(IDFT)为3.2快速傅里叶变换
非周期性连续时间信号x(t)的傅里叶变换可以表示为
式中计算出来的是信号x(t)的连续频谱。但是，在实际的控制系统中能够得到的是连续信号x(t)的离散采样值x(nT)。因此需要利用离散信号x(nT)来计算信号x(t)的频谱。
有限长离散信号x(n)，n=0，1，…，N-1的DFT定义为：
可以看出，DFT需要计算大约N2次乘法和N2次加法。当N较大时，这个计算量是很大的。利用WN的对称性和周期性，将N点DFT分解为两个N／2点的 DFT，这样两个N／2点DFT总的计算量只是原来的一半，即(N／2)2+(N／2)2=N2／2，这样可以继续分解下去，将N／2再分解为N／4点 DFT等。对于N=2m 点的DFT都可以分解为2点的DFT，这样其计算量可以减少为(N／2)log2N次乘法和Nlog2N次加法。图1为FFT与DFT-所需运算量与计算点数的关系曲线。由图可以明显看出FFT算法的优越性。
图4.1 DIT-FFT与DFT所需乘法次数比较曲线
将x(n)分解为偶数与奇数的两个序列之和，即
x1(n)和x2(n)的长度都是N／2，x1(n)是偶数序列，x2(n)是奇数序列，则
其中X1(k)和X2(k)分别为x1(n)和x2(n)的N／2点DFT。由于X1(k)和X2(k)均以N／2为周期，且WN k+N/2=-WN k，所以X(k)又可表示为：
上式的运算可以用图2表示，根据其形状称之为蝶形运算。依此类推，经过m-1次分解，最后将N点DFT分解为N／2个两点DFT。图3为8点FFT的分解流程。
图4.2 蝶形运算示意图
图4.3 8点DFT一次时域抽取分解运算流图
图4.4 8点DIT-FFT运算流图
FFT算法的原理是通过许多小的更加容易进行的变换去实现大规模的变换，降低了运算要求，提高了与运算速度。FFT不是DFT的近似运算，它们完全是等效的。
减少运算量方法：
1.长序列分为短序列： 由于N点DFT的运算量随N2增长，因此，当N较大时，减少运算量的途径之一就是将N点DFT分解为几个较短的DFT进行计算，则可大大减少其运算量。