Updated on 

離散フーリエ変換(DFT)

注意!

自分が理解するためのメモ書きのようなものなので、以下の記事↓の下位互換のような記事になってます。

また、ところどころ引用が入っております。

参考

離散フーリエ変換とは

離散フーリエ変換では、時系列データがN個な場合、区間Nで1/2周期とする周波数を基本に、0倍(定数成分)からN-1倍までのN個の周波数成分を算出します。

フーリエ変換は、「関数を無限次元のベクトルとみたときの基底変換」と言うことができる。このとき、時間を離散的に(とびとびの値)として表すと、これはただのベクトルの基底変換と言える。

つまり、与えられたベクトルを をもとに生成された基底に基底変換することが離散フーリエ変換である。


フーリエ変換:

  • 入力、出力が(複素)関数

離散フーリエ変換:

  • 入力、出力が(複素)ベクトル

導出

sin, cosの離散化

をサンプリングし、ベクトルとして表してみる。

※ベクトルの次元とサンプリング数を同じにするのは、逆変換したときに同じ形になるようにするため

sin

cos

行列にする

sin,cosの2つの周波数成分に分解

離散フーリエ変換(DFT)の前段階

入力ベクトルを の周波数成分にそれぞれ変換する。

二つの周波数成分からもとのベクトルを合成

逆離散フーリエ変換(IDFT)の前段階

の周波数成分から元のベクトルを合成する。 ※定義より、もとまった係数とサンプリングした三角関数ベクトルの積を合わせるともとのベクトルが再現できる

複素数形式で表示

とおいて新しい行列を考えると、 となる。

オイラーの公式

を用いて、先ほどの を書き直すと、

離散フーリエ変換(DFT)

に対して、入力ベクトル を作用させると、フーリエ変換後の複素ベクトルが得られる。

逆離散フーリエ変換(IDFT)

とおく。 より、

ここで、 であるので、

SC=0の検算

での検算.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from sympy import *

C = Matrix(
[[1,1,1,1],
[1,0,-1,0],
[1,-1,1,-1],
[1,0,-1,0]]
)

S = Matrix(
[[0,0,0,0],
[0,1,0,-1],
[0,0,0,0],
[0,-1,0,1]]
)

print(C @ S)

↓ 出力

1
2
3
4
5
Matrix([
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]])

とおくと、

以上より、 が得られる。

公式

離散フーリエ変換

の要素(回転因子) が、 と表されることを用いて、

逆離散フーリエ変換

であることを用いて、 よって、

普通のフーリエ変換の公式にならって、

と表記する場合もある。↑以降はこの表記を使います!

いよいよ高速化です!


このページはHexoStellarを使用して作成されました。