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