FFT의 계산량

표본 $N$ 개의 DFT를 계산하려면 곱셈이 몇 번 필요하고, FFT는 그것을 어떻게 줄일까?

정의대로 계산하면 $X[k]$ 하나에 곱 $N$ 개, $X[k]$ 가 $N$ 개이므로 복소 곱셈이 $N^2$ 번이다. FFT(fast Fourier transform)는 DFT 행렬의 대칭을 써서 같은 값을 더 적은 계산으로 구한다.

$N$ 이 짝수이면 표본을 짝수 번째 $x[2m]$ 과 홀수 번째 $x[2m+1]$ 로 나눈다. 두 수열의 $N/2$ 점 DFT를 $E[k]$ , $O[k]$ 라 하고 $w_N=e^{-j2\pi/N}$ 이라 두면, $k=0,1,\ldots,N/2-1$ 에서

\begin{aligned} X[k]&=E[k]+w_N^k\,O[k]\\ X[k+N/2]&=E[k]-w_N^k\,O[k] \end{aligned}

이다. 짝수 번째 표본에서는 $e^{-j2\pi k(2m)/N}=e^{-j2\pi km/(N/2)}$ 라 $N/2$ 점 DFT가 그대로 나오고, 홀수 번째 표본에는 $w_N^k$ 가 한 번 더 곱해진다. $w_N^{k+N/2}=-w_N^k$ 이므로 아래 식은 위 식의 부호만 바꾼 것이다. 곱 $w_N^kO[k]$ 하나를 두 번 쓰므로, 한 단계에서 복소 곱셈은 $N/2$ 번이다.

$N$ 이 2의 거듭제곱이면 이 나눔을 $\log_2N$ 단계 되풀이해 길이 1까지 내려간다. 복소 곱셈은 $(N/2)\log_2N$ 번이다. 계산량이 $O(N^2)$ 에서 $O(N\log N)$ 으로 준다.

$N$	DFT: $N^2$	FFT: $(N/2)\log_2N$	비
1,024	1,048,576	5,120	약 205
$2^{16}=65{,}536$	$\approx4.29\times10^9$	524,288	8,192

실습에서 한 번에 받는 $2^{16}$ 개 표본의 스펙트럼을 바로 그릴 수 있는 것은 이 차이 덕분이다. np.fft.fft는 어떤 $N$ 에서도 동작하고, $N$ 이 2의 거듭제곱처럼 작은 수들의 곱일 때 특히 빠르다.