クーリー・テューキーFFTアルゴリズム

Cooley –Tukey アルゴリズムは、JW CooleyとJohn Tukeyにちなんで名付けられた、最も一般的な高速フーリエ変換(FFT) アルゴリズムです。任意の合成サイズの離散フーリエ変換(DFT) を、サイズN _2のN _{1 個}のより小さな DFT で再帰的に表現し直し、高度に合成されたN (滑らかな数) に対して計算時間を O( N log N ) に短縮します。このアルゴリズムの重要性から、特定のバリアントと実装スタイルは、以下で説明するように独自の名前で知られるようになりました。 ${\displaystyle N=N_{1}N_{2}}$

Cooley-Tukey アルゴリズムは DFT をより小さな DFT に分割するため、DFT の他のアルゴリズムと任意に組み合わせることができます。たとえば、RaderまたはBluestein のアルゴリズムを使用して、Cooley-Tukey では分解できない大きな素因数を処理したり、素因数アルゴリズムを使用して、互いに素な因数を分離する際の効率を高めたりすることができます。

このアルゴリズムとその再帰的応用は、カール・フリードリヒ・ガウスによって発明されました。160年後、クーリーとテューキーが独立してこれを再発見し、普及させました。

このアルゴリズムは、その再帰的応用も含めて、1805年頃にカール・フリードリヒ・ガウスによって発明され、彼はこのアルゴリズムを使って小惑星 パラスとジュノの軌道を補間したが、彼の研究は広く認知されることはなかった（彼の死後に新ラテン語で出版されただけである）。^{[1] [2]}しかし、ガウスは漸近的な計算時間については分析しなかった。19世紀から20世紀初頭にかけて、さまざまな限定形式も何度か再発見された。^[2] FFTは、IBMのジェームズ・クーリーとプリンストンのジョン・テューキーが1965年にこのアルゴリズムを再発明し、それをコンピュータ上で便利に実行する方法を説明した論文を発表して以来、人気^{を博した。 [3]}

伝えられるところによると、テューキーはケネディ大統領の科学諮問委員会の会議中にこのアイデアを思いついた。この会議では、国外に設置した地震計を使ってソ連での核兵器実験を検知する方法について議論していた。これらのセンサーは地震の時系列を生成する。しかし、このデータの分析には、センサーの数と時間の長さのため、DFTを計算するための高速アルゴリズムが必要になる。この作業は、ソ連の施設を訪問することなく違反を検知できるように、提案された核実験禁止の批准にとって非常に重要だった。^{[4] [5]} その会議のもう一人の参加者であるIBMのリチャード・ガーウィンは、この方法の可能性を認識し、テューキーをクーリーに紹介した。しかし、ガーウィンはクーリーが本来の目的を知らないようにした。その代わりに、クーリーには、これはヘリウム3の3次元結晶におけるスピン配向の周期性を決定するために必要であると伝えられた。その後、Cooley 氏と Tukey 氏は共同論文を発表し、最大 300 kHz のレートでサンプリングできる アナログ - デジタル コンバーターが同時に開発されたため、急速に広く採用されるようになりました。

ガウスが同じアルゴリズムを（漸近的コストを解析せずに）記述していたという事実は、クーリーとテューキーの1965年の論文の数年後まで認識されませんでした。^[2]彼らの論文では、現在素因数FFTアルゴリズム（PFA）と呼ばれているIJグッド の研究のみをインスピレーションとして引用していました。 ^[3]グッドのアルゴリズムは当初、クーリー–テューキーアルゴリズムと同等であると考えられていましたが、PFAはまったく異なるアルゴリズムであることがすぐに認識されました（クーリー–テューキーが任意の合成サイズをサポートしているのとは異なり、互いに素因数を持つサイズに対してのみ機能し、中国剰余定理に依存しています）。^[6]

基数2 の時間的デシメーション ( DIT ) FFT は、Cooley–Tukey アルゴリズムの最も単純で一般的な形式ですが、高度に最適化された Cooley–Tukey 実装では通常、以下に説明する他の形式のアルゴリズムが使用されます。基数 2 DIT は、サイズNの DFT を、各再帰ステージでサイズN /2の 2 つのインターリーブされた DFT (「基数 2」という名前が付けられている) に分割します。

離散フーリエ変換 (DFT) は次の式で定義されます。

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk},}$

ここで は0 から までの整数です。 ${\displaystyle k}$${\displaystyle N-1}$

