雷德演算法

雷德演算法（）是一種於1968年由麻省理工學院林肯實驗室之查爾斯·M·雷德（Charles M. Rader）提出的快速傅立葉轉換演算法。當訊號的資料點數量為質數時，此演算法可藉由將離散傅立葉轉換重新表示為圓周摺積，快速計算出該訊號之離散傅立葉轉換結果。另一種稱為布魯斯坦演算法的作法也是透過類似的方式將離散傅立葉轉換改寫為摺積完成轉換，且同樣限制訊號長度需為質數。

由於雷德演算法之運作原理只依賴於具有週期性的離散傅立葉轉換核，故它也可直接套用於其它具有類似特性的轉換（惟訊號長度需為質數），例如數論轉換或離散哈特利轉換。

當所欲轉換的訊號資料皆為實數時，可透過重新索引或排列將原轉換拆成兩個長度為一半的實數循環摺積，如此稍微修改後的雷德演算法可進一步使運算時間減半；另一種快速計算實數訊號之離散傅立葉轉換的方法則是使用離散哈特利轉換。

進一步延伸了雷德演算法，使其也可用於長度為質數之次方數 p^m的訊號之離散傅立葉轉換；也因此，雷德演算法亦可被視為威諾格拉德快速傅立葉轉換演算法（亦稱為乘法性傅立葉轉換演算法）的特例之一，其中後者可用的訊號長度範圍較廣。然而，當訊號長度為合數（如質數之次方數）時，使用庫利－圖基快速傅立葉轉換演算法更加簡單且實作上也較容易，故雷德演算法一般只用於庫利－圖基演算法之遞迴拆解下較大質數之基本情況）——一個整數 g,使得對於任意的非零索引數 n \in \{1, 2, \cdots, N-1\},都存在唯一的 q \in \{0, 1, \cdots, N-2\}令 n=g^q\pmod N，即形成一q至非零n的對射；同樣地，對於任意的非零索引數 k \in \{1, 2, \cdots, N-1\},都存在唯一的 p \in \{0, 1, \cdots, N-2\}令 k=g^{-p}\pmod N，其中指數的負號代表的是 g^p之模反元素。這代表所求之離散傅立葉轉換可用新的索引數 p及 q改寫如下：

: X_0 = \sum_{n=0}^{N-1} x_n,

: X_{g^{-p}} = x_0 + \sum_{q=0}^{N-2} x_{g^q} e^{-\frac{2\pi i}{N} g^{-(p-q)} }
\qquad
p = 0,\dots,N-2

其中 x_n 和 X_k 皆對 N 隱含週期性，而 e^{2\pi i}=1 。因此，所有索引數以及指數皆可依群算術之要求取模 N 之結果。

上式中最後的加總即為長度 N-1 （ q=0,\ldots,N-2 ）之兩數列 a_q 和 b_q 的圓周摺積：

:a_q = x_{g^q}
:b_q = e^{-\frac{2\pi i}{N} g^{-q} }

摺積計算
由於N-1必為合數，上述之圓周摺積可直接由摺積定理以及其它常用之快速傅立葉轉換演算法求得。然而，若 N-1本身具有較大之質因數，則此作法須遞迴使用雷德演算法，而較不具效率。替代方法之一乃是將原長度為 N-1之數列補零至長度大於2(N-1)-1，甚或是2的次方數，便可透過快速演算法在O(N\log{N})的時間內求得而不須遞迴使用雷德演算法。

如此一來，此演算法則需要O(N)之加法運算以及O(N\log{N})之摺積運算。實作上，O(N)之加法常可被包含至後續的摺積運算中：若摺積是由一對快速傅立葉轉換求得，則 x_n的加總即是 x_0以及 a_q離散傅立葉轉換的第0項輸出（即DC項）之和。同時，可在逆轉換前先將 x_0加至摺積之DC項，這樣可使最後的輸出皆已包含x_0。不過，此演算所需的運算步驟仍然比其它接近之合數長度的快速傅立葉轉換來得多，實務上耗時是其 3 至 10 倍。

若雷德演算法未使用如上的補零法，而直接透過長度N-1之快速傅立葉轉換計算，則其效率將取決於N值以及雷德演算法本身遞迴呼叫的次數。最壞情況乃是當N-1=2N_2且N_2為質數，N_2-1=2N_3且N_3為質數，依此類推；在此情況下，若上述的質數鍊一直延伸至某界值，則遞迴雷德演算法之複雜度將為O(N^2)。諸如此類的N_j稱為索菲·熱爾曼質數，而它們所形成的質數數列則稱為第一類。然而，康寧漢鍊之長度增長的速度一般而言遠較\log_{2}{N}慢，故如此使用雷德演算法之複雜度應不為O(N^2)，但在最壞情況下複雜度仍應比O(N\log{N})高。不過，使用上述的補零法，便可達到 O(N\log{N})之複雜度。

參考資料