【DSP数字信号处理学习笔记】—— 详细推导DFT的快速实现算法：FFT 基于库利-图基算法的实现

ゝ一纸荒年。 2022-12-25 04:54 65阅读 0赞

> 引言：尽管离散傅里叶变换（DFT）让频谱分析技术在计算机上的实现成为可能，但是受限于DFT算法庞大的计算量  O ( N 2 ) O(N^2) O(N2)，使得DFT在一开始并没有被广泛使用，直到快速傅里叶变换算法（FFT）的提出，使得计算复杂度降至  O ( N ⋅ l o g N ) O(N\\sdot logN) O(N⋅logN) 。从此，DFT技术如雨后春笋般在更各领域大显身手。那么今天这篇博文，我们就和大家一起来剖析一下FFT算法的推导过程。【注：由于FFT算法有几种版本，因此我们这里重点关注“库利-图基”算法】。

--------------------

【注：本文虽然涉及大量公式推导，但是博主相信只要大家从第一行开始跟着一步一步往下推是一定可以顺利推出来滴！！】

--------------------

# 要解决的事情（如何用更短的序列计算N点DFT？） #

【说明】：以下的推导，我们考虑的是长度为N的序列（N假定为2的幂）

现在我们有一个离散序列  x \[ n \] x\[n\] x\[n\]，我们首先回顾一下它的直接N点 DFT公式： X \[ k \] = ∑ n = 0 N − 1 x \[ n \] W N k n X\[k\] = \\sum\_\{n=0\}^\{N-1\}x\[n\]W\_N^\{kn\} X\[k\]=n=0∑N−1x\[n\]WNkn  
其中，这个  W N k n W\_N^\{kn\} WNkn ，其具体的表达式如下： W N k n = e − j 2 π N k n W\_N^\{kn\} = e^\{-j\\frac\{2π\}\{N\}kn\} WNkn=e−jN2πkn

--------------------

> 我们首先来思考一下DFT的计算复杂度，从上面这个公式我们可以知道：计算每一个X\[k\]的值，都需要做 N 次的复数乘法和 (N-1) 次的复数加法，而 X\[k\] 一共有 N 个点，所以完成所有 X\[k\] 的计算一共需要  N 2 N^2 N2 次复数乘法和  N ( N − 1 ) N(N-1) N(N−1) 次的复数加法。计算量还是很大的。

下面我们就思考：能不能用较短的序列的DFT计算这个较长的N点DFT呢？—— 首先容易想到的办法是：能不能把  x \[ n \] x\[n\] x\[n\] 拆成偶数项  g \[ n \] g\[n\] g\[n\] 和 奇数项  h \[ n \] h\[n\] h\[n\] 这样一来， g \[ n \] , h \[ n \] g\[n\], h\[n\] g\[n\],h\[n\] 分别都是长度为  N / 2 N/2 N/2 的序列，这两个序列的 DFT 能不能通过什么关系来表示出  X \[ k \] X\[k\] X\[k\]呢？我们来试试看：

X \[ k \] = ∑ n = 0 N − 1 x \[ n \] W N k n = ∑ r = 0 N / 2 − 1 x \[ 2 r \] W N 2 r k + ∑ r = 0 N / 2 − 1 x \[ 2 r + 1 \] W N ( 2 r + 1 ) k \\begin\{aligned\} X\[k\] &= \\sum\_\{n=0\}^\{N-1\}x\[n\]W\_N^\{kn\}\\\\ &=\\sum\_\{r=0\}^\{N/2-1\}x\[2r\]W\_N^\{2rk\}+\\sum\_\{r=0\}^\{N/2-1\}x\[2r+1\]W\_N^\{(2r+1)k\} \\end\{aligned\} X\[k\]=n=0∑N−1x\[n\]WNkn=r=0∑N/2−1x\[2r\]WN2rk\+r=0∑N/2−1x\[2r\+1\]WN(2r\+1)k

