快速傅里叶变换

「FFT」重定向至此。关于其他用法，请见「FFT (消歧义)」。

快速傅里叶变换（英語：Fast Fourier Transform, FFT），是快速计算序列的离散傅里叶变换（DFT）或其逆变换的方法^[1]。傅里叶分析将信号从原始域（通常是时间或空间）转换到頻域的表示或者逆过来转换。FFT会通过把DFT矩阵分解为稀疏（大多为零）因子之积来快速计算此类变换。^[2]因此，它能够将计算DFT的复杂度从只用DFT定义计算需要的 ${\displaystyle O(n^{2})}$，降低到 ${\displaystyle O(n\log n)}$，其中 ${\displaystyle n}$ 为数据大小。

快速傅里叶变换广泛的应用于工程、科学和数学领域。这里的基本思想在1965年才得到普及，但早在1805年就已推导出来。^[3]1994年美國數學家吉爾伯特·斯特朗把FFT描述为“我们一生中最重要的数值算法”^[4]，它还被IEEE科学与工程计算期刊列入20世纪十大算法。^[5]

用FFT计算DFT会得到与直接用DFT定义计算相同的结果；最重要的区别是FFT更快。（由于捨入誤差的存在，许多FFT算法还会比直接运用定义求值精确很多，后面会讨论到这一点。）

令 x₀, ...., x_N-1 為复数。DFT由下式定义

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{i2\pi k{\frac {n}{N}}}}\qquad k=0,\dots ,N-1.}$

直接按这个定义求值需要${\displaystyle O(N^{2})}$次运算：X_k 共有 N 个输出，每个输出需要 N 项求和。直接使用DFT運算需使用N個複數乘法（4N個實數乘法）與N-1個複數加法（2N-2個實數加法），因此，計算使用DFT所有N點的值需要N²複數乘法與N²-N 個複數加法。FFT则是能够在${\displaystyle O(N\log {}N)}$次操作计算出相同结果的任何方法。更准确的说，所有已知的FFT算法都需要${\displaystyle O(N\log {}N)}$次运算（技术上O只标记上界），虽然还没有已知的证据证明更低的复杂度是不可能的。^[6]

要说明FFT节省时间的方式，就得考虑复数相乘和相加的次数。直接计算DFT的值涉及到 N² 次复数相乘和 N(N−1) 次复数相加（可以通过削去琐碎运算（如乘以1）来节省${\displaystyle O(N)}$次运算）。众所周知的基2库利-图基算法，N 为2的幂，可以只用 (N/2)log₂(N) 次复数乘法（再次忽略乘以1的简化）和 Nlog₂(N) 次加法就可以得到相同结果。在实际中，现代计算机通常的实际性能通常不受算术运算的速度和对复杂主体的分析主导^[7]，但是从${\displaystyle O(N^{2})}$到${\displaystyle O(N\log {}N)}$的总体改进仍然能够体现出来。

假設一個M*N型矩阵S可分解成列向量以及行向量相乘：

${\displaystyle \mathbf {S} ={\begin{bmatrix}a_{1}\\a_{2}\\\vdots \\a_{m}\end{bmatrix}}{\begin{bmatrix}b_{1}&b_{2}&\cdots &b_{n}\end{bmatrix}}}$

若${\displaystyle {\begin{bmatrix}a_{1}&a_{2}&\cdots &a_{m}\end{bmatrix}}^{T}}$有${\displaystyle M_{0}}$個相異的非平凡值（${\displaystyle a_{m}\neq \pm 2^{k},a_{m}\neq \pm 2^{k}a_{n}}$ where ${\displaystyle m\neq n}$）　

${\displaystyle {\begin{bmatrix}b_{1}&b_{2}&\cdots &b_{n}\end{bmatrix}}}$有${\displaystyle N_{0}}$個相異的非平凡值

則S共需要${\displaystyle M_{0}*N_{0}}$個乘法。

