離散フーリエ変換

離散フーリエ変換（りさんフーリエへんかん、、DFT）とは次式で定義される変換で、フーリエ変換に類似したものであり、信号処理などで離散化されたデジタル信号の周波数解析などによく使われる。また偏微分方程式や畳み込み積分の数値計算を効率的に行うためにも使われる。離散フーリエ変換は（計算機上で）高速フーリエ変換(FFT)を使って高速に計算することができる。
離散フーリエ変換とは、複素関数 formula_1を複素関数formula_2に写す写像であって、次の式で定義されるものを言う。
ここで、Nは任意の自然数、 formula_4 はネイピア数、formula_5 は虚数単位 (formula_6)で、formula_7は円周率である。このとき、{formula_8}を標本点という。また、この変換を formula_9 という記号で表し、
のように略記することが多い。
この逆変換にあたる逆離散フーリエ変換（、IDFT）は
正規化係数（DFT は 1, IDFT は 1/"N"）や指数の符号は単なる慣習的なものであり、上式とは異なる式を扱うことがある。DFT と IDFT の差について、それぞれの正規化係数を掛けると 1 / "N" になることと、指数の符号が異符号であるということがだけが重要であり、根本的には同一の変換作用素と考えられる。DFT と IDFT の正規化係数を両方とも formula_11 にすると、両方ともユニタリ作用素（ユニタリ変換）になる。理論的にはユニタリ作用素にするのが好ましいが、実用上数値計算を行うときは上式のように正規化係数を1つにまとめて、スケーリングを一度に行うことが多い。
性質.
離散フーリエ変換はフーリエ変換に類似した変換であるので、フーリエ変換と類似した性質を持つ。
完全性.
離散フーリエ変換においては、有限個の標本点しか使わないため、ある関数を離散フーリエ変換し、それを逆変換した場合に、標本点以外で元の関数と一致するとは限らない。
すなわち、複素関数ｆに対して、
により離散フーリエ変換を行い、それを逆変換したものをgとすると
は言えるが、その他の点でformula_14が言えるとは限らない。これを高周波の問題、あるいはエイリアシング(aliasing)という。
選点直交性.
formula_15 は内積
に関し、formula_17が整数のとき直交基底である。
formula_19はクロネッカーのデルタ
畳み込み定理と相互相関定理.
二つの（一般には複素数値の）関数formula_1 と formula_21 の畳み込みformula_22は次のように定義される。
ただし、formula_24とformula_25は次のような周期性を持つとする。
周期関数の畳み込みを離散フーリエ変換したものは、それぞれの離散フーリエ変換の積になる(畳み込み定理)。
つまり
畳み込み和を直接定義式を用いて計算すると "O"("N"²) の計算量が掛かる。しかし、上式より一旦 DFT をしてから掛算をして、そして IDFT で戻す方法もある。DFT の高速アルゴリズムである FFT を介してこのように計算すると "O"("N" log "N") の計算量で済む。
また、二つの（一般には複素数値の）関数formula_1とformula_21の相互相関formula_30は以下のように定義される。
formula_31が上記の周期性を持てば、
さらにformula_24の関数値が実数であれば、formula_33となる．ここで上線をつけたformula_34はformula_35の複素共役を表す。
実数値関数の離散フーリエ変換.
応用上は、実数値関数を対象とすることが多いが、formula_24が実数値関数であるときには、
(formula_34はformula_35の複素共役)。そのため出力formula_39の半分(formula_40)で全ての情報を持っていることになる。
一般化.
離散フーリエ変換が持つ多くの性質は、formula_41 が1の原始N乗根(primitive root)であることのみに依存している。そのため、単位元の原始N乗根 formula_42 が存在するならば、複素数以外の環や体においても同様に離散フーリエ変換を定義することができる。離散フーリエ変換 (一般)を参照のこと。
2次元での変換.
デジタル画像処理では2次元変換が画像の周波数成分を解析するのに使われる。
変換は以下のように定義される。
そして逆変換は次のようになる。
但し
2次元DFT は行列を用いて簡単に記述できる。
ここで
行列の表記による変形.
2次元DFT を行列計算によって以下のように変形できる。
以下上式の 1 - 7 を解説すると、
formula_65の行はformula_45の"x"行目の行を1次元DFTしたものである。ゆえにformula_65はformula_45の各行の1次元DFTした結果の行ベクトルを集めたものになる。"F"="WF""v"Tにおける、"F""v"Tを後から掛ける作用素はformula_65の列の1次元DFTしたものと同じと考えて良い。
つまり、2次元DFT（2次元フーリエ変換も同様だが）はformula_45を、各行ごとに1次元DFTし、その結果をさらに各列ごとに1次元DFTする事と等価である。ここで、1次元DFTの計算はFFTのアルゴリズムで高速に計算できる。そのため実用上は2次元DFTも、2次元FFTとして計算される。
離散フーリエ変換表.
表中で、
formula_71
応用.
DFTは多くの広い分野で利用されている。ここでは、その中の一部を示しているだけに過ぎない。これらの応用は高速フーリエ変換(FFT)とその逆変換(IFFT)で高速に計算できることを前提としていて、定義通りにDFTを計算しているのではない。
信号解析.
信号"x"("t")を解析するのに使われる。ここで"t"は時間で[0,"T"]の範囲をとるものとする。例えば、音声信号の場合は、"x"("t")は時刻"t"での空気の圧力を表現することになる。
この信号は"N"個の等間隔の点で標本化されて、"x"0, "x"1, "x"2, ... , "x""N"-1 の実数列になる。但し標本化の間隔を Δ"x"(="T"/"N") とすると "x""k"="x"("k" Δ"x") である。これのDFTである "f"0, ..., "f""N"−1 をFFTで計算できる。ただし標本化定理からこれの半分("N"が偶数とすると、"f""N"/2 + 1, ..., "f""N"−1)は冗長であるので捨てるか無視する。
DFT から得られる |"f"k|/"N" は信号の周波数 "j"/"T" 成分の振幅の半分の値であり、振幅スペクトルと呼ばれる。また、この偏角である arg("f""j") はこの周波数成分の位相を表す。また、|"f"k|2はパワースペクトルと呼ばれ、この周波数成分のエネルギーを表している。
"f""k"は信号"x"("t")のフーリエ級数の係数に相当するものと考えることができる。そのために、無限に広がるフーリエ級数計算を、有限のサンプル点に対しての DFT を使って近似するという形になる。連続信号の場合はこれをスペクトル推定(spectral estimation)と呼び、色々な推定法がある。(例えば、DFT が有限サンプル点を扱うことに起因するスペクトル漏れの弊害を少しでも和らげるために窓関数(窓))を使うことがよく行われる。)
データ圧縮.
信号処理の分野では周波数領域（フーリエ変換）で処理をすることも少なくない。例えば、画像の非可逆圧縮や音声圧縮技術などでは離散フーリエ変換の考えが用いられている。信号に対して DFT (実装上ではFFT) を行い、人間が知覚しづらい周波数成分の情報を取り除くことで、正味の情報量を削減（圧縮）する。最も単純な方法では、IDFTの際にその取り除いた周波数情報（フーリエ係数）を0にすることにより、通常のIDFTを実現する。実装の単純化（計算の効率化）のために、実数演算のみで可能な離散コサイン変換を使って2次元情報を圧縮した例がJPEGである。
大きな数の掛け算の計算.
大きな数や多項式のにおいて、DFTを使う高速なアルゴリズムとして1971年にショーンハーゲ・ストラッセン法が発見された。数字や多項式の係数の列を畳み込み演算の対象のベクトルと見なす。するとそれぞれのベクトルの DFT を造り、その結果同士のベクトルを要素ごとに乗算した新たなベクトルを作り、それを逆変換することにより掛算の計算結果が得られる（つまり畳み込み定理を使う）。2007年に理論上はショーンハーゲ・ストラッセン法よりも高速なアルゴリズム（）が発見された。
別な定義.
離散フーリエ変換　formula_72
離散フーリエ逆変換　formula_73とするところもある（図解雑学　フーリエ変換）。
これは、フーリエ変換をformula_74、フーリエ逆変換をformula_75としたときの式である。