FFT

fast Fourier transform, FFT

フーリエ変換を高速に行う計算方法。コンピューターを使うので連続的な積分の代わりに有限の離散的な和で実行される。離散的な和をいくつかのグループに分け、さらに計算の順序を工夫して計算量を大幅に減少させる方法。周期 N の離散フーリエ変換では、通常の変換では演算の回数がNの2乗に比例するが、FFTでは NlogN に比例する。高分解能像の解析等に使われる。

A computing method to decrease the calculation time of a Fourier transform. Since "fast Fourier transform (FFT)" is executed using a computer, calculations are performed by a discrete finite sum, instead by an integration. It greatly decreases the computation time by dividing the calculation into certain sub-groups and by changing the order of the calculation. In a discrete Fourier transform with a period of N, the number of operation is normally proportional to N² but it is decreased to N log N in FFT. This method is used for analysis of high-resolution images.