離散フーリエ変換

離散フーリエ変換（りさんフーリエへんかん、英語: discrete Fourier transform、DFT）とは離散群上のフーリエ変換であり、信号処理などで離散化されたデジタル信号の周波数解析などによく使われる。また偏微分方程式や畳み込み積分を効率的に計算するためにも使われる。離散フーリエ変換は（計算機上で）高速フーリエ変換(FFT)を使って高速に計算することができる。

n 個の複素数列 x₀, ..., x_n−1 に対して DFT することで n 個の複素数列 f₀, ..., f_n−1 が得られる。

$f_j = \sum_{k=0}^{n-1} x_k e^{-\frac{2 \pi i}{n} j k} \quad \quad j = 0, \dots, n-1$

ここで e はネイピア数、i は虚数単位 (i² = -1)で、πは円周率である。また、この変換を $\mathcal{F}$ という記号で表し、x = (x₀, ..., x_n−1), f = (f₀, ..., f_n−1) とおいて

$\mathbf{f} = \mathcal{F}(\mathbf{x})$

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

この逆変換にあたる逆離散フーリエ変換（英語: inverse discrete Fourier transform、IDFT）は

$x_k = \frac{1}{n} \sum_{j=0}^{n-1} f_j e^{\frac{2\pi i}{n} j k} \quad \quad k = 0,\dots,n-1.$

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

性質

離散フーリエ変換はフーリエ変換を離散群上で定義したものであるので、フーリエ変換#性質と同様の性質を持つ。

完全性

完全性 DFT は逆変換を持ち、次のような線形写像である。

$\mathcal{F}:\mathbf{C}^n \to \mathbf{C}^n$

但し、C は複素数の集合である。つまり、任意の n 次元複素ベクトルは、その DFT と IDFT としてn次元複素ベクトルを持つということである（n ≥ 0 とした）。

直交性

exp(2πi jk/n) は直交基底である。

$\sum_{k=0}^{n-1} \left(e^{ 2\pi ijk/n }\right) \left(e^{-2\pi ij'k/n}\right) =n~\delta_{jj'}$

δ_jk はクロネッカーのデルタ

パーセバルの定理

X_j, Y_j がそれぞれ x_k, y_kの DFT の時、Plancherelの定理から

$\sum_{k=0}^{n-1} x_k y^*_k = \frac{1}{n} \sum_{j=0}^{n-1} X_j Y^*_j$

ここで * は複素共役を表す。パーセバルの定理は Plancherelの定理の特殊なものであり、

$\sum_{k=0}^{n-1} |x_k|^2 = \frac{1}{n} \sum_{j=0}^{n-1} |X_j|^2.$

信号処理の観点から見ると、左辺は x_k のエネルギーを示している。また、|X_j|² はパワースペクトルと呼ぶように、右辺は全周波数のエネルギーを表しているといえる。つまり DFT の変換前後でのエネルギーの関係を示していると解釈できる。

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

x = x_j と y = y_k の畳み込みx*yは

$(\mathbf{x*y})_k = \sum_{j=0}^{n-1} x_j y_{k-j} \quad \quad k = 0,\dots,n-1$

ここでyは次のように循環するとする。

$y_{-j} = y_{n-j}\quad\quad~~~~~~~~~~ j = 0, ..., n-1$

循環畳み込みを DFT すると単なる積になる(畳み込み定理)。つまり$z_k = (\mathbf{x*y})_k$は

$Z_j=X_j Y_j \quad \quad~~~~~~~~~~ j = 0,\dots,n-1$

となる。ただし大文字のX, Y, Zはそれぞれ小文字のx, y, zの DFT である。なお、DFT の正規化係数が 1 ではない場合は上式に定数係数が付くことになる。

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

x_j と y_k の相互相関 z_k は以下のように定義される。

$z_k=(\mathbf{x\star y})_k = \sum_{j=0}^{n-1}x_j^*\,y_{j+k}$

ここでyは既述のように循環するとして、z_k の DFT は

$Z_k = X_k^*\,Y_k$

補間三角多項式との関係

この節は執筆中です。加筆、訂正して下さる協力者を求めています。

実数列の DFT

応用の上ではx₀, ..., x_n−1が実数のことが多いが、このとき、f_j = f_n−j^* である(*は複素共役)。そのため出力f₀, ..., f_n−1の半分で全ての情報を持っていることになる。このとき、直流成分 f₀ は純粋に実数で、ナイキスト成分 f_n/2 も実数であるので、複素数出力fの最初の半分とナイキスト成分というn個実数列によって DFT は冗長性なく完全に記述ができる。

一般化

この節は執筆中です。加筆、訂正して下さる協力者を求めています。

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) } \quad \quad u = 0, \dots, M-1; v = 0, \dots, N-1$

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

$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) } \quad \quad x = 0, \dots, M-1; y = 0, \dots, N-1$

但し

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

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

$F = W f^T W$

ここで

• $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 を行列計算によって以下のように変形できる。

1. $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} ) }$
2. $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} }$
3. $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} }$
4. $F_v = W f$
5. $F(u, v) = \sum_{x=0}^{M-1} F_v(x, v) e^{- 2 \pi i \frac{u x}{M} }$
6. $F = W F_v^{T}$
7. $F = W f^T W$

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

1. 2次元DFTの定義
2. 式1から e^-2πiux/M を内側σから出した
3. 内側のσは、信号$f(x, y)$のyの次元($\mathcal{F}_y\{f(x, y)\}$と書いた行)の1次元DFTであることを示している
4. 式3で示した、$\mathcal{F}_y\{f(x, y)\}$の行列表現
5. 式3の注目箇所を$F_v(x, v)$で書き変えた - $F_v(x, v)$は$f(x, y)$のx行目の行のv番目の周波数。$f(x, y)$の1次元DFTの行を集めたものがF_vである。
6. 式4の1次元DFTの行列表現と同様に、F_v^Tを使って式5を表現した
7. 式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$は$\exp(-2\pi i/n)$を表すものとする。

$x_j=\frac{1}{n}\sum_{k=0}^{n-1}f_k \omega_n^{-jk}$	$f_k=\sum_{j=0}^{n-1}x_j \omega_n^{jk}$
$a^j\,$	$\frac{1-a^n\omega_n^{kn}}{1-a\omega_n^k}$
${n-1 \choose j}\,$	$(1+\omega_n^{k})^{n-1}\,$

応用

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である。

偏微分方程式

この節は執筆中です。加筆、訂正して下さる協力者を求めています。

大きな数の掛け算の計算

大きな数や多項式の乗算のアルゴリズムで DFTを使う高速なアルゴリズムが知られている。（ただし現在は理論的により高速なアルゴリズムが見付かっている）数字や多項式の係数の列は畳み込み演算の対象のベクトルと見なす。するとそれぞれのベクトルを DFT して、その結果同士を掛けて、そして逆変換することで掛算の結果が得られる。（つまり畳み込み定理を使う）

参考文献

• 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)

関連項目

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