高速フーリエ変換（ＦＦＴ）

高速フーリエ変換は、得られる結果自体はこの離散フーリエ変換とまったく同じなのですが、計算アルゴリズムを工夫することで、掛け算の回数をN**2回より減らすものです。

Nが素数でなく複数の自然数（１を除く）の積で表わせるのであれば使える手法ですが、特にNが2のべき乗数（512や1024など）の場合が代表的です。

このアルゴリズムを一般的に記述するのは難しいので、ここではN=8の場合を例にとって示しましょう。

【手順1】
入力信号列である（ｆ0、ｆ1、ｆ2、ｆ3、ｆ4、ｆ5、ｆ6、ｆ7）を、次のように並べ替えます。

（ｆ0、ｆ4、ｆ2、ｆ6、ｆ1、ｆ5、ｆ3、ｆ7）

一般的にいうと、N=2**mの時、0、1、・・・、N-1という数をそれぞれNビットの２進数で表わし、そのN桁の並べ順を完全に逆にし、その結果できた値の順番で並べるということです。

ビット逆順並べ替えと呼ばれます。

今回の場合はm=3なので、逆順にする前は以下のパターンということになります。

（000、001、010、011、100、101、110、111）

これを逆順にすると、以下のようになります。

（000、100、010、110、001、101、011、111）

すなわち0、4、2、6、1、5、3、7ということです。

この数列を新たな順番として、ｆの値を並べ替えるわけです。

【手順2】
並べ替えた８つの数字に対し、左から順に2つずつを１組とします。

その各組に対して以下の演算を行います。

［ａ，ｂ］→［ａ+ｂ，ａ-ｂ］

この結果、やはり2つ１組の数が発生します。

その2つ１組をそのまま左から順に並べます。

そうして得られた８つの数（８次元ベクトル）を便宜的に（ｇ0、ｇ1、ｇ2、ｇ3、ｇ4、ｇ5、ｇ6、ｇ7）と書きます。

その中味は以下の通りです。

（ｆ0+ｆ1、ｆ0-ｆ1、ｆ2+ｆ3、ｆ2-ｆ3、ｆ4+ｆ5、ｆ4-ｆ5、ｆ6+ｆ7、ｆ6-ｆ7）。

【手順3】
（ｇ0、ｇ1、ｇ2、ｇ3、ｇ4、ｇ5、ｇ6、ｇ7）に対し、今度は左から順に4つずつを１組とし、各組に対して以下の演算を行います。

［ａ，ｂ，ｃ，ｄ］→［ａ+ｃ，ｂ-i*ｄ，ａ-ｃ，ｂ+i*ｄ］

そうして得られた4つ１組をそのまま左から順に並べます。

そうして得られた８つの数（８次元ベクトル）を便宜的に（ｈ0、ｈ1、ｈ2、ｈ3、ｈ4、ｈ5、ｈ6、ｈ7）と書きます。

その中味は以下の通りです。

（ｇ0+ｇ2，ｇ1-i*ｇ3，ｇ0-ｇ2，ｇ1+i*ｇ3，ｇ4+ｇ6，ｇ5-i*ｇ7，ｇ4-ｇ6，ｇ5+i*ｇ7）とりあえず手順3としてはこの通りなのですが、その意味を正確に把握するために、4つ１組に対する演算結果を以下のように考えるのがよいでしょう。

［ａ+ｐ0*ｃ，ｂ+ｐ1*ｄ，ａ+ｐ2*ｃ，ｂ+ｐ3*ｄ］ただしｐ0＝1、ｐ1＝-i、ｐ2＝-1、ｐ3＝i

このｐ0、ｐ1、ｐ2、ｐ3は、実は下記のように一般的に書くことができます。

ｐk＝exp(-2kπi/4)ここでk＝0、1、2、3

一般にexp(i *z)＝cos(z)+ i *sin(z)なので、実際に上記のようなｐの値が得られるのです。

【手順4】
（ｈ0、ｈ1、ｈ2、ｈ3、ｈ4、ｈ5、ｈ6、ｈ7）に対し、今度は左から順に8つずつを１組とし、各組に対して以下の演算を行います。

なお、データ数（N）を8としているので、「各組」とはいっても、この場合にできるのは1組だけです。

［ａ，ｂ，ｃ，ｄ，e，ｆ，ｇ，ｈ］
→
［ａ+ ｑ0*e，ｂ+ｑ1*ｆ，ｃ+ｑ2*ｇ，ｄ+ｑ3*ｈ，ａ+ ｑ4*e，ｂ+ｑ5*ｆ，ｃ+ｑ6*ｇ，ｄ+ｑ7*ｈ］
ただしｑk＝exp(-2kπi/8) ここでk＝0、1、2、3、4、5、6、7。

そうして得られた8つ１組をそのまま左から順に並べます。

くどいようですが、N＝8の時は1組だけです。

これがN＝8の時の高速フーリエ変換のアルゴリズムです。

N=2**mの時、手順はm+1まで続くことになります。

なぜこれで離散フーリエ変換が実現できるかの説明は省略します。

重要なことは、これにより掛け算の回数を減らすことができる、という点です。

たとえば上記手順4の中では、掛け算が8回出てきます。

実は一般に、手順2から手順m+1のそれぞれに対して、掛け算はN回出てきます。

m＝log2 N（2を底とするNの対数）なので、結局掛け算の総数は、N*log2 Nということになります。

一方、一般の離散フーリエ変換で必要とされる掛け算の総数はN**2ですから、ずっと小さな値となったことがわかります。

画像の離散フーリエ変換では、入力値は実数ですが、出力値は一般に複素数となります。

高速フーリエ変換でも同じです。

Ｆ0が直流成分量であり、以下、Ｆ1、...、Ｆ(N-1)となるに従って高周波の成分量を表わします。

変換によりN個の実数からN個の複素数が作られるので、単純に考えると波形を記述するパラメータの情報量が増えてしまったようですが、変換後の値は完全に独立ではなく対称性があるので、結局パラメータの数は同じということになります。