왜 FFT를 사용하는가? DFT를 통해서 f(x)의 Frequency Spectrum을 볼 수 있다. 일반적으로 DFT를 수행하기 위해 몇번의 계산을 거쳐야 할까. 이 식을 계산하려면 n번 더해야 한다. 이러한 계산을 다시 n번만큼 해줘야 최종 DFT를 얻는다. 즉, n^2번의 계산이 필요한 셈인데, 만약 데이터 갯수가 1천개라면, 백만번의 계산을 해야한다는 결론이 나온다. Fast Fourier Transform(FFT)를 사용하는 이유는 이 계산 수의 절반이하 수준의 계산수를 통해 Aliasing을 피하면서 같은 결과를 얻을 수 있기 때문이다. Aliasing이라는 것은, 차이가 모호해지는 것 정도로 이해하고 있으면 된다. 이유는 간단하다. Sampling의 빈도가 낮아진다는 것은 곧, DFT의 기반..

개요 어떠한 경우에는 함수 대신 Sampling 된 데이터에 대해서 Fourier Transform을 해야할 경우가 있다. 이때 사용하는 것이 Discrete Fourier Transform이다. 유도 먼저 f(x)가 Periodic 하다고 가정하자. 편의상 Period를 2π로 잡자. 그리고 이 Period에서 N만큼의 Sample을 얻었다고 하자. 그러면 어떤 Sample Point x_k는 다음과 같이 표시할 수 있다. 즉, f(x)가 이러한 Points에 대하여 Sampling 되었다고 할 수 있다. 위 식은 Complex Trigonometric Polynomial q(x)를 나타낸 것으로, f(x)를 이러한 q(x)의 형태로 나타낼 수 있다고 했을때, x 대신 x_k를 넣어 식을 다시 써보면,..

Existence f(x)가 x축에서 Absolutely Integrable하고, 모든 유한한 구간에서 Piecewise Continuous할때, f(x)의 Fourier Transform이 존재한다는 것이 Theorem of Existence of the Fourier Transform이다. Piecewise Continuous에 대한 내용: http://blastic.tistory.com/94 Absolutely Integrable에 대해서는 아래 링크를 참조하기 바란다. (링크: https://ccrma.stanford.edu/~jos/st/Existence_Fourier_Transform.html) Absolutely Integrable을 간단히 설명하면, f(x)를 절대값으로 씌운 것, 즉 |f..

Complex Fourier Integral 이전의 포스트에서 다룬 Fourier Cosine and Sine Transform은 실수 범위에 대한 Transform이다. 이제 Fourier Integral을 토대로, 복소수 범위에 대한 Transform인 Fourier Transform을 얻어 보려고 한다. 일단, 그 전에 Complex Fourier Integral을 얻어야 한다. 차근차근 식을 써 내려가 보도록 하겠다. 먼저 Fourier Integral을 다시 가져와 보면, 여기서 A(w)와 B(w)를 f(x)에 다시 집어 넣고 식을 다시쓰면, 위와 같이 정리할 수 있다. 위의 Integral을 보면, w에 관한 Integral의 경우 아래끝이 0임을 볼 수 있는데, 이것을 -∞으로 확장할 것이다..

개요 Integral Transform 이란 주어진 함수를 Integral의 형태로 변환시키는 것으로, ODE와 PDE, Integral Equation을 푸는데 자주 사용되는 도구라고 할 수 있다. 이전에 다뤘던 Laplace Transform 역시 Integral Transform의 한 종류라고 할 수 있다. 여기서는 Fourier Transform에 대해 다뤄보겠다. Fourier Transform은 Fourier Integral으로부터 얻을 수 있다. Fourier Transform은 Fourier Cosine Transform과 Fourier Sine Transform으로 나뉘며, 각각은 Even Function과 Odd Function에 대해 사용한다. Fourier Cosine Transfo..

유도 지금까지 다룬 Fourier Series는 Periodic 한 것이나, Finite Interval한 함수에 대해서는 상당히 강력한 해결도구가 되지만, Non-periodic하거나 x축 전체를 사용하는 함수에 대해서는 이를 그대로 적용하기 어렵다. 그래서 나오게 된 개념이 바로 Fourier Integral이다. Fourier Integral은 만약 Period에 사용되는 변수 L을 무한대로 보내버렸을 때에는 과연 어떻게 될 것인가에 대한 생각으로부터 출발한다. L → ∞ 에 따라서 Summation이 Integral로 바뀔 것을 예상해 볼 수 있으며, 식의 간결함을 위해서 w_n을 쓰긴 했지만, 이제 n이 integer일 필요는 없게 되었다. 따라서 이후에는 w_n 대신 w로 바꾸어 쓰게 될 것이..