この文書は、離散フーリエ変換DFTの理解をもとに、高速フーリエ変換FFTの振る舞いを理解することを目標とするものです。 はじめにDFTが何をするものかを簡単に説明し、そのDFT処理をJavaScriptコードに書き下し、FFT実装の検証対象となる具体例でのDFT実行結果を示します。 そして、再帰版FFT実装を天下り的に提示し、具体例を用いてFFTの中で何が行われるかを解析します。 最後に、この解析結果にもとづいて、ループ版FFTを導出します。 1. 離散フーリエ級数(DFT) 離散フーリエ変換(Discrete Fourier Transform, DFT) は、一定期間の時系列の数値列を、その期間を周期的に繰り返す合成波とみなし、その周波数成分の複素数値の列(低周波数から高周波数の順)を算出する仕組みです。 各周波数における複素数値のうち、実数成分が偶関数であるcos波の係数であり、虚数