我们从上面的式子里面可以注意到：第二项里面的  W N ( 2 r + 1 ) k W\_N^\{(2r+1)k\} WN(2r\+1)k是可以拆开的，这里用到了  W N k W\_N^k WNk的一个性质，如下： W N ( 2 r + 1 ) k = e − j 2 π N ( 2 r + 1 ) k = e − j 2 π N 2 r k ⋅ e − j 2 π N k = W N 2 r k ⋅ W N k W\_N^\{(2r+1)k\} = e^\{-j\\frac\{2π\}\{N\}(2r+1)k\} =e^\{-j\\frac\{2π\}\{N\}2rk\}\\sdot e^\{-j\\frac\{2π\}\{N\}k\} = W\_N^\{2rk\}\\sdot W\_N^\{k\} WN(2r\+1)k=e−jN2π(2r\+1)k=e−jN2π2rk⋅e−jN2πk=WN2rk⋅WNk

所以，我们把第二项里面这个与  r r r 无关的  W N k W\_N^k WNk提出来，就变成： X \[ k \] = ∑ r = 0 N / 2 − 1 x \[ 2 r \] W N 2 r k + W N k ∑ r = 0 N / 2 − 1 x \[ 2 r + 1 \] W N 2 r k = ∑ r = 0 N / 2 − 1 g \[ r \] W N 2 r k + W N k ∑ r = 0 N / 2 − 1 h \[ r \] W N 2 r k \\begin\{aligned\} X\[k\] &=\\sum\_\{r=0\}^\{N/2-1\}x\[2r\]W\_N^\{2rk\} + W\_N^k\\sum\_\{r=0\}^\{N/2-1\}x\[2r+1\]W\_N^\{2rk\}\\\\ &=\\sum\_\{r=0\}^\{N/2-1\}g\[r\]W\_N^\{2rk\} + W\_N^k\\sum\_\{r=0\}^\{N/2-1\}h\[r\]W\_N^\{2rk\} \\end\{aligned\} X\[k\]=r=0∑N/2−1x\[2r\]WN2rk\+WNkr=0∑N/2−1x\[2r\+1\]WN2rk=r=0∑N/2−1g\[r\]WN2rk\+WNkr=0∑N/2−1h\[r\]WN2rk  
下面又遇到困难了：我们这里的  g \[ n \] , h \[ n \] g\[n\], h\[n\] g\[n\],h\[n\]明明都是长度为  N / 2 N/2 N/2的序列，你这里的 W 下标怎么还是  N N N ？与DFT的定义不一致啊！别急，所以我们下面做这样的变形： X \[ k \] = ∑ r = 0 N / 2 − 1 g \[ r \] ( W N 2 ) r k + W N k ∑ r = 0 N / 2 − 1 h \[ r \] ( W N 2 ) r k \\begin\{aligned\} X\[k\] &=\\sum\_\{r=0\}^\{N/2-1\}g\[r\](W\_N^\{2\})^\{rk\} + W\_N^k\\sum\_\{r=0\}^\{N/2-1\}h\[r\](W\_N^\{2\})^\{rk\} \\end\{aligned\} X\[k\]=r=0∑N/2−1g\[r\](WN2)rk\+WNkr=0∑N/2−1h\[r\](WN2)rk  
下面我们用用到了这样一个性质： W N 2 = W N / 2 1 W\_N^2 = W\_\{N/2\}^1 WN2=WN/21，我们下面简单证明一下： W N 2 = e − j 2 π N 2 = e − j 4 π N W\_N^2 = e^\{-j\\frac\{2π\}\{N\}2\} = e^\{-j\\frac\{4π\}\{N\}\} WN2=e−jN2π2=e−jN4π  
而： W N / 2 1 = e − j 2 π N / 2 1 = e − j 4 π N W\_\{N/2\}^1 = e^\{-j\\frac\{2π\}\{N/2\}1\} = e^\{-j\\frac\{4π\}\{N\}\} WN/21=e−jN/22π1=e−jN4π因此得证。  
有了这样得关系，上面的式子我们继续又可以写成： X \[ k \] = ∑ r = 0 N / 2 − 1 g \[ r \] ( W N / 2 1 ) r k + W N k ∑ r = 0 N / 2 − 1 h \[ r \] ( W N / 2 1 ) r k = ∑ r = 0 N / 2 − 1 g \[ r \] W N / 2 r k + W N k ∑ r = 0 N / 2 − 1 h \[ r \] W N / 2 r k \\begin\{aligned\} X\[k\] &=\\sum\_\{r=0\}^\{N/2-1\}g\[r\](W\_\{N/2\}^\{1\})^\{rk\} + W\_N^k\\sum\_\{r=0\}^\{N/2-1\}h\[r\](W\_\{N/2\}^\{1\})^\{rk\}\\\\ &=\\sum\_\{r=0\}^\{N/2-1\}g\[r\]W\_\{N/2\}^\{rk\} + W\_N^k\\sum\_\{r=0\}^\{N/2-1\}h\[r\]W\_\{N/2\}^\{rk\} \\end\{aligned\} X\[k\]=r=0∑N/2−1g\[r\](WN/21)rk\+WNkr=0∑N/2−1h\[r\](WN/21)rk=r=0∑N/2−1g\[r\]WN/2rk\+WNkr=0∑N/2−1h\[r\]WN/2rk  
那么我们但看这一项： ∑ r = 0 N / 2 − 1 g \[ r \] W N / 2 r k \\sum\_\{r=0\}^\{N/2-1\}g\[r\]W\_\{N/2\}^\{rk\} ∑r=0N/2−1g\[r\]WN/2rk这不恰好就是  g \[ r \] g\[r\] g\[r\] 的DFT嘛！而且是  N / 2 N/2 N/2 点的！  
所以，现在的  X \[ k \] X\[k\] X\[k\] 我们就可以写成： X \[ k \] = G \[ k \] + W N k H \[ k \] X\[k\] = G\[k\] + W\_N^kH\[k\] X\[k\]=G\[k\]\+WNkH\[k\]  
但是，需要特别注意的是，此时我们的  k k k 的取值范围只是： k = 0 , 1 , 2 , ⋯   , N 2 − 1 k = 0,1,2,\\cdots, \\frac\{N\}\{2\}-1 k=0,1,2,⋯,2N−1，因此，上面这个式子算出来的，只是  X \[ k \] X\[k\] X\[k\] 的前  N / 2 N/2 N/2 个，也就是一半，那么剩下的另一半应该如何计算呢？我们接着看：

