雷德演算法
維基百科,自由的 encyclopedia
雷德演算法(英語:Rader's algorithm)是一種於1968年由麻省理工學院林肯實驗室之查爾斯·M·雷德(Charles M. Rader)提出的快速傅立葉轉換演算法[1]。當訊號的資料點數量為質數時,此演算法可藉由將離散傅立葉轉換重新表示為圓周摺積,快速計算出該訊號之離散傅立葉轉換結果。另一種稱為布魯斯坦演算法的作法也是透過類似的方式將離散傅立葉轉換改寫為摺積完成轉換,且同樣限制訊號長度需為質數。
由於雷德演算法之運作原理只依賴於具有週期性的離散傅立葉轉換核,故它也可直接套用於其它具有類似特性的轉換(惟訊號長度需為質數),例如數論轉換或離散哈特利轉換。
當所欲轉換的訊號資料皆為實數時,可透過重新索引或排列將原轉換拆成兩個長度為一半的實數循環摺積,如此稍微修改後的雷德演算法可進一步使運算時間減半[2];另一種快速計算實數訊號之離散傅立葉轉換的方法則是使用離散哈特利轉換[3]。
薩繆爾·威諾格拉德(英语:Shmuel Winograd)進一步延伸了雷德演算法,使其也可用於長度為質數之次方數 的訊號之離散傅立葉轉換[4][5];也因此,雷德演算法亦可被視為威諾格拉德快速傅立葉轉換演算法(亦稱為乘法性傅立葉轉換演算法[6])的特例之一,其中後者可用的訊號長度範圍較廣。然而,當訊號長度為合數(如質數之次方數)時,使用庫利-圖基快速傅立葉轉換演算法更加簡單且實作上也較容易,故雷德演算法一般只用於庫利-圖基演算法之遞迴拆解下較大質數之基本情況[3]。