FFT로 합성곱하기

핵심 질문

FFT는 실제로 다항식 곱셈을 어떻게 빠르게 만들까?

교과서 설명

FFT를 이용한 합성곱은 세 단계로 볼 수 있다.

주파수 영역에서는 합성곱이 자리별 곱셈으로 바뀐다.

왜 곱셈이 되는지 핵심만 보면 다음과 같다. 먼저 두 배열 뒤에 $0$을 충분히 붙여 같은 길이 $L$로 맞추었다고 보자. 이 길이는 선형 합성곱 결과가 말려 들어가지 않도록 $L\ge m+n-1$을 만족해야 한다.

이제 $\omega_L=e^{-2\pi i/L}$이고, 합성곱은 $c[t]=\sum_i a[i]b[t-i]$라고 두자.

$c[t]$는 $i+j=t$가 되는 모든 곱 $a[i]b[j]$를 모은 값이다. 그래서 모든 $t$를 돌며 더하는 것은 결국 모든 쌍 $(i,j)$를 한 번씩 더하는 것과 같다. 이 생각으로 $\sum_t$를 $\sum_i\sum_j$로 펼치면 DFT 합은 이렇게 정리된다.

시간 영역에서는 여러 위치를 밀어 더해야 하지만, 주파수 영역에서는 같은 $k$끼리만 곱하면 된다.

마지막으로 역 FFT를 하면 원래 영역의 합성곱을 얻는다. 앞 장에서 본 것처럼 IFFT는 회전 방향을 반대로 쓰고, 마지막에 길이 $L$로 나누는 역변환이다.

여기서 IFFT는 주파수 영역의 값 $C[k]$를 다시 계수 배열 $c[t]$로 되돌리는 단계다. FFT와 자리별 곱셈까지만 하면 아직 답은 주파수 영역에 남아 있다.

이렇게 뒤에 $0$을 충분히 붙이는 과정을 zero padding이라고 한다.

두 배열 길이가 $m$, $n$이면 결과 길이가 $m+n-1$이므로 FFT 길이는 적어도 이만큼 필요하다.

보통 FFT가 편하게 동작하도록 $L$은 $2$의 거듭제곱으로 잡는다.

이때 전체 계산량은 길이 $L$짜리 FFT 두 번, 역 FFT 한 번, 그리고 자리별 곱셈 $L$번으로 볼 수 있다.

직접 합성곱의 $O(mn)$ 또는 길이가 비슷할 때의 $O(N^2)$보다 큰 입력에서 훨씬 유리해진다.

또 한 가지 주의할 점이 있다. DFT 세계에서 그냥 곱하면 원형으로 말려 들어가는 순환 합성곱이 된다. zero padding을 충분히 해야 우리가 원하는 선형 합성곱과 같아진다.

즉 이 장의 zero padding은 합성곱 결과를 안전하게 담기 위한 장치다. 샘플링된 신호 뒤에 $0$을 붙인다고 원래 없던 정보가 생기는 것은 아니다.

합성곱 정리의 조건

DFT 길이를 $L$로 고정하면 모든 인덱스는 $L$로 나눈 나머지처럼 작동한다. 그래서 DFT 영역에서 곱한 뒤 IFFT하면 기본적으로 길이 $L$의 순환 합성곱이 나온다.

우리가 다항식 곱셈에서 원하는 것은 선형 합성곱이다.

두 결과가 같아지려면 선형 합성곱의 모든 결과 칸이 $0$부터 $L-1$ 안에 들어와야 한다. 그래서

이 필요하다. 이 조건을 만족하도록 뒤에 $0$을 붙이면, 원래는 앞으로 말려 들어갈 항들이 안전한 뒤쪽 칸에 남는다. 반대로 $L$이 작으면 뒤쪽 계수가 앞쪽 계수에 더해져 버리므로, 겉으로는 길이 $L$짜리 답이 나오더라도 다항식 곱셈 결과는 틀린다.

다항식 관점에서는 같은 사실을 이렇게 말할 수 있다. 충분히 많은 점에서 $A(x)$와 $B(x)$를 평가하고, 각 점에서 값을 곱해 $C(x)=A(x)B(x)$의 값을 얻은 뒤, 역변환으로 $C$의 계수를 복원한다. FFT는 평가와 복원을 빠르게 해 주고, 자리별 곱셈은 값 표현에서 다항식 곱셈을 수행하는 단계다.

예를 들어 길이 $2$로만 계산하면 결과가 두 칸 안에서 말려 들어간다.

하지만 길이 $2$ 순환 합성곱으로 보면 마지막 $8$이 앞 칸으로 돌아와 다음처럼 섞인다.

여기서 $8$은 사라진 것이 아니라 $0$번 칸으로 접혀 들어가 $3$과 더해진다. 이 현상이 aliasing이다. 그래서 길이 $3$ 이상의 공간을 만들기 위해 $0$을 붙여야 한다.

직관 비유

복잡한 퍼즐을 직접 맞추기 어렵다면, 퍼즐 조각을 색깔별로 분류한 뒤 같은 색끼리 처리하고 다시 합치는 방법을 쓸 수 있다. FFT는 문제를 “계산하기 쉬운 세계”로 잠깐 옮기는 도구다.

예제

두 배열 $a=[1,2]$, $b=[3,4]$의 합성곱은 다음과 같다.

FFT로 계산할 때는 길이 $3$ 이상이 필요하므로 길이 $4$로 맞출 수 있다.

계산 순서는 다음과 같다.

컴퓨터에서는 복소수 소수 오차가 생길 수 있으므로 마지막 결과가 $9.999999$처럼 나오면 가까운 정수로 반올림한다.

손풀이 체크

1. 길이 $2$ 배열 두 개의 선형 합성곱 결과 길이는?

   답 보기

   $2+2-1=3$

2. $[1,2]*[3,4]=[3,10,8]$을 길이 $2$ 순환 합성곱으로 보면 무엇이 앞 칸으로 말려 들어갈까?

   답 보기

   마지막 값 $8$

3. FFT 합성곱의 세 핵심 단계는?

   답 보기

   FFT, 자리별 곱셈, IFFT

4. $[1,2]$와 $[3,4]$를 길이 $4$로 zero padding해서 계산하면 IFFT 결과의 앞 세 칸은 무엇이어야 할까?

   답 보기

   선형 합성곱 결과인 $[3,10,8]$이어야 한다. 네 번째 칸은 padding 때문에 생긴 여분 칸이다.

마무리

DFT는 삼각함수, 복소수, 벡터, 좌표평면이 “회전으로 신호를 읽는 법”으로 이어진 결과다. FFT는 그 DFT를 빠르게 계산해서 합성곱과 다항식 곱셈에 사용할 수 있게 해 주는 알고리즘이다.