離散フーリエ変換

離散フーリエ変換とは次式で定義される変換で、フーリエ変換に類似したものであり、信号処理などで離散化されたデジタル信号の周波数解析などによく使われる。また偏微分方程式や畳み込み積分の数値計算を効率的に行うためにも使われる。離散フーリエ変換は高速フーリエ変換を使って高速に計算することができる。

離散フーリエ変換とは、複素関数 を複素関数に写す写像であって、次の式で定義されるものを言う。

ここで、Nは任意の自然数、 はネイピア数、 は虚数単位 で、は円周率である。このとき、{}を標本点という。また、この変換を という記号で表し、 のように略記することが多い。

この逆変換にあたる逆離散フーリエ変換は

正規化係数や指数の符号は単なる慣習的なものであり、上式とは異なる式を扱うことがある。DFT と IDFT の差について、それぞれの正規化係数を掛けると 1 / //N// になることと、指数の符号が異符号であるということがだけが重要であり、根本的には同一の変換作用素と考えられる。DFT と IDFT の正規化係数を両方とも にすると、両方ともユニタリ作用素になる。理論的にはユニタリ作用素にするのが好ましいが、実用上数値計算を行うときは上式のように正規化係数を1つにまとめて、スケーリングを一度に行うことが多い。

1. 性質
-----

離散フーリエ変換はフーリエ変換に類似した変換であるので、フーリエ変換と類似した性質を持つ。

1.1. 完全性
--------

離散フーリエ変換においては、有限個の標本点しか使わないため、ある関数を離散フーリエ変換し、それを逆変換した場合に、標本点以外で元の関数と一致するとは限らない。

すなわち、複素関数ｆに対して、

により離散フーリエ変換を行い、それを逆変換したものをgとすると

は言えるが、その他の点でが言えるとは限らない。これを高周波の問題、あるいはエイリアシングという。

1.2. 選点直交性
----------

は内積

に関し、が整数のとき直交基底である。

はクロネッカーのデルタ

1.3. 畳み込み定理と相互相関定理
------------------

二つの関数 と の畳み込みは次のように定義される。

ただし、とは次のような周期性を持つとする。

周期関数の畳み込みを離散フーリエ変換したものは、それぞれの離散フーリエ変換の積になる。 つまり

畳み込み和を直接定義式を用いて計算すると //O// の計算量が掛かる。しかし、上式より一旦 DFT をしてから掛算をして、そして IDFT で戻す方法もある。DFT の高速アルゴリズムである FFT を介してこのように計算すると //O// の計算量で済む。

また、二つの関数との相互相関は以下のように定義される。

が上記の周期性を持てば、 さらにの関数値が実数であれば、となる．ここで上線をつけたはの複素共役を表す。

1.4. 補間三角多項式との関係
----------------

1.5. 実数値関数の離散フーリエ変換
-------------------

応用上は、実数値関数を対象とすることが多いが、が実数値関数であるときには、 。そのため出力の半分で全ての情報を持っていることになる。

2. 一般化
------

離散フーリエ変換が持つ多くの性質は、 が1の原始N乗根であることのみに依存している。そのため、単位元の原始N乗根 が存在するならば、複素数以外の環や体においても同様に離散フーリエ変換を定義することができる。離散フーリエ変換 を参照のこと。

3. 2次元での変換
----------

デジタル画像処理では2次元変換が画像の周波数成分を解析するのに使われる。

変換は以下のように定義される。

そして逆変換は次のようになる。

但し

は2次元信号であり、//f//の//x//列//y//行成分のことである。
はの2次元周波数スペクトラムである。ここで//u//は//x//成分の周波数、//v//は//y//成分の周波数である。2次元DFT は行列を用いて簡単に記述できる。

ここで



3.1. 行列の表記による変形
---------------

2次元DFT を行列計算によって以下のように変形できる。

以下上式の 1 - 7 を解説すると、

2次元DFTの定義
式1から //e//-2π//iux/////M// を内側σから出した
内側のσは、信号の//y//の次元の1次元DFTであることを示している
式3で示した、の行列表現
式3の注目箇所をで書き変えた - はの//x//行目の行の//v//番目の周波数。の1次元DFTの行を集めたものが//F////v//である。
式4の1次元DFTの行列表現と同様に、//F////v//Tを使って式5を表現した
式4を式6に代入した結果。ここで//W//は対称行列であるので//W//=//W//Tとした。の行はの//x//行目の行を1次元DFTしたものである。ゆえにはの各行の1次元DFTした結果の行ベクトルを集めたものになる。//F//=//WF////v//Tにおける、//F////v//Tを後から掛ける作用素はの列の1次元DFTしたものと同じと考えて良い。

