FFT

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

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

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

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