Signals and Systems-8. 고속 푸리에 변환(FFT Fast Fourier Transform)&웨이블렛 변환(Wavelet Transform)
09 Mar 2020 | Signals and Systems목차
1. 고속 푸리에 변환(FFT : Fast Fourier Transform)
지난 번에 DFT Matrix에 대해서 살펴봤었다. DFT Matrix는 하나도 0인 부분이 없기 때문에 Matrix가 dense하다. 선형대수학에서 Sparse Matrix라고 배웠었다. 행렬의 많은 영역이 0으로 채워져있는 행렬을 의미한다. 0인 부분이 있기 때문에, 구현 할 때, 이러한 부분을 지나치면서 연산을 수행하여 연산시간을 많이 줄일 수 있다. 그렇다면 DFT Matrix를 Sparse한 matrix의 곱으로 표현할 수 있다면 연산시간을 줄일 수 있을까? 라는 생각에서 나온게 FFT이다. FFT를 사용하면 시간이 $O(N^2)$에서 $O(nlogn)$으로 줄어든다.
2. 웨이블렛 변환(Wavelet Transform)
푸리에 변환후 그래프를 보면, 시간과 amplitude의 축으로 표현된 모습을 볼 수 있다. 이 뜻은 즉, 시간에 대한 정보를 잃어버린다는 것이다. 전체 신호를 봤을 때, 어떤 주파수가 어느정도 쓰였는지는 파악이 가능하지만, 이 신호의 t시간에 어떤 주파수가 어느정도 쓰였는지에 대한 정보는 알 수 없는 것이다. 이러한 시간에 대한 정보도 알 수 있도록 고안된 아이디어가 웨이블렛 변환이다. 참고링크1 참고링크2
참고링크1에서 시간분해능, 주파수분해능을 논하고, 윈도우에 따른, STFT의 예제가 참고링크2에 나온다. 참고링크2에서 3차원으로 푸리에변환의 그래프가 겹쳐나오는 모습이 마치 라플라스 변환에서 얘기했던것과 비슷한데, 나중에 어떤 연관이 있는지 알면 좋을것 같다.
STFT(Short Time Fourier Transform)에서 윈도우가 뜻하는 것은, 시간을 얼마나 크게두고 관측할지, 작게두고 관측할지의 기준이라고 얘기했다. 시간을 크게 둔다면, 짧은 시간동안 관측하는 것보다, 다양하게 변하는 신호를 관측할 수 있을 것이다. 다양하게 변하는 신호는 다양한 주파수로 구성이 되있을 것이므로, 어떤 주파수가 신호에 있는지 관측될 것이다. 그리고 시간을 작게둔다면 이와 반대로, 짧은 신호이므로, 이 신호를 구성하는 주파수의 다양성은 줄어듦으로, 관측되는 주파수의 범위는 줄어들게 될 것이다.
n차함수를 생각해보자, 그리고 x축이 점점 줄어든다고 생각해보자. 그러면 n차함수는 처음에는 아주 구불구불한 모습이었겠 지만, x축이 점점 줄어들면서 그냥 단순한 직선에 가까워 질 것이다. 구불구불한 모양을 표현하기 위해서는 다양한 주파수가 필요하고, 단순한 직선및 선을 표현하기 위해서는 몇 개의 주파수만 존재하면 될 것이다. 그렇기 때문에, 시간분해능을 높히면, 단순하게 몇 개의 주파수 밖에 관측이 되지 않기 때문에, 주파수분해능이 낮아지는 것이고, 주파수분해능을 높히면, 구불구불한 신호를 표현하기 위해서 주파수의 다양성은 높아지지만, 그만큼 시간을 많이보는 것이기 때문에, 특정 시간을 단정짓지 못하기 때문에, 시간분해능이 떨어지는 것이다.
이것을 해결하기 위해서 나온게 Wavelet Transform 이다. wavelet transform에 대해서도 추후에 알아보도록 할 에정이다. 오늘은 어떤 개념인지 짚고 넘어가려고 한다.