Radix-2 DIT は、最初に偶数インデックスの入力 と奇数インデックスの入力のDFT を計算し、次にこれら 2 つの結果を組み合わせてシーケンス全体の DFT を生成します。この考え方は、再帰的に実行することで、全体の実行時間を O( N log N ) に短縮できます。この簡略化された形式では、 N が2 の累乗であると想定しています。サンプル ポイントの数Nは通常、アプリケーションによって自由に選択できるため (サンプル レートやウィンドウの変更、ゼロ パディングなど)、これは多くの場合、重要な制限ではありません。 ${\displaystyle (x_{2m}=x_{0},x_{2},\ldots ,x_{N-2})}$${\displaystyle (x_{2m+1}=x_{1},x_{3},\ldots ,x_{N-1})}$

基数2のDITアルゴリズムは、関数のDFTを偶数インデックスの合計と奇数インデックスの合計の 2つの部分に再配置します。${\displaystyle x_{n}}$${\displaystyle n={2m}}$${\displaystyle n={2m+1}}$

${\displaystyle {\begin{matrix}X_{k}&=&\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac {2\pi i}{N}}(2m)k}+\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N}}(2m+1)k}\end{matrix}}}$

下の式に示すように、2 番目の合計から共通の乗数を因数分解することができます。すると、2 つの合計が関数の偶数インデックス部分の DFTと奇数インデックス部分の DFTであることがわかります。E の偶数インデックス入力の DFTを で表し、O の奇数インデックス入力の DFTを で表すと、次の式が得られます。 ${\displaystyle e^{-{\frac {2\pi i}{N}}k}}$${\displaystyle x_{2m}}$${\displaystyle x_{2m+1}}$${\displaystyle x_{n}}$${\displaystyle x_{2m}}$${\displaystyle E_{k}}$${\displaystyle x_{2m+1}}$${\displaystyle O_{k}}$

${\displaystyle {\begin{matrix}X_{k}=\underbrace {\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac {2\pi i}{N/2}}mk}} _{\mathrm {DFT\;of\;even-indexed\;part\;of\;} x_{n}}{}+e^{-{\frac {2\pi i}{N}}k}\underbrace {\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N/2}}mk}} _{\mathrm {DFT\;of\;odd-indexed\;part\;of\;} x_{n}}=E_{k}+e^{-{\frac {2\pi i}{N}}k}O_{k}\qquad {\text{ }}k=0,\dots ,{\frac {N}{2}}-1.\end{matrix}}} の場合$

等式は に対して成り立つことに注意してください。しかし、肝心なのは、と が に対してのみこのように計算されるということです。複素指数 の周期性により、はおよびからも得られます。 ${\displaystyle k=0,\dots ,N-1}$${\displaystyle E_{k}}$${\displaystyle O_{k}}$${\displaystyle k=0,\dots ,{\frac {N}{2}}-1}$${\displaystyle X_{k+{\frac {N}{2}}}}$${\displaystyle E_{k}}$${\displaystyle O_{k}}$

${\displaystyle {\begin{aligned}X_{k+{\frac {N}{2}}}&=\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac {2\pi i}{N/2}}m(k+{\frac {N}{2}})}+e^{-{\frac {2\pi i}{N}}(k+{\frac {N}{2}})}\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N/2}}m(k+{\frac {N}{2}})}\\&=\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac {2\pi i}{N/2}}mk}e^{-2\pi mi}+e^{-{\frac {2\pi i}{N}}k}e^{-\pi i}\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N/2}}mk}e^{-2\pi mi}\\&=\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac {2\pi i}{N/2}}mk}-e^{-{\frac {2\pi i}{N}}k}\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N/2}}mk}\\&=E_{k}-e^{-{\frac {2\pi i}{N}}k}O_{k}\end{aligned}}}$

と を次のように書き直すことができます。 ${\displaystyle X_{k}}$${\displaystyle X_{k+{\frac {N}{2}}}}$

${\displaystyle {\begin{matrix}X_{k}&=&E_{k}+e^{-{\frac {2\pi i}{N}}{k}}O_{k}\\X_{k+ {\frac {N}{2}}}&=&E_{k}-e^{-{\frac {2\pi i}{N}}{k}}O_{k}\end{行列}}}$

