[Fourier Transforms] Discrete Fourier Transform (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를 넣어 식을 다시 써보면,

이제 c_0 ~ c_{N_1} 에 대해서 결정해야할 시간이다. 
우리는 이전에 Fourier Series에서 Fourier Coefficient를 구하기 위해 Orthogonality를 이용한 적이 있다.

(링크 : http://blastic.tistory.com/101)

여기서도 비슷한 아이디어를 사용하여 c_0 ~ c_{N_1}을 결정할 것이다.

그런데 여기서는 Integral 대신 Summation을 사용하고 있다. 

따라서 f_k에 e^{-imx_k}를 곱하고, k를 0 ~ N-1 까지 더하는 Summation으로 Integral을 대신할 것이다.

식으로 나타내면,

만약 위 식에서 n = m 이라면 Exponential 값은 1이될 것이다.

즉, n = m인 경우의 Summation은 곧 N이 될 것이다.

한편, n ≠ m인 경우를 생각해 보면, 일정한 비율, 즉 e^{i(n-m)2π/N} 으로 곱해지는 값들을 더해나가는 꼴이 되므로,

r = e^{i(n-m)2π/N} 이라고 잡았을때, 이 식의 합을 다음과 같이 다시 쓸 수 있다.

그런데 r^N을 고려해 보면,

즉 n = m 인 경우에 대해서만 고려해 주면 된다.

정리해서 식을 써 보면,

이렇게 쓸 수 있다. 편의상 m대신 n으로 바꾸어 식을 다시 써보면,

을 구할 수 있다.

여기서 도출된 c_n은 우리가 식을 구하는 과정에서 N이라는 크기만큼 나누어진 상태로 나타나게 된다. 

일반적으로, Discrete Fourier Transform은 

어떠한 Signal이 위와 같이 정의되었을때,

위와 같은 Component 에 의해서 다음과 같이 나타나게 된다.

Vector의 형태로 나타내면, 

위와 같다.