FFT 推导过程

所有考试总算考完了，于是我被 L^AJ_i 学校坑去生产线 QAQ

趁着脑袋还记得先马一下（距离遗忘 DSP 所有内容还有 30min

计算过程

已知 $X [m] = \sum_{k = 0}^{N - 1} x [k] W_{N}^{k m}, m = 0, 1, . . . N - 1$

那么

\begin{aligned} X [m] & = \sum_{k = 0}^{N - 1} [k == 2 r] x [k] W_{N}^{k m} + \sum_{k = 0}^{N - 1} [k == 2 r + 1] x [k] W_{N}^{k m} \\ = \sum_{r = 0}^{N / 2 - 1} x [2 r] W_{N}^{2 r m} + \sum_{r = 0}^{N / 2 - 1} x [2 r + 1] W_{N}^{(2 r + 1) m} \\ = \sum_{r = 0}^{N / 2 - 1} x [2 r] W_{N}^{2 r m} + W_{N}^{m} \sum_{r = 0}^{N / 2 - 1} x [2 r + 1] W_{N}^{2 r m} \\ = \sum_{r = 0}^{N / 2 - 1} x_{1} [r] W_{N}^{2 r m} + W_{N}^{m} \sum_{r = 0}^{N / 2 - 1} x_{2} [r] W_{N}^{2 r m} \end{aligned}

由可约，

\begin{aligned} X [m] & = \sum_{r = 0}^{N / 2 - 1} x_{1} [r] W_{N / 2}^{r m} + W_{N}^{m} \sum_{r = 0}^{N / 2 - 1} x_{2} [r] W_{N / 2}^{r m} \\ = X_{1} [m] + X_{2} [m] \end{aligned}

由周期，

X_{1} [m + N / 2] = X_{1} [m]

X_{2} [m + N / 2] = X_{2} [m]

由对称，

W_{N}^{m + N / 2} = - W_{N}^{m}

可得到另一边

X [m + N / 2] = X_{1} [m + N / 2] + W_{N}^{m + N / 2} X_{2} [m + N / 2] = X_{1} [m] - W_{N}^{m} X_{2} [m]

对比一下

\begin{aligned} X [m] & = X_{1} [m] + W_{N}^{m} X_{2} [m] \\ X [m + N / 2] & = X_{1} [m] - W_{N}^{m} X_{2} [m] \end{aligned}

可以得出复杂度 $T (n) = 2 T (n / 2) + O (n)$

本来考试前画了一张挺漂亮的图但找不到了..

换了一张灵魂作图