Cooley–Tukey型アルゴリズムは、派生アルゴリズムが多数あります。その中で最も使用頻度が高いとされるのが、Radix-2 FFTです。

Radix-2 FFTの導出は以下の式で表すことができます。

(1)　DFT（離散フーリエ変換）の式を、偶数（Even）と奇数（Odd）の2つに分割します。

(2)　奇数の項をさらに分割して、指数関数部分（）を取り出します。

(3)　偶数項の周期がN/2であることを示します。

(4)　奇数項の周期がN/2であることを示します。

(5)　N/2を境にしてFの値が変動することを示します。

(6)　(5)の上辺からFの導出となります。

(7)　(3)、(4)と(5)の下辺から、t+N/2のFの導出となります。

上記の結果を一般化して、アルゴリズムとして表すと以下の擬似コードに一般化することができます。

Cooley-Tukey型アルゴリズムは、nの2乗からO(n log2 n)に計算量を削減することが可能です。

CPUを使用した古典的アルゴリズムは再帰的に処理を行いますが、以下のようなパラメーターと戻り値を持ちます。

offsetは再帰時の各位置となります。例えば以下のように再帰処理で高速フーリエ変換を行う関数の各ステップ（又はステージ）の処理を一般化してみましょう。

(2)と(3)で、部分列を1/2に分割していき、最終的には、N＝2まで再帰するものとします。

この一連の再帰処理については「図：FFT整列ネットワーク（N=8）」（図12.1「図：FFT整列ネットワーク（N=8）」）を参照ください。

図12.1 図：FFT整列ネットワーク（N=8）

図では、stage0はN=2、stage1はN=4、stage2はN=8の周波数成分というように前のステージで計算した結果を、次のステージでは倍の規模のFFTの入力に使うことができます。CPU処理で一般的な再帰を使う場合は、stage2→stage1→stage0という順序で呼び出しますが、実際の「処理順序」はstage0→stage1→stage2となります。

stage0の入力は観測値[,,…,]としますが、図のように上半分に偶数の添字、下半分に奇数の添字となるよう再配置します。

この再配置は奇数と偶数をスワップするだけですが、ビット反転を使うことで、容易に実装することができます。

ビット反転（bit reversal）は、Cooley-Tukey型アルゴリズムにおける偶数項と、奇数項の分離のために使うことができます。

JavaのIntegerクラスにはビットを反転するInteger.reverseというメソッドがありますが、これはベースを32ビットとして演算します。

public static int reverse(int i) {
  i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
  i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
  i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
  i = (i << 24) | ((i & 0xff00) << 8) | ((i >>> 8) & 0xff00) | (i >>> 24);
  return i;
}

例えば整数の「3」のビット反転をする場合は3を2進数にまず変換します。

00000000000000000000000000000011

これをビット反転すると以下のような2進数の列に変換されます。

11000000000000000000000000000000

ビットの反転は、このように対応する位置にあるビットをスワップ（入れ替え）します。「3」の例で言えば、1桁目と32桁目のビットを交換したことになります。

これを効率的に計算するアルゴリズムは多く開発されており、Integer.reverseも代表的なアルゴリズムの一つを採用しています。

しかしFFTの文脈では、32ビットの反転が必要とされることはほとんどありません。インデックスの数が512（0ー511）であれば9ビット、4096（0ー4095）であれば、12ビットを要します。

ではビット反転の実装を考えてみます。

private static int reverseBit(int x, int maxBits) {
    int bit = 0;
    while (maxBits != 0){ //(1)
        bit <<=1; //(2)
        bit |=( x &1 ); //(3)
        x >>=1; //(4)
        maxBits>>=1; //(5)
    }
    return bit;
}

シフト演算子は2進数の1/0のビットの読み込む順番を制御するために使います。引数xは右シフトすることにより、右側のビットから読み込み、変数xの右側にコピーしたビットは、左にシフトすることで、ビットを反転していきます。

最後に配列をビット反転した添字に基づいて並び変えてみます。

private static void reverseData(int N, double[] data) {
    for(int i = 2; i < N*2; i+=2) {
        int rev = reverseBit(i/2,N-1) << 1;
        if(i < rev) {
            double tmpR = data[i];
            double tmpI = data[i+1];
            data[i] = data[rev];
            data[i+1] = data[rev+1];
            data[rev] = tmpR;
            data[rev+1] = tmpI;
        }
    }
}

data配列を並び変える際には、複素数の処理が入ります。添字iとrevを入れ替えるだけでなく、虚数部分の入れ替えも同時に行います。