クーリー–テューキー型FFTアルゴリズム
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/12/08 05:20 UTC 版)
「高速フーリエ変換」の記事における「クーリー–テューキー型FFTアルゴリズム」の解説
詳細は「クーリー–テューキー型FFTアルゴリズム(英語版)」を参照 クーリー–テューキー型アルゴリズムは、代表的な高速フーリエ変換 (FFT) アルゴリズムである。 分割統治法を使ったアルゴリズムで、N = N1 N2 のサイズの変換を、より小さいサイズである N1, N2 のサイズの変換に分割していくことで高速化を図っている。 最もよく知られたクーリー–テューキー型アルゴリズムは、ステップごとに変換のサイズをサイズ N/2 の2つの変換に分割するので、2 の累乗次数に限定される。しかし、一般的には次数は 2 の累乗にはならないので、素因数が偶数と奇数とで別々のアルゴリズムに分岐する。 伝統的なFFTの処理実装の多くは、再帰的な処理を、系統だった再帰をしないアルゴリズムにより実現している。 クーリー–テューキー型アルゴリズムは変換をより小さい変換に分解していくので、後述のような他の離散フーリエ係数のアルゴリズムと任意に組み合わせることができる。とりわけ、N ≤ 8 あたりまで分解すると、固定次数の高速なアルゴリズムに切り替えることが多い。
※この「クーリー–テューキー型FFTアルゴリズム」の解説は、「高速フーリエ変換」の解説の一部です。
「クーリー–テューキー型FFTアルゴリズム」を含む「高速フーリエ変換」の記事については、「高速フーリエ変換」の概要を参照ください。
- クーリー–テューキー型FFTアルゴリズムのページへのリンク