離散フーリエ変換の解説

離散フーリエ変換とは

(以下では離散フーリエ変換をDFTと記述します) DFTとは、「ある関数f(x)から、関数F(t)を求める変換」です。

ただし、f(x)もF(t)も連続した関数ではありません。離散した関数なので、どちらかというと数列に近いです。

F(t)は以下の式により定義されます。

Nはf(x)の範囲[0, N-1]のNです。tの範囲は[0, N-1]*1です。

なぜeが出てくるのか

フーリエ変換といえばcosとsinをガチャガチャするイメージがありますよね。それなのにDFTでは突如eが出てきます。これは、オイラーの公式が関係しています。オイラーの公式を使うと、eのiθ乗でcosθ+isinθを表すことができます。

離散フーリエ変換の実装

プログラムで実装するときは、長さNの配列を受け取り、長さNの配列を返す関数という形で実装されます。実際の実装は離散フーリエ変換をC++で実装したでしましたので、気になる方はごらんください。

変換の例

f(x) = x² (0 <= x < 10, xは整数) という関数をF(t)へ変換します。

F(0) = 285 + 0i
F(1) = 2.36068 + 153.884i
F(2) = -35.5279 + 68.8191i
F(3) = -42.3607 + 36.3271i
F(4) = -44.4721 + 16.246i
F(5) = -45 + 0i
F(6) = -44.4721 + -16.246i
F(7) = -42.3607 + -36.3271i
F(8) = -35.5279 + -68.8191i
F(9) = 2.36068 + -153.884i

normalization

離散フーリエ変換は実装により出力が異なる場合があります。それは、正規化係数、というものが違うからです。上の式ではF(t)には何もかけていません。しかし、実装によっては1/root(N)をかけている場合があります。Wolfram alphaがそうです。これはnormalizationが関係しているらしいです。どちらかが間違えているわけではないのでビックリしないでください。

*1:tは整数ならばいくつでもよく、[-N/2, N/2-1](Nは偶数)や[-(N-1)/2, (N-1)/2](Nは奇数)とする場合もあります。ですが今回は[0, N-1]とします