# 库利-图基快速傅里叶变换算法

## 時域/頻域抽取法

### 時域抽取法

${\displaystyle X[k]=\sum _{n=0}^{N-1}x[n]e^{-j(2\pi {\frac {nk}{N}})}\qquad k=0,1,\ldots ,N-1}$

${\displaystyle =\sum _{n\ even}x[n]W_{N}^{nk}+\sum _{n\ odd}x[n]W_{N}^{nk}}$

${\displaystyle =\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}}$

${\displaystyle =\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}}$

${\displaystyle =\sum _{r=0}^{(N/2)-1}x[2r]W_{N/2}^{rk}+W_{N}^{k}\sum _{r=0}^{(N/2)-1}x[2r+1]W_{N/2}^{rk}}$

${\displaystyle =G[k]+W_{N}^{k}H[k]}$

• ${\displaystyle {\begin{cases}G[k+{\frac {N}{2}}]=G[k]\\H[k+{\frac {N}{2}}]=H[k]\end{cases}}}$

• ${\displaystyle W_{N}^{k+N/2}=-W_{N}^{k}}$

### 頻域抽取法

${\displaystyle X[2r]=\sum _{n=0}^{N-1}x[n]W_{N}^{n(2r)}\ r=0,1,\cdots ,{\frac {N}{2}}-1}$

${\displaystyle =\sum _{n=0}^{{\frac {N}{2}}-1}x[n]W_{N}^{2nr}+\sum _{n={\frac {N}{2}}}^{N-1}x[n]W_{N}^{2nr}}$

${\displaystyle =\sum _{n=0}^{{\frac {N}{2}}-1}x[n]W_{N}^{2nr}+\sum _{n=0}^{{\frac {N}{2}}-1}x[n+{\frac {N}{2}}]W_{N}^{2r[n+{\frac {N}{2}}]}}$

${\displaystyle {\color {Gray}\because W_{N}^{2r[n+{\frac {N}{2}}]}=W_{N}^{2rn}W_{N}^{rN}=W_{N}^{2rn}}}$

${\displaystyle =\sum _{n=0}^{{\frac {N}{2}}-1}x[n]W_{N}^{2rn}+\sum _{n=0}^{{\frac {N}{2}}-1}x[n+{\frac {N}{2}}]W_{N}^{2rn}}$

${\displaystyle =\sum _{n=0}^{{\frac {N}{2}}-1}(x[n]+x[n+{\frac {N}{2}}])W_{\frac {N}{2}}^{rn}}$

${\displaystyle =\sum _{n=0}^{{\frac {N}{2}}-1}g[n]W_{\frac {N}{2}}^{rn}}$

${\displaystyle X[2r+1]=\sum _{n=0}^{N-1}x[n]W_{N}^{n(2r+1)}\ r=0,1,\cdots ,{\frac {N}{2}}-1}$

${\displaystyle =\sum _{n=0}^{{\frac {N}{2}}-1}x[n]W_{N}^{n(2r+1)}+\sum _{n={\frac {N}{2}}}^{N-1}x[n]W_{N}^{n(2r+1)}}$

${\displaystyle =\sum _{n=0}^{{\frac {N}{2}}-1}x[n]W_{N}^{n(2r+1)}+\sum _{n=0}^{{\frac {N}{2}}-1}x[n+{\frac {N}{2}}]W_{N}^{(2r+1)[n+{\frac {N}{2}}]}}$

${\displaystyle {\color {Gray}\because W_{N}^{(2r+1)[n+{\frac {N}{2}}]}=W_{N}^{(2r+1)n}W_{N}^{(2r+1){\frac {N}{2}}}=-W_{N}^{(2r+1)n}}}$

${\displaystyle =\sum _{n=0}^{{\frac {N}{2}}-1}x[n]W_{N}^{(2r+1)n}-\sum _{n=0}^{{\frac {N}{2}}-1}x[n+{\frac {N}{2}}]W_{N}^{(2r+1)n}}$

${\displaystyle =\sum _{n=0}^{{\frac {N}{2}}-1}(x[n]-x[n+{\frac {N}{2}}])W_{N}^{n(2r+1)}}$

