入れ替え
入れ替えは、1⇔4、3⇔6 でこれは2進数で表現したとき、ビット列の逆順に相当します。
001⇔100 011⇔110
離散フーリエ変換手法
N=8の場合DFTは元の信号の順番を入れ替えると次の図ように計算できる。線の数字は重みで、同じノードへの集まりは和を意味する。
計算量
各段階(ステップ)でバタフライ演算はN/2、段階数はlogN になります。したがってFFTの計算量は
N log N
になります。
通常のDFTの計算を行うとN・N の計算量が必要です。
バタフライ(蝶)演算
この計算をバタフライ計算と呼びます。