먼저 fft를 알기 위해서는 ft, 즉 푸리에 변환이 무엇인지부터 알아야 한다. 하지만, 이 페이지에서 푸리에 변환, 이산 푸리에 변환, 고속 푸리에 변환을 모두 살펴보기엔 무리가 있기 때문에 푸리에 변환과 관련된 영상을 보는 것을 추천한다.
(이 글은 wkipedia의 고속 푸리에 변환 페이지를 읽은 후 작성하는 글이기 때문에 해당 페이지와 유사한 흐름을 가지며, 해당 글을 읽으면서 자신의 생각을 추가해 더 쉽게 이해할 수 있도록 쓴 글임을 밝힙니다.)
고속 푸리에 변환을 살펴보기 이전에 이산 푸리에 변환부터 짚고 넘어가자. 이산 푸리에 변환으로 계속 부르기엔 너무 이름이 길기 때문에 dft라 하겠다.
dft는 아날로그에서의 푸리에변환을 이산 데이터, 즉 디지털 데이터의 주파수를 찾는데 사용하기 위한 방법이다.
푸리에변환과 dft의 식을 살펴보도록 하자.
$$ \hat h(f) = \int^{\infty}_{-\infty} x(x) e^{-2 \pi i f x} dx $$
$$ X(k) = \sum^{N-1}_{n=0} x_n e^{\frac{-2\pi k n}{N}} $$
다음과 같이 적분의 형태를 합의 형태로 바꿔 놓은 것으로 연속되지 않은 데이터를 처리할 수 있다.
이는 각 k에 대해 N번의 연산이 필요하기 때문에 $O(n^2)$의 시간복잡도를 가진다.
이는 데이터가 늘어날 수록 시간 복잡도가 기하급수적으로 커지기 때문에 이를 개선할 알고리즘이 필요하다.
고속 푸리에 변환은 dft의 문제점을 해결하기 위해 사용하는 알고리즘으로 결론적으로 말하면, $O(n \log n)$의 시간복잡도를 가진다. 이때, 고속 푸리에 변환은 Fast Fourier Transform, 즉 fft로 부르도록 하겠다.
먼저 dft의 식을 변환하며 fft에 대해 알아보자.