Radix-2アルゴリズムRadix-2アルゴリズムおよびバタフライ演算について述べる。フーリエ変換の結果を以下に示す。(2.9)(2.10)(2.11)(2.12)これらの式を偶奇で分けてシグマでまとめると、(3.1)式のようになる。(3.1)このように1つのFFTはNの偶奇で分けて2つのFFTに分割することができる。FFT(バタフライ演算)まで分割できる。これをRadix-2アルゴリズムという。Radix-2アルゴリズムにおいては、基本的には複素加減算だけで行えるため計算量を節約できる。バタフライ演算を行う回路を表したものが、図1のバタフライ演算回路である。減算、線の上部の回転因子は乗算を表している。(3.6)式となり、DFTでの結果と等しいことが確認できる。