因为我们现在的  k k k 的范围是： k = 0 , 1 , 2 , ⋯   , N 2 − 1 k = 0,1,2,\\cdots, \\frac\{N\}\{2\}-1 k=0,1,2,⋯,2N−1，所以使得  X \[ k \] X\[k\] X\[k\]只表示一半的值。那么，如果我们令  k ′ = k + N / 2 k' = k + N/2 k′=k\+N/2，这样一来，新的  k ′ k' k′ 的取值范围就是： k ′ = N 2 , N 2 + 1 , ⋯   , N − 1 k' = \\frac\{N\}\{2\}, \\frac\{N\}\{2\}+1, \\cdots, N-1 k′=2N,2N\+1,⋯,N−1  
所以我们欲求 X \[ k \] X\[k\] X\[k\]的后半部分，也就是计算： X \[ k + N 2 \] X\[k + \\frac\{N\}\{2\}\] X\[k\+2N\]。我们首先回顾一下刚刚我们都得到了什么式子： X \[ k \] = ∑ r = 0 N / 2 − 1 x \[ 2 r \] W N 2 r k + ∑ r = 0 N / 2 − 1 x \[ 2 r + 1 \] W N ( 2 r + 1 ) k X\[k\] =\\sum\_\{r=0\}^\{N/2-1\}x\[2r\]W\_N^\{2rk\}+\\sum\_\{r=0\}^\{N/2-1\}x\[2r+1\]W\_N^\{(2r+1)k\} X\[k\]=r=0∑N/2−1x\[2r\]WN2rk\+r=0∑N/2−1x\[2r\+1\]WN(2r\+1)k  
那么，我们把上面这个式子里面的  k k k 替换成： k + N 2 k + \\frac\{N\}\{2\} k\+2N，就可以得到： X \[ k + N 2 \] = ∑ r = 0 N / 2 − 1 x \[ 2 r \] W N 2 r ( k + N 2 ) + ∑ r = 0 N / 2 − 1 x \[ 2 r + 1 \] W N ( 2 r + 1 ) ( k + N 2 ) = ∑ r = 0 N / 2 − 1 x \[ 2 r \] W N 2 k r ⋅ W N r N + ∑ r = 0 N / 2 − 1 x \[ 2 r + 1 \] W N 2 r k ⋅ W N r N ⋅ W N k ⋅ W N N 2 \\begin\{aligned\} X\[k+\\frac\{N\}\{2\}\] &=\\sum\_\{r=0\}^\{N/2-1\}x\[2r\]W\_N^\{2r(k+\\frac\{N\}\{2\})\}+\\sum\_\{r=0\}^\{N/2-1\}x\[2r+1\]W\_N^\{(2r+1)(k+\\frac\{N\}\{2\})\}\\\\ &=\\sum\_\{r=0\}^\{N/2-1\}x\[2r\]W\_N^\{2kr\}\\sdot W\_N^\{rN\} + \\sum\_\{r=0\}^\{N/2-1\}x\[2r+1\]W\_N^\{2rk\}\\sdot W\_N^\{rN\}\\sdot W\_N^k\\sdot W\_N^\{\\frac\{N\}\{2\}\} \\end\{aligned\} X\[k\+2N\]=r=0∑N/2−1x\[2r\]WN2r(k\+2N)\+r=0∑N/2−1x\[2r\+1\]WN(2r\+1)(k\+2N)=r=0∑N/2−1x\[2r\]WN2kr⋅WNrN\+r=0∑N/2−1x\[2r\+1\]WN2rk⋅WNrN⋅WNk⋅WN2N  
大家看到这个式子是不是觉得有点奇怪，但是没关系，我们把这些  W W W 都变成指数就明白了：

