離散フーリエ変換

は有限長の離散時間信号をフーリエ変換様に周波数領域へ変換する操作である。

## 概要
離散フーリエ変換（以下、DFT）は有限長の離散時間信号をフーリエ変換様に周波数領域へ変換する操作である（⇒ #定義）。応用数学から信号処理まで、幅広く応用される（⇒ #応用）。

DFTは（計算機上で）高速フーリエ変換を使って高速に計算できる。

## 定義
k \in \left \{ 0, 1, \cdots, N-1 \right \} を離散変数とし、有限長 N \in \N^1 をもつ複素離散時間信号 x[n] の**離散フーリエ変換** X[k] は次式で定義される：

:X[k] = \sum_{n=0}^{N-1} x[n] \, e^{-i \omega_k n}, \quad \omega_k = \frac{2 \pi k}{N}


\omega_k は正規化角周波数と呼ばれ、X[k] は周波数スペクトルとも呼ばれる。

### 連続時間信号に対する定義
t \in \R^1 を連続変数、N \in \N^1 を任意定数とし、無限長の複素連続時間信号 f(x) の**離散フーリエ変換** F(t) は次式で定義される：
:F(t)= \sum_{x=0}^{N-1} f(x) \exp\left(-i\frac{2 \pi t x}{N} \right)
この定義においてDFTは複素関数 f(x) を複素関数 F(t) に写す写像と理解される。{x = 0,\dots,N-1}は**標本点**と呼ばれる。また、この変換を \mathcal{F}_N という記号で表し、
のように略記することが多い。

なお、この定義は1つめの定義において x[n] を f(n) で置き換えた（=有限長の離散時間信号を無限長の連続時間信号で置き換えた）ものである。この置き換えは総和 \Sigma

 の部分で f(n) から離散的に N 個の値を取り出している（=その場で x[n] を作っている）ため成立する。

以下では、フーリエ変換やサンプリングとの関係を説明するために、2つめの定義で説明している箇所がある。

## 表記
DFTの定義は別の表記法で表現されることもある。

### 回転因子
は定数 N \in \Z^+ で特徴づけられる複素指数定数 e^{- i 2\pi / N} である。 W あるいは W_N で略記される。

回転因子 W_N は定数 N \in \Z^+ で特徴づけられる、絶対値 1、偏角 2\pi / N, (0 \leq \text{arg} \leq 2\pi) の複素指数定数である。絶対値が 1 であるため、W_N の実数乗はこの複素指数を複素平面上で回転することと解釈できる。そのため実数変数（例: n）で累乗すれば W_N が周波数を規定する回転の信号を表現でき（例: y(n) = {W_N}^n
）、それを実数定数（例: k）で累乗すれば k 倍の周波数をもった信号を表現できる（例: y_k(n) = {W_N}^{kn}

）。

回転因子を用いて DFT の定義は以下の式でも表現される：
:X[k] = \sum_{n=0}^{N-1} x[n] \, {W_N}^{kn}



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

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

すなわち、複素関数ｆに対して、
:F(t)= \sum_{x=0}^{N-1} f(x) \exp\left(-i\frac{2 \pi t x}{N}\right)
により離散フーリエ変換を行い、それを逆変換したものをgとすると
:f(x)=g(x) \quad x = 0,\dots,N-1
は言えるが、その他の点でf(x)=g(x)が言えるとは限らない。これを**高周波の問題**、あるいは**[[折り返し雑音|エイリアシング(aliasing)]]**という。

