離散フーリエ変換

物性理論におけるDFT「密度汎関数理論」とは異なります。

離散フーリエ変換（りさんフーリエへんかん、（英: discrete Fourier transform, DFT）は有限長の離散時間信号をフーリエ変換様に周波数領域へ変換する操作である^[1]。

概要

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

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

定義

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

${\displaystyle X[k]=\sum _{n=0}^{N-1}x[n]\,e^{-i\omega _{k}n},\quad \omega _{k}={\frac {2\pi k}{N}}}$

${\displaystyle \omega _{k}}$ は正規化角周波数と呼ばれ^[3]、${\displaystyle X[k]}$ は周波数スペクトルとも呼ばれる。

連続時間信号に対する定義

${\displaystyle t\in \mathbb {R} ^{1}}$ を連続変数、${\displaystyle N\in \mathbb {N} ^{1}}$ を任意定数とし、無限長の複素連続時間信号 ${\displaystyle f(x)}$ の離散フーリエ変換 ${\displaystyle F(t)}$ は次式で定義される：

${\displaystyle F(t)=\sum _{x=0}^{N-1}f(x)\exp \left(-i{\frac {2\pi tx}{N}}\right)}$

この定義においてDFTは複素関数 ${\displaystyle f(x)}$ を複素関数 ${\displaystyle F(t)}$ に写す写像と理解される。{${\displaystyle x=0,\dots ,N-1}$}は標本点と呼ばれる。また、この変換を ${\displaystyle {\mathcal {F}}_{N}}$ という記号で表し、

${\displaystyle F={\mathcal {F}}_{N}(f)}$

のように略記することが多い。

なお、この定義は1つめの定義において ${\displaystyle x[n]}$ を ${\displaystyle f(n)}$ で置き換えた（=有限長の離散時間信号を無限長の連続時間信号で置き換えた）ものである。この置き換えは総和 ${\displaystyle \Sigma }$ の部分で ${\displaystyle f(n)}$ から離散的に ${\displaystyle N}$ 個の値を取り出している（=その場で ${\displaystyle x[n]}$ を作っている）ため成立する。

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

表記

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

回転因子

回転因子（かいてんいんし、（英: twiddle factor）は定数 ${\displaystyle N\in \mathbb {Z} ^{+}}$ で特徴づけられる複素指数定数 ${\displaystyle e^{-i2\pi /N}}$ である^[2]。 ${\displaystyle W}$ あるいは ${\displaystyle W_{N}}$ で略記される。

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

回転因子を用いて DFT の定義は以下の式でも表現される^[2]：

${\displaystyle X[k]=\sum _{n=0}^{N-1}x[n]\,{W_{N}}^{kn}}$

性質

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

完全性

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

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

${\displaystyle F(t)=\sum _{x=0}^{N-1}f(x)\exp \left(-i{\frac {2\pi tx}{N}}\right)}$

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

${\displaystyle f(x)=g(x)\quad x=0,\dots ,N-1}$

は言えるが、その他の点で${\displaystyle f(x)=g(x)}$が言えるとは限らない。これを高周波の問題、あるいはエイリアシング(aliasing)という。

選点直交性

${\displaystyle h(t,x)=\exp(i2\pi tx/N)}$ は内積

${\displaystyle (f,g)=\sum _{n=0}^{N-1}{f(n)}^{*}g(n)}$