1.  首先，  W N r N W\_N^\{rN\} WNrN可以变成： ( W N N ) r (W\_N^N)^r (WNN)r，那么 ，我们就有： W N N = e − j 2 π N N = e − j 2 π = 1 W\_N^N = e^\{-j\\frac\{2π\}\{N\}N\} = e^\{-j2π\} = 1 WNN=e−jN2πN=e−j2π=1因此我们就可以知道： ( W N N ) r = 1 (W\_N^N)^r=1 (WNN)r=1。
2.  下面我们看第二项最后的那个： W N N 2 W\_N^\{\\frac\{N\}\{2\}\} WN2N，它展开成指数形式就是： W N N 2 = e − j 2 π N ⋅ N 2 = e − j 2 π 2 = e − j π = − 1 W\_N^\{\\frac\{N\}\{2\}\} = e^\{-j\\frac\{2π\}\{N\}\\sdot \\frac\{N\}\{2\}\} = e^\{-j\\frac\{2π\}\{2\}\} = e^\{-jπ\} = -1 WN2N=e−jN2π⋅2N=e−j22π=e−jπ=−1

好的，完成了这些项的分析，那么我们把它们带入到上面那个长长的式子里面去，就会得到： X \[ k + N 2 \] = ∑ r = 0 N / 2 − 1 x \[ 2 r \] W N 2 k r + ∑ r = 0 N / 2 − 1 x \[ 2 r + 1 \] W N 2 r k ⋅ W N k ⋅ ( − 1 ) = ∑ r = 0 N / 2 − 1 x \[ 2 r \] W N 2 k r − W N k ∑ r = 0 N / 2 − 1 x \[ 2 r + 1 \] W N 2 r k = ∑ r = 0 N / 2 − 1 g \[ r \] W N / 2 r k − W N k ∑ r = 0 N / 2 − 1 h \[ r \] W N / 2 r k \\begin\{aligned\} X\[k + \\frac\{N\}\{2\}\] &= \\sum\_\{r=0\}^\{N/2-1\}x\[2r\]W\_N^\{2kr\}+ \\sum\_\{r=0\}^\{N/2-1\}x\[2r+1\]W\_N^\{2rk\}\\sdot W\_N^k\\sdot (-1)\\\\ &= \\sum\_\{r=0\}^\{N/2-1\}x\[2r\]W\_N^\{2kr\} - W\_N^k \\sum\_\{r=0\}^\{N/2-1\}x\[2r+1\]W\_N^\{2rk\}\\\\ &=\\sum\_\{r=0\}^\{N/2-1\}g\[r\]W\_\{N/2\}^\{rk\} - W\_N^k\\sum\_\{r=0\}^\{N/2-1\} h\[r\] W\_\{N/2\}^\{rk\} \\end\{aligned\} X\[k\+2N\]=r=0∑N/2−1x\[2r\]WN2kr\+r=0∑N/2−1x\[2r\+1\]WN2rk⋅WNk⋅(−1)=r=0∑N/2−1x\[2r\]WN2kr−WNkr=0∑N/2−1x\[2r\+1\]WN2rk=r=0∑N/2−1g\[r\]WN/2rk−WNkr=0∑N/2−1h\[r\]WN/2rk

