はじめに FFTと私 高速フーリエ変換(Fast Fourier Transform, FFT)は,通常の離散フーリエ変換(Discrete Fourier Transform, DFT)に比べて非常に高速なアルゴリズムとして知られており,ランダウの記号を用いると,DFTの計算量がO(N2)であるところ,FFTではO(N log N)になるようです。このため,理学・工学の幅広い分野で応用されております。言わば,ディジタル信号処理の中の1つの大きな“柱”となっています。ただし,入力される時間領域のディジタル信号のデータ点数が2のべき乗(例えば64とか1,024とか4,096など)となっている必要…