つまり、2次元DFTはを、各行ごとに1次元DFTし、その結果をさらに各列ごとに1次元DFTする事と等価である。ここで、1次元DFTの計算はFFTのアルゴリズムで高速に計算できる。そのため実用上は2次元DFTも、2次元FFTとして計算される。

4. 離散フーリエ変換表
------------

表中で、



5. 応用
-----

DFTは多くの広い分野で利用されている。ここでは、その中の一部を示しているだけに過ぎない。これらの応用は高速フーリエ変換とその逆変換で高速に計算できることを前提としていて、定義通りにDFTを計算しているのではない。

5.1. 信号解析
---------

信号//x//を解析するのに使われる。ここで//t//は時間で[0,//T//]の範囲をとるものとする。例えば、音声信号の場合は、//x//は時刻//t//での空気の圧力を表現することになる。

この信号は//N//個の等間隔の点で標本化されて、//x//0, //x//1, //x//2, ... , //x////N//-1 の実数列になる。但し標本化の間隔を Δ//x// とすると //x////k//=//x// である。これのDFTである //f//0, ..., //f////N//−1 をFFTで計算できる。ただし標本化定理からこれの半分は冗長であるので捨てるか無視する。

DFT から得られる |//f//k|///N// は信号の周波数 //j/////T// 成分の振幅の半分の値であり、振幅スペクトルと呼ばれる。また、この偏角である arg はこの周波数成分の位相を表す。また、|//f//k|2はパワースペクトルと呼ばれ、この周波数成分のエネルギーを表している。

//f////k//は信号//x//のフーリエ級数の係数に相当するものと考えることができる。そのために、無限に広がるフーリエ級数計算を、有限のサンプル点に対しての DFT を使って近似するという形になる。連続信号の場合はこれをスペクトル推定と呼び、色々な推定法がある。)を使うことがよく行われる。)

5.2. データ圧縮
----------

信号処理の分野では周波数領域で処理をすることも少なくない。例えば、画像の非可逆圧縮や音声圧縮技術などでは離散フーリエ変換の考えが用いられている。信号に対して DFT  を行い、人間が知覚しづらい周波数成分の情報を取り除くことで、正味の情報量を削減する。最も単純な方法では、IDFTの際にその取り除いた周波数情報を0にすることにより、通常のIDFTを実現する。実装の単純化のために、実数演算のみで可能な離散コサイン変換を使って2次元情報を圧縮した例がJPEGである。

5.3. 偏微分方程式
-----------

5.4. 大きな数の掛け算の計算
----------------

大きな数や多項式の乗算アルゴリズムにおいて、DFTを使う高速なアルゴリズムとして1971年にショーンハーゲ・ストラッセン法が発見された。数字や多項式の係数の列を畳み込み演算の対象のベクトルdate=2021年7月}}と見なす。するとそれぞれのベクトルの DFT を造り、その結果同士のベクトルを要素ごとに乗算した新たなベクトルを作り、それを逆変換することにより掛算の計算結果が得られる。2007年に理論上はショーンハーゲ・ストラッセン法よりも高速なアルゴリズムが発見された。

6. 別な定義
-------

離散フーリエ変換　

離散フーリエ逆変換　 とするところもある。

これは、フーリエ変換を、フーリエ逆変換をとしたときの式である。

7. 脚注
-----

8. 参考文献
-------

E. O. Brigham, //The Fast Fourier Transform and Its Applications// .
A. V. Oppenheim, R. W. Schafer, and J. R. Buck, //Discrete-Time Signal Processing// .
S. W. Smith, [1], 
W. L. Briggs and van E. Henson: //The DFT - An Owner's Manual for the Discrete Fourier Transform// .
A. V. Oppenheim, R. W. Schafer, 伊達玄訳, //ディジタル信号処理// .

9. 関連項目
-------

高速フーリエ変換
フーリエ級数
フーリエ変換
Z変換
直交関数系
離散時間フーリエ変換