那么，我们就可以得到  X \[ k \] X\[k\] X\[k\] 后面一半的值的表达式，为： X \[ k + N 2 \] = G \[ k \] − W N k H \[ k \] X\[k+\\frac\{N\}\{2\}\] = G\[k\] - W\_N^kH\[k\] X\[k\+2N\]=G\[k\]−WNkH\[k\]

因此，我们就得到了下面这个优美的表达式，即用两个  N / 2 N/2 N/2 的DFT表示一个 N 点DFT： X \[ k \] = \{ G \[ k \] + W N k H \[ k \] k = 0 , 1 , 2 , ⋯   , N 2 − 1 G \[ k \] − W N k H \[ k \] k = N 2 + 1 , ⋯   , N − 1 X\[k\] = \\begin\{cases\} G\[k\] + W\_N^kH\[k\] \\quad k = 0,1,2,\\cdots , \\frac\{N\}\{2\}-1\\\\ G\[k\] - W\_N^kH\[k\] \\quad k = \\frac\{N\}\{2\}+1, \\cdots, N-1 \\end\{cases\} X\[k\]=\{ G\[k\]\+WNkH\[k\]k=0,1,2,⋯,2N−1G\[k\]−WNkH\[k\]k=2N\+1,⋯,N−1  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4NjQ3Mw_size_16_color_FFFFFF_t_70_pic_center]

这只是一层的分解，如果我们发现  N 2 \\frac\{N\}\{2\} 2N 还能够继续分解成两个  N 4 \\frac\{N\}\{4\} 4N 的DFT，那么就继续重复刚刚的分析。下面我们来看一个例子巩固一下：

--------------------

我们现在要计算一个8点的DFT，那么首先，我们根据偶部和奇部将其分为两个4点的DFT，如下图所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4NjQ3Mw_size_16_color_FFFFFF_t_70]

那么结果其实也是分两个部分计算出来的，第一部分是： X \[ 0 \] , X \[ 1 \] , X \[ 2 \] , X \[ 3 \] X\[0\],X\[1\],X\[2\],X\[3\] X\[0\],X\[1\],X\[2\],X\[3\]，它们就是利用公式： G \[ k \] + W N k H \[ k \] G\[k\] + W\_N^kH\[k\] G\[k\]\+WNkH\[k\]  
如框图所示。第二部分就是  X \[ 4 \] , X \[ 5 \] , X \[ 6 \] , X \[ 7 \] X\[4\],X\[5\],X\[6\],X\[7\] X\[4\],X\[5\],X\[6\],X\[7\]，它利用公式： G \[ k \] − W N k H \[ k \] G\[k\] - W\_N^kH\[k\] G\[k\]−WNkH\[k\]  
同时，我们也注意到：左边由于是对输入信号按照时间抽取的，因此实际的输入顺序就变成了： x \[ 0 \] , x \[ 2 \] , x \[ 4 \] , x \[ 6 \] , x \[ 1 \] , x \[ 3 \] , x \[ 5 \] , x \[ 7 \] x\[0\],x\[2\], x\[4\],x\[6\],x\[1\],x\[3\],x\[5\],x\[7\] x\[0\],x\[2\],x\[4\],x\[6\],x\[1\],x\[3\],x\[5\],x\[7\]，但是输出就是按照顺序的。

接下来，对于每一组的  N / 2 = 4 N/2 = 4 N/2=4点DFT，我们还可以继续细分，一个4点DFT可以由两个2点DFT得出，因此我们再看看如何由2点DFT得到4点DFT。

