離散フーリエ変換 - ad2004ks @ ウィキ

有限長の離散時間信号に対するフーリエ変換。略してDFTと呼ぶことが多い。

有限長系列x(n)、0≦k<Nとすると、

X(k)=Σ(n=0→N-1)[x(n)e^(-j2πkn/N)]

で定義される。0≦n<Nの区間でのみ値x(n)をもち、その他の範囲で0となる系列のフーリエ変換をX(e^(jω))とすると、X(k)=X (e^(j2πk/N))で定義される。IDFTにより得られたx(n)は周期Nの周期系列となり、0≦n<Nの区間ではもとの系列と一致する。

DFTはフーリエ変換を計算する実用的な手段として広く用いられており、その計算を高速に行うアルゴリズムが高速フーリエ変換(FFT)である。