快速傅立葉變換

快速傅立葉變換（Fast Fourier Transform, FFT），是快速計算序列的離散傅立葉變換（DFT）或其逆變換的方法。傅立葉分析將信號從原始域（通常是時間或空間）轉換到頻域的表示或者逆過來轉換。FFT會通過把DFT矩陣分解為稀疏（大多為零）因子之積來快速計算此類變換。因此，它能夠將計算DFT的複雜度從只用DFT定義計算需要的 $O(n^2)$，降低到 $O(n \log n)$，其中 $n$ 為數據大小。

快速傅立葉變換廣泛的應用於工程、科學和數學領域。這裡的基本思想在1965年才得到普及，但早在1805年就已推導出來。1994年美國數學家吉爾伯特·斯特朗把FFT描述為「我們一生中最重要的數值演算法」，它還被IEEE科學與工程計算期刊列入20世紀十大演算法。

## 定義和速度

用FFT計算DFT會得到與直接用DFT定義計算相同的結果；最重要的區別是FFT更快。（由於捨入誤差的存在，許多FFT演算法還會比直接運用定義求值精確很多，後面會討論到這一點。）

令 $X_0, \cdots , X_{N-1}$ 為複數。DFT由下式定義

$$X_k = \sum_{n=0}^{N-1} x_n e^{-{i 2\pi k \frac{n}{N}}} \qquad k = 0,\dots,N-1.$$

直接按這個定義求值需要 $O(N^2)$ 次運算：$X^k$ 共有 $N$ 個輸出，每個輸出需要 $N$ 項求和。直接使用DFT運算需使用 $N$ 個複數乘法（$4N$ 個實數乘法）與 $N-1$ 個複數加法（$2N-2$ 個實數加法），因此，計算使用DFT所有 $N$ 點的值需要 $N^2$ 複數乘法與 $N^2-N$ 個複數加法。FFT則是能夠在 $O(N\log{}N)$ 次操作計算出相同結果的任何方法。更準確的說，所有已知的FFT演算法都需要 $O(N\log{}N)$ 次運算（技術上 $O$ 只標記上界），雖然還沒有已知的證據證明更低的複雜度是不可能的。

要說明FFT節省時間的方式，就得考慮複數相乘和相加的次數。直接計算DFT的值涉及到 $N^2$ 次複數相乘和 $N(N-1)$ 次複數相加（可以通過削去瑣碎運算（如乘以1）來節省 $O(N)$ 次運算）。眾所周知的基2庫利-圖基演算法，$N$ 為2的冪，可以只用 $(N/2)\log_{2} N$ 次複數乘法（再次忽略乘以1的簡化）和 $N\log_{2} N$ 次加法就可以得到相同結果。在實際中，現代電腦通常的實際性能通常不受算術運算的速度和對複雜主體的分析主導，但是從$O(N^2)$到$O(N\log{}N)$的總體改進仍然能夠體現出來。

## 一般的簡化理論

假設一個 $m\times n$ 型矩陣 $\mathbf{S}$ 可分解成列向量以及行向量相乘：

$$\mathbf{S}=\begin{bmatrix} a_1 \\ a_2 \\ \vdots \\ a_m\end{bmatrix}\begin{bmatrix} b_1 & b_2 & \cdots & b_n\end{bmatrix}$$

若 $\begin{bmatrix} a_1 & a_2 & \cdots & a_m\end{bmatrix}^T$ 有 $M_0$ 個相異的非平凡值（$a_m\ne\pm2^k,a_m\ne\pm2^ka_n$ 其中 $m\ne n$）

$\begin{bmatrix} b_1 & b_2 & \cdots & b_n\end{bmatrix}$ 有 $N_0$ 個相異的非平凡值

則 $\mathbf{S}$ 共需要 $M_0\times N_0$ 個乘法。

$$\begin{bmatrix} Z[1] \\ Z[2] \\ \vdots \\ Z[N] \end{bmatrix}= \mathbf{S}\begin{bmatrix} X[1] \\ X[2] \\ \vdots \\ X[N]\end{bmatrix}=\begin{bmatrix} a_1 \\ a_2 \\ \vdots \\ a_m\end{bmatrix}\begin{bmatrix} b_1 & b_2 & \cdots & b_n\end{bmatrix}\begin{bmatrix} X[1] \\ X[2] \\ \vdots \\ X[N]\end{bmatrix}$$

