Lec 14. Discrete Convolution

본 게시물은 University of Arizona의 Prof. J. Scott Tyo의 OPTI512R 강의를 보고 정리한 내용입니다.
전공자가 아닌 만큼 부정확한 정보가 포함되어 있을 수 있습니다.
부정확한 정보가 있다면 알려주시면 감사하겠습니다.

---

The Convolution Theorem for DFT

우리는 Convolution integral이 다음과 같이 정의되는 Continuous linear System에 대해 학습하였다.

 

$$g(x) = f(x) * h(x) = \int^{\infty}_{-\infty} f(\alpha) h(x-\alpha) d\alpha$$

 

여기서 $\alpha$는 integration을 위한 dummy variable이다. 우리는 위 수식의 Integral과 Fourier Transform을 연관 짓는 다음의 중요한 theorem을 배웠다.

 

$$G(\xi) = F(\xi)H(\xi)$$

 

위 theorem에 의해 $f(x) \leftrightarrow F(\xi)$이고, $h(\xi) \leftrightarrow G(\xi)$이다. 여기서 볼 수 있는 것과 같이 Discrete signal에 대한 비슷한 convolution 정리를 도출할 수 있다.

 

$\mathcal{DFT} \{f_k\} = F_n$과 $\mathcal{DFT} \{h_k\} = H_n$가 성립하는 Discrete Sequence $G_n = F_n H_n$이 있다고 하자. 이때 $g_k = \mathcal{DFT}^{-1} \{G_n\}$을 $f_k$와 $h_k$를 사용하여 표현할 수 있을까?

Inverse DFT부터 시작해보자.

 

$$g_k = {1\over N} \sum^{N-1}_{n=0} F_n H_n e^{j2pi{kn \over N}} \\ =  {1\over N} \sum^{N-1}_{n=0} \{[\sum^{N-1}_{k_1=0} f_{k_1} e^{-j2\pi {k_1n \over N}}][\sum^{N-1}_{k_2=0} h_{k_2} e^{-j2\pi {k_2n \over N}}]e^{j2\pi {kn \over N}}\}$$

 

Complex exponential의 sum을 다음과 같이 분리하기 위해 summation의 순서를 rearrange 할 수 있다.

 

$$g_k = {1 \over N} \sum^{N-1}_{k_1 = 0}\sum^{N-1}_{k_2 = 0} \{f_{k_1}h_{k_2} \sum^{N-1}_{n = 0} e^{j {2\pi \over N}[(k-k_1) - k_2]n}\}$$

 

우리는 이미 Complex Exponential의 sum이 다음과 같이 주어지는 것을 알고 있다.

 

$$ \sum^{N-1}_{n = 0} e^{j {2\pi \over N}[(k-k_1)-k_2]n} = N\delta_{(k-k_1,k_2)}$$

 

이를 이용해 우리는 rearrange 한 수식을 위 수식으로 substitute 할 수 있다.

 

$$g_k =  \sum^{N-1}_{k_1 = 0}  \sum^{N-1}_{k_2 = 0} f_{f_1}f_{k_2} \delta_{(k-k_1,k_2)} \\ = \sum^{N-1}_{k_1 = 0} h_{k-k_1}f_{k_1}$$

 

위 equation은 놀랍게도 convolutional sum과 같아 보인다. 하지만 아직까지 DFT의 Property가 위 수식에 적용된다는 확신이 없기에 검증이 필요하다.

 

다음의 두 function의 convolution을 생각해보자.

 

$$f(x) = ramp(x) rect(x-.5) \\ h(x) = rect({x-.25 \over .5})$$

 

아래 두 그림은 위 두 function의 graphical convolution 단계를 보여준다. $f(x)$의 length가 1이고, $h(x)$의 length가 0.5 이기 때문에 $g(x) = f(x) * h(x)$의 length는 1.5 임을 알 수 있다. function $h(x-\alpha)$가 $f(x)$를 통과하면, output은 0이 된다.

 

두 signal의 DFT를 정의하기 위해서는 각 sequence의 length를 정의해야 한다. 우리는 $f(x)$와 $h(x)$가 모두 $0 \leq x < 1.25$의 interval에 걸쳐 정의된다고 정의할 것이다. 그러나 DFT와 IDFT operation이 periodic 하기 때문에 $k-k_1$이 range $0,1,...., N-1$의 밖에 있다면, 우리는 Input sequence에 Periodicity를 적용해야 하고, 이는 아래 그림과 같다.

위 그림에서 보이다시피 $f(x)$의 한 interval 이후로, function $h(x)$를 fit 할 수 있는 만큼의 space가 없기 때문에, function의 succeissive period 사이에 overlap이 발생하게 되고, $g(x)$가 periodicity를 가지게 된다.

 

 

위 그림과 같은 Convolution은 Circular convolution 또는 Periodic convolution이라고 불린다. Linear axis를 따라 function을 표시하는 대신에, axis의 끝과 끝이 만나도록 warping 한다.

 

$h(x)$를 flip 하고, shifting 한다면, $h(x)$는 위 그림과 같이 circle을 따라 cycle 하게 된다.

만약 function의 zero padding이 더욱 줄어든다면 아래 그림과 같은 결과를 확인할 수 있다. 이는 Periodic representation에서 본 것과 유사한 effect를 보인다.