FFT의 분할 정복

핵심 질문

DFT 계산을 어떻게 훨씬 빠르게 줄일 수 있을까?

교과서 설명

DFT를 그대로 계산하면 모든 $k$와 모든 $n$을 비교해야 하므로 대략 $N^2$번 계산한다.

이 장에서는 가장 기본적인 radix-2 FFT를 다룬다. 따라서 배열 길이 $N$은 계속 반으로 나눌 수 있는 $2$의 거듭제곱이라고 가정한다.

여기서 꼭 구분해야 한다. FFT는 DFT와 다른 결과를 만드는 새 변환이 아니다. FFT는 DFT를 빠르게 계산하는 알고리즘일 뿐이다. 따라서 FFT 결과는 같은 길이와 같은 정규화 약속을 쓰는 DFT 결과와 같아야 한다.

합성곱에서 필요한 zero padding 조건은 마지막 장에서 자세히 다룬다. 이 장에서는 먼저 길이가 $2$의 거듭제곱이라고 두고, 왜 짝수/홀수 분해만으로 같은 DFT 값을 더 적은 계산으로 얻는지에 집중하자.

FFT는 입력을 짝수 번째와 홀수 번째로 나누어 같은 문제를 절반 크기로 다시 푼다.

이 식은 다항식의 항을 짝수 차수와 홀수 차수로 나누면 나온다.

짝수 차수만 모으면 $a_0+a_2x^2+a_4x^4+\cdots$이고, 홀수 차수만 모으면 $x(a_1+a_3x^2+a_5x^4+\cdots)$이다. 그래서 같은 문제를 $x^2$에 대해 더 작은 크기로 다시 풀 수 있다.

작은 예로 보면 구조가 더 선명하다. 길이 $4$ 다항식

를 생각하자. 짝수 차수 항만 모으면

이고, 홀수 차수 항에서 앞의 $x$를 하나 떼어 내면

이다. 여기서 $u=x^2$로 두면

가 된다. 즉 “짝수 번째 계수 배열”과 “홀수 번째 계수 배열”은 각각 절반 길이의 새 다항식이고, 원래 다항식은 이 둘을 다시 끼워 맞춘 것이다.

DFT에서는 검사하는 점들이 단위원 위의 특수한 회전값이다. 길이가 $N$일 때 기본 회전값을 다음처럼 쓴다.

$X[k]$는 다항식 $A(x)$를 $x=\omega_N^k$에 대입한 값으로 볼 수 있다.

위의 짝수/홀수 분해식에 $x=\omega_N^k$를 넣으면 다음처럼 된다.

그런데 단위원근에는

가 성립한다. 그래서 $A_{\text{even}}$과 $A_{\text{odd}}$는 $N/2$개의 단위원근에서 평가하면 되고, 이것이 바로 절반 크기 DFT다.

$k$가 $0$부터 $N-1$까지 움직이면 $\omega_{N/2}^k$는 $N/2$개의 값만 두 번 반복한다. 실제로

이다. 그래서 절반 크기 DFT 결과 $E[k]$, $O[k]$를 아래쪽 출력에서도 다시 사용할 수 있다.

마지막으로 $\omega_N^{k+N/2}=-\omega_N^k$라는 짝 관계 때문에 한 번 계산한 절반 크기 DFT 결과를 위쪽 출력과 아래쪽 출력에 함께 재사용할 수 있다.

조금 더 엄밀하게 계산량을 쓰면, 길이 $N$짜리 FFT 시간 $T(N)$은 길이 $N/2$짜리 FFT 두 번과 합치는 일 $O(N)$으로 이루어진다.

각 단계에서 전체 합치는 일은 $O(N)$이고, 반으로 나누는 단계가 $\log_2 N$개 있으므로 전체 계산량은 다음처럼 줄어든다.

분할 정복 유도 자세히 보기

입력 배열을 다항식의 계수라고 보고

라고 하자. 짝수 차수와 홀수 차수를 분리하면

이고, $u=x^2$라고 두면

가 된다. 이때 $A_{\text{even}}$과 $A_{\text{odd}}$는 원래 다항식보다 항의 개수가 절반이다. 따라서 이 둘을 단위원근에서 평가하는 일은 길이 $N/2$짜리 DFT와 같은 모양이 된다.

이제 $x=\omega_N^k$를 넣으면

이다. 여기서 핵심은 입력점이 $\omega_N^k$였는데, 짝수/홀수 다항식에는 그 제곱인 $(\omega_N^k)^2=\omega_{N/2}^k$가 들어간다는 점이다. 그래서 원래 길이 $N$ DFT를 직접 계산하지 않고, 짝수 계수 다항식의 길이 $N/2$ DFT 결과를 $E[k]$, 홀수 계수 다항식의 길이 $N/2$ DFT 결과를 $O[k]$라고 놓을 수 있다.

