2022-05

バタフライ演算を図示した。 演算が交差している様が蝶々のようなのでバタフライ演算と呼ばれている。 入力サンプリングの入れ替えルールはビットリバースに準じている。 これら一連の流れを「CooleyTukey型FFTアルゴリズム」と呼ぶ。 このアルゴリズムは入力サンプリングが2のべき乗であることが前提。

Nの回転因子にN/2の回転因子を含めることが可能 複数段の行列に分解可能。 つまり、演算を分解できる。 最終的に残る値はかなり限られる。 これを利用してバタフライ演算を行うことになる。

回転因子を元に行列表現してみた。 回転位置による最適化が可能。 必ず実数になる点が存在することによる最適化が可能。 対角線による最適化が可能。 ここまででもかなり便利ではあるが、さらにバタフライ演算をするための最適化もある。

タイトル詐欺にならないようにMATLAB、Pythonを使って各回転因子を算出して見た。 1/√2のような計算結果にはならないので1/√2=0.7071を想定した見方になる。 前回の回転因子と同一の結果が得られた。 虚数表現はMATLABはi、Pythonはjとなっている。

FFT、IFFTの数式上のバリエーションはDFT、IDFTと一緒。 元にしている数式自体は同一。 FFT、IFFTはバタフライ変換による高速化を行ってる点で異なるのみ。 バタフライ変換を理解するためには回転因子のイメージが重要。 オイラーの公式のおかげで複素指数関数と三角関数が紐づく。