自分専用のFFTアルゴリズムの説明

misc

まず最初に信号データセットの「逆読み代入」を施こしておく*1。
例えばデータ長が28のデータのFFTの場合、FFT用の配列の(10101111)2番目の要素に信号データセットの(11110101)2番目のデータを格納する。
それからデータ長が2kのFFTの場合、k段の「バタフライ演算」を行う。
例えば（データ長が28の場合）5段目のバタフライ演算では、配列の要素 f[(11110101)2] は添字の下から5ビット目だけが異なる添字の要素 f[(11100101)2] と次式で与えられるバタフライ演算を行う：


f[(11100101)2]＝f[(11100101)2]＋f[(11110101)2]Δ5(00101)2
f[(11110101)2]＝f[(11100101)2]＋f[(11110101)2]Δ5(10101)2
ここでΔ5＝exp(2πi/25)であり、その指数は各々の配列添字の下位5ビットである。
これをすべてのペアに対して行う。
このバタフライ演算を第1段目から第8段目まで実行すると、配列要素 f[k] には信号データのフーリェ変換 Fk＝Σ fm Wmk (W＝exp(2πi/28))が格納されている。

*1:「ビット反転」と呼ばれることが多いが、ビット反転というと「0と1」の入れ替えのような気がして仕方が無い。