고속 푸리에 변환(Fast Fourier Transform)이란?

고속 푸리에 변환(FFT, Fast Fourier Transform)이란, 푸리에 변환을 빠르게 수행할 수 있는 알고리즘이다. 일반적으로 이산 푸리에 변환(Discrete Fourier Transform)을 빠르게 수행하기 위해 사용하는데, DFT는 n개의 샘플에 대해 O(n^2)의 계산이 필요하지만 FFT는 O(nlogn)의 계산만 하면 된다.
 
FFT의 핵심은 "쪼개어 생각하기"이다. 총 2N개의 샘플이 있을 때, 이를 짝수 인덱스와 홀수 인덱스로 분리하여 나타내는 것이다.
 

다니엘슨 - 란초스 보조정리 (D-L Lemma)

 
아래와 같은 DFT가 있다고 하자. 이때, x_n은 복소수열이며 이의 DFT인 f_k도 복소수열이다.

 
아래와 같이 Twiddle Factor W_n을 정의할 때, 복소평면에서 이는 x축에서 시계방향으로 2pi/N만큼 떨어진 동경을 그린다. 따라서 twiddle factor를 N승 하면, 동경은 원점으로 돌아온다.

즉, twiddle factor는 다음과 같은 주기성을 가진다.

그러면 DFT 식을 이렇게 적을 수 있다.

위 식을 전개하면, 홀수 항과 짝수 항을 분리하여 아래와 같이 쓸 수 있다.

 
이때 짝수항 E와 홀수항 O를 분리하여 아래와 같이 쓸 수 있다.

또한, twiddle factor의 주기성에 의해,

 
이 성립한다. (못 믿겠으면 위의 DFT식에 직접 k + N/2를 넣어 볼 것!)
 
이 식이 시사하는 바는, 2M개짜리 데이터의 푸리에 변환을 수행하기 위해, 이를 1, 3, ..., 2M-3, 2M-1의 홀수 항(M개)과 0, 2, 4, .., 2M-2의 짝수 항으로 나누어 M개짜리 푸리에 변환 두 번으로 바꿀 수 있음을 의미한다.

이를 위와 같은 도표로 나타내기도 하는데, 이를 butterfly operation이라고 한다.