我们先写出  g \[ n \] g\[n\] g\[n\] 的DFT表达式： G \[ k \] = ∑ n = 0 N / 2 − 1 g \[ n \] W N / 2 k n G\[k\] = \\sum\_\{n = 0\}^\{N/2-1\}g\[n\]W\_\{N/2\}^\{kn\} G\[k\]=n=0∑N/2−1g\[n\]WN/2kn  
那么，还是一样的做法，我们把  g \[ n \] g\[n\] g\[n\] 分为偶部  a \[ n \] a\[n\] a\[n\] 和奇部  b \[ n \] b\[n\] b\[n\]，那么就可以写成： G \[ k \] = ∑ r = 0 N / 4 − 1 g \[ 2 r \] W N / 2 2 r k + ∑ r = 0 N / 4 − 1 g \[ 2 r + 1 \] W N / 2 ( 2 r + 1 ) k = ∑ r = 0 N / 4 − 1 g \[ 2 r \] W N / 2 2 r k + W N / 2 k ∑ r = 0 N / 4 − 1 g \[ 2 r + 1 \] W N / 2 2 k r = ∑ r = 0 N / 4 − 1 a \[ r \] W N / 4 r k + W N / 2 k ∑ r = 0 N / 4 − 1 b \[ r \] W N / 4 k r = A \[ k \] + W N / 2 k B \[ k \] = A \[ k \] + W N 2 k B \[ k \] \\begin\{aligned\} G\[k\] &=\\sum\_\{r = 0\}^\{N/4-1\}g\[2r\]W\_\{N/2\}^\{2rk\} + \\sum\_\{r = 0\}^\{N/4-1\}g\[2r+1\]W\_\{N/2\}^\{(2r+1)k\}\\\\ &=\\sum\_\{r = 0\}^\{N/4-1\}g\[2r\]W\_\{N/2\}^\{2rk\} + W\_\{N/2\}^k\\sum\_\{r = 0\}^\{N/4-1\}g\[2r+1\]W\_\{N/2\}^\{2kr\}\\\\ &=\\sum\_\{r = 0\}^\{N/4-1\}a\[r\]W\_\{N/4\}^\{rk\} + W\_\{N/2\}^k\\sum\_\{r = 0\}^\{N/4-1\}b\[r\]W\_\{N/4\}^\{kr\}\\\\ &=A\[k\] + W\_\{N/2\}^kB\[k\]\\\\ &=A\[k\] + W\_N^\{2k\}B\[k\] \\end\{aligned\} G\[k\]=r=0∑N/4−1g\[2r\]WN/22rk\+r=0∑N/4−1g\[2r\+1\]WN/2(2r\+1)k=r=0∑N/4−1g\[2r\]WN/22rk\+WN/2kr=0∑N/4−1g\[2r\+1\]WN/22kr=r=0∑N/4−1a\[r\]WN/4rk\+WN/2kr=0∑N/4−1b\[r\]WN/4kr=A\[k\]\+WN/2kB\[k\]=A\[k\]\+WN2kB\[k\]

因此，做类似的何理推断，我们也可以得出  G \[ k \] G\[k\] G\[k\] 后一半的表达式为： G \[ k + N / 4 \] = A \[ k \] − W N 2 k B \[ k \] k = 0 , 1 , ⋯   , N / 4 − 1 G\[k + N/4\] = A\[k\] - W\_N^\{2k\}B\[k\] \\quad k = 0, 1,\\cdots , N/4-1 G\[k\+N/4\]=A\[k\]−WN2kB\[k\]k=0,1,⋯,N/4−1

因此，我们就可以得到下面细分的框图。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4NjQ3Mw_size_16_color_FFFFFF_t_70 1][]

--------------------

我们发现：如果是按照时间抽取，那么在输入端是需要按照一定的顺序输入的（乱序输入），下面我们介绍另外一种类似的方式——从频域抽取：

还是一样，我们先摆出DFT公式： X \[ k \] = ∑ n = 0 N − 1 x \[ n \] W N k n X\[k\] = \\sum\_\{n=0\}^\{N-1\}x\[n\]W\_N^\{kn\} X\[k\]=n=0∑N−1x\[n\]WNkn

