目录
Preliminaries
- DFT
- \(W_N^{nk}\)的性质
- 周期性：\(W_N^{a+N} = W_N^a\)
- 对称性：\(W_N^{a+\frac{N}{2}}=-W_N^a\)
- 缩放性：\(W_N^a = W_{\frac{N}{m}}^{\frac{a}{m}}\)
DFT分治计算
将序列\(x[n]\)分奇偶表示
\[\begin{aligned} x_{even}[m] &= x[2m], &m= 0,1,2,\cdots,\frac{N}{2}-1\\ x_{odd}[m] &= x[2m+1], &m= 0,1,2,\cdots, \frac{N}{2} - 1\\ \end{aligned} \]则DFT表达式可以改写为
\[\begin{aligned} X(k) &= \sum_{n=0}^{N-1}x[n]W_N^{nk}, &k = 0,1,2,\cdots,N-1\\ &=\sum_{m=0}^{\frac{N}{2}-1}x[2m]W_N^{2mk} + \sum_{m=0}^{\frac{N}{2}-1}x[2m+1]W_N^{(2m+1)k}, &k=0,1,2,\cdots,N-1\\ &=\sum_{m=0}^{\frac{N}{2}-1}x[2m]W_{\frac{N}{2}}^{mk} + W_N^k\sum_{m=0}^{\frac{N}{2}-1}x[2m+1]W_{\frac{N}{2}}^{mk}, &k=0,1,2,\cdots,N-1\\ X(k)&=X_{even}(k) + W_N^kX_{odd}(k), &k=0,1,2,\cdots,\frac{N}{2} - 1\\ \end{aligned} \]在\(X_{even}(k)\)和\(X_{odd}(k)\)中，\(k\)的取值范围是\(\{0,1,2,\cdots, \frac{N}{2}-1\}\)，而在\(X(k)\)中\(k\)的取值范围是\(\{0,1,2,\cdots,N - 1\}\)，因此还要求出\(k\)在\(\{\frac{N}{2}, \cdots, N-1\}\)范围\(X(k)\)的值：
\[\begin{aligned} X(k+\frac{N}{2}) &= X_{even}(k+\frac{N}{2}) + W_N^{k+\frac{N}{2}}X_{odd}(k+\frac{N}{2}), &k=\frac{N}{2},\frac{N}{2}+1, \cdots, N-1\\ &= X_{even}(k) - W_N^kX_{odd}(k), &k=\frac{N}{2},\frac{N}{2}+1, \cdots, N-1\\ \end{aligned} \]以此类推，可以将\(X_{even}(k)\)和\(X_{odd}(k)\)按照上述方法分治运算……
FFT蝶形运算
以\(X(1)\)为例：
\[\begin{aligned} X(1) &= x(0) - x(8)W_{16}^0 + x(4)W_{16}^4 - x(12)W_{16}^4 + x(2)W_{16}^2 - x(10)W_{16}^2 + x(6)W_{16}^6 - x(14)W_{16}^6 \\&+ x(1)W_{16}^1 - x(9)W_{16}^1 + x(5)W_{16}^5 - x(13)W_{16}^5 + x(3)W_{16}^3 - x(11)W_{16}^3 + x(7)W_{16}^7 - x(15)W_{16}^7\\ &= x(0) + x(1)W_{16}^1 + x(2)W_{16}^2 + x(3)W_{16}^3 + x(4)W_{16}^4 + x(5)W_{16}^5 + x(6)W_{16}^6 + x(7)W_{16}^7\\&- x(8)W_{16}^0 - x(9)W_{16}^1 - x(10)W_{16}^2 - x(11)W_{16}^3- x(12)W_{16}^4 - x(13)W_{16}^5 - x(14)W_{16}^6 - x(15)W_{16}^7\\ &= x(0) + x(1)W_{16}^1 + x(2)W_{16}^2 + x(3)W_{16}^3 + x(4)W_{16}^4 + x(5)W_{16}^5 + x(6)W_{16}^6 + x(7)W_{16}^7\\&+ x(8)W_{16}^8 + x(9)W_{16}^9 + x(10)W_{16}^{10} + x(11)W_{16}^{11}+ x(12)W_{16}^{12}+ x(13)W_{16}^{13}+ x(14)W_{16}^{14}+ x(15)W_{16}^{15}\\ &=\sum_{n=0}^{15} x(n)W_{16}^{n1} \end{aligned} \] 标签：even,frac,16,变换,傅里叶,cdots,2m,aligned,快速 From： https://www.cnblogs.com/euler0525/p/17810661.html