離散フーリエ変換

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

離散フーリエ変換とは、複素関数 ${\displaystyle f($x)} $f(x)$を複素関数${\displaystyle F($t)} $F(t)$に写す写像であって、次の式で定義されるものを言う。

${\displaystyle F($k)=\sum _{n=0}^{N-1}f(x)\exp \left(-i{\frac {2\pi kx_{n}}{x_{N}-x_{0}}}\right)} $F(k)=\sum _{n=0}^{N-1}f(x)\exp \left(-i{\frac {2\pi kx_{n}}{x_{N}-x_{0}}}\right)$
ここで、kは波数、Nは標本数、 $e$$e$はネイピア数、$i$$i$ は虚数単位 ($i^{2}=-1$$i^{2}=-1$)で、$\pi$$\pi$は円周率である。標本番号 $n=\{0,\dots ,N-1\}$$n=\{0,\dots ,N-1\}$に対応する $x_{n}$$x_{n}$を標本点という。

また、この変換を ${\mathcal {F}}_{N}$${\mathcal {F}}_{N}$という記号で表し、


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

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

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

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

性質

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

完全性

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

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

${\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)という。

選点直交性

$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'}$はクロネッカーのデルタ

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

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

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

ただし、$f$ と$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)}  の相互相関$f\star g$ は以下のように定義される。


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


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


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

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

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


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


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

一般化

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

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

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

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

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

(四)$F_{v}=Wf$ 

(五)$F(u,v)=\sum _{x=0}^{M-1}F_{v}(x,v)e^{-2\pi i{\frac {ux}{M}}}$ 

(六)$F=WF_{v}^{T}$ 

(七)$F=Wf^{T}W$ 

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

(一)2次元DFTの定義

(二)式1から e^-2πiux/M を内側σから出した

(三)内側のσは、信号$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として計算される。

離散フーリエ変換表

表中で、

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

関連項目

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