この結果は、長さNの DFT をサイズN /2の 2 つの DFT で再帰的に表現したもので、基数 2 DIT 高速フーリエ変換の核心です。このアルゴリズムは、中間計算の結果を再利用して複数の DFT 出力を計算することで速度を上げています。最終出力は、との +/− の組み合わせによって得られることに注意してください。これは、単にサイズ 2 の DFT (この文脈ではバタフライと呼ばれることもあります) です。これを以下のようにより大きな基数に一般化すると、サイズ 2 の DFT はより大きな DFT (それ自体は FFT で評価できます) に置き換えられます。 ${\displaystyle E_{k}}$${\displaystyle O_{k}\exp(-2\pi ik/N)}$

このプロセスは、分割統治アルゴリズムの一般的な手法の例です。ただし、従来の多くの実装では、明示的な再帰は回避され、代わりに幅優先方式で計算ツリーをトラバースします。

上記のサイズN のDFT を 2 つのサイズN /2 の DFT として再表現したものは、ダニエルソン–ランチョスの 補題と呼ばれることがあります。これは、この恒等式が 1942 年にこの 2 人の著者によって指摘されたためです^[7] (ルンゲの1903 年の研究^[2]の影響を受けた)。彼らは補題を「後方」再帰的に適用し、変換スペクトルが収束するまで DFT サイズを繰り返し2 倍にしました(ただし、彼らは達成した線形[つまり、順序N  log  N ] の漸近的複雑性を認識していなかったようです)。ダニエルソン – ランチョスの作業は、機械式または電子式のコンピュータが広く普及する前のものであり、手計算(おそらく加算機などの機械的な補助を使用) が必要でした。彼らは、3 ～ 5 桁の有効桁の実数入力で動作するサイズ 64 の DFT の計算時間が 140 分であると報告しました。 Cooley と Tukey の 1965 年の論文では、 IBM 7094 (おそらく 36 ビット単精度、約 8 桁)でサイズ 2048 の複素 DFT を実行するのに 0.02 分かかると報告されています。 ^[3] 時間を演算回数で再スケーリングすると、これは約 800,000 倍の高速化係数に相当します。(手計算にかかる時間を理解するために、サイズ 64 で 140 分は、浮動小数点演算あたり平均最大 16 秒に相当し、そのうち約 20% が乗算です。)

擬似コードでは、以下の手順を書くことができる: ^[8]

X 0,..., N −1 ← ditfft2 ( x , N , s ):              (x 0 , x s , x 2 s , ..., x ( N -1) s ) の DFT :
     N = 1の場合 、X 0 ← x 0単純なサイズ 1 DFT 基本ケース、それ以外の場合、X 0,..., N /2−1 ← ditfft2 ( x , N /2, 2 s )              (x 0 , x 2 s , x 4 s , ..., x ( N -2) s )
        の DFT X N /2,..., N −1 ← ditfft2 ( x +s, N /2, 2 s )            k = 0 からN /2−1の場合、(x s , x s +2 s , x s +4 s , ..., x ( N -1) s )
        のDFT 2 つの半分の DFT を完全な DFT に結合します。DFT: 
            p ← X k 
            q ← exp(−2π i / N k ) X k + N /2 X k ← p + q 
             X k + N /2 ← p − q
        終了終了 if
                                              
    
                                  
            
    

ここで、ditfft2( x , N ,1) は、基数 2 DIT FFT によってX =DFT( x )をアウトオブプレースで計算します。ここで、 N は2 の整数乗であり、s =1 は入力x配列のストライドです。 x + s は、x _sで始まる配列を表します。

(結果はX内で正しい順序になっており、それ以上のビット反転の置換は必要ありません。よく言われる別のビット反転ステージの必要性は、以下で説明するように、特定のインプレース アルゴリズムでのみ発生します。)

高性能 FFT 実装では、この単純な疑似コードと比較して、このようなアルゴリズムの実装に多くの変更が加えられています。たとえば、再帰のオーバーヘッドを償却するためにN =1 よりも大きな基本ケースを使用したり、回転因子を 事前に計算したり、キャッシュ上の理由から大きな基数を使用したりすることができます。これらの最適化とその他の最適化を組み合わせることで、パフォーマンスを 1 桁以上向上させることができます。^[8] (多くの教科書的な実装では、深さ優先再帰は非再帰的な幅優先アプローチに置き換えられていますが、深さ優先再帰の方がメモリの局所性が優れていると主張されています。^{[8] [9]} ) これらのアイデアのいくつかについては、以下でさらに詳しく説明します。 ${\displaystyle \exp[-2\pi ik/N]}$

