离散傅立叶变换（DFT）的定义：
为了表达简洁，令，则。
FFT的种类很多，这里以最简单的基于2的FFT（信号长度是2的整数幂）为例：
FFT实际上一种分治算法。FFT将长度为的信号分解成两个长度为信号进行处理，这样分解一直到最后，每一次的分解都会减少计算的次数。理解FFT分以下三个步骤进行：
步骤1：将信号分解成两个子信号
偶数样本点信号：；
奇数样本点信号：；
则：
步骤2：将两个求和项理解成两个长度为的DFT
其中，所以
其中，偶数样本点信号的DFT：
奇数样本点信号的DFT：
步骤3：FFT的具体计算过程（通过蝶形图可视化）
由于对和都具有周期性：，所以，
，（周期性）
以为例，信号的FFT计算过程如下：
第1次分解：
第2次分解：
第3次分解：
FFT与DFT的性能比较
根据DFT的定义，
对于任意都要进行次加法操作，所以DFT共有次乘法操作。
对于任意都要进行次加法操作，所以DFT共有次加法操作。
从FFT的蝶形图中可以看出，
共有次乘法操作和次加法操作。