${\displaystyle =\sum _{n=0}^{{\frac {N}{2}}-1}(x[n]-x[n+{\frac {N}{2}}])W_{N}^{n}W_{\frac {N}{2}}^{nr}}$

${\displaystyle =\sum _{n=0}^{{\frac {N}{2}}-1}(h[n]W_{N}^{n})W_{\frac {N}{2}}^{rn}}$

## 單一基底

### 2基底

2基底-快速傅立葉演算法（Radix-2 FFT）是最廣為人知的一種库利－图基快速傅立葉演算法分支。此方法不斷地將N點的FFT拆解成兩個'N/2'點的FFT，利用旋轉因子${\displaystyle W^{nk},W^{\frac {N}{2}}}$的對稱性藉此來降低DFT的計算複雜度，達到加速的功效。

### 4基底

4基底快速傅立葉變換演算法則是承接2基底的概念，在此裡用時域抽取的技巧，將原本的DFT公式拆解為四個一組的形式：

${\displaystyle X[k]=\sum _{n=0}^{N-1}x[n]e^{-j(2\pi {\frac {nk}{N}})}\qquad k=0,1,\ldots ,N-1}$

${\displaystyle =\sum _{n=0}^{{\frac {N}{4}}-1}x[4n+0]W_{N}^{(4n+0)k}+\sum _{n=0}^{{\frac {N}{4}}-1}x[4n+1]W_{N}^{(4n+1)k}}$

${\displaystyle +\sum _{n=0}^{{\frac {N}{4}}-1}x[4n+2]W_{N}^{(4n+2)k}+\sum _{n=0}^{{\frac {N}{4}}-1}x[4n+3]W_{N}^{(4n+3)k}}$

${\displaystyle =W_{N}^{0}\sum _{n=0}^{{\frac {N}{4}}-1}x[4n+0]W_{\frac {N}{4}}^{nk}+W_{N}^{1k}\sum _{n=0}^{{\frac {N}{4}}-1}x[4n+1]W_{\frac {N}{4}}^{nk}}$

${\displaystyle +W_{N}^{2k}\sum _{n=0}^{{\frac {N}{4}}-1}x[4n+2]W_{\frac {N}{4}}^{nk}+W_{N}^{3k}\sum _{n=0}^{{\frac {N}{4}}-1}x[4n+3]W_{\frac {N}{4}}^{nk}}$

${\displaystyle W_{N}^{0}F_{0}(k)+W_{N}^{k}F_{1}(k)+W_{N}^{2k}F_{2}(k)+W_{N}^{3k}F_{3}(k)}$

## 混合基底

### 2/8基底

${\displaystyle C_{2k}=\sum _{n=0}^{{\frac {N}{2}}-1}(x_{2n}+x_{{\frac {N}{2}}+n})W^{2nk}}$

${\displaystyle C_{8k+1}=\sum _{n=0}^{{\frac {N}{8}}-1}{\begin{Bmatrix}[(x_{n}-x_{n+{\frac {N}{2}}})-j(x_{n+{\frac {N}{4}}}-x_{n+{\frac {3N}{4}}})]+W^{\frac {N}{8}}[(x_{n+{\frac {N}{8}}}-x_{n+{\frac {5N}{8}}})-j(x_{n+{\frac {3N}{8}}}-x_{n+{\frac {7N}{8}}})]\end{Bmatrix}}W^{8nk}W^{n}}$

${\displaystyle C_{8k+5}=\sum _{n=0}^{{\frac {N}{8}}-1}{\begin{Bmatrix}[(x_{n}-x_{n+{\frac {N}{2}}})-j(x_{n+{\frac {N}{4}}}-x_{n+{\frac {3N}{4}}})]-W^{\frac {N}{8}}[(x_{n+{\frac {N}{8}}}-x_{n+{\frac {5N}{8}}})-j(x_{n+{\frac {3N}{8}}}-x_{n+{\frac {7N}{8}}})]\end{Bmatrix}}W^{8nk}W^{5n}}$

