logo

離散フーリエ変換行列 📂フーリエ解析

離散フーリエ変換行列

説明

離散フーリエ変換discrete Fourier transform, DFTはフーリエ変換を有限次元ベクトル、つまりデジタル信号に適用できるように変形したものである。離散フーリエ変換の定義は次の通りである。

次のように定義される線形変換 FN:CN→CN\mathcal{F}_{N} : \mathbb{C}^{N} \to \mathbb{C}^{N}を離散フーリエ変換(DFT)という。

FN(a)=a^,a^m=∑n=0N−1e−i2πmn/Nan(0≤m<N) \mathcal{F}_{N}(\mathbf{a}) = \hat{\mathbf{a}},\quad \hat{a}_{m}=\sum_{n=0}^{N-1}e^{-i2\pi mn /N} a_{n}\quad (0\le m < N)

ここでa=(a0,a1,…,aN−1)\mathbf{a} = (a_{0}, a_{1}, \dots, a_{N-1})、a^=(a^0,a^1,…,a^N−1)∈CN\hat{\mathbf{a}} = (\hat{a}_{0}, \hat{a}_{1}, \dots, \hat{a}_{N-1}) \in \mathbb{C}^{N}である。

言い換えると、この変換は行列の積として表すことができる。 F=[Fij]F = [F_{ij}]を離散フーリエ変換行列としよう。すると定義に従ってFFは次のようになる。

F=[111⋯11e−i2π/Ne−i4π/N⋯e−i2(N−1)π/N1e−i4π/Ne−i8π/N⋯e−i4(N−1)π/N⋮⋮⋮⋱⋮1e−i2(N−1)π/Ne−i4(N−1)π/N⋯e−i2(N−1)(N−1)π/N] F = \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & e^{-i2\pi/N} & e^{-i4\pi/N} & \cdots & e^{-i2(N-1)\pi/N} \\ 1 & e^{-i4\pi/N} & e^{-i8\pi/N} & \cdots & e^{-i4(N-1)\pi/N} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & e^{-i2(N-1)\pi/N} & e^{-i4(N-1)\pi/N} & \cdots & e^{-i2(N-1)(N-1)\pi/N} \end{bmatrix}

このとき、ω=e−i2π/N\omega = e^{-i2\pi/N}と表せば、

F=[111⋯11ωω2⋯ωN−11ω2ω4⋯ω2(N−1)⋮⋮⋮⋱⋮1ωN−1ω2(N−1)⋯ω(N−1)2] F = \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega & \omega^2 & \cdots & \omega^{N-1} \\ 1 & \omega^2 & \omega^4 & \cdots & \omega^{2(N-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{N-1} & \omega^{2(N-1)} & \cdots & \omega^{(N-1)^{2}} \end{bmatrix}

したがって、NN次元ベクトルx\mathbf{x}の離散フーリエ変換x^\hat{\mathbf{x}}は次の通りである。

x^=Fx \widehat{\mathbf{x}} = F \mathbf{x}

逆変換は定義に従って符号だけを変えればよい。ω‾=ei2π/N\overline{\omega} = e^{i2\pi/N}と表せば、

F−1=1N[111⋯11ω‾ω‾2⋯ω‾N−11ω‾2ω‾4⋯ω‾2(N−1)⋮⋮⋮⋱⋮1ω‾N−1ω‾2(N−1)⋯ω‾(N−1)2]=1NF‾ F^{-1} = \dfrac{1}{N} \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \overline{\omega} & \overline{\omega}^2 & \cdots & \overline{\omega}^{N-1} \\ 1 & \overline{\omega}^2 & \overline{\omega}^4 & \cdots & \overline{\omega}^{2(N-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \overline{\omega}^{N-1} & \overline{\omega}^{2(N-1)} & \cdots & \overline{\omega}^{(N-1)^{2}} \end{bmatrix} = \dfrac{1}{N} \overline{F}

2次元離散フーリエ変換

2次元のN×NN \times N行列X=[x1x2⋯xN]\mathbf{X} = [\mathbf{x}_{1}\quad \mathbf{x}_{2}\quad \cdots\quad \mathbf{x}_{N}]が与えられているとしよう。 2次元離散フーリエ変換はそれぞれの行と列に対して1次元DFTを適用するものである。 それぞれの列に対してDFTを適用することは、行列積の定義により次のようになる。 FX F \mathbf{X} それぞれの行に対してDFTを適用するには、行と列を入れ替えればよく、これは転置行列である。 (FXT)T=XFT (F \mathbf{X}^{\mathsf{T}})^{\mathsf{T}} = \mathbf{X} F^{\mathsf{T}} したがって、2次元離散フーリエ変換は次のようになる。 X^=FXFT \widehat{\mathbf{X}} = F \mathbf{X} F^{\mathsf{T}} 逆変換は次の通りである。 X=1N2F‾X^F‾T \mathbf{X} = \dfrac{1}{N^{2}} \overline{F} \widehat{\mathbf{X}} \overline{F}^{\mathsf{T}}

実装する