Step 1：$Z_a=b_1X[1]+b_2X[2]+\cdots+b_nX[N]$

Step 2：$Z[1]=a_1Z_a,Z[2]=a_2Z_a,\cdots,Z[N]=a_mZ_a$

簡化理論的變型：

$$\mathbf{S}=\begin{bmatrix} a_1 \\ a_2 \\ \vdots \\ a_m\end{bmatrix}\begin{bmatrix} b_1 & b_2 & \cdots & b_n\end{bmatrix}+\mathbf{S}_1$$

$\mathbf{S}_1$ 也是一個 $M\times N$ 的矩陣。

若 $\mathbf{S}_1$ 有 $P_1$ 個值不等於 $0$，則 $\mathbf{S}$ 的乘法量上限為 $M_0+N_0+P_1$。

## 快速傅立葉變換乘法量的計算

假設 $N= P_1 \times P_2 \times \cdots \times P_k$，其中 $P_1,P_2, \cdots , P_k$ 彼此互質。

$P_k$ 點DFT的乘法量為 $B_k$，則 $N$ 點DFT的乘法量為：

$$\frac{N}{P_1}B_1+\frac{N}{P_2}B_2+\cdots\cdots+\frac{N}{P_k}B_k$$

假設 $N=P^c$，$P$ 是一個質數。

若 $N_1=P^a$ 點的DFT需要的乘法量為 $B_1$

且 $n_1\times n_2$ 當中（$n_1=0,1,\cdots,N_1-1, \quad n_2=0,1, \cdots , N_2-1$）

有 $D_1$ 個值不為 $\frac{N}{12}$ 及 $\frac{N}{8}$ 的倍數。

有 $D_2$ 個值為 $\frac{N}{12}$ 及 $\frac{N}{8}$ 的倍數，但不為 $\frac{N}{4}$ 的倍數。

則 $N$ 點DFT的乘法量為：

$$N_2B_1+N_1B_2+3D_1+2D_2$$

## 庫利-圖基演算法

庫利-圖基演算法是最常見的FFT演算法。這一方法以分治法為策略遞歸地將長度為$N=N_1 N_2$的離散傅立葉變換分解為長度為$N_1$的$N_2$個較短序列的離散傅立葉變換，以及與$\Omicron (N)$個旋轉因子的複數乘法。

這種方法以及FFT的基本思路在1965年J. W. Cooley和J. W. Tukey合作發表An algorithm for the machine calculation of complex Fourier series之後開始為人所知。但後來發現，實際上這兩位作者只是重新發明了高斯在1805年就已經提出的演算法（此演算法在歷史上數次以各種形式被再次提出）。

庫利-圖基演算法最有名的應用，是將序列長為 $N$ 的DFT分割為兩個長為 $N/2$ 的子序列的DFT，因此這一應用只適用於序列長度為2的冪的DFT計算，即基2-FFT。實際上，如同高斯和Cooley與Tukey都指出的那樣，Cooley-Tukey演算法也可以用於序列長度 $N$ 為任意因數分解形式的DFT，即混合基FFT，而且還可以應用於其他諸如分裂基FFT等變種。儘管Cooley-Tukey演算法的基本思路是採用遞歸的方法進行計算，大多數傳統的演算法實現都將顯式的遞歸演算法改寫為非遞歸的形式。另外，因為Cooley-Tukey演算法是將DFT分解為較小長度的多個DFT，因此它可以同任一種其他的DFT演算法聯合使用。

### 設計思想

下面，我們用 $N$ 次單位根 $W_{N}$ 來表示 $e^{-j\frac{2\pi}{N}}$。

$W_{N}$ 的性質：

- 周期性，$W_{N}$具有周期$N$，即$W_{N}^{k+N}=W_{N}^{k}$
- 對稱性：$W_{N}^{k+N/2}=-W_{N}^{k}$。
- 若$m$是$N$的約數，$W_{N}^{mkn}=W_{N/m}^{kn}$