${\displaystyle C_{8k+3}=\sum _{n=0}^{{\frac {N}{8}}-1}{\begin{Bmatrix}[(x_{n}-x_{n+{\frac {N}{2}}})+j(x_{n+{\frac {N}{4}}}-x_{n+{\frac {3N}{4}}})]+W^{\frac {3N}{8}}[(x_{n+{\frac {N}{8}}}-x_{n+{\frac {5N}{8}}})+j(x_{n+{\frac {3N}{8}}}-x_{n+{\frac {7N}{8}}})]\end{Bmatrix}}W^{8nk}W^{3n}}$

${\displaystyle C_{8k+7}=\sum _{n=0}^{{\frac {N}{8}}-1}{\begin{Bmatrix}[(x_{n}-x_{n+{\frac {N}{2}}})+j(x_{n+{\frac {N}{4}}}-x_{n+{\frac {3N}{4}}})]-W^{\frac {3N}{8}}[(x_{n+{\frac {N}{8}}}-x_{n+{\frac {5N}{8}}})+j(x_{n+{\frac {3N}{8}}}-x_{n+{\frac {7N}{8}}})]\end{Bmatrix}}W^{8nk}W^{7n}}$

### 2/4/8基底

8n點FFT在不同演算法下所需複數乘法量
N=8n 2基底 4基底 2/4混合基底 2/4/8基底
8 2 - 2 0
64 98 76 72 48
512 1538 - 1082 824
4096 18434 13996 12774 10168

### 22基底