${\displaystyle {\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：${\displaystyle Z_{a}=b_{1}X[1]+b_{2}X[2]+\cdots +b_{n}X[N]}$

Step 2：${\displaystyle Z[1]=a_{1}Z_{a},Z[2]=a_{2}Z_{a},\cdots ,Z[N]=a_{m}Z_{a}}$

簡化理論的變型：

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

${\displaystyle S_{1}}$也是一個M*N的矩陣。

若${\displaystyle S_{1}}$有${\displaystyle P_{1}}$個值不等於0，則${\displaystyle \mathbf {S} }$的乘法量上限為${\displaystyle M_{0}+N_{0}+P_{1}}$。

假設${\displaystyle N=P_{1}\times P_{2}\times \cdots \times P_{k}}$，其中${\displaystyle P_{1},P_{2},\cdots ,P_{k}}$彼此互質

${\displaystyle \mathbf {P_{k}} }$點DFT的乘法量為${\displaystyle \mathbf {B_{k}} }$，則${\displaystyle \mathbf {N} }$點DFT的乘法量為：

${\displaystyle {\frac {N}{P_{1}}}B_{1}+{\frac {N}{P_{2}}}B_{2}+\cdots \cdots +{\frac {N}{P_{k}}}B_{k}}$

假設${\displaystyle \mathbf {N=P^{c}} }$，P是一個質數。

若${\displaystyle \mathbf {N_{1}=P^{a}} }$點的DFT需要的乘法量為${\displaystyle \mathbf {B_{1}} }$

且${\displaystyle n_{1}\times n_{2}}$當中（${\displaystyle n_{1}=0,1,\cdots ,N_{1}-1,\quad n_{2}=0,1,\cdots ,N_{2}-1}$）

有${\displaystyle D_{1}}$個值不為${\displaystyle {\frac {N}{12}}}$及${\displaystyle {\frac {N}{8}}}$的倍數，

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

則N點DFT的乘法量為：

${\displaystyle \mathbf {N_{2}B_{1}+N_{1}B_{2}+3D_{1}+2D_{2}} }$

库利-图基算法是最常见的FFT算法。这一方法以分治法为策略递归地将长度为${\displaystyle N=N_{1}N_{2}}$的离散傅里叶变换分解为长度为${\displaystyle N_{1}}$的${\displaystyle N_{2}}$个较短序列的离散傅里叶变换，以及与${\displaystyle \mathrm {O} (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次单位根${\displaystyle W_{N}}$来表示${\displaystyle e^{-j{\frac {2\pi }{N}}}}$。

${\displaystyle W_{N}}$的性质：

1. 周期性，${\displaystyle W_{N}}$具有周期${\displaystyle N}$，即${\displaystyle W_{N}^{k+N}=W_{N}^{k}}$
2. 对称性：${\displaystyle W_{N}^{k+{\frac {N}{2}}}=-W_{N}^{k}}$。
3. 若${\displaystyle m}$是${\displaystyle N}$的约数，${\displaystyle W_{N}^{mkn}=W_{\frac {N}{m}}^{kn}}$

为了简单起见，我们下面设待变换序列长度${\displaystyle n=2^{r}}$。根据上面单位根的对称性，求级数${\displaystyle y_{k}=\sum _{n=0}^{N-1}W_{N}^{kn}x_{n}}$时，可以将求和区间分为两部分：

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

${\displaystyle F_{odd}(k)}$和${\displaystyle F_{even}(k)}$是两个分别关于序列${\displaystyle \left\{x_{n}\right\}_{0}^{N-1}}$奇数号和偶数号序列N/2点变换。由此式只需计算出${\displaystyle y_{k}}$的前N/2个点，对于后N/2个点可以通过复指数函数的对称性快速求解。即，注意${\displaystyle F_{odd}(k)}$和${\displaystyle F_{even}(k)}$都是周期为N/2的函数，由单位根的对称性，有以下变换公式：

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

这样，一个N点变换就分解成了两个N/2点变换。照这样可继续分解下去。这就是库利-图基快速傅里叶变换算法的基本原理。根据主定理不难分析出此时算法的时间复杂度为${\displaystyle \mathrm {O} (N\log N)}$

• 蝶形结网络和位反转（Bit Reversal）：

首先将${\displaystyle 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个点列作为输入传送到蝶形结网络中，注意将因子${\displaystyle W_{N}^{k}}$逐层加入到蝶形网络中。

由于按蝶形结网络计算n点变换要进行log n层计算，每层计算n个点的变换，故算法的时间复杂度为${\displaystyle \mathrm {O} (n\log n)}$。

在Cooley-Tukey算法之外还有其他DFT的快速演算法。对于长度${\displaystyle N=N_{1}N_{2}}$且${\displaystyle N_{1}}$与${\displaystyle 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看成是${\displaystyle z^{N}-1}$，并把它分解成${\displaystyle z^{M-1}}$与${\displaystyle z^{2M}+az^{M}+1}$的形式。

另一个从多项式观点的快速傅立叶变换法是Winograd算法。此演算法把${\displaystyle z^{N}-1}$分解成cyclotomic多项式，而这些多项式的系数通常为1，0，-1。这样只需要很少的乘法量（如果有需要的话），所以winograd是可以得到最少乘法量的快速傅立叶演算法，对于较小的数字，可以找出有效率的算方式。更精确地说，winograd演算法让DFT可以用${\displaystyle 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的结果会满足对称性：

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

而有一些演算法是专门为这种情形设计的（e.g. Sorensen, 1987）。另一些则是利用旧有的演算法（e.g. Cooley-Tukey），删去一些不必要的演算步骤，如此省下了记忆体的使用，也省下了时间。另一方面，也可以把一个偶数长度且纯实数的DFT，用长度为原本一半的复数型态DFT来表示（实数项为原本纯实数资料的偶数项，虚数项则为奇数项）。

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

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)的乘積運算。^[8]

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

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

首先考慮系統輸入為x₀, x₁, ..., x_7，並在前8個cycle依序輸入。

• Cycle 0~3: x₀~x₃依序存入第一級BF-2上方的暫存器中。
• Cycle 4: x₀和x₄輸入第一級BF-2後輸出x₀^'和x₄^'，x₀^'存入第二級BF-2上方的暫存器中，x₄^'存入第一級BF-2上方的暫存器中。
• Cycle 5: x₁和x₅輸入第一級BF-2後輸出x₁^'和x₅^'，x₁^'存入第二級BF-2上方的暫存器中，x₅^'存入第一級BF-2上方的暫存器中。
• Cycle 6: x₂和x₆輸入第一級BF-2後輸出x₂^'和x₆^'，x₆^'存入第一級BF-2上方的暫存器中，x₀^'和x₂^'輸入第二級BF-2後輸出x₀^''和x₂^''，x₀^''存入第三級BF-2上方的暫存器中，x₂^''存入第二級BF-2上方的暫存器中。
• Cycle 7: x₃和x₇輸入第一級BF-2後輸出x₃^'和x₇^'，x₇^'存入第一級BF-2上方的暫存器中，x₁^'和x₃^'輸入第二級BF-2後輸出x₁^''和x₃^''，x₃^''存入第二級BF-2上方的暫存器中，x₀^''和x₁^''輸入第三級BF-2後輸出x₀^'''和x₁^'''，x₀^'''直接輸出，x₁^'''存入第三級BF-2上方的暫存器中。(此為第一筆輸出，此後每一個cycle皆會輸出一筆資料。)
• Cycle 8: x₄^'乘上W⁰後存入第二級BF-2上方的暫存器中，x₂^''乘上W⁰後存入第三級BF-2上方的暫存器中，x₁^'''直接輸出。
• Cycle 9: x₅^'乘上W¹後存入第二級BF-2上方的暫存器中，x₃^''乘上W²後和x₂^''輸入第三級BF-2後輸出x₂^'''和x₃^'''， x₂^'''直接輸出，x₃^'''存入第三級BF-2上方的暫存器中。
• Cycle 10: x₆^'乘上W²後和x₄^'輸入第二級BF-2後輸出x₄^''和x₆^''，x₆^''存入第二級BF-2上方的暫存器中，x₄^''存入第三級BF-2上方的暫存器中，x₃^'''直接輸出。
• Cycle 11: x₇^'乘上W³後和x₅^'輸入第二級BF-2後輸出x₅^''和x₇^''，x₇^''存入第二級BF-2上方的暫存器中，x₄^''和x₅^''輸入第三級BF-2後輸出x₄^'''和x₅^'''，x₄^'''直接輸出，x₅^'''存入第三級BF-2上方的暫存器中。
• Cycle 12: x₆^''乘上W⁰後存入第三級BF-2上方的暫存器中，x₅^'''直接輸出。
• Cycle 13: x₇^''乘上W²後和x₆^''輸入第三級BF-2後輸出x₆^'''和x₇^'''，x₆^'''直接輸出，x₇^'''存入第三級BF-2上方的暫存器中。
• Cycle 14: x₇^'''直接輸出。(此為最後一筆輸出。)

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

1. Radix-2 SDF: 2(log₄N-1) 個乘法器、4log₄N 個加法器、記憶體大小為 N-1。
2. Radix-4 SDF: log₄N-1 個乘法器、8log₄N 個加法器、記憶體大小為 N-1。
3. Radix-2² SDF: log₄N-1 個乘法器、4log₄N 個加法器、記憶體大小為 N-1。
4. Radix-2 MDC: 2(log₄N-1) 個乘法器、4log₄N 個加法器、記憶體大小為 1.5N-2。
5. Radix-4 MDC: 3(log₄N-1) 個乘法器、8log₄N 個加法器、記憶體大小為 2.5N-4。
6. Radix-4 SDC: log₄N-1 個乘法器、3log₄N 個加法器、記憶體大小為 2N-2。

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

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

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

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

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

For a N-point DFT:

N = 1~60

N < 1000

N > 1000

其他N的算法:

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

設${\displaystyle N=P_{1}\times P_{2}}$，且${\displaystyle P_{1}}$與${\displaystyle P_{2}}$互質(無須${\displaystyle P_{1}}$與${\displaystyle P_{2}}$為質數):

則當輸入信號長度為N所需之的乘法器=${\displaystyle P_{1}\times B_{2}+P_{2}\times B_{1}}$

其中${\displaystyle B_{1}}$為${\displaystyle P_{1}}$-point DFT乘法量，${\displaystyle B_{2}}$為${\displaystyle P_{2}}$-point DFT乘法量。

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

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

所以13-points DFT乘法量為 ${\displaystyle 5\times 52+13\times 10=390}$。

擴展:

設${\displaystyle N=P_{1}\times P_{2}\times \cdot \cdot \cdot \times P_{K}}$，且${\displaystyle P_{1}\times P_{2}\times \cdot \cdot \cdot \times P_{K}}$互質，

${\displaystyle P_{k}}$-point DFT乘法量為${\displaystyle B_{k}}$，

則N-point DFT可分解為${\displaystyle N/P_{1}}$個${\displaystyle P_{1}}$-point DFT+${\displaystyle N/P_{2}}$個${\displaystyle P_{2}}$-point DFT+${\displaystyle \cdot \cdot \cdot }$+${\displaystyle N/P_{K}}$個${\displaystyle P_{K}}$-point DFT，

總乘法量為${\displaystyle {\frac {N}{P_{1}}}B_{1}+{\frac {N}{P_{2}}}B_{2}+...+{\frac {N}{P_{K}}}B_{K}}$

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

設${\displaystyle N=P_{1}\times P_{2}}$，且${\displaystyle P_{1}}$與${\displaystyle P_{2}}$不互質:

且${\displaystyle n\times m}$當中(${\displaystyle n=1,2,...,P_{1}-1}$，${\displaystyle m=1,2,...,P_{2}-1}$)，

有${\displaystyle D_{1}}$個值不為${\displaystyle N/12}$及${\displaystyle N/8}$的倍數，

有${\displaystyle D_{2}}$個值為${\displaystyle N/12}$或${\displaystyle N/8}$的倍數，但不為${\displaystyle N/4}$的倍數。

則N-point DFT所需之的乘法量=${\displaystyle P_{1}\times B_{2}+P_{2}\times B_{1}+3D_{1}+2D_{2}}$

其中${\displaystyle B_{1}}$為${\displaystyle P_{1}}$-point DFT乘法量，${\displaystyle B_{2}}$為${\displaystyle P_{2}}$-point DFT乘法量。

例如:16-point DFT，${\displaystyle 16=8\times 2}$

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

or ${\displaystyle 16=4\times 4}$

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

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

其應用涵蓋：

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

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

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

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

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

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

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

• 离散傅里叶变换
• 并行快速傅里叶变换
• 快速數論變換