為了簡單起見，我們下面設待變換序列長度 $n=2^r$。根據上面單位根的對稱性，求級數 $y_k=\sum_{n=0}^{N-1} W_{N}^{kn}x_n$ 時，可以將求和區間分為兩部分：

$$\begin{matrix}y_k=\sum_{n=2t} W_{N}^{kn} x_n + \sum_{n=2t+1} W_{N}^{kn}x_n\\= \sum_{t} W_{\frac{N}{2}}^{kt}x_{2t} + W_{N}^{k}\sum_{t} W_{\frac{N}{2}}^{kt}x_{2t+1}\\= F_{even}(k) + W_{N}^{k}F_{odd}(k)&&&&&&(i\in\mathbb{Z})\end{matrix}$$

$F_{odd}(k)$ 和 $F_{even}(k)$ 是兩個分別關於序列 $\left\{x_n\right\}_0^{N-1}$ 奇數號和偶數號序列N/2點變換。由此式只需計算出 $y_k$ 的前 $N/2$ 個點，對於後N/2個點可以通過復指數函數的對稱性快速求解。即，注意 $F_{odd}(k)$ 和 $F_{even}(k)$ 都是周期為 $N/2$ 的函數，由單位根的對稱性，有以下變換公式：

- $$y_{k+\frac{N}{2}} = F_{even}(k) - W_{N}^{k}F_{odd}(k)$$
- $y_k = F_{even}(k) + W_{N}^{k}F_{odd}(k)$。

這樣，一個 $N$ 點變換就分解成了兩個 $N/2$ 點變換。照這樣可繼續分解下去。這就是庫利-圖基快速傅立葉變換演算法的基本原理。根據主定理不難分析出此時演算法的時間複雜度為$\Omicron (N\log N)$.

### 演算法實現

首先將$n=2^N$個輸入點列按二進位進行編號，然後對各個編號按位倒置並按此重新排序。例如，對於一個8點變換。

001倒置以後變成 100

000 → 000

001 → 100

010 → 010

011 → 110

100 → 001

101 → 101

110 → 011

111 → 111

倒置後的編號為{0,4,2,6,1,5,3,7}。

然後將這n個點列作為輸入傳送到蝶形結網路中，注意將因子 $W_{N}^{k}$ 逐層加入到蝶形網路中。

### 演算法複雜度

由於按蝶形結網路計算 $n$ 點變換要進行 $\log{} n$ 層計算，每層計算n個點的變換，故演算法的時間複雜度為$\Omicron (n \log n)$。

## 其他演算法

在Cooley-Tukey演算法之外還有其他DFT的快速演演算法。對於長度 $N = N_1N_2$ 且 $N_1$ 與 $N_2$ 互質的序列，可以採用基於中國剩餘定理的互質因子算法將N長序列的DFT分解為兩個子序列的DFT。與Cooley-Tukey演算法不同的是，互質因子算法不需要旋轉因子。

Rader-Brenner演算法是類似於Cooley-Tukey演算法，但是採用的旋轉因子都是純虛數，以增加加法運算和降低了數值穩定性為代價減少了乘法運算。這方法之後被split-radix variant of Cooley-Tukey所取代，與Rader-Brenner演演算法相比，有一樣多的乘法量，卻有較少的加法量，且不犧牲數值的準確性。

Bruun以及QFT演演算法是不斷的把DFT分成許多較小的DFT運算。（Rader-Brenner以及QFT演演算法是為了2的指數所設計的演演算法，但依然可以適用在可分解的整數上。Bruun演演算法則可以運用在可被分成偶數個運算的數字）。尤其是Bruun演演算法，把FFT看成是 $z^N-1$，並把它分解成 $z^{M-1}$與$z^{2M}+az^M+1$ 的形式。

