フーリエ変換と離散フーリエ変換

１次元フーリエ変換とは、１次元関数を、さまざまな周期の正弦関数（いわゆる三角関数のsin、位相は0でなくてもよい）に係数をかけたものの和と考え、その係数の集まりとして表現しようというものです。

まず簡単のため、有限長区間の繰り返しで表現される関数の場合で説明します。

一般に有限長区間の繰り返しで表現される、連続で滑らかな１次元関数は、区間の平均値である直流成分と、その区間を１周期とする正弦関数、その区間を２周期とする正弦関数、その区間を３周期とする正弦関数、...のそれぞれに係数（重み）づけした和（無限線形和）として書き表すことができます。

その係数は、さまざまな周波数成分がどれだけ含まれているかの量を示します。

特にその繰り返し区間が-∞から+∞まで広がった時、これは無限和というよりは、その極限である積分になります。

このような関数ｆ(x)のフーリエ変換F(ｗ)は、以下のように与えられます。

ただし本来はこれにある定数を掛けるべきなのですが、ここでは重要でないので省略します。

∫は積分範囲-∞から+∞までの定積分、exp()は自然対数の底e（2.71828...）を底とする指数関数、iは虚数単位です。

Ｆ(ｗ) ＝∫ｆ(x) * exp(-iwx) dx

フーリエ変換に対し、離散フーリエ変換（ＤＦＴ）を考えることができます。

すなわちｆ(x)の定義域をN個に離散化し、関数でなくN個の数字ｆ0、ｆ1、...、ｆ(N-1)を入力とし、やはりN個の数字Ｆ0、Ｆ1、...、Ｆ(N-1)を出力とする、N次元ベクトルからN次元ベクトルへの変換です。

数式では以下のように表現されます。

やはり定数との積は省略します。

Σはk=0からk=N-1までの級数、exp()は自然対数の底eを底とする指数関数、iは虚数単位です。

Ｆj ＝ Σｆk * exp(-2πijk/N)

Σは苦手だという人のためにもう少しわかりやすく書くと、以下の通りです。

Ｆj ＝ｆ0 +ｆ1 * exp(-2πij/N) +ｆ2 * exp(-2πij2/N) +ｆ3 * exp(-2πij3/N) + ・・・ + ｆ(N-1) * exp(-2πij(N-1)/N)

ここでｆ0の係数が１である理由は、k=０だとexpの中味が０となり、eの０乗は１だからです。

こういった例外的な係数の場合を無視すれば、あるjについてＦjを計算するためには、ｆの値とexpの値との乗算をN回行うことになります。

jも0からN-1まで動きますから、結局離散フーリエ変換全体としては、N**2（Nの二乗）回の乗算が必要です。

なお、expの値は、ｆの各値に関係なくあらかじめ計算できるので、定数としてメモリなどに用意しておくのが普通です。