高速フーリエ変換のアルゴリズム

高速フーリエ変換は、離散フーリエ変換を高速化したものです。
変換と逆変換のマトリクスは、回転の方向が違うだけで、本質的に同じような対称性があります。
そこで、変換側の演算の対称性について、次のツールを用いて検討します。

はじめは、ステージは「始め」の位置にあります。
　
「次」を1回クリックして、次のステージに進みます。
ここで、ベクトルとマトリクスの奇数行と偶数行に注目してください。
奇数行には斜めの成分が含まれていません。
そこで、行の入れ替えを行い、奇数行と偶数行を別々に処理することにします。（次をクリック）: 　
その結果、ベクトルは（4×1）、マトリクスは（4×8）となります。
ここで、マトリクスの対称性に注目して下さい。（赤と青で色分け）
例えば上のマトリクスでは、右半分と左半分には同じ形をしています。
一方、下のマトリクスでは、右半分にマイナスをつけたものが左半分になっています。（次をクリック）
　
そこで、マトリクスの右半分を左半分で代用することを考えます。
信号 x0 ～ x7 について、加算もしくは減算を行ってから、（4×4）のマトリクスをかけます。
この過程は、いわゆる分配則を用いて因数分解する操作に等価です。（次をクリック）
　
このようにして、（4×1）のベクトルと（4×4）のマトリクスをかける演算に置き替えることができました。
この結果、乗算数は約1/2に減少しています。: 　
次に、2つの（4×4）のマトリクスに着目して下さい。これらにも、まだ対称性が残っています。（次をクリック）
　
先ほどと同じようにマトリクスの奇数行と偶数行に規則性が見られます。そこでこれらを分離して計算します。
　
今度は、（2×1）のベクトル、（2×4）のマトリクスを用いた4つの式が生成されました。
これらのマトリクスの左右を見比べて下さい。左右が全く等しい場合と、90°180°270°回転させた
関係になっていることがわかります。（次をクリック）
　
そこでの、先ほどと同様に、マトリクスの右半分を左半分で代用します。
具体的には、ベクトルの演算を行ってから、左半分のマトリクスを乗じます。（次をクリック）
　
最終的には、（2×1）のベクトル、（2×2）のマトリクスを用いた4つの式が生成されました。
この乗算数は10となり、何もしない通常のDFTの64に対し、約1/6に減少していることがわかります。

⇒　教材コンテンツ集に戻る