其中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的分解流程。

    FFT算法的原理是通过许多小的更加容易进行的变换去实现大规模的变换，降低了运算要求，提高了与运算速度。FFT不是DFT的近似运算，它们完全是等效的。

2 快速傅里叶算法在TMS320LF2407上的实现
    根据FFT算法的特点，处理器要在一个指令周期内完成乘和累加的工作，因为复数运算要多次查表相乘才能实现。其二就是间接寻址，可以实现增／减1个变址量，方便各种查表方法。再次，FFT变换的输入序列x(n)是按所谓的码位倒序排列的，处理器要有反序间接寻址的能力。DSP控制器专门设计了特有的反序间接寻址，并能在一个指令周期内完成乘和累加的运算。因此，对数字信号的分析处理，DSP比其它的处理器有绝对的优势。本文采用TI公司C2000系列TMS320LF2407芯片来实现FFT算法。