그러면 위 식은

가 된다. 즉 짝수 계수 다항식과 홀수 계수 다항식을 절반 크기 DFT로 계산한 뒤, 회전 인자 $\omega_N^k$만 곱해 합치면 된다.

반대편 출력도 동시에 나온다. $k+N/2$를 넣으면

이고, 동시에 제곱된 입력점은 그대로다.

따라서 $E[k]$와 $O[k]$는 다시 쓰고, 앞에 붙는 회전 인자의 부호만 바뀐다.

가 된다. 그래서 한 쌍의 출력은

로 동시에 만들어진다. 이 한 쌍의 결합이 butterfly다.

구현으로 옮길 때

처음 FFT를 코드로 옮길 때는 재귀형이 가장 이해하기 쉽다. 입력을 짝수 인덱스 배열과 홀수 인덱스 배열로 나누고, 두 작은 FFT 결과를 butterfly 공식으로 다시 합치면 된다.

대회 코드에서는 새 배열을 계속 만들면 느려질 수 있어서 반복문 형태의 FFT를 쓰기도 한다. 이때 입력을 먼저 bit reversal 순서로 재배치한다. 예를 들어 $N=8$이면 인덱스 $3$은 이진수로 $011$이고, 이를 뒤집으면 $110$이므로 $6$번 위치와 연결된다.

bit reversal은 새로운 수학 원리가 아니라, 작은 butterfly들이 차례대로 만날 수 있도록 배열 순서를 미리 정리하는 구현 기법이다. 이 장에서는 재귀형으로 원리를 이해하고, 반복문 구현은 같은 butterfly를 배열 안에서 직접 수행하는 방식이라고 보면 충분하다.

역 FFT를 구현할 때는 회전 방향을 반대로 쓰고, 마지막에 전체 길이 $N$으로 나눈다. 정수 계수 합성곱에서는 계산 결과가 $9.999999$처럼 나올 수 있으므로 마지막에 가까운 정수로 반올림한다. 이 오차는 복소수 실수 계산에서 생기는 작은 오차이지, 합성곱 공식이 달라졌다는 뜻은 아니다.

직관 비유

큰 시험지를 한 장씩 다 확인하는 대신, 짝수 번호 문제 묶음과 홀수 번호 문제 묶음으로 나누어 동시에 채점하는 느낌이다.

예제

길이 $8$ 배열은 $4$, $2$, $1$ 크기로 계속 나뉜다. 나뉜 결과를 다시 합칠 때 회전 인자들이 사용된다.

합치는 단계에서는 짝수 쪽 결과 $E[k]$와 홀수 쪽 결과 $O[k]$를 다음처럼 섞는다.

반대편 출력은 홀수 쪽에서 온 회전 항의 부호만 바뀐다.

길이 $4$ 숫자 예시를 보자.

짝수 인덱스와 홀수 인덱스로 나누면 다음과 같다.

길이 $2$ DFT를 하면

길이 $4$의 기본 회전값은 $\omega_4=e^{-2\pi i/4}=-i$이다. 따라서 합치는 과정은 다음처럼 된다.

위아래 두 결과가 한 번에 만들어지는 모양이 나비처럼 보여서 이 결합을 butterfly라고 부른다.

이 예시에서 $E[0]$과 $O[0]$은 $X[0]$, $X[2]$를 만들 때 함께 쓰이고, $E[1]$과 $O[1]$은 $X[1]$, $X[3]$를 만들 때 함께 쓰인다. 작은 DFT 결과를 다시 계산하지 않고 두 출력에 재사용하는 것이 FFT의 속도 이득이다.

손풀이 체크

1. $[5,7]$의 길이 $2$ DFT는?

   답 보기

   $[12,-2]$

2. $x=[1,2,3,4]$에서 even 배열과 odd 배열은?

   답 보기

   even은 $[1,3]$, odd는 $[2,4]$

3. $\omega_4=e^{-2\pi i/4}$의 값은?

   답 보기

   $-i$

4. 위 예시에서 $E[0]=4$, $O[0]=6$이면 $X[0]$과 $X[2]$는?

   답 보기

   $X[0]=4+6=10$, $X[2]=4-6=-2$이다.

다음으로 이어지는 생각

FFT로 DFT를 빠르게 하면 합성곱과 다항식 곱셈도 빠르게 할 수 있다.