另一個從多項式觀點的快速傅立葉變換法是Winograd演算法。此演演算法把 $z^N-1$ 分解成cyclotomic多項式，而這些多項式的係數通常為1，0，-1。這樣只需要很少的乘法量（如果有需要的話），所以winograd是可以得到最少乘法量的快速傅立葉演演算法，對於較小的數字，可以找出有效率的算方式。更精確地說，winograd演演算法讓DFT可以用 $2^k$ 點的DFT來簡化，但減少乘法量的同時，也增加了非常多的加法量。Winograd也可以利用剩餘值定理來簡化DFT。

Rader演演算法提出了利用點數為N（N為質數）的DFT進行長度為N-1的迴旋摺積來表示原本的DFT，如此就可利用摺積用一對基本的FFT來計算DFT。另一個prime-size的FFT演演算法為chirp-Z演演算法。此法也是將DFT用摺積來表示，此法與Rader演演算法相比，能運用在更一般的轉換上，其轉換的基礎為Z轉換（Rabiner et al., 1969）。

## 實數或對稱資料專用的演演算法

在許多的運用當中，要進行DFT的資料是純實數，如此一來經過DFT的結果會滿足對稱性：

$\mathbf{X}_{N-k}$=$\mathbf{X}_k^*$

而有一些演演算法是專門為這種情形設計的（e.g. Sorensen, 1987）。另一些則是利用舊有的演演算法（e.g. Cooley-Tukey），刪去一些不必要的演算步驟，如此省下了記憶體的使用，也省下了時間。另一方面，也可以把一個偶數長度且純實數的DFT，用長度為原本一半的複數型態DFT來表示（實數項為原本純實數資料的偶數項，虛數項則為奇數項）。

在Matlab上用一次N點FFT計算兩個N點實數信號x,y的FFT:

```matlab
function [X,Y] = Real2FFT( x,y )

% N-point FFT is used for 2 real signals both with length N

N = length(x);

z = x+y*i ;

Z = fft(z);

X = 0.5*(Z+conj(Z(1+mod(0:-1:1-N,N))));

Y = 0.5*(Z-conj(Z(1+mod(0:-1:1-N,N))))/i;

end
```

一度人們認為，用離散哈特利轉換（Discrete Hartley Transform）來處理純實數的DFT會更有效率，但接著人們發現，對於同樣點數的純實數DFT，經過設計的FFT，可以比DHT省下更多的運算。Bruun演演算法是第一個試著從減少實數輸入的DFT運算量的演演算法，但此法並沒有成為人們普遍使用的方法。

對於實數輸入，且輸入為偶對稱或奇對稱的情形，可以更進一步的省下時間以及記憶體，此時DFT可以用離散餘弦轉換或離散正弦轉換來代替（Discrete cosine/sine transforms）。由於DCT/DST也可以設計出FFT的演演算法，故在此種情形下，此方法取代了對DFT設計的FFT演演算法。

DFT可以應用在頻譜分析以及做摺積的運算，而在此處，不同應用可以用不同的演演算法來取代，列表如下：

用來做頻譜分析的情況下，DFT可用下列的演演算法代替：

- DCT
- DST
- DHT
- 正交基底的擴展（orthogonal basis expantion）包括正交多項式（orthogonal polynomials）以及CDMA.
- Walsh（Hadamard）轉換
- Haar轉換
- 小波（wavelet）轉換
- 時頻分布（time-frequency distribution）

用來做摺積的情況下，DFT可用下列的演演算法代替：

- DCT
- DST
- DHT
- 直接做摺積（direct computing）
- 分段式DFT摺積（sectioned DFT convolution）
- 威諾格拉德快速傅立葉變換演演算法
- 沃爾什（Walsh、Hadamard）轉換
- 數論轉換

## 單一路徑延遲迴授系統

單一路徑延遲迴授系統(英語：Single-path delay feedback，縮寫為SDF)是一種用於實現快速傅立葉轉換(Fast Fourier Transform)中運算的管線式架構(pipeline architecture)。此架構的特點是資料從輸入一直到最終的輸出只會通過單一的路徑，並使用蝶形結(butterfly diagram)做為資料的運算單元。經過蝶形結後的輸出資料會先暫存在系統的移位暫存器(shift registers)或是隨機存取記憶體(RAM)當中，而由於只有單一路徑的關係，對於每一級的蝶形結架構我們只需要一個複數乘法器來進行和FFT當中的旋轉因子(twiddle factor)的乘積運算。

