バタフライによる表現

先に定義した高速フーリエ変換を、「バタフライ」という図形を用いて表現することが可能です。

このような表現を用いることにより、高速フーリエ変換のアルゴリズムを幾何学的に記述することができます。

　

バタフライとは、2つの入力と出力を持つ演算の単位であり、最も単純なバタフライは、2つの入力の和と差を

出力するものです。

2つの三角形で構成され、形が蝶々(Butterfly)に似ていることからバタフライと呼ばれます。

　

下のツールは、先に求めたFFTのアルゴリズムを表しています。

図の小さな三角形は、入力信号の値に定数をかけて出力する乗算素子です。

左下のボタンを操作することにより、ステ-ジを移動することができます。

ステージ毎に、対応する信号と図形の関連を色を用いて表現していますので、上で説明したアルゴリズムが実現される

過程を復習して下さい。

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