### 選点直交性
h(t,x)=\exp(i2\pi t x/N) は内積
:(f,g)=\sum_{n=0}^{N-1} {f(n)}^{*} g(n) 
に関し、t,t'が整数のとき直交基底である。
:(h(t,x),h(t',x))=\sum_{n=0}^{N-1}
\exp \left(-i2\pi\frac{tn}{N}\right)
\exp \left(i2\pi\frac{t'n}{N}\right)
=N~\delta_{tt'}

\delta_{tt'}はクロネッカーのデルタ

### 畳み込み定理と相互相関定理
畳み込み定理は、離散フーリエ変換では本来成立しないものであるが、変換される関数（あるいは数列）を「周期関数（周期数列）とみなす」ことにより成立するのもである。

離散フーリエ変換の標本点を0,\dots,N-1とした場合、二つの（一般には複素数値の）関数f(x) と g(x) の畳み込みf*gは、まず関数f(x) と g(x)を周期化した関数\tilde{f}(x)、\tilde{g}(x)を次のように定め、
:\tilde{f}(x)=f(x-kN)、ただし0\le x-kNとなるよう整数kを決める
:\tilde{g}(x)=g(x-kN)、ただし0\le x-kNとなるよう整数kを決める
次のように定められる。
:(f*g)(x) = \sum_{n=0}^{N-1} \tilde{f}(n) \tilde{g}(x-n)
本来的な（周期化しない）畳み込みは、 \sum_{n=0}^{N-1} f(n) g(x-n)であるため、x-n  の部分で周期化した畳み込みと異なっている。

周期化した関数の離散フーリエ変換は、f(x)=\tilde{f}(x)（0\le x ）のため、元の関数の離散フーリエ変換と同じものになる。\mathcal{F}_N(\tilde{f})=\mathcal{F}_N(f)

周期関数の畳み込みを離散フーリエ変換したものは、それぞれの離散フーリエ変換の積になる(畳み込み定理)。
:\mathcal{F}_N(f*g)=\mathcal{F}_N(\tilde{f})\mathcal{F}_N(\tilde{g})=\mathcal{F}_N(f)\mathcal{F}_N(g)

離散フーリエ変換を数列に対して定義する場合も、同様に元の数列を周期数列に拡張し、周期化した畳み込みを定義して、同様な畳み込み定理を成立させることができる。

畳み込み和を直接定義式を用いて計算すると *O*(*N*&sup2;) の計算量が掛かる。しかし、上式より一旦、離散フーリエ変換をしてから掛算をして、そして逆変換で戻す方法もある。DFT の高速アルゴリズムである FFT を介してこのように計算すると *O*(*N*&nbsp;log&nbsp;*N*) の計算量で済む。

ただし、この方法により、逆変換で正しい値を算出できるのは標本点だけで、それ以外の点では正しい値を得られるとは限らない。また、「離散フーリエ変換の積」を「周期化した畳み込みの離散フーリエ変換」とみなして、それを逆変換して得られるものは、周期化した畳み込み関数（数列）であるため、標本点以外の点では周期化の影響を受ける。この誤差を**折り返し雑音**と言う。

また、二つの（一般には複素数値の）関数f(x)とg(x)の相互相関f\star gは以下のように定義される。

f,gが上記の周期性を持てば、

さらにfの関数値が実数であれば、\mathcal{F}_N(f)(-u)=\overline{\mathcal{F}_N(f)(u)}となる．ここで上線をつけた\bar{z}はzの複素共役を表す。

### 実数値関数の離散フーリエ変換

応用上は、実数値関数を対象とすることが多いが、fが実数値関数であるときには、

(\bar{z}はzの複素共役)。そのため出力(\mathcal{F}_Nf)(t)の半分(t>0)で全ての情報を持っていることになる。

## 逆離散フーリエ変換
は次で定義される：
:f(x) = \frac{1}{N} \sum_{t=0}^{N-1} F(t) \exp\left(i\frac{2\pi x t}{N} \right)

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

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

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

:F(u, v) = \sum_{x=0}^{M-1} \sum_{y=0}^{N-1} f(x,y) e^{- 2 \pi i \left(\frac{u x}{M} +\frac{v y}{N} \right) }

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

:f(x, y) = \frac{1}{M N} \sum_{u=0}^{M-1} \sum_{v=0}^{N-1} F(u, v) e^{2 \pi i \left(\frac{u x}{M} +\frac{v y}{N} \right) }

但し
*f(x, y)は2次元信号(例えば画像)であり、*f*の*x*列*y*行成分のことである。
*F(u, v)はf(x, y)の2次元周波数スペクトラムである。ここで*u*は*x*成分の周波数、*v*は*y*成分の周波数である。

2次元DFT は行列を用いて簡単に記述できる。

ここで
*F = \begin{bmatrix}
F(0, 0) & F(1, 0) & \ldots & F(M-1, 0) \\
F(0, 1) & F(1, 1) & \ldots & F(M-1, 1) \\
\vdots & \vdots & \ddots & \vdots \\
F(0, N-1) & F(1, N-1) & \ldots & F(M-1, N-1)
\end{bmatrix}
*W = \begin{bmatrix}
\omega_n^{0 \cdot 0} & \omega_n^{0 \cdot 1} & \ldots & \omega_n^{0 \cdot (N-1)} \\
\omega_n^{1 \cdot 0} & \omega_n^{1 \cdot 1} & \ldots & \omega_n^{1 \cdot (N-1)} \\
\vdots & \vdots & \ddots & \vdots \\
\omega_n^{(N-1) \cdot 0} & \omega_n^{(N-1) \cdot 1} & \ldots & \omega_n^{(N-1) \cdot (N-1)} \\
\end{bmatrix} (注:これはユニタリ行列)
*f = \begin{bmatrix}
f(0, 0) & f(1, 0) & \ldots & f(M-1, 0) \\
f(0, 1) & f(1, 1) & \ldots & f(M-1, 1) \\
\vdots & \vdots & \ddots & \vdots \\
f(0, N-1) & f(1, N-1) & \ldots & f(M-1, N-1)
\end{bmatrix}

### 行列の表記による変形

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

#F(u, v) = \sum_{x=0}^{M-1} \sum_{y=0}^{N-1} f(x,y) e^{ -2 \pi i ( \frac{u x}{M} + \frac{v y}{N} ) }
#F(u, v) = \sum_{x=0}^{M-1} \left[ \sum_{y=0}^{N-1} f(x,y) e^{ -2 \pi i \frac{v y}{N} } \right] e^{ -2 \pi i \frac{u x}{M} }
#F(u, v) = \sum_{x=0}^{M-1} \underbrace{ \left[ \sum_{y=0}^{N-1} f(x,y) e^{ -2 \pi i \frac{v y}{N} } \right] }_{ \mathcal{F}_y f(x, y) } e^{ -2 \pi i \frac{u x}{M} } 
#F_v = W f
#F(u, v) = \sum_{x=0}^{M-1} F_v(x, v) e^{- 2 \pi i \frac{u x}{M} }
#F = W F_v^{T}
#F = W f^T W

以下上式の 1 - 7 を解説すると、
# 2次元DFTの定義
# 式1から *e*-2&pi;*iux*/*M* を内側&sigma;から出した
# 内側の&sigma;は、信号f(x, y)の*y*の次元(\mathcal{F}_y\{f(x, y)\}と書いた行)の1次元DFTであることを示している
# 式3で示した、\mathcal{F}_y\{f(x, y)\}の行列表現
# 式3の注目箇所をF_v(x, v)で書き変えた - F_v(x, v)はf(x, y)の*x*行目の行の*v*番目の周波数。f(x, y)の1次元DFTの行を集めたものが*F**v*である。
# 式4の1次元DFTの行列表現と同様に、*F**v*Tを使って式5を表現した
# 式4を式6に代入した結果。ここで*W*は対称行列であるので*W*=*W*Tとした。

F_vの行はf(x, y)の*x*行目の行を1次元DFTしたものである。ゆえにF_vはf(x, y)の各行の1次元DFTした結果の行ベクトルを集めたものになる。*F*=*WF**v*Tにおける、*F**v*Tを後から掛ける作用素はF_vの列の1次元DFTしたものと同じと考えて良い。

つまり、2次元DFT（2次元フーリエ変換も同様だが）はf(x, y)を、各行ごとに1次元DFTし、その結果をさらに各列ごとに1次元DFTする事と等価である。ここで、1次元DFTの計算はFFTのアルゴリズムで高速に計算できる。そのため実用上は2次元DFTも、2次元FFTとして計算される。

## 他の変換との関係

### 一般化
離散フーリエ変換が持つ多くの性質は、\omega_{N} = e^{\frac{i2\pi}{N}} が1の原始N乗根(primitive root)であることのみに依存している。そのため、単位元の原始N乗根 \omega_N が存在するならば、複素数以外の環や体においても同様に離散フーリエ変換を定義することができる。離散フーリエ変換 (一般)を参照のこと。

## 例

表中で、

W=e^{-i\frac{2\pi}{N}}

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

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

この信号は*N*個の等間隔の点で標本化されて、*x*0, *x*1, *x*2, ... , *x**N*-1 の実数列になる。但し標本化の間隔を &Delta;*x*(=*T*/*N*) とすると *x**k*=*x*(*k*&nbsp;&Delta;*x*) である。これのDFTである *f*0, ..., *f**N*&minus;1 をFFTで計算できる。ただし標本化定理からこれの半分(*N*が偶数とすると、*f**N*/2 + 1, ..., *f**N*&minus;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年に理論上はショーンハーゲ・ストラッセン法よりも高速なアルゴリズム（:en:Fürer's algorithm）が発見された。

## 別な定義
離散フーリエ変換　F_n=\dfrac{1}{N} \sum^{N-1}_{k=0}f_k e^{-i \dfrac{2n \pi}{N}k}

離散フーリエ逆変換　f_k=\sum^{N-1}_{n=0} F_n e^{i \dfrac{2n \pi}{N} k}とするところもある（図解雑学　フーリエ変換）。

これは、フーリエ変換をF(\omega)=\int^{\infty}_{-\infty} f(x) e^{-i \omega x}dx、フーリエ逆変換をf(x)=\dfrac{1}{2 \pi} \int^{\infty}_{-\infty} F(\omega) e^{i \omega x} d\omegaとしたときの式である。

## 脚注

### 出典

## 参考文献
* E. O. Brigham, *The Fast Fourier Transform and Its Applications* (Prentice-Hall, Englewood Cliffs, NJ, 1988).
* A. V. Oppenheim, R. W. Schafer, and J. R. Buck, *Discrete-Time Signal Processing* (Prentice-Hall, 1999).
* S. W. Smith, The Scientist and Engineer's Guide to Digital Signal Processing, (California Technical Publishing, San Diego, 2nd edition, 1999)
* W. L. Briggs and van E. Henson: *The DFT - An Owner's Manual for the Discrete Fourier Transform* (SIAM, 1995).

* A. V. Oppenheim, R. W. Schafer, 伊達玄訳, *ディジタル信号処理* (コロナ社, 1978).
* 

## 関連項目
* 高速フーリエ変換(FFT)
* フーリエ級数
* フーリエ変換
* 離散時間フーリエ変換
* Z変換
* 直交関数系