より一般的には、クーリー・テューキーアルゴリズムは、複合サイズN = N ₁ N ₂のDFTを再帰的に次のように再表現する：^[10]

1. サイズN _2のN ₁ DFTを実行します。
2. 複素数根（回転因子と呼ばれることが多い）を掛けます。
3. _サイズN1のN2DFTを_実行します。

通常、N ₁またはN _2は、基数と呼ばれる小さな因数（必ずしも素数ではない）です（再帰のステージ間で異なる場合があります）。N ₁が基数の場合、それは時間的デシメーション（DIT）アルゴリズムと呼ばれ、 N ₂が基数の場合、それは周波数的デシメーション（DIF、Sande–Tukey アルゴリズムとも呼ばれます）と呼ばれます。上記で示したバージョンは基数 2 DIT アルゴリズムでした。最終式では、奇数変換を乗算する位相が回転因子であり、偶数変換と奇数変換の +/- 組み合わせ（バタフライ）はサイズ 2 DFT です。（基数の小さな DFT はバタフライと呼ばれることもあります。これは、基数 2 の場合の データフロー図の形状にちなんで名付けられています。）

Cooley–Tukey アルゴリズムには、他にも多くのバリエーションがあります。 混合基数実装は、2 に加えてさまざまな (通常は小さな) 因数を持つ合成サイズを処理し、通常は (常にではありませんが) 再帰の素数ベースのケースに O(N2) アルゴリズムを使用します⁽ RaderやBluesteinのアルゴリズム など、素数ベースのケースにN  log  Nアルゴリズムを使用することもできます)。分割基数は、基数 2 と 4 を結合し、基数 2 の最初の変換には回転因子が必要ないという事実を利用して、2 の累乗のサイズに対して長い間知られている中で最も少ない算術演算回数を達成しましたが、^[10]最近のバリエーションではさらに少ない回数が達成されています。^{[11] [12]} （今日のコンピュータでは、パフォーマンスは厳密な演算数よりもキャッシュとCPUパイプラインの考慮によって決まります。最適化されたFFT実装では、より大きな基数や、かなりのサイズのハードコードされた基本ケース変換が使用されることが多いです。^[13]）。

Cooley–Tukey アルゴリズムの別の見方は、サイズN の1 次元 DFT をN ₁ x N ₂の2 次元 DFT (および回転子) として再表現し、出力行列が転置されるというものです。基数 2 アルゴリズムの場合、これらすべての転置の最終的な結果は、入力 (DIF) または出力 (DIT) インデックスのビット反転に対応します。小さな基数を使用する代わりに、およそ √ N の基数と明示的な入力/出力行列の転置を使用する場合、それは4 ステップ FFTアルゴリズム (または転置の数に応じて6 ステップ) と呼ばれ、当初はメモリの局所性を向上させるために提案されました^{[14] [15]}たとえば、キャッシュ最適化やアウトオブコア操作用であり、後に最適なキャッシュ忘却アルゴリズムであることが示されました^[16]。

一般的な Cooley–Tukey 分解では、インデックスkとn をそれぞれおよび に書き換えます。ここで、インデックスk _aとn _aは 0.. N _a -1 ( aは 1 または 2) の範囲です。つまり、入力 ( n ) と出力 ( k ) を、それぞれ列優先と行優先のN _{1 ×} N ₂の2 次元配列に再インデックスします。これらのインデックスの違いは、前述のように転置です。この再インデックスをnkの DFT 式に代入すると、交差項は消え (その指数は 1)、残りの項は次のようになります 。${\displaystyle k=N_{2}k_{1}+k_{2}}$${\displaystyle n=N_{1}n_{2}+n_{1}}$${\displaystyle N_{1}n_{2}N_{2}k_{1}}$

${\displaystyle X_{N_{2}k_{1}+k_{2}}=\sum _{n_{1}=0}^{N_{1}-1}\sum _{n_{2}=0}^{N_{2}-1}x_{N_{1}n_{2}+n_{1}}e^{-{\frac {2\pi i}{N_{1}N_{2}}}\cdot (N_{1}n_{2}+n_{1})\cdot (N_{2}k_{1}+k_{2})}}$