那么，我们可以先直接把  X \[ k \] X\[k\] X\[k\] 拆成前一半的DFT和后一半的DFT的叠加，即： X \[ k \] = ∑ n = 0 N / 2 − 1 x \[ n \] W N k n + ∑ n = N / 2 N − 1 x \[ n \] W N k n = ∑ n = 0 N / 2 − 1 x \[ n \] W N k n + ∑ n = 0 N / 2 − 1 x \[ n + N 2 \] W N k ( n + N / 2 ) = ∑ n = 0 N / 2 − 1 x \[ n \] W N k n + ( W N N / 2 ) k ∑ n = 0 N / 2 − 1 x \[ n + N 2 \] W N k n \\begin\{aligned\} X\[k\] &= \\sum\_\{n=0\}^\{N/2-1\}x\[n\]W\_N^\{kn\}+\\sum\_\{n=N/2\}^\{N-1\}x\[n\]W\_N^\{kn\}\\\\ &=\\sum\_\{n=0\}^\{N/2-1\}x\[n\]W\_N^\{kn\}+\\sum\_\{n=0\}^\{N/2-1\}x\[n+\\frac\{N\}\{2\}\]W\_N^\{k(n+N/2)\}\\\\ &=\\sum\_\{n=0\}^\{N/2-1\}x\[n\]W\_N^\{kn\}+ (W\_N^\{N/2\})^k\\sum\_\{n=0\}^\{N/2-1\}x\[n+\\frac\{N\}\{2\}\]W\_N^\{kn\} \\end\{aligned\} X\[k\]=n=0∑N/2−1x\[n\]WNkn\+n=N/2∑N−1x\[n\]WNkn=n=0∑N/2−1x\[n\]WNkn\+n=0∑N/2−1x\[n\+2N\]WNk(n\+N/2)=n=0∑N/2−1x\[n\]WNkn\+(WNN/2)kn=0∑N/2−1x\[n\+2N\]WNkn

我们又意识到： ( W N N / 2 ) k = ( − 1 ) k (W\_N^\{N/2\})^k = (-1)^k (WNN/2)k=(−1)k，因此，上式就可以表示为： X \[ k \] = ∑ n = 0 N / 2 − 1 x \[ n \] W N k n + ( − 1 ) k ∑ n = 0 N / 2 − 1 x \[ n + N 2 \] W N k n X\[k\] = \\sum\_\{n=0\}^\{N/2-1\}x\[n\]W\_N^\{kn\}+(-1)^k\\sum\_\{n=0\}^\{N/2-1\}x\[n+\\frac\{N\}\{2\}\]W\_N^\{kn\} X\[k\]=n=0∑N/2−1x\[n\]WNkn\+(−1)kn=0∑N/2−1x\[n\+2N\]WNkn

看到  ( − 1 ) k (-1)^k (−1)k ，我们就发现，这里就需要对  k k k 做奇偶的讨论了。  
【1】当 k 是偶数时，我们可以得到： X \[ 2 r \] = ∑ n = 0 N / 2 − 1 x \[ n \] W N 2 r n + ∑ n = 0 N / 2 − 1 x \[ n + N 2 \] W N 2 r n = ∑ n = 0 N / 2 − 1 x \[ n \] W N / 2 r n + ∑ n = 0 N / 2 − 1 x \[ n + N 2 \] W N / 2 r n = ∑ n = 0 N / 2 − 1 \{ x \[ n \] + x \[ n + N 2 \] \} W N / 2 r n \\begin\{aligned\} X\[2r\] &= \\sum\_\{n=0\}^\{N/2-1\}x\[n\]W\_N^\{2rn\}+\\sum\_\{n=0\}^\{N/2-1\}x\[n+\\frac\{N\}\{2\}\]W\_N^\{2rn\}\\\\ &=\\sum\_\{n=0\}^\{N/2-1\}x\[n\]W\_\{N/2\}^\{rn\}+\\sum\_\{n=0\}^\{N/2-1\}x\[n+\\frac\{N\}\{2\}\]W\_\{N/2\}^\{rn\}\\\\ &=\\sum\_\{n=0\}^\{N/2-1\}\\\{x\[n\] + x\[n+ \\frac\{N\}\{2\}\]\\\}W\_\{N/2\}^\{rn\} \\end\{aligned\} X\[2r\]=n=0∑N/2−1x\[n\]WN2rn\+n=0∑N/2−1x\[n\+2N\]WN2rn=n=0∑N/2−1x\[n\]WN/2rn\+n=0∑N/2−1x\[n\+2N\]WN/2rn=n=0∑N/2−1\{ x\[n\]\+x\[n\+2N\]\}WN/2rn

