離散フーリエ変換（りさんフーリエへんかん、、DFT）とは離散化されたフーリエ変換であり、信号処理などで離散化されたデジタル信号の周波数解析などによく使われる。また偏微分方程式や畳み込み積分を効率的に計算するためにも使われる。離散フーリエ変換は（計算機上で）高速フーリエ変換(FFT)を使って高速に計算することができる。離散フーリエ変換とは、複素関数 formula_1を複素関数formula_2に写す写像であって、次の式で定義されるものを言う。ここで、Nは任意の自然数、 formula_3 はネイピア数、formula_4 は虚数単位 (formula_5)で、formula_6は円周率である。このとき、{formula_7}を標本点という。また、この変換を formula_8 という記号で表し、のように略記することが多い。この逆変換にあたる逆離散フーリエ変換（、IDFT）は正規化係数（DFT は 1, IDFT は 1/"N"）や指数の符号は単なる慣習的なものであり、上式とは異なる式を扱うことがある。DFT と IDFT の差について、それぞれの正規化係数を掛けると 1 / "N" になることと、指数の符号が異符号であるということがだけが重要であり、根本的には同一の変換作用素と考えられる。DFT と IDFT の正規化係数を両方とも formula_9 にすると、両方ともユニタリ作用素（ユニタリ変換）になる。理論的にはユニタリ作用素にするのが好ましいが、実用上数値計算を行うときは上式のように正規化係数を1つにまとめて、スケーリングを一度に行うことが多い。離散フーリエ変換はフーリエ変換を離散化したものであるので、フーリエ変換と同様の性質を持つ。離散フーリエ変換においては、有限個の標本点しか使わないため、ある関数を離散フーリエ変換し、それを逆変換した場合に、標本点以外で元の関数と一致するとは限らない。すなわち、複素関数ｆに対して、により離散フーリエ変換を行い、それを逆変換したものをgとするとは言えるが、その他の点でが言えるとは限らない。これを高周波の問題、あるいはエイリアシング(aliasing)という。formula_10 は内積に関し、formula_11が整数のとき直交基底である。 ight)left(e^{-i2pifrac{t'n}{N}} ight)formula_12はクロネッカーのデルタformula_1 と formula_14 の畳み込みformula_15は次のように定義される。ここでformula_16は次のような周期性を持つとする。周期関数の畳み込みを離散フーリエ変換したものは、それぞれの離散フーリエ変換の積になる(畳み込み定理)。つまり畳み込み和を直接定義式を用いて計算すると "O"("N"²) の計算量が掛かる。しかし、上式より一旦 DFT をしてから掛算をして、そして IDFT で戻す方法もある。DFT の高速アルゴリズムである FFT を介してこのように計算すると "O"("N" log "N") の計算量で済む。formula_1とformula_14の相互相関formula_19は以下のように定義される。formula_16が上記の周期性を持てば、応用の上は、実数値関数を対象とすることが多いが、このとき、(formula_21はformula_22の複素共役)。そのため出力formula_23の半分(formula_24)で全ての情報を持っていることになる。デジタル画像処理では2次元変換が画像の周波数成分を解析するのに使われる。変換は以下のように定義される。そして逆変換は次のようになる。但し2次元DFT は行列を用いて簡単に記述できる。ここで2次元DFT を行列計算によって以下のように変形できる。以下上式の 1 - 7 を解説すると、formula_45の行はformula_25の"x"行目の行を1次元DFTしたものである。ゆえにformula_45はformula_25の各行の1次元DFTした結果の行ベクトルを集めたものになる。"F"="WF"における、"F"を後から掛ける作用素はformula_45の列の1次元DFTしたものと同じと考えて良い。つまり、2次元DFT（2次元フーリエ変換も同様だが）はformula_25を、各行ごとに1次元DFTし、その結果をさらに各列ごとに1次元DFTする事と等価である。ここで、1次元DFTの計算はFFTのアルゴリズムで高速に計算できる。そのため実用上は2次元DFTも、2次元FFTとして計算される。表中で、formula_51DFTは多くの広い分野で利用されている。ここでは、その中の一部を示しているだけに過ぎない。これらの応用は高速フーリエ変換(FFT)とその逆変換(IFFT)で高速に計算できることを前提としていて、定義通りにDFTを計算しているのではない。信号"x"("t")を解析するのに使われる。ここで"t"は時間で[0,"T"]の範囲をとるものとする。例えば、音声信号の場合は、"x"("t")は時刻"t"での空気の圧力を表現することになる。この信号は"N"個の等間隔の点で標本化されて、"x

出典:wikipedia