${\displaystyle =\sum _{n_{1}=0}^{N_{1}-1}\left[e^{-{\frac {2\pi i}{N_{1}N_{2}}}n_{1}k_{2}}\right]\left(\sum _{n_{2}=0}^{N_{2}-1}x_{N_{1}n_{2}+n_{1}}e^{-{\frac {2\pi i}{N_{2}}}n_{2}k_{2}}\right)e^{-{\frac {2\pi i}{N_{1}}}n_{1}k_{1}}}$

${\displaystyle =\sum _{n_{1}=0}^{N_{1}-1}\left(\sum _{n_{2}=0}^{N_{2}-1}x_{N_{1}n_{2}+n_{1}}e^{-{\frac {2\pi i}{N_{2}}}n_{2}k_{2}}\right)e^{-{\frac {2\pi i}{N_{1}N_{2}}}n_{1}(N_{2}k_{1}+k_{2})}}$。

ここで、各内側の合計はサイズN ₂の DFT であり、各外側の合計はサイズN ₁の DFT であり、[...] 括弧内の項は回転因子です。

^{Cooley と Tukey [3]}および Gauss (基数 3 と基数 6 の手順の例を示した)の両方によって示されているように、任意の基数r (および混合基数) を使用できます。^[2] Cooley と Tukey は、もともと基数バタフライには O( r ² ) の作業が必要であると想定し、基数rの計算量をO( r ² N / r  log _r N ) = O( N  log ₂ ( N )  r /log ₂ r ) と計算しました。r の値が 2 から 12 までの整数の場合の r /log 2 r の計算から、最適な基数_は3 ( eに最も近い整数で、 r /log ₂ r を最小化する)であることがわかります。^{[3] [17]} しかし、この分析は誤りでした。基数バタフライも DFT であり、FFT アルゴリズムを使用して O( r log r ) 演算で実行できるため、基数r は実際には計算量 O( r  log( r )  N / r  log _r N ) で打ち消され、最適なrはより複雑な考慮によって決定されます。実際には、非常に大きなr (32 または 64) は、たとえば最新のプロセッサの多数のプロセッサ レジスタを効果的に活用するために重要です。 ^[13]また、無制限の基数r = √ Nでも O( N  log  N ) の計算量を達成し、前述のように大きなNに対して理論的および実用的な利点があります。 ^{[14] [15] [16]} 

上記の DFT の抽象的な Cooley-Tukey 分解は、何らかの形でアルゴリズムのすべての実装に適用されますが、FFT の各段階でデータを順序付けしてアクセスする手法には、はるかに大きな多様性が存在します。特に興味深いのは、 O(1) の補助ストレージのみを使用して、入力を出力データで上書きするインプレース アルゴリズムを考案する問題です。

最もよく知られている並べ替え手法は、インプレース radix-2 アルゴリズムの明示 的なビット反転を伴います。ビット反転とは、数字b ₄ b ₃ b ₂ b ₁ b ₀ (たとえば、N =32 入力の場合は 5 桁) を使用してバイナリで記述されたインデックスnのデータが、数字が反転されたb ₀ b ₁ b ₂ b ₃ b ₄のインデックスに転送される順列です。上記で示したような、出力が入力にインプレースで書き込まれる radix-2 DIT アルゴリズムの最後のステージについて考えてみましょう。と がサイズ 2 DFT と組み合わされると、これら 2 つの値は出力によって上書きされます。ただし、2 つの出力値は、最上位ビットb ₄ ( N =32 の場合)に対応する出力配列の前半と後半に入る必要があります。一方、2 つの入力 と は、最下位ビットb ₀に対応する偶数要素と奇数要素にインターリーブされます。したがって、出力を正しい場所に得るためには、b _{0 が}b ₄の代わりになり、インデックスはb ₀ b ₄ b ₃ b ₂ b ₁になります。次の再帰段階では、これらの最下位 4 ビットはb ₁ b ₄ b ₃ b ₂になります。基数 2 DIT アルゴリズムの再帰段階をすべて含める場合、すべてのビットを逆にする必要があり、したがって、順序どおりの出力を得るには、ビット反転を使用して入力を前処理 (または出力を後処理) する必要があります。(サイズN /2 の各サブ変換が連続したデータに対して動作する場合、DIT入力はビット反転によって前処理されます。) 同様に、すべての手順を逆の順序で実行すると、後処理 (または前処理) でビット反転を行う基数 2 DIF アルゴリズムが得られます。 ${\displaystyle E_{k}}$${\displaystyle O_{k}}$${\displaystyle E_{k}}$${\displaystyle O_{k}}$