**我们发现， X \[ k \] X\[k\] X\[k\]的偶数项正好是  x \[ n \] + x \[ n + N 2 \] x\[n\] + x\[n+\\frac\{N\}\{2\}\] x\[n\]\+x\[n\+2N\]的 N/2 点DFT。**

类似地，当 k 是奇数时，有： X \[ 2 r + 1 \] = ∑ n = 0 N / 2 − 1 x \[ n \] W N ( 2 r + 1 ) n − ∑ n = 0 N / 2 − 1 x \[ n + N 2 \] W N ( 2 r + 1 ) n = ∑ n = 0 N / 2 − 1 x \[ n \] W N 2 r n ⋅ W N n − ∑ n = 0 N / 2 − 1 x \[ n + N 2 \] W N 2 r n ⋅ W N n = ∑ n = 0 N / 2 − 1 \{ \{ x \[ n \] − x \[ n + N 2 \] \} W N n \} W N / 2 r n \\begin\{aligned\} X\[2r+1\] &= \\sum\_\{n=0\}^\{N/2-1\}x\[n\]W\_N^\{(2r+1)n\} - \\sum\_\{n=0\}^\{N/2-1\}x\[n+\\frac\{N\}\{2\}\]W\_N^\{(2r+1)n\}\\\\ &=\\sum\_\{n=0\}^\{N/2-1\}x\[n\]W\_\{N\}^\{2rn\}\\sdot W\_N^n-\\sum\_\{n=0\}^\{N/2-1\}x\[n+\\frac\{N\}\{2\}\]W\_\{N\}^\{2rn\}\\sdot W\_N^n\\\\ &=\\sum\_\{n=0\}^\{N/2-1\}\\\{\\\{x\[n\] - x\[n+\\frac\{N\}\{2\}\]\\\}W\_N^n\\\}W\_\{N/2\}^\{rn\} \\end\{aligned\} X\[2r\+1\]=n=0∑N/2−1x\[n\]WN(2r\+1)n−n=0∑N/2−1x\[n\+2N\]WN(2r\+1)n=n=0∑N/2−1x\[n\]WN2rn⋅WNn−n=0∑N/2−1x\[n\+2N\]WN2rn⋅WNn=n=0∑N/2−1\{ \{ x\[n\]−x\[n\+2N\]\}WNn\}WN/2rn

我们发现， \[ k \] \[k\] \[k\] 的奇数项正好是  \{ x \[ n \] − x \[ n + N 2 \] \} W N n \} \\\{x\[n\] - x\[n+\\frac\{N\}\{2\}\]\\\}W\_N^n\\\} \{ x\[n\]−x\[n\+2N\]\}WNn\}的N/2点DFT。所以在  x \[ n \] x\[n\] x\[n\] 输入时，我们首先得做这样的变换：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4NjQ3Mw_size_16_color_FFFFFF_t_70_pic_center 1]  
搞明白这个了，那么我们直接上8点DFT的FFT实现就很清晰了：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4NjQ3Mw_size_16_color_FFFFFF_t_70 2]  
这里，我们不加证明地给出：**FFT算法中，当N是2的整数次幂时，N点FFT复数相乘和复数相加的总数等于  N ( l o g 2 N N(log\_2N N(log2N）**。是不是快了很多！！

--------------------

那么至此，我们对基于库利-图基算法的FFT就介绍完毕啦！我们在学习的时候，还是应该保证一种欣赏的态度去学习，殊不知这些现在理所应当的东西是当时轰动一时的艺术品之一！

PS:能坚持推导到这里的想必也是真爱了！赶紧吃顿好的犒劳一下自己吧！！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4NjQ3Mw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/eec7023c81644e209cda0d41e235dfe0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4NjQ3Mw_size_16_color_FFFFFF_t_70]: /images/20221120/1f8ee587868e4f3ba238292aea9fd17a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4NjQ3Mw_size_16_color_FFFFFF_t_70 1]: /images/20221120/1b06c13d760f48f18da2bfa902940da8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4NjQ3Mw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/8693e76ecfc14a848242f4b30c2edc41.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4NjQ3Mw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201202181512640.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4NjQ3Mw==,size_16,color_FFFFFF,t_70