FFT

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

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

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

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