MATALB信号处理——信号的变换（6）

2-6快速傅里叶变换

       快速傅里叶变换 (fast Fourier transform), 即利用计算机计算离散傅里叶变换（DFT)的高效、快速计算方法的统称，简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。

1.DFT存在的问题和FFT的基本流程

       有限长序列可以通过离散傅里叶变换(DFT）将其频域也离散化成有限长序列。这里面要用到复数乘法和复数加法，相比较于实数乘法和实数加法，复数的运算次数要多上好几倍，而我们实际取N的值也很大，所以整个流程其计算量太大，很难实时地处理问题。

       将DFT中的定义为指数因子，因为其指数函数的特殊性，它具有对称性和周期性，可以借助它的性质来减小计算量。

       FFT的基本流程就是：1.把原始的N点序列，依次分解成一系列的短序列；2.求出这些短序列相应的DFT并进行适当组合，达到删除重复计算，减少乘法运算和简化结构的目的。听起来是不是很类似于小学学的组合运算。

2.FFT的计算方法

       计算离散傅里叶变换的快速方法，有按时间抽取的FFT算法和按频率抽取的FFT算法。前者是将时域信号序列按偶奇分排，后者是将频域信号序列按偶奇分排。它们都借助于的两个特点：一是周期性；二是对称性，这里符号*代表其共轭。这样，便可以把离散傅里叶变换的计算分成若干步进行，计算效率大为提高。

1.按时间抽取

       令信号长度为N（2的幂），可以将时域信号序列x(n)分解成两部分，一是偶数部分x（2n），另一是奇数部分x（2n+1），，，DFT的运算也分成了2部分

其中 

有。H(k)，G(k)都有N/2个点，从0到N/2-1。

       根据对称性，有，那么，因此，一个抽样点数为N 的信号序列x(n）的离散傅里叶变换，可以由两个 N/2抽样点序列的离散傅里叶变换求出。依此类推，这种按时间抽取算法是将输入信号序列分成越来越小的子序列进行离散傅里叶变换计算，最后合成为N点的离散傅里叶变换。

       通常蝶形算法的信号流图来表示离散傅里叶变换运算。例如，N=8的抽样点的信号序列x(n）的离散傅里叶变换，可用如图2所示的FET算法的信号流图来计算。

​ 

       对于N=2^M，通过M次分解，最后会成为2点的DFT运算，构成了从x(n)到X(k)的M级运算。　N=2点的离散傅里叶变换的计算全由蝶形运算组成，需要M级运算，每级包括N/2个蝶形运算，总共有(M)个蝶形运算。所以，总的计算量为次复数乘法运算和次复数加法运算。 

2.按频率抽取

        对于频率抽取，输入序列不是按奇数偶数分解，而是整个序列从中间截断，前后各一半，即

根据指数因子的展开，可以知道，再进一步分解为奇数组和偶数组，

剩下的和第一种方法类似。

参考资料——《MATLAB信号处理》沈再阳

                        百度百科