に関し、${\displaystyle t,t'}$が整数のとき直交基底である。

${\displaystyle (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'}}$

${\displaystyle \delta _{tt'}}$はクロネッカーのデルタ

畳み込み定理と相互相関定理

二つの（一般には複素数値の）関数${\displaystyle f(x)}$ と ${\displaystyle g(x)}$ の畳み込み${\displaystyle f*g}$は次のように定義される。

${\displaystyle (f*g)(x)=\sum _{n=0}^{N-1}f(n)g(x-n)}$

ただし、${\displaystyle f}$と${\displaystyle g}$は次のような周期性を持つとする。

${\displaystyle {\begin{aligned}f(x+N)&=f(x)\\g(x+N)&=g(x)\end{aligned}}}$

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

${\displaystyle {\mathcal {F}}_{N}(f*g)={\mathcal {F}}_{N}(f){\mathcal {F}}_{N}(g)}$

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

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

${\displaystyle h(x)=(f\star g)(x)=\sum _{n=0}^{N-1}f(n)g(x+n)}$

${\displaystyle f,g}$が上記の周期性を持てば、

${\displaystyle ({\mathcal {F}}_{N}h)(u)=({\mathcal {F}}_{N}(f\star g))(u)={\mathcal {F}}_{N}(f)(-u){\mathcal {F}}_{N}(g)(u)}$

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

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

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

${\displaystyle ({\mathcal {F}}_{N}f)(-t)={\overline {({\mathcal {F}}_{N}f)(t)}}}$

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

逆離散フーリエ変換

逆離散フーリエ変換（ぎゃくりさんフーリエへんかん、（英: inverse discrete Fourier transform, IDFT）は次で定義される：

${\displaystyle f(x)={\frac {1}{N}}\sum _{t=0}^{N-1}F(t)\exp \left(i{\frac {2\pi xt}{N}}\right)}$

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

2次元での変換

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

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

${\displaystyle F(u,v)=\sum _{x=0}^{M-1}\sum _{y=0}^{N-1}f(x,y)e^{-2\pi i\left({\frac {ux}{M}}+{\frac {vy}{N}}\right)}}$

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

${\displaystyle f(x,y)={\frac {1}{MN}}\sum _{u=0}^{M-1}\sum _{v=0}^{N-1}F(u,v)e^{2\pi i\left({\frac {ux}{M}}+{\frac {vy}{N}}\right)}}$

但し

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

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

${\displaystyle F=Wf^{T}W}$

ここで

• ${\displaystyle 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}}}$
• ${\displaystyle 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}}}$ (注:これはユニタリ行列)
• ${\displaystyle 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 を行列計算によって以下のように変形できる。

1. ${\displaystyle F(u,v)=\sum _{x=0}^{M-1}\sum _{y=0}^{N-1}f(x,y)e^{-2\pi i({\frac {ux}{M}}+{\frac {vy}{N}})}}$
2. ${\displaystyle F(u,v)=\sum _{x=0}^{M-1}\left[\sum _{y=0}^{N-1}f(x,y)e^{-2\pi i{\frac {vy}{N}}}\right]e^{-2\pi i{\frac {ux}{M}}}}$
3. ${\displaystyle F(u,v)=\sum _{x=0}^{M-1}\underbrace {\left[\sum _{y=0}^{N-1}f(x,y)e^{-2\pi i{\frac {vy}{N}}}\right]} _{{\mathcal {F}}_{y}f(x,y)}e^{-2\pi i{\frac {ux}{M}}}}$
4. ${\displaystyle F_{v}=Wf}$
5. ${\displaystyle F(u,v)=\sum _{x=0}^{M-1}F_{v}(x,v)e^{-2\pi i{\frac {ux}{M}}}}$
6. ${\displaystyle F=WF_{v}^{T}}$
7. ${\displaystyle F=Wf^{T}W}$

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

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

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

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

他の変換との関係

一般化

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

例

表中で、

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

時間領域	周波数領域	備考
${\displaystyle f(x)={\frac {1}{N}}\sum _{k=0}^{N-1}F(k)W^{-kx}}$	${\displaystyle F(t)=\sum _{n=0}^{N-1}f(n)W^{tn}}$	IDFT,DFTのWを使った定義
${\displaystyle f(x)}$	${\displaystyle F(t)}$	定義
${\displaystyle g(x)}$	${\displaystyle G(t)}$	定義
${\displaystyle af(x)+bg(x)}$	${\displaystyle aF(t)+bG(t)}$	線形性
${\displaystyle f(x){e^{i{\frac {2\pi {mx}}{N}}}}}$	${\displaystyle F(t-m)}$	時間軸変調、周波数軸移動
${\displaystyle f(x-a)}$	${\displaystyle W^{at}F(t)}$	時間軸移動（正）
${\displaystyle f(x+a)}$	${\displaystyle W^{-at}F(t)}$	時間軸移動（負）
${\displaystyle \sum _{m=0}^{N-1}f(m)g(x-m)}$	${\displaystyle F(t)G(t)}$	時間軸畳み込み、周波数軸積
${\displaystyle f(x)g(x)}$	${\displaystyle {\frac {1}{N}}\sum _{m=0}^{N-1}F(m)G(t-m)}$	時間軸積、周波数軸畳み込み
${\displaystyle {\overline {f(x)}}}$	${\displaystyle {\overline {F(N-t)}}}$	時間軸共役、周波数軸反転
${\displaystyle {\overline {f(N-x)}}}$	${\displaystyle {\overline {F(t)}}}$	時間軸反転、周波数軸共役
${\displaystyle Re(f(x))}$	${\displaystyle {\frac {1}{2}}(F(t)+{\overline {F(N-t)}})}$	時間軸実部、周波数軸偶関数
${\displaystyle Im(f(x))}$	${\displaystyle {\frac {1}{2i}}(F(t)-{\overline {F(N-t)}})}$	時間軸虚部、周波数軸奇関数
${\displaystyle {\frac {1}{2}}(f(x)+{\overline {f(N-x)}})}$	${\displaystyle Re(F(t))}$	時間軸偶関数、周波数軸実部
${\displaystyle {\frac {1}{2i}}(f(x)-{\overline {f(N-x)}})}$	${\displaystyle Im(F(t))}$	時間軸奇関数、周波数軸虚部
${\displaystyle a^{x}\,}$	${\displaystyle {\frac {1-a^{N}{W}^{tx}}{1-{a}W^{t}}}}$	べき乗

応用

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

信号解析

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

この信号はN個の等間隔の点で標本化されて、x₀, x₁, x₂, ... , x_N-1 の実数列になる。但し標本化の間隔を Δx(=T/N) とすると x_k=x(k Δx) である。これのDFTである f₀, ..., f_N−1 をFFTで計算できる。ただし標本化定理からこれの半分(Nが偶数とすると、f_{N/2 + 1}, ..., f_N−1)は冗長であるので捨てるか無視する。

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

f_kは信号x(t)のフーリエ級数の係数に相当するものと考えることができる。そのために、無限に広がるフーリエ級数計算を、有限のサンプル点に対しての DFT を使って近似するという形になる。連続信号の場合はこれをスペクトル推定(spectral estimation)と呼び、色々な推定法がある。(例えば、DFT が有限サンプル点を扱うことに起因するスペクトル漏れの弊害を少しでも和らげるために窓関数(窓))を使うことがよく行われる。)

データ圧縮

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

大きな数の掛け算の計算

→詳細は「ショーンハーゲ・ストラッセン法」および「en:Fürer's algorithm」を参照

大きな数や多項式の乗算アルゴリズム（英語版）において、DFTを使う高速なアルゴリズムとして1971年にショーンハーゲ・ストラッセン法が発見された。数字や多項式の係数の列を畳み込み演算の対象のベクトル^{[要曖昧さ回避]}と見なす。するとそれぞれのベクトルの DFT を造り、その結果同士のベクトルを要素ごとに乗算した新たなベクトルを作り、それを逆変換することにより掛算の計算結果が得られる（つまり畳み込み定理を使う）。2007年に理論上はショーンハーゲ・ストラッセン法よりも高速なアルゴリズム（en:Fürer's algorithm）が発見された。

別な定義

離散フーリエ変換　${\displaystyle F_{n}={\dfrac {1}{N}}\sum _{k=0}^{N-1}f_{k}e^{-i{\dfrac {2n\pi }{N}}k}}$

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

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