SDF的優點在於其架構簡單並且利用硬體實現的成本較低，原因在於其單一路徑的設計，使得資料會依序進行處理並輸出，並不會在系統中加入多個複雜的運算單元以進行平行化的運算，事實上SDF的架構在管線式快速傅立葉轉換處理器(pipelined FFT processors)中具有最高的記憶體使用效率，而由於記憶體單元數量會隨快速傅立葉轉換的級數而指數增長，記憶體使用效率進而成為影響電路面積和功耗的主要因素之一。因此在實作大型快速傅立葉轉換處理器的情況下，SDF架構一直是被優先考量採用的選擇。然而其缺點也同樣來自於單一路徑的設計，導致其吞吐量(throughput)和多路徑延遲交換線路系統(英語：Multiple-path delay commutator，縮寫為MDC)相比較低。

接著我們將以8個點的基-2單一路徑延遲迴授系統(8-point R2SDF)為例進行其演演算法細節的介紹，並且展示在硬體實作中每一個cycle的運算和中間結果的存儲位置。

<image>

首先考慮系統輸入為x0, x1, ..., x7，並在前8個cycle依序輸入。

- Cycle 0~3: x0~x3依序存入第一級BF-2上方的暫存器中。
- Cycle 4: x0和x4輸入第一級BF-2後輸出x0'和x4'，x0'存入第二級BF-2上方的暫存器中，x4'存入第一級BF-2上方的暫存器中。
- Cycle 5: x1和x5輸入第一級BF-2後輸出x1'和x5'，x1'存入第二級BF-2上方的暫存器中，x5'存入第一級BF-2上方的暫存器中。
- Cycle 6: x2和x6輸入第一級BF-2後輸出x2'和x6'，x6'存入第一級BF-2上方的暫存器中，x0'和x2'輸入第二級BF-2後輸出x0`''`和x2`''`，x0`''`存入第三級BF-2上方的暫存器中，x2`''`存入第二級BF-2上方的暫存器中。
- Cycle 7: x3和x7輸入第一級BF-2後輸出x3'和x7'，x7'存入第一級BF-2上方的暫存器中，x1'和x3'輸入第二級BF-2後輸出x1`''`和x3`''`，x3`''`存入第二級BF-2上方的暫存器中，x0`''`和x1`''`輸入第三級BF-2後輸出x0`'''`和x1`'''`，x0`'''`直接輸出，x1`'''`存入第三級BF-2上方的暫存器中。(此為第一筆輸出，此後每一個cycle皆會輸出一筆資料。)
- Cycle 8: x4'乘上W0後存入第二級BF-2上方的暫存器中，x2`''`乘上W0後存入第三級BF-2上方的暫存器中，x1`'''`直接輸出。
- Cycle 9: x5'乘上W1後存入第二級BF-2上方的暫存器中，x3`''`乘上W2後和x2`''`輸入第三級BF-2後輸出x2`'''`和x3`'''`， x2`'''`直接輸出，x3`'''`存入第三級BF-2上方的暫存器中。
- Cycle 10: x6'乘上W2後和x4'輸入第二級BF-2後輸出x4`''`和x6`''`，x6`''`存入第二級BF-2上方的暫存器中，x4`''`存入第三級BF-2上方的暫存器中，x3`'''`直接輸出。
- Cycle 11: x7'乘上W3後和x5'輸入第二級BF-2後輸出x5`''`和x7`''`，x7`''`存入第二級BF-2上方的暫存器中，x4`''`和x5`''`輸入第三級BF-2後輸出x4`'''`和x5`'''`，x4`'''`直接輸出，x5`'''`存入第三級BF-2上方的暫存器中。
- Cycle 12: x6`''`乘上W0後存入第三級BF-2上方的暫存器中，x5`'''`直接輸出。
- Cycle 13: x7`''`乘上W2後和x6`''`輸入第三級BF-2後輸出x6`'''`和x7`'''`，x6`'''`直接輸出，x7`'''`存入第三級BF-2上方的暫存器中。
- Cycle 14: x7`'''`直接輸出。(此為最後一筆輸出。)

此外，我們可以在蝶形結中的加法器和乘法器加上額外的暫存器(register)來降低系統的關鍵路徑(critical path)，來避免某些時刻不同級之間的繁重運算必須擠在同一個cycle中運算完成，進而嚴重影響整體電路在timing上的表現。但如此的管線式設計(pipeline design)也會增加整體電路的延遲(latency)和暫存器使用量。

### 相似架構之硬體實作比較

- Radix-2 SDF: 2(log4N-1) 個乘法器、4log4N 個加法器、記憶體大小為 N-1。
- Radix-4 SDF: log4N-1 個乘法器、8log4N 個加法器、記憶體大小為 N-1。
- Radix-22 SDF: log4N-1 個乘法器、4log4N 個加法器、記憶體大小為 N-1。
- Radix-2 MDC: 2(log4N-1) 個乘法器、4log4N 個加法器、記憶體大小為 1.5N-2。
- Radix-4 MDC: 3(log4N-1) 個乘法器、8log4N 個加法器、記憶體大小為 2.5N-4。
- Radix-4 SDC: log4N-1 個乘法器、3log4N 個加法器、記憶體大小為 2N-2。

## 複雜度以及運算量的極限

長久以來，人們對於求出快速傅立葉變換的複雜度下限以及需要多少的運算量感到很有興趣，而實際上也還有許多問題需要解決。即使是用較簡單的情形，即 $2^k$ 點的DFT，也還沒能夠嚴謹的證明出FFT至少需要 $\Omega (N\log N)$ （不比 $N\log N$ 小）的運算量，目前也沒有發現複雜度更低的演演算法。通常數學運算量的多寡會是運算效率好壞最主要的因素，但在現實中，有許多因素也會有很大的影響，如快取記憶體以及CPU均有很大的影響。

在1978年，Winograd率先導出一個較嚴謹的FFT所需乘法量的下限： $\Theta (N)$。當 $N=2^k$ 時，DFT只需要 $4N-2\log_{2}^2N-2\log_{2}N-4$ 次無理實數的乘法即可以計算出來。更詳盡，且也能趨近此下限的演演算法也一一被提出（Heideman & Burrus, 1986; Duhamel, 1990）。很可惜的是，這些演演算法，都需要很大量的加法計算，目前的硬體無法克服這個問題。

對於所需加法量的數目，雖然我們可以在某些受限制的假設下，推得其下限，但目前並沒有一個精確的下限被推導出來。1973年，Morgenstern在乘法常數趨近巨大的情形下（對大部分的FFT演演算法為真，但不是全部）推導出加法量的下限： $\Omega \left(N \log N \right)$。Pan（1986）在假設FFT演演算法的不同步的情形有其極限下證明出加法量的下限 $\Omega (NlogN)$，但一般來說，此假設相當的不明確。長度為 $N=2^k$ 的情形下，在某些假設下，Papadimitriou（1979）提出使用Cooley-Tukey演演算法所需的複數加法量 $N\log_{2}N$ 是最少的。到目前為止，在長度為 $N=2^k$ 情況，還沒有任何FFT的演演算法可以讓複數的加法量 比$N\log_{2}N$ 還少。

還有一個問題是如何把乘法量與加法量的總和最小化，有時候稱作"演算複雜度"（在這裡考慮的是實際的運算量，而不是漸近複雜度）。同樣的，沒有一個嚴謹下限被證明出來。從1968年開始，$N=2^k$點DFT而言，split-radix FFT演演算法需要最少的運算量，在 $N>1$ 的情形下，其需要 $4N\log_{2}N-6N+8$ 個乘法運算以及加法運算。最近有人導出更低的運算量： $\frac{34}{9}N\log_{2}N$。（Johnson and Frigo, 2007; Lundy and Van Buskirk, 2007）

大多數嘗試要降低或者證明FFT複雜度下限的人都把焦點放在複數資料輸入的情況，因其為最簡單的情形。但是，複數資料輸入的FFT演演算法，與實數資料輸入的FFT演演算法，離散餘弦轉換（DCT），離散哈特列轉換（DHT），以及其他的演演算法，均有很大的關連性。故任何一個演演算法，在複雜度上有任何的改善的話，其他的演演算法複雜度也會馬上獲得改善（Duhamel & Vetterli, 1990）。

## 快速演演算法查表

對於 $N$ 點的DFT:

$N$ = 1~60

N｜乘法數｜加法數｜N｜乘法數｜N｜乘法數｜N｜乘法數

1｜0｜0｜11｜46｜24｜28｜39｜182

2｜0｜4｜12｜8｜25｜148｜40｜100

3｜2｜12｜13｜52｜26｜104｜42｜124

4｜0｜16｜14｜32｜27｜114｜44｜160

5｜10｜34｜15｜40｜28｜64｜45｜170

6｜4｜36｜16｜20｜30｜80｜48｜92

7｜16｜72｜18｜32｜32｜72｜52｜208

8｜4｜52｜20｜40｜33｜160｜54｜228

9｜16｜72｜21｜62｜35｜150｜56｜156

10｜20｜88｜22｜80｜36｜64｜60｜160

$N$ < 1000

N｜乘法數｜N｜乘法數｜N｜乘法數｜N｜乘法數

63｜256｜96｜280｜192｜752｜360｜1540

64｜204｜104｜468｜204｜976｜420｜2080

66｜284｜108｜456｜216｜1020｜480｜2360

70｜300｜112｜396｜224｜1016｜504｜2300

72｜164｜120｜380｜240｜940｜512｜3180

80｜260｜128｜560｜252｜1024｜560｜3100

81｜480｜144｜436｜256｜1308｜672｜3496

84｜248｜160｜680｜288｜1160｜720｜3620

88｜412｜168｜580｜312｜1324｜784｜4412

90｜340｜180｜680｜336｜1412｜840｜4580

$N$ > 1000

N｜乘法數｜N｜乘法數｜N｜乘法數｜N｜乘法數

1008｜5356｜1440｜8680｜2520｜16540｜4032｜29488

1024｜7436｜1680｜10420｜2688｜19108｜4096｜37516

1152｜7088｜2016｜12728｜2880｜20060｜4368｜35828

1260｜7640｜2048｜16836｜3369｜24200｜4608｜36812

1344｜8252｜2304｜15868｜3920｜29900｜5040｜36860

其他 $N$ 的演算法:

(1)若 $N$ 可被兩個以上互質的數相乘得到

設 $N = P_1\times P_2$，且 $P_1$ 與 $P_2$ 互質(無須 $P_1$ 與 $P_2$ 為質數):

則當輸入信號長度為N所需之的乘法器 $=P_1 \times B_2+P_2 \times B_1$。

其中 $B_1$ 為 $P_1$點DFT乘法量， $B_2$ 為 $P_2$ 點DFT乘法量。

例如: $N=65$ 可以拆成 $65=5\times 13$，其中5與13互質。

藉由查表可得知5點 DFT乘法量為10，13點DFT乘法量為52。

所以65點DFT乘法量為 $5\times52 + 13\times10 = 390$。

擴展:

設 $N = P_1\times P_2\times\cdot\cdot\cdot\times P_K$，且 $P_1\times P_2\times\cdot\cdot\cdot\times P_K$ 互質。

$P_k$ 點DFT乘法量為 $B_k$。

則 $N$ 點DFT可分解為 $N/P_1$ 個$P_1$-point DFT+$N/P_2$ 個 $P_2$-point DFT+$\cdot\cdot\cdot$+$N/P_K$ 個$P_K$-point DFT。

總乘法量為 $\frac{N}{P_1}B_1+\frac{N}{P_2}B_2+ \cdots +\frac{N}{P_K}B_K$

(2)若N不可被兩個互質的數相乘得到

設 $N = P_1\times P_2$，且 $P_1$ 與 $P_2$ 不互質:

且 $n \times m$ 當中( $n = 1,2,...,P_1-1$，$m = 1,2,...,P_2-1$ )。

有 $D_1$ 個值不為 $N/12$ 及 $N/8$ 的倍數。

有 $D_2$ 個值為 $N/12$ 或 $N/8$ 的倍數，但不為 $N/4$ 的倍數。

則 $N$ 點DFT所需之的乘法量 $=P_1 \times B_2+P_2 \times B_1+3D_1+2D_2$。

其中 $B_1$ 為 $P_1$ 點DFT乘法量， $B_2$ 為 $P_2$ 點DFT乘法量。

例如:16點DFT， $16=8 \times 2$

乘法量 $=2 \times 4 + 8 \times 0+3 \times 4+2 \times 2=24$

或 $16=4 \times 4$

乘法量 $=4 \times 0 + 4 \times 0 +3 \times 4+2 \times 4=20$

## FFT的應用

快速傅立葉變換可將卷積化乘法並以對數級數降低運算量，已成數位訊號與科學計算核心工具。

其應用涵蓋：

### 1.音訊與影像壓縮

MP3、AAC 與 JPEG 均把訊號分塊後先作 FFT／MDCT，以把時域樣本轉到頻域；高能量係數集中於低頻，小幅子載波便能重現重要訊息。接著結合人耳／視覺掩蔽模型及 Zig-zag 掃描，將低感知值係數量化為零，大幅降低位元率。最後用霍夫曼或算術編碼存儲係數與量化步階，達到有損壓縮與可調畫質／音質的目的。若不經 FFT，逐點卷積將耗費 O(N²) 運算，無法在即時裝置上完成。

### 2.無線通訊

現代蜂巢式網路與 Wi-Fi 系統皆採正交分頻多工 (OFDM)。基站先將並行調變符號經 IFFT 合成等間隔子載波；終端則以 FFT 還原頻域資料。此架構可在多徑通道中保持子載波互不干擾，同時透過可變子載波間距支撐 5G NR 的 eMBB 與 mMTC 場景。運用循環字首可把時域摺積化為頻域乘法，等效頻率選擇通道簡化為每載波一次複數乘法，計算量對比傳統單載波大幅減少。

### 3.頻譜分析與測試儀器

FFT 讓示波器、功率分析儀與機房電力品質監控能在毫秒級顯示功率頻譜。將長度 N 的窗函數樣本取 FFT 後，平方其複數幅度並適當標準化，即得單／雙邊功率譜密度 (PSD)。工程師可由此快速辨識諧波、雜訊底或機械轉速邊帶；科學領域亦用來分析地震波與星體光譜。無須昂貴的掃頻式分析器，即可精確估測頻率分量與相位。

### 4.圖像處理與快速卷積

空間濾波、去模糊及模板匹配常利用「乘頻域、回時域」策略：對影像與濾波器 PSF 取 FFT，相乘後作 IFFT，即得卷積結果，計算量 $O(N^2)$ 降為 $O(N\log{} N)$。在盲去模糊或維納解卷積中，亦可用頻域除法抑制模糊並保留高頻細節。此方法支援任意遮罩大小，遠優於滑動視窗直接卷積，適用醫學影像與天文攝影等高解析度場景。

### 5.雷達／聲納脈衝壓縮

雷達為兼顧高解析與大探測距離，常發射長碼調變脈衝並於接收端做匹配濾波。將回波與已知碼序列分別取 FFT，相乘後 IFFT，即可在頻域完成相關；此「脈衝壓縮」技術能在固定峰值功率下獲得窄等效脈衝寬，提升距離解析度與信雜比，並大幅降低即時硬體乘加數。

### 6.多項式乘法與同態加密

在多項式乘法或卷積為瓶頸的應用（例如格基同態加密、FFT-based 大數計算）中，先將係數以 NTT/FFT 轉到頻域，再做逐點乘法，最後逆變換還原，即可把 $O(N^2)$ 乘法降至 $O(N\log{} N)$。加密函式庫 SEAL、HElib 均內建此優化，使百萬階多項式運算在一般 CPU 上於毫秒內完成，直接左右現代隱私計算性能。

由此可見，FFT已由數學演演算法演變為支撐資訊社會不可或缺的基礎技術。

## 參閱

- 離散傅立葉變換
- 並行快速傅立葉變換
- 快速數論變換