이산 푸리에 변환 행렬
📂푸리에해석 이산 푸리에 변환 행렬 설명 이산 푸리에 변환 discrete Fourier transform, DFT 은 푸리에변환 을 유한차원 벡터, 즉 디지털 신호에 적용할 수 있도록 변형한 것이다. 이산 푸리에 변환의 정의는 다음과 같다.
다음과 같이 정의되는 선형변환 F N : C N → C N \mathcal{F}_{N} : \mathbb{C}^{N} \to \mathbb{C}^{N} F N : C N → C N 이산 푸리에 변환(DFT) 이라 한다.
F N ( a ) = a ^ , a ^ m = ∑ n = 0 N − 1 e − i 2 π m n / N a n ( 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)
F N ( a ) = a ^ , a ^ m = n = 0 ∑ N − 1 e − i 2 πmn / N a n ( 0 ≤ m < N )
이때 a = ( a 0 , a 1 , … , a N − 1 ) \mathbf{a} = (a_{0}, a_{1}, \dots, a_{N-1}) a = ( a 0 , a 1 , … , a N − 1 ) a ^ = ( a ^ 0 , a ^ 1 , … , a ^ N − 1 ) ∈ C N \hat{\mathbf{a}} = (\hat{a}_{0}, \hat{a}_{1}, \dots, \hat{a}_{N-1}) \in \mathbb{C}^{N} a ^ = ( a ^ 0 , a ^ 1 , … , a ^ N − 1 ) ∈ C N
다시말해서 이 변환은 행렬 의 곱으로 나타낼 수 있다. F = [ F i j ] F = [F_{ij}] F = [ F ij ] F F F
F = [ 1 1 1 ⋯ 1 1 e − i 2 π / N e − i 4 π / N ⋯ e − i 2 ( N − 1 ) π / N 1 e − i 4 π / N e − i 8 π / N ⋯ e − i 4 ( N − 1 ) π / N ⋮ ⋮ ⋮ ⋱ ⋮ 1 e − i 2 ( N − 1 ) π / N e − i 4 ( N − 1 ) π / N ⋯ e − i 2 ( 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}
F = 1 1 1 ⋮ 1 1 e − i 2 π / N e − i 4 π / N ⋮ e − i 2 ( N − 1 ) π / N 1 e − i 4 π / N e − i 8 π / N ⋮ e − i 4 ( N − 1 ) π / N ⋯ ⋯ ⋯ ⋱ ⋯ 1 e − i 2 ( N − 1 ) π / N e − i 4 ( N − 1 ) π / N ⋮ e − i 2 ( N − 1 ) ( N − 1 ) π / N
이때 ω = e − i 2 π / N \omega = e^{-i2\pi/N} ω = e − i 2 π / N
F = [ 1 1 1 ⋯ 1 1 ω ω 2 ⋯ ω N − 1 1 ω 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}
F = 1 1 1 ⋮ 1 1 ω ω 2 ⋮ ω N − 1 1 ω 2 ω 4 ⋮ ω 2 ( N − 1 ) ⋯ ⋯ ⋯ ⋱ ⋯ 1 ω N − 1 ω 2 ( N − 1 ) ⋮ ω ( N − 1 ) 2
따라서 N N N x \mathbf{x} x x ^ \hat{\mathbf{x}} x ^
x ^ = F x
\widehat{\mathbf{x}} = F \mathbf{x}
x = F x
역변환 은 정의에 따라서 부호만 바꿔주면 된다. ω ‾ = e i 2 π / N \overline{\omega} = e^{i2\pi/N} ω = e i 2 π / N
F − 1 = 1 N [ 1 1 1 ⋯ 1 1 ω ‾ ω ‾ 2 ⋯ ω ‾ N − 1 1 ω ‾ 2 ω ‾ 4 ⋯ ω ‾ 2 ( N − 1 ) ⋮ ⋮ ⋮ ⋱ ⋮ 1 ω ‾ N − 1 ω ‾ 2 ( N − 1 ) ⋯ ω ‾ ( N − 1 ) 2 ] = 1 N F ‾
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}
F − 1 = N 1 1 1 1 ⋮ 1 1 ω ω 2 ⋮ ω N − 1 1 ω 2 ω 4 ⋮ ω 2 ( N − 1 ) ⋯ ⋯ ⋯ ⋱ ⋯ 1 ω N − 1 ω 2 ( N − 1 ) ⋮ ω ( N − 1 ) 2 = N 1 F
2차원 이산 푸리에 변환 2차원 N × N N \times N N × N X = [ x 1 x 2 ⋯ x N ] \mathbf{X} = [\mathbf{x}_{1}\quad \mathbf{x}_{2}\quad \cdots\quad \mathbf{x}_{N}] X = [ x 1 x 2 ⋯ x N ] 행렬 곱 의 정의에 의해 다음과 같다.
F X
F \mathbf{X}
F X 전치행렬 이다.
( F X T ) T = X F T
(F \mathbf{X}^{\mathsf{T}})^{\mathsf{T}} = \mathbf{X} F^{\mathsf{T}}
( F X T ) T = X F T X ^ = F X F T
\widehat{\mathbf{X}} = F \mathbf{X} F^{\mathsf{T}}
X = F X F T X = 1 N 2 F ‾ X ^ F ‾ T
\mathbf{X} = \dfrac{1}{N^{2}} \overline{F} \widehat{\mathbf{X}} \overline{F}^{\mathsf{T}}
X = N 2 1 F X F T
구현하기 