### DFT的快速算法
#### 1.1 FFT算法（基于抽选）
##### 1.1.1 基2FFT：DIT和DIF
**1.1.1.1 DIT（按时间抽取）**
DIT算法是FFT算法的一种实现方式，它通过将输入序列按照奇偶分开，然后递归地对每个子序列进行DFT计算来减少运算量。具体步骤如下：
1. **第一次分解**
将输入信号\( x[n] \)分为两个子序列：一个由所有偶数索引的元素组成，另一个由所有奇数索引的元素组成。
\[
g[m] = x[2m],\quad m=0,1,\ldots,\frac{N}{2}-1
\]
\[
h[m] = x[2m+1],\quad m=0,1,\ldots,\frac{N}{2}-1
\]
对于\( k=0,1,\ldots,\frac{N}{2}-1 \)，有：
\[
G[k] = \sum_{m=0}^{\frac{N}{2}-1} g[m] W_{\frac{N}{2}}^{mk}
\]
\[
H[k] = \sum_{m=0}^{\frac{N}{2}-1} h[m] W_{\frac{N}{2}}^{mk}
\]
2. **第二次分解**
再次对\( g[m] \)和\( h[m] \)进行分解，直到分解成单个元素为止。
\[
X[k] = G[k] + W_N^k H[k],\quad k=0,1,\ldots,\frac{N}{2}-1
\]
\[
X[k+\frac{N}{2}] = G[k] - W_N^k H[k],\quad k=0,1,\ldots,\frac{N}{2}-1
\]
其中，\( W_N^k = e^{-j\frac{2\pi k}{N}} \) 是旋转因子。
**1.1.1.2 DIF（按频率抽取）**
DIF算法与DIT算法类似，但其操作顺序不同。在DIF算法中，首先是对输入序列进行DFT计算，然后再根据结果的不同部分进行分离。
1. **第一次分解**
将输入信号\( x[n] \)的DFT分为两部分：
\[
G[k] = \sum_{m=0}^{\frac{N}{2}-1} x[m] W_N^{mk}
\]
\[
H[k] = \sum_{m=\frac{N}{2}}^{N-1} x[m] W_N^{mk}
\]
2. **第二次分解**
再次对\( G[k] \)和\( H[k] \)进行分解，直到分解成单个元素为止。
\[
X[k] = G[k] + W_N^k H[k],\quad k=0,1,\ldots,\frac{N}{2}-1
\]
\[
X[k+\frac{N}{2}] = G[k] - W_N^k H[k],\quad k=0,1,\ldots,\frac{N}{2}-1
\]
##### 1.1.2 混合基（包括任意基）FFT
混合基FFT允许使用不同的基数进行分解，例如基2、基3等。这种灵活性使得混合基FFT能够在处理不同大小的数据集时更加高效。
1. **混合基FFT原理**
该方法可以结合多种基数的分解，如先使用基2分解，再使用其他基数进行进一步分解。
2. **应用场景**
适用于非2的幂次方的数据长度，可以有效减少运算次数。
##### 1.1.3 分裂基（组合基，SRFFT）
分裂基FFT是一种特殊的混合基FFT，它可以将不同基数的分解结合在一起，以达到更高的效率。
1. **分裂基FFT原理**
它可以先对数据进行一次大的基数分解，然后再对剩余部分使用较小的基数进行分解。
2. **优点**
能够更好地适应各种数据长度，并且在某些情况下比传统的混合基FFT更高效。
#### 1.2 GOERTZEL（戈泽尔）算法
戈泽尔算法是一种用于计算离散傅里叶变换(DFT)中的单个或少数几个频谱线的高效算法。
1. **算法特点**
- 仅适用于计算DFT中的部分频谱线。
- 运算量相比直接法减少了大约一半。
- 实现简单，易于编程。
2. **数学描述**
对于长度为\( N \)的序列\( x[n] \)，戈泽尔算法计算\( X[k] \)的具体步骤如下：
\[
y[n] = x[n] + e^{-j2\pi k/N} y[n-1] - e^{-j4\pi k/N} y[n-2]
\]
其中，初始条件为\( y[-1] = y[-2] = 0 \)。最终得到的频谱线值为：
\[
X[k] = y[N] - e^{-j2\pi k/N} y[N-1]
\]
3. **应用场景**
- 语音识别系统中的特定频率检测。
- 音乐合成器中的音符检测。
- 无线通信中的载波频率检测。
#### 1.3 CHIRPZ（线性调频）变换算法（CTA，CZT）
线性调频变换(CHIRP-Z变换)是一种通用的频域变换技术，它可以计算任意起点和间隔的频谱线。
1. **算法原理**
- 可以计算任意起点和间隔的频谱线。
- 不需要等间距采样。
- 计算复杂度较低。
2. **应用场景**
- 适用于需要计算不连续频谱线的情况。
- 在雷达信号处理、图像处理等领域有广泛应用。
### 总结
DFT的快速算法主要包括FFT算法和戈泽尔算法，以及CHIRPZ变换算法。FFT算法通过将大问题分解为小问题的方式来减少计算量，而戈泽尔算法则专门针对计算少数频谱线的情况进行了优化。CHIRPZ变换算法则是一种更为灵活的频谱分析工具，能够处理非等间距的频谱分析需求。这些算法的选择取决于具体的应用场景和技术需求。
天蓝色de海2017-08-18挺好的资源，学习了
