FFTはなぜバタフライのように構築されるのか

FFTは回転因子の対称性と周期性を利用してその乗算回数を減らします。ここではそれら回転因子がいかに対称で周期的なのか、またなぜFFTがバタフライのように構築されるのかをベクターイメージを使って説明します。 Fig.1はDFT(Discrete Fourier Transform、FFTの原型）のプロセスです。回転因子はそれぞれの周波数において固有のステップを持ちながら回転します。角度のパターンの類似性、たとえば5kHzと1kHzの角度がいかに似ているか、などを下のPDFにまとめましたのでダウンロードしてご覧ください。 Fig.1 8ポイントDFTとその回転因子 回転因子の角度のパターンを考慮に入れたFFTの考察をPDFにまとめました。 (0) for 1, 3, 5 and 7kHz 5kHzの角度は1kHzのそれに似ている。 3kHzと7kHzの角度は1kHzと少し違う。ゆえにいくらかの補償が必要になる。 (1) for 0, 2, 4 and 6kHz 4kHzの角度は0kHzのそれに似ている。 2kHzと6kHzの角度は0kHzと少し違う。ゆえにいくらかの補償が必要になる。 Back

Top Page