N點DFT公式： ${\displaystyle X(k)=\sum _{n=0}^{N-1}x(n)W_{N}^{nk},0\leqq k

${\displaystyle {\begin{cases}n=<{\frac {N}{2}}n_{1}+{\frac {N}{4}}n_{2}+n_{3}>_{N}\\k=_{N}\end{cases}}}$

${\displaystyle X(k_{1}+2k_{2}+4k_{3})=\sum _{n_{3}=0}^{{\frac {N}{4}}-1}\sum _{n_{2}=0}^{1}\sum _{n_{1}=0}^{1}x({\frac {N}{2}}n_{1}+{\frac {N}{4}}n_{2}+n_{3})W_{N}^{({\frac {N}{2}}n_{1}+{\frac {N}{4}}n_{2}+n_{3})(k_{1}+2k_{2}+4k_{3})}}$

${\displaystyle =\sum _{n_{3}=0}^{{\frac {N}{4}}-1}\sum _{n_{2}=0}^{1}{\begin{Bmatrix}B_{\frac {N}{2}}^{k_{1}}W_{N}^{({\frac {N}{4}}n_{2}+n_{3})k_{1}}\end{Bmatrix}}W_{N}^{({\frac {N}{4}}n_{2}+n_{3})(2k_{2}+4k_{3})}}$

${\displaystyle B_{\frac {N}{2}}^{k_{1}}=x({\frac {N}{4}}n_{2}+n_{3})+(-1)^{k_{1}}x({\frac {N}{4}}n_{2}+n_{3}+{\frac {N}{2}})}$

${\displaystyle W_{N}^{({\frac {N}{4}}n_{2}+n_{3})(k_{1}+2k_{2}+4k_{3})}=W_{N}^{Nn_{2}n_{3}}W_{N}^{{\frac {N}{4}}n_{2}(k_{1}+2k_{2})}W_{N}^{n_{3}(k_{1}+2k_{2})}W_{N}^{4n_{3}k_{3}}}$

${\displaystyle =(-j)^{n_{2}(k_{1}+2k_{2})}W_{N}^{n_{3}(k_{1}+2k_{2})}W_{N}^{4n_{3}k_{3}}}$

${\displaystyle X(k_{1}+2k_{2}+4k_{3})=\sum _{n_{3}=0}^{{\frac {N}{4}}-1}[H(k_{1},k_{2},n_{3})W_{N}^{n_{3}(k_{1}+2k_{2})}]W_{N}^{4n_{3}k_{3}}}$

${\displaystyle H(k_{1},k_{2},n_{3})={\begin{matrix}\underbrace {{\begin{matrix}BF2I\\\overbrace {[x(n_{3})+(-1)^{k_{1}}(n_{3}+{\frac {N}{2}})]} \end{matrix}}{\begin{matrix}\\\\+(-j)^{k_{1}+2k_{2}}\end{matrix}}{\begin{matrix}BF2I\\\overbrace {[x(n_{3}+{\frac {N}{4}})+(-1)^{k_{1}}(n_{3}+{\frac {3N}{4}})]} \end{matrix}}} \\BF2II\end{matrix}}}$

R2SDF 2(log4N-1) 4log4N N-1 簡單
R4SDF log4N -1 8log4N N-1 中等
R22SDF log4N -1 4log4N N-1 簡單

### 23基底

#### ${\displaystyle {\frac {\sqrt {2}}{2}}}$乘法化簡

${\displaystyle W^{\frac {N}{8}}=-W^{\frac {5N}{8}}={\frac {\sqrt {2}}{2}}(1-j),W^{\frac {3N}{8}}=-W^{\frac {7N}{8}}=-{\frac {\sqrt {2}}{2}}(1+j)}$

─並沒有被利用到。主要是因為${\displaystyle {\frac {\sqrt {2}}{2}}(1-j)}$的乘法運算會讓整個FFT變得複雜，但是如果藉由近似的方法，我們便可以將此一運算化簡為12個加法。

${\displaystyle {\frac {\sqrt {2}}{2}}=0.70710678=2^{-1}+2^{-3}+2^{-4}+2^{-6}+2^{-8}+2^{-9}}$

## 一般性分解[2]

### ${\displaystyle N_{1}N_{2}}$非互質

${\displaystyle F[m]=\sum _{n=0}^{N-1}e^{-i{\frac {2\pi }{N}}mn}f[n]\qquad m,n=0,1,\ldots ,N-1}$

${\displaystyle n=n_{1}P_{1}+n_{2}\qquad m=m_{1}+m_{2}P_{2}}$
${\displaystyle n_{1},m_{1}=0,1,\ldots ,P_{2}-1\qquad n_{2},m_{2}=0,1,\ldots ,P_{1}-1}$

${\displaystyle F[m_{1}+m_{2}P_{2}]=\sum _{n_{1}=0}^{P_{2}-1}\sum _{n_{2}=0}^{P_{1}-1}e^{-i{\frac {2\pi }{P_{1}P_{2}}}(m_{1}+m_{2}P_{2})(n_{1}P_{1}+n_{2})}f[n_{1}P_{1}+n_{2}]}$

${\displaystyle F[m_{1}+m_{2}P_{2}]=\sum _{n_{1}=0}^{P_{2}-1}\sum _{n_{2}=0}^{P_{1}-1}f[n_{1}P_{1}+n_{2}]e^{-i{\frac {2\pi }{P_{2}}}m_{1}n_{1}}e^{-i{\frac {2\pi }{P_{1}}}m_{2}n_{2}}e^{-i{\frac {2\pi }{P_{1}P_{2}}}m_{1}n_{2}}e^{-i2\pi m_{2}n_{1}}}$

${\displaystyle F[m_{1}+m_{2}P_{2}]=\sum _{n_{2}=0}^{P_{1}-1}\sum _{n_{1}=0}^{P_{2}-1}f[n_{1}P_{1}+n_{2}]e^{-i{\frac {2\pi }{P_{2}}}m_{1}n_{1}}e^{-i{\frac {2\pi }{N}}m_{1}n_{2}}e^{-i{\frac {2\pi }{P_{1}}}m_{2}n_{2}}}$

${\displaystyle F[m_{1}+m_{2}P_{2}]=\sum _{n_{2}=0}^{P_{1}-1}\left\{\left\{\sum _{n_{1}=0}^{P_{2}-1}f[n_{1}P_{1}+n_{2}]e^{-i{\frac {2\pi }{P_{2}}}m_{1}n_{1}}\right\}e^{-i{\frac {2\pi }{N}}m_{1}n_{2}}\right\}e^{-i{\frac {2\pi }{P_{1}}}m_{2}n_{2}}}$

${\displaystyle F[m_{1}+m_{2}P_{2}]=\sum _{n_{2}=0}^{P_{1}-1}\left\{G_{1}[m_{1},n_{2}]e^{-i{\frac {2\pi }{N}}m_{1}n_{2}}\right\}e^{-i{\frac {2\pi }{P_{1}}}m_{2}n_{2}}}$

${\displaystyle F[m_{1}+m_{2}P_{2}]=\sum _{n_{2}=0}^{P_{1}-1}G_{2}[m_{1},n_{2}]e^{-i{\frac {2\pi }{P_{1}}}m_{2}n_{2}}}$

${\displaystyle F[m(=m_{1}+m_{2}P_{2})]=G_{3}[m_{1},m_{2}]}$

${\displaystyle P_{2}B_{1}+P_{1}B_{2}+3D_{3}+2D_{2}}$

### ${\displaystyle N_{1}N_{2}}$互質

${\displaystyle N_{1}N_{2}}$互質的情況下，仍是採取和上面相近的思路來將問題進行拆分，首先，為了避免之後的符號混淆，我們同樣將${\displaystyle N_{1}N_{2}}$置換為${\displaystyle P_{1}P_{2}}$

${\displaystyle F[m]=\sum _{n=0}^{N-1}e^{-i{\frac {2\pi }{N}}mn}f[n]\qquad m,n=0,1,\ldots ,N-1}$

${\displaystyle P_{1},P_{2}}$互質，對所有${\displaystyle n=0,1,\ldots ,N-1}$我們可以找到唯一且不重複的一組${\displaystyle n_{1},n_{2}}$使得：

${\displaystyle n=((n_{1}P_{1}+n_{2}P_{2}))_{N}=n_{1}P_{1}+n_{2}P_{2}+c_{1}N\qquad 0\leq n_{1}

${\displaystyle m=((m_{1}P_{1}+m_{2}P_{2}))_{N}=m_{1}P_{1}+m_{2}P_{2}+c_{2}N\qquad 0\leq m_{1}

${\displaystyle F[((m_{1}P_{1}+m_{2}P_{2}))_{N}]=\sum _{n_{1}=0}^{P_{2}-1}\sum _{n_{2}=0}^{P_{1}-1}e^{-i{\frac {2\pi }{N}}(m_{1}P_{1}+m_{2}P_{2}+c_{2}N)(n_{1}P_{1}+n_{2}P_{2}+c_{1}N)}f[((n_{1}P_{1}+n_{2}P_{2}))_{N}]}$

{\displaystyle {\begin{aligned}F[((m_{1}P_{1}+m_{2}P_{2}))_{N}]&=\sum _{n_{1}=0}^{P_{2}-1}\sum _{n_{2}=0}^{P_{1}-1}e^{-i{\frac {2\pi }{N}}(m_{1}P_{1}+m_{2}P_{2})(n_{1}P_{1}+n_{2}P_{2})}e^{-i2\pi c_{2}(n_{1}P_{1}+n_{2}P_{2}+c_{1}N)}e^{-i2\pi c_{1}(m_{1}P_{1}+m_{2}P_{2}+c_{2}N)}e^{-i2\pi c_{1}c_{2}N}f[((n_{1}P_{1}+n_{2}P_{2}))_{N}]\\&=\sum _{n_{1}=0}^{P_{2}-1}\sum _{n_{2}=0}^{P_{1}-1}e^{-i{\frac {2\pi }{N}}(m_{1}P_{1}+m_{2}P_{2})(n_{1}P_{1}+n_{2}P_{2})}f[((n_{1}P_{1}+n_{2}P_{2}))_{N}]\end{aligned}}}

{\displaystyle {\begin{aligned}F[((m_{1}P_{1}+m_{2}P_{2}))_{N}]&=\sum _{n_{1}=0}^{P_{2}-1}\sum _{n_{2}=0}^{P_{1}-1}f[((n_{1}P_{1}+n_{2}P_{2}))_{N}]e^{-i{\frac {2\pi }{P_{2}}}m_{1}P_{1}n_{1}}e^{-i{\frac {2\pi }{P_{1}}}m_{2}P_{2}n_{2}}e^{-i2\pi m_{1}n_{2}}e^{-i2\pi m_{2}n_{1}}\\&=\sum _{n_{1}=0}^{P_{2}-1}\sum _{n_{2}=0}^{P_{1}-1}f[((n_{1}P_{1}+n_{2}P_{2}))_{N}]e^{-i{\frac {2\pi }{P_{2}}}m_{1}P_{1}n_{1}}e^{-i{\frac {2\pi }{P_{1}}}m_{2}P_{2}n_{2}}\end{aligned}}}

${\displaystyle F[((m_{1}P_{1}+m_{2}P_{2}))_{N}]=\sum _{n_{2}=0}^{P_{1}-1}\left\{\sum _{n_{1}=0}^{P_{2}-1}f[((n_{1}P_{1}+n_{2}P_{2}))_{N}]e^{-i{\frac {2\pi }{P_{2}}}m_{1}P_{1}n_{1}}\right\}e^{-i{\frac {2\pi }{P_{1}}}m_{2}P_{2}n_{2}}}$

${\displaystyle F[((m_{1}P_{1}+m_{2}P_{2}))_{N}]=\sum _{n_{2}=0}^{P_{1}-1}G_{1}[m_{3},n_{2}]e^{-i{\frac {2\pi }{P_{1}}}m_{2}P_{2}n_{2}}}$

${\displaystyle F[m]=F[((m_{1}P_{1}+m_{2}P_{2}))_{N}]=G_{2}[m_{3},m_{4}]=G_{2}[((m_{1}P_{1}))_{P_{2}},((m_{2}P_{2}))_{P_{1}}]}$

${\displaystyle P_{2}B_{1}+P_{1}B_{2}+3D_{3}+2D_{2}}$

${\displaystyle ((n_{11}P_{1}+n_{21}P_{2}))_{N}=1}$

${\displaystyle ((kn_{11}P_{1}+kn_{21}P_{2}))_{N}=k=((kn_{11}P_{1}-c_{1}N+kn_{21}P_{2}-c_{2}N))_{N}=(((kn_{11}-c_{1}P_{2})P_{1}+(kn_{21}-c_{2}P_{1})P_{2}))_{N}}$

${\displaystyle n_{1k}=((kn_{11}))_{P_{2}}\qquad n_{2k}=((kn_{21}))_{P_{1}}}$

${\displaystyle ((n_{1k}P_{1}+n_{2k}P_{2}))_{N}=k\qquad 0\leq n_{1k}

## 參考資料

1. ^ 程佩青. 数字信号处理教程. 清华大学出版社. 2001. ISBN 9787900631671.
2. ^ Jian-Jiun Ding. advanced digital signal processing lecture note, P375-387. 高等數位訊號處理課程網頁. [2022-06-16]. （原始内容存档于2020-05-08）.
1. Widhe, T., J. Melander, et al. (1997). Design of efficient radix-8 butterfly PEs for VLSI. Circuits and Systems, 1997. ISCAS '97., Proceedings of 1997 IEEE International Symposium on.
2. Lihong, J., G. Yonghong, et al. (1998). A new VLSI-oriented FFT algorithm and implementation. ASIC Conference 1998. Proceedings. Eleventh Annual IEEE International.
3. Duhamel, P. and H. Hollmann (1984). "Split-radix FFT algorithm." Electronics Letters 20(1): 14-16.
4. Vetterli, M. and P. Duhamel (1989). "Split-radix algorithms for length-pm DFT's." Acoustics, Speech and Signal Processing, IEEE Transactions on 37(1): 57-64.
5. Richards, M. A. (1988). "On hardware implementation of the split-radix FFT." Acoustics, Speech and Signal Processing, IEEE Transactions on 36(10): 1575-1581.
6. Shousheng, H. and M. Torkelson (1996). A new approach to pipeline FFT processor. Parallel Processing Symposium, 1996., Proceedings of IPPS '96, The 10th International.
7. Shousheng, H. and M. Torkelson (1998). Designing pipeline FFT processor for OFDM (de)modulation. Signals, Systems, and Electronics, 1998. ISSSE 98. 1998 URSI International Symposium on.