합성곱

핵심 질문

다항식 곱셈에서 같은 차수로 모이는 계수들은 어떻게 계산할까?

이 자료에서는 합성곱을 먼저 다항식 계수 조합으로 본다. 두 계수 배열 $a$ , $b$ 를 곱해서 새 배열 $c$ 를 만들 때, $c[k]$ 는 차수가 $k$ 가 되는 모든 곱을 더한 값이다.

c[k]=(a*b)[k]=\sum_{i+j=k} a[i]b[j]

같은 식을 $j=k-i$ 로 바꾸어 쓰면 다음과 같다.

c[k]=\sum_i a[i]b[k-i]

신호 처리에서는 이 계산을 “한 배열을 뒤집고 밀어 가며 겹침을 더한다”고 설명하기도 한다. 하지만 FFT와 다항식 곱셈을 연결할 때는 “ $i+j=k$ 인 계수 조합을 모은다”는 관점이 더 직접적이다.

길이가 $m$ 인 배열과 길이가 $n$ 인 배열을 선형 합성곱하면 결과 길이는 $m+n-1$ 이다. 없는 칸은 $0$ 이라고 생각한다.

a[i]=0\quad\text{if }i\text{ is outside }a,\qquad b[j]=0\quad\text{if }j\text{ is outside }b

결과 길이가 $m+n-1$ 인 이유는 가능한 차수 합의 범위 때문이다. 가장 작은 합은 $0+0=0$ 이고, 가장 큰 합은

(m-1)+(n-1)=m+n-2

이다. 따라서 결과 인덱스는

0,1,2,\dots,m+n-2

이고, 칸의 개수는 $m+n-1$ 개다.

두 다항식을

A(x)=\sum_i a[i]x^i,\qquad B(x)=\sum_j b[j]x^j

라고 쓰자. 곱하면

A(x)B(x)=\left(\sum_i a[i]x^i\right)\left(\sum_j b[j]x^j\right)

이고, 분배법칙으로 모든 항을 곱하면

A(x)B(x)=\sum_i\sum_j a[i]b[j]x^{i+j}

가 된다. 이제 결과 다항식을

C(x)=\sum_k c[k]x^k

라고 쓰면, $x^k$ 의 계수 $c[k]$ 는 $i+j=k$ 가 되는 모든 항에서 나온다. 따라서

c[k]=\sum_{i+j=k}a[i]b[j]

가 된다. 이것이 합성곱 공식이다.

직접 계산하면 모든 쌍 $(i,j)$ 를 확인해야 하므로 대략 $mn$ 번의 곱셈이 필요하다. 두 배열 길이가 모두 $N$ 정도라면 $O(N^2)$ 계산이 된다. FFT를 쓰는 이유는 이 병목을 줄이기 위해서다.

또 하나 구분해야 할 말이 있다. 지금 정의한 것은 선형 합성곱이다. DFT 안에서 길이를 고정한 채 곱하면 결과가 끝에서 앞으로 말려 들어가는 순환 합성곱이 된다. 그래서 FFT로 선형 합성곱을 하려면 뒤에서 zero padding을 반드시 다룬다.

두 주사위를 던져 합이 $k$ 가 되는 경우를 모은다고 생각하자. 합이 $3$ 인 경우는 $(1,2)$ 와 $(2,1)$ 처럼 여러 조합이 있다. 합성곱도 차수의 합이 $k$ 가 되는 곱들을 모두 모아 더한다.

(1+2x)(3+4x)=3+10x+8x^2

가운데 계수 $10$ 은 $1\cdot4+2\cdot3$ 에서 나온다.

배열로 쓰면 같은 계산이다.

[1,2]*[3,4]=[3,10,8]

각 칸은 다음처럼 채워진다.

\begin{aligned} c[0]&=1\cdot3=3\\ c[1]&=1\cdot4+2\cdot3=10\\ c[2]&=2\cdot4=8 \end{aligned}

차수 조합표로 쓰면 다음과 같다.

\begin{array}{c|c|c} k&i+j=k&c[k]\\ \hline 0&(0,0)&1\cdot3=3\\ 1&(0,1),(1,0)&1\cdot4+2\cdot3=10\\ 2&(1,1)&2\cdot4=8 \end{array}

이 표에서 $k$ 는 결과 배열의 번호이자 다항식의 차수다. 같은 $x^k$ 앞에 모이는 곱을 모두 더하면 $c[k]$ 가 된다.

그냥 계산하면 느리지만, DFT와 FFT를 이용하면 빠르게 만들 수 있다. 다음 장에서는 “느리다”와 “빠르다”를 계산량으로 비교한다.