按时间抽取的FFT算法—DIT 原理

按时间抽取的FFT算法（Discrete Fourier Transform）是一种计算离散信号的频率分量的方法。DIT（Decimation In Time）是按时间抽取的FFT算法的一种实现方式，其基本思想是将原始信号分解为多个子信号，然后对每个子信号进行FFT计算得到频率分量，最后组合成整个信号的FFT。

DIT算法的实现过程如下：

1. 将原始信号分解为长度为2的子信号，每个子信号包含原始信号中相邻的两个采样点。

2. 对每个子信号进行2点FFT计算得到频率分量。

3. 将每个子信号按照奇偶性分为两组，分别进行下一级的FFT计算。

4. 重复步骤2和3，直到得到长度为N的FFT结果。

DIT算法的优点是计算速度快，适用于长度为2的幂次的信号，且可以通过递归实现。

然而，DIT算法的缺点是需要进行多次数据重排操作，导致计算复杂度较高，对于非2的幂次长度的信号需要进行零填充，影响计算精度。