このアルゴリズムで使用される対数 (log) は、底が 2 の対数です。

以下はビット反転置換法を用いて実装された反復基数2FFTアルゴリズムの疑似コードである。^[18]

アルゴリズムiterative-fftは、
    入力: n 個の複素数値の配列a (n は 2 の累乗)、
    出力: a の DFT である配列A です。
 
    ビット逆コピー(a, A)
    n ← a .length 
     s = 1からlog( n )まで、m ← 2 s ω m ← exp(−2π i / m ) 
         k = 0からn -1まで、 mによって、ω ← 1
             j = 0からm / 2 – 1 まで、t ← ω A [ k + j + m /2]
                 u ← A [ k + j ]
                 A [ k + j ] ← u + t A [ k + j + m /2] ← u – t ω ← ω ω m
        
            
              
                 
                
                 
   
     Aを返す

ビット逆コピー手順は次のように実装できます。

アルゴリズムbit-reverse-copy( a , A )の
    入力: n 個の複素数値の配列a (n は 2 の累乗)。
    出力:サイズnの配列A。

    n ← a .length
     、 k = 0から n – 1までA [rev(k)] := a [k]
を実行する
        

あるいは、一部のアプリケーション (畳み込みなど) はビット反転されたデータでも同様に機能するため、ビット反転なしで順方向変換、処理、逆変換をすべて実行して、自然な順序で最終結果を生成できます。

しかし、多くの FFT ユーザーは自然順序の出力を好み、明示的なビット反転段階が計算時間に無視できない影響を与える可能性があります^[13]。ただし、ビット反転は O( N ) 時間で実行でき、多くの研究の対象となっています^{[19] [20] [21]} 。また、基数 2 の場合は置換がビット反転ですが、混合基数の場合はより一般的には任意の (混合基数) 桁反転であり、置換アルゴリズムの実装がより複雑になります。さらに、多くのハードウェア アーキテクチャでは、FFT アルゴリズムの中間段階を並べ替えて、連続する (または少なくともより局所的な) データ要素に対して動作するようにすることが望ましいです。この目的のために、Cooley–Tukey アルゴリズム用に、中間段階での個別のビット反転や追加の置換を必要とせずに済む、いくつかの代替実装スキームが考案されています。

アウトオブプレースの場合、問題は大幅に単純化されます。つまり、出力配列が入力配列と異なるか、または同等のサイズの補助配列が利用可能であるということです。ストックハム自動ソートアルゴリズム^{[22][23] は、}FFT の各段階をアウトオブプレースで実行し、通常は 2 つの配列間で書き込みを行い、各段階でインデックスの 1 つの「桁」を転置します。このアルゴリズムは、特にSIMDアーキテクチャで人気があります。^[23][24] より大きな潜在的な SIMD の利点 (連続アクセスの増加) はピーズアルゴリズム^[25]このアルゴリズムも各段階でアウトオブプレースで並べ替えますが、この方法では個別のビット/桁の反転と O(NlogN深さ優先を使用して、Cooley–Tukey 分解定義を直接適用することもできます。これにより、個別の置換ステップなしで自然な順序のアウトオブプレース出力が生成され (上記の疑似コードのように)、階層型メモリを備えたシステムでキャッシュを無視した。^[9][13][26]

補助記憶装置や個別の桁反転パスを使わないインプレースアルゴリズムの典型的な戦略は、中間段階での小さな行列転置（個々の桁のペアを交換する）を含み、これを基数バタフライと組み合わせることで、データのパス数を減らすことができる。^{[13] [27] [28] [29] [30]}

• 「高速フーリエ変換 - FFT」。Cooley-Tukey 法。記事。10. C++ でのシンプルで教育的な基数 2 アルゴリズム
• 「KISSFFT」。GitHub。2022年2月11日。C言語によるシンプルな混合基数Cooley-Tukey実装
• GitHubの Dsplib
• 「時間FFTアルゴリズムにおける基数2のデシメーション」。2017年10月31日時点のオリジナルよりアーカイブ。 「Алг​​оритм БПФ по основанию два с прореживанием по времени」（ロシア語）。
• 「周波数 FFT アルゴリズムにおける基数 2 デシメーション」。2017 年 11 月 14 日時点のオリジナルからアーカイブ。 「Алг​​оритм БПФ по основанию два с прореживанием по частоте」（ロシア語）。