[나만 보는 정리노트] 합성곱, 컨볼루션, Convolution

연속 시스템에서는 $f(x)*g(x)=\int_{-\infin}^{+\infin}{f(\tau)g(x-\tau)} d\tau$로 정의된다.

이산 시스템에서는 $a_n*b_n=\displaystyle\sum_{i=0}^{n}{a_ib_{n-i}}$로 표현된다.

간단히 말해서 양쪽 끝에서부터 두 함수를 교차해서 곱한 것들을 더한다는 것이다.

어, 그런데 이런 꼴을 어디서 본 적이 있었으니...

$H(f)=\displaystyle\int_{-\infin}^{+\infin}{h(t)e^{-iwt}dt}$
푸리에 변환식에서 저런 꼴을 본 적이 있을 것이다.

놀랍게도 푸리에 변환한 후의 곱셈 뒤 역변환은 합성곱과 똑같으니...
이를 증명해보자.

푸리에 변환식 안에 합성곱을 넣어서...

$\displaystyle\int_{-\infin}^{+\infin}{}\{\displaystyle\int_{-\infin}^{+\infin}{f(\lambda)g(t-\lambda)d\lambda \} e^{-iwt}dt}=\displaystyle\int_{-\infin}^{+\infin}{f(\lambda) \{\displaystyle\int_{-\infin}^{+\infin}{g(t-\lambda)e^{-iwt}dt}\}d\lambda}$

밖으로 빼내준 뒤 치환하고...

$=\displaystyle\int_{-\infin}^{+\infin}{f(\lambda) \{\displaystyle\int_{-\infin}^{+\infin}{g(m)e^{-iw(m+\lambda)}dm}\}d\lambda}=\displaystyle\int_{-\infin}^{+\infin}{f(\lambda)e^{-iw\lambda}d\lambda \displaystyle\int_{-\infin}^{+\infin}{g(m)e^{-iwm}dm}}$

$=F(w)\times G(w)$

지수를 분리시켜주면 푸리에 변환식의 곱 꼴이 된다.

이산 푸리에 변환 역시 마찬가지로 할 수 있다.

합성곱으로 할 수 있는 건 매우 많다ㅡ우선 곱셈을 합성곱을 이용하여 빠르게 할 수 있다. 곱하는 수들을 값 표기법으로 나타낸 수열로 보는 것이다. $213\times 123$을 $[3, 1, 2]$와 $[3, 2, 1]$로 나타낼 수 있을 것이다. 이 때 $x=10$이다. 이 수열 둘을 합성곱한 뒤 $x=10$을 대입해준다면 간단히 두 수의 곱을 $O(N\log N)$만에 할 수 있을 것이다.

합의 경우의 수 역시 합성곱으로 구할 수 있다. $[1, 2, 3], [0, 4, 8]$에 대해 양쪽에서 하나씩 골라 더하여 만들 수 있는 수는 $1,5, 9, 2, 6, 10, 3, 7, 11$이 있을 것이다.
$[1, 2, 3]$을 $[0, 1, 1, 1, 0, ...]$처럼, $[0, 4, 8]$을 $[1, 0, 0, 0, 1, 0, 0, 0, 1,...]$처럼 나타내보자. 둘을 합성곱하면 $[0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, ...]$이 됨을 알 수 있다. 이 때 이 값이 $1$인 경우의 인덱스가 $1, 5, 9, 2, 6, 10, 3, 7, 11$임을 알 수 있다!