書記が数学やるだけ#819 高速フーリエ変換

フーリエ変換の実装で用いられる高速フーリエ変換について，原理を確認しておく。

問題

説明

高速フーリエ変換の原理は分割統治法に基づいており，次数Nが2の累乗のときに O(N log N) の計算量で得るアルゴリズムである。

解答

通常の離散フーリエ変換では，行列計算により計算量がO(N^2)となり，Nの上昇に伴い指数増加してしまう。

ここでN=4の場合の計算を示しておく。

ここでは時間間引きFFTを紹介する。一般論として，偶数番目と奇数番目を分けて計算する。

これにより2分割の繰り返しで計算を示すことができ，この計算量はO(NlogN)と大幅に改善される。

ではN=4の場合で中身を示していく。変換行列を偶数列と奇数列に分け，2分割した行列での表示を考える。

これは以下のようなバタフライ演算で表すことができる。ここで，青線はそのままの値を，赤線は数字をかけた値を足すことを示している。

さらにN=2から2分割して，分割が完了する。

先ほどの具体例をバタフライ演算で確認しておく。

本記事のもくじはこちら：