離散フーリエ変換

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

${\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}}$ という記号で表し、

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

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

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

回転因子

回転因子（かいてんいんし、（英: 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 0,\dots ,N-1}$とした場合、二つの（一般には複素数値の）関数${\displaystyle f(x)}$ と ${\displaystyle g(x)}$ の畳み込み${\displaystyle f*g}$は、まず関数${\displaystyle f(x)}$ と ${\displaystyle g(x)}$を周期化した関数${\displaystyle {\tilde {f}}(x)}$、${\displaystyle {\tilde {g}}(x)}$を次のように定め、

${\displaystyle {\tilde {f}}(x)=f(x-kN)}$、ただし${\displaystyle 0\leq x-kN<N}$となるよう整数${\displaystyle k}$を決める

${\displaystyle {\tilde {g}}(x)=g(x-kN)}$、ただし${\displaystyle 0\leq x-kN<N}$となるよう整数${\displaystyle k}$を決める

次のように定められる。

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

本来的な（周期化しない）畳み込みは、${\displaystyle \sum _{n=0}^{N-1}f(n)g(x-n)}$であるため、${\displaystyle x-n<0}$ の部分で周期化した畳み込みと異なっている。

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

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

${\displaystyle {\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) の計算量で済む。

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

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

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

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

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

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

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

行列の表記による変形

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}}$ が存在するならば、複素数以外の環や体においても同様に離散フーリエ変換を定義することができる。離散フーリエ変換 (一般)を参照のこと。

信号解析

信号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を使う高速なアルゴリズムとして1971年にショーンハーゲ・ストラッセン法が発見された。数字や多項式の係数の列を畳み込み演算の対象のベクトルと見なす。するとそれぞれのベクトルの DFT を造り、その結果同士のベクトルを要素ごとに乗算した新たなベクトルを作り、それを逆変換することにより掛算の計算結果が得られる（つまり畳み込み定理を使う）。2007年に理論上はショーンハーゲ・ストラッセン法よりも高速なアルゴリズム（en:Fürer's algorithm）が発見された。