離散フーリエ変換

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

概要

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

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

定義

$k\in \left\{0,1,\cdots ,N-1\right\}$ を離散変数とし、有限長 $N\in \mathbb {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 \mathbb {R} ^{1}$ を連続変数、$N\in \mathbb {N} ^{1}$ を任意定数とし、無限長の複素連続時間信号 $f(x)$ の離散フーリエ変換 $F(t)$ は次式で定義される：

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

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

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

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

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

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

表記

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

回転因子

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

回転因子 $W_{N}$ は定数 $N\in \mathbb {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 tx}{N}}\right)$

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

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

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

選点直交性

$h(t,x)=\exp(i2\pi tx/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\leq x-kN<N$となるよう整数$k$を決める

${\tilde {g}}(x)=g(x-kN)$、ただし$0\leq x-kN<N$となるよう整数$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<0$ の部分で周期化した畳み込みと異なっている。

周期化した関数の離散フーリエ変換は、$f(x)={\tilde {f}}(x)$（$0\leq x<N$）のため、元の関数の離散フーリエ変換と同じものになる。${\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²) の計算量が掛かる。しかし、上式より一旦、離散フーリエ変換をしてから掛算をして、そして逆変換で戻す方法もある。DFT の高速アルゴリズムである FFT を介してこのように計算すると O(N log N) の計算量で済む。

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

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

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

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

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

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

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

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

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

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

逆離散フーリエ変換

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

$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 の正規化係数を両方とも $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 {ux}{M}}+{\frac {vy}{N}}\right)}$

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

$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)}$

但し

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

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

$F=Wf^{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 {ux}{M}}+{\frac {vy}{N}})}$
2. $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. $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. $F_{v}=Wf$
5. $F(u,v)=\sum _{x=0}^{M-1}F_{v}(x,v)e^{-2\pi i{\frac {ux}{M}}}$
6. $F=WF_{v}^{T}$
7. $F=Wf^{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}=e^{\frac {i2\pi }{N}}$ が1の原始N乗根(primitive root)であることのみに依存している。そのため、単位元の原始N乗根 $\omega _{N}$ が存在するならば、複素数以外の環や体においても同様に離散フーリエ変換を定義することができる。離散フーリエ変換 (一般)を参照のこと。

例

表中で、

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

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

別な定義

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

離散フーリエ逆変換　$f_{k}=\sum _{n=0}^{N-1}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).
• 菊池久和「1群-9編-6章 変換・解析技術」『知識の森』電子情報通信学会、2009年、1-20頁。https://www.ieice-hbkb.org/files/ad_base/view_pdf.html?p=/files/01/01gun_09hen_06m.pdf。 

関連項目

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