Discrete Fourier Transform에 대하여
18 Jun 2021 | signal-analysis이산 푸리에 변환에 대해 알아보도록 하겠습니다.
Fourier transform
푸리에 변환이란 임의의 입력 신호를 다양한 주파수를 갖는 주기함수들의 합으로 분해하여 표현한 것입니다. 여러 주기함수가 혼합되어 있는 신호를 봤을 땐 신호의 특성을 살피기 어려우나, 푸리에 변환은 아래 그림처럼 혼합된 신호(빨간색)을 여러 종류의 주파수를 갖는 주기함수들(파란색)로 분해할 수 있기 때문에, 신호의 특징을 살펴볼 수 있습니다.
푸리에 변환의 수학적 의미는 Time Domain(x축 : 시간, y축 : 진폭)을 Frequency Domain으로 변환(x축 : Frequency, y축 : 푸리에 변환 결과에 해당되는 계수)하는 것입니다. 아래는 일반 신호를 푸리에 변환한 결과(Spectogram)를 나타냅니다. Input 신호는 두 개의 주파수가 메인인 신호의 합성파입니다. 이처럼 푸리에 변환을 통해서 raw 데이터에서 볼 수 없는 특징을 찾아낼 수 있습니다.
일반적으로 Audio나 EEG 등 signal 데이터는 연속적일 수 없습니다. 왜냐하면, 기계를 통해 신호가 수집(sampling)이 되기 때문에 이산(Discrete)적인 특징을 띄고 있습니다. 예를 들어 256Hz로 샘플링 되는 신호라는 뜻은 1초에 256개 신호 sample을 수집한다는 뜻입니다.
따라서, 이산적인 특징을 다룰 수 있는 이산 푸리에 변환(Discrete Fourier Transform)을 사용합니다. 연속 푸리에 변환과 이산 푸리에 변환식은 아래와 같습니다.
\[\hat{f}(\xi) = \int_{\mathbf{R}^d} f(x)e^{2\pi ix\xi} \,dx \tag{1}\]Concept of Fourier Transform
푸리에 변환은 위에서 언급했듯이 여러 종류의 주파수를 갖는 함수로 분해하는 과정이라 하였습니다. 이 부분에 관한 의미를 2가지 측면으로 살펴보겠습니다. 푸리에 변환의 파동적인 측면에서의 개념(기본적 개념)과 선형대수적 개념입니다.
1. 푸리에 변환의 기본적 개념
푸리에 변환은 위에서 언급했듯이 여러 종류의 주파수를 갖는 함수로 분해하는 과정이라고 하였습니다. 어떤 방식으로 분해하는 걸까요 ? 이를 이해하기 위해선 오일러 공식을 알아야 합니다. 오일러 공식에 따르면, 복소지수함수 $e^{ix}$ 는 코사인과 사인의 합으로 구성됩니다. 오일러 공식을 좌표평면위에 나타나면 <그림 4.>와 같습니다. 이는 반지름이 1인 단위 원 위에 각 $x$ (그림에선 $\omega$) 성분을 가진 점으로 표현됩니다.
\[e^{ix} = cost + isinx \tag{3}\]
<수식 1.>와 <수식 2.>를 보면 오일러 공식 부분을 대입해서 다시 쓰면 아래와 같습니다(이산 푸리에 변환에 대해서만 진행).
\[\mathnormal{X_k} = \sum_{n=0}^{N-1}x_n \cdot [cos(\frac{2\pi}{N}kn) - isin(\frac{2\pi}{N}kn)] \tag{4}\]<그림 4.>에서 단위 원 위에 있는 점이 일정한 속도로 움직이고, 이를 time domain 위에 그림을 그리면 <그림 5.>의 1번째 그림이 됩니다(1번째 그림이 단위 원이라고 가정한 것입니다). 여기서 속도를 결정하는 것이 바로 주파수에 해당됩니다. 즉 $\frac{2 \pi k}{N}$ 가 크면 클수록 원 위의 점이 빨리 움직이게 됩니다. <그림 5.>에서의 2번째그림에서 4번째 그림으로 갈수록 점의 움직임이 빨라지는 것을 볼 수 있는데, 이는 아래로 갈수록 큰 주파수를 가지는 것을 뜻합니다.
마지막으로 <수식 4.>에서 $x_n$ 은 원의 반지름을 결정하는 요소입니다. 즉, $x_n$ 이 작을수록 작은 크기의 원 위의 점의 움직임에 해당되는 것입니다. <그림 5>에서 4번째 그림에 해당되는 것입니다.
즉 푸리에 변환이란 <그림 5.>의 마지막 그림처럼 여러 크기와 주파수를 가진 복소수 함수의 분해를 뜻하는 것입니다. 마지막 그림에서 그려지는 신호는 결국 1~4번째 단일 신호들의 합으로 표현되는 것과 마찬가지입니다.
푸리에 변환의 결과인 $\mathnormal{X_k}$ 가 뜻하는 건 이산화된 신호 $x_1, \cdots, x_n$ 인 각 지점에서 $\frac{2\pi k}{N}$ 주파수를 가진 주기함수를 얼마만큼 가지고 있느냐를 계산한 후 합한 것입니다. 즉, 전체적으로 해당 주파수를 가진 부분을 신호가 얼마만큼 가지고 있는지에 대한 정도를 하나의 계수로 표현한 것입니다. 따라서 <그림 3.> 에서 y축은 해당 주파수를 가진 주기함수가 이 신호에 얼마만큼 들어있는지에 대한 양을 나타내는 것입니다.
2. 푸리에 변환의 선형대수적 개념
다음으론 푸리에 변환의 선형대수적 개념에 대해 살펴보도록 하겠습니다. 이를 살펴보기 위해선 선형대수 지식이 필요합니다. 선형대수에서 N차원에서 N개의 직교기저가 있다면 이들 기저의 선형결합으로 N차원 위의 모든 점을 표현할 수 있습니다. 예를 들어 3차원 공간에서, 3개의 직교기저 (1,0,0), (0,1,0), (0,0,1)의 선형결합으로 3차원 위의 모든 점을 표현할 수 있습니다.
\[(x, y, z) = x(1, 0, 0) + y(0,1,0) + z(0,0,1) \tag{5}\]이산 푸리에 변환의 행렬 표현을 보면, 선형대수적인 개념을 확인할 수 있습니다. <수식 2.>와 <수식 4.>에서 k=4까지의 이산 푸리에 변환 행렬은 아래와 같습니다.
마찬가지로, 푸리에변환도 cosine과 sine로 구성된 직교 주기 함수의 선형결합으로, 신호가 N개로 이뤄진 벡터라면, cosine과 sine로 구성된 N차원의 선형결합으로 분석하고자 하는 신호를 표현한 것입니다. 이산 푸리에 변환을 행렬로 표현하는 과정을 보면 쉽게 이해하실 수 있습니다.
전체 신호의 길이가 N인 이산 신호 $x_n$ 와 길이가 N인 주파수 성분 $\mathnormal X_k$ 에 대하여, <수식 2.>를 전개해보면 아래와 같습니다.
\[\mathnormal X_0 = x_0e^{-i\frac{2 \pi 0}{N}0} + x_1e^{-i\frac{2 \pi 0}{N}1} + x_2e^{-i\frac{2 \pi 0}{N}2} + \cdots + x_{N-1}e^{-i\frac{2 \pi 0}{N}(N-1)} \tag{6}\] \[\mathnormal X_1 = x_0e^{-i\frac{2 \pi 1}{N}0} + x_1e^{-i\frac{2 \pi 1}{N}1} + x_2e^{-i\frac{2 \pi 1}{N}2} + \cdots + x_{N-1}e^{-i\frac{2 \pi 1}{N}(N-1)} \tag{7}\]$w = e^{-i\frac{2 \pi}{N}}$ 이라 한다면, 아래와 같이 선형 결합의 행렬 형태로 표현할 수 있습니다.
\[\begin{bmatrix} \ X_0 \\ X_1 \\ \vdots \\ X_{N-1}\end{bmatrix} = \begin{bmatrix} \ 1 & 1 & 1 & \cdots & 1 \\ \ 1 & w^1 & w^2 &\cdots & w^{N-1} \\ \ \vdots & \vdots & \vdots & \ddots & \vdots \\ \ 1 & w^{N-1} & w^{(N-1)2} & \cdots & w^{(N-1)(N-1)}\end{bmatrix} \begin{bmatrix} \ x_0 \\ x_1 \\ \vdots \\ x_{N-1} \\\end{bmatrix} \tag{8}\]행렬의 선형 결합은 행렬 곱으로서 생각한다면, ‘내적’의 의미로도 해석할 수 있습니다. 내적의 의미는 곱해지는 벡터가 행렬의 열벡터와 얼마만큼 닮았는가를 의미하는데, 특정 주파수의 함량이 높다라는 건 해당 주파수와 이산 신호가 유사함을 높다라는 것을 뜻합니다.
이상으로 포스팅을 마치겠습니다.
- 푸리에 변환 참고, https://ralasun.github.io/deep%20learning/2021/02/15/gcn/
- 선형대수와 푸리에 변환 - 공돌이의 수학노트, https://angeloyeo.github.io/2020/11/08/linear_algebra_and_Fourier_transform.html
- Fourier Transform, https://ratsgo.github.io/speechbook/docs/fe/ft
- Discrete Fourier Transform, https://en.wikipedia.org/wiki/Discrete_Fourier_transform
Comments