DIT-FFT 至简设计实现法
1、 DIT-FFT 算法的基本原理
有限长序列
x
n
的 N 点 DFT 定义为：
X
(
k
)
=
∑
𝑁
―
1
𝑛
=
0
𝑥
(
𝑛
)
𝑊
𝐾𝑛
𝑁
,式中
𝑊
𝑁
=
𝑒
―
𝑗
2𝜋
𝑁
。
DFT 在实际应用中很重要，但是如果直接按 DFT 变换进行计算，当序列长度 N
很大时，计算量会非常大，所需时间也很长，因此常用的是 DFT 的一种快速计
算算法，简称 FFT。
最常用的 FFT 算法是基于时间抽取的基 2-FFT 算法和基于频率抽取的基
2-FFT 算法，这种算法的特点在于 FFT 会把一次大的 DFT 分割成几个小的
DFT，这样递归式地细分下去，例如有 8 个采样点的 FFT，首先会把最外层的 8
点运算分成两个 4 点 FFT 的奇偶组合，第二层 FFT 又分成四个两点 FFT 的奇偶
组合，并且由此计算出的频谱中很有趣的一点在于对于实数输出的数组，后面一
半和前面一半正好对称相同，对于虚数输出的数组，后面一半是前面数组对称后
乘上负 1，因此，我们只需要算出 FFT 的一半即可求出全部。
本设计讨论的是基于至简设计法实现按时间抽选的基 2-FFT 算法（即
DIF-FFT）实现过程，支持 N 由 8 到 1024。
图 1 按时间抽取的基 2-FFT 算法蝶形运算流图（N=8）
