[Fourier Transforms] Fast Fourier Transform (FFT)

왜 FFT를 사용하는가?

DFT를 통해서 f(x)의 Frequency Spectrum을 볼 수 있다.

일반적으로 DFT를 수행하기 위해 몇번의 계산을 거쳐야 할까.

이 식을 계산하려면 n번 더해야 한다.

이러한 계산을 다시 n번만큼 해줘야 최종 DFT를 얻는다.

즉, n^2번의 계산이 필요한 셈인데, 

만약 데이터 갯수가 1천개라면, 백만번의 계산을 해야한다는 결론이 나온다.

Fast Fourier Transform(FFT)를 사용하는 이유는 이 계산 수의 절반이하 수준의 계산수를 통해

Aliasing을 피하면서 같은 결과를 얻을 수 있기 때문이다.

Aliasing이라는 것은, 차이가 모호해지는 것 정도로 이해하고 있으면 된다.

이유는 간단하다. Sampling의 빈도가 낮아진다는 것은 곧, 

DFT의 기반 데이터 수가 적어진다는 것을 의미한다. 

곧, 결과는 좀 더 모호해 질 것이라는 것을 예상해 볼 수 있다. Aliasing은 그런 의미다.

30fps 영화와 12fps 애니메이션을 떠올려 보자. 어느 편이 좀 더 부드러운 영상을 제공할까? 답은 너무 뻔하다.

일반적으로 FFT는 N × log_2 N 만큼의 계산만 거치면 된다.

1000개의 데이터라면 약 100분의 1 수준의 계산이 필요할 뿐이다.

어떻게 해서 이것이 가능한지 FFT의 유도과정을 살펴보자.

유도

먼저 M = N/2로 잡음으로써 size N을 M으로 줄일 것이다.

그러면, 다음과 같은 계산이 가능하다.

N = 2M으로 위와 같은 계산이 가능했다. 

이제, 우리는 DFT를 다시 가져와서 N을 M으로 바꿔가는 작업을 할 것이다.

f_{ev,k}는 k중 짝수인 것, f_{od,k}는 홀수인 것을 나타낸다.

이러한 계산 과정을 통해, 우리는 큰 사이즈의 DFT를 작은 사이즈의 DFT 2개로 쪼개냈다.

즉, 아래와 같이 나눈다면,

각각의 DFT는

위와 같다.

마지막 식의 경우, 

다음과 같이 계산된다.