DSP) Overlap-Add와 Overlap-Save 컨볼루션

디지털 신호 x[n]에 대한 주파수 성분을 나타내는 방식에는 두 가지 방법이 있다.

 

DTFT 와 DFT.

 

DTFT(Discrete Time Fourier Transform)은 주파수 축의 표기가 w(오메가)인 연속신호이고

DFT(Discrete Fourier Transform)은 주파수 축의 표기가 k인 이산신호다.

 

DFT는 사실 DTFT에서 N-point에 대해 sampling한 결과다. 이에 따라 아래와 같이 보일 수 있다.

또한, DTFT에서 sampling된 값이므로, DTFT가 그렇듯이 DFT도 주기성을 가진다.

 

 

원형 컨볼루션(circular convolution)

두 이산신호의 convolution은 아래와 같이 나타낼 수 있다.

그렇다면 DFT에서의 두 이산산호 convolution은 아래와 같다.

@처럼 생긴 기호는 N-point로 circular convolution 했다는 기호다. circular convolution은 지금까지 해왔던 linear convolution과 사뭇 다르면서 같다. 이해를 돕기위해 그림과 같이 나타내면 아래의 그림과 같고, 계산 식 또한 옆에 그렸다.

 이때, 주의할 점은, x1[n]과 x2[n]의 크기가 같아야 한다는 점이다. 크기가 다르다면 크기가 더 큰 입력신호에 맞춰 크기가 작은 신호의 부족한 부분에 '0'으로 채워넣어야 한다. 또한, N-point로 circular convolution 했다면, 그 결과도 N개가 나온다.

 

circular convolution과 linear convolution의 관계.

예를 들어, 아래와 같이 입력신호 x1[n]과 x2[n] 두 가지 신호가 아래와 같이 주어졌다고 하자.

이때의 circular convolution의 값과 linear convolution의 값은 아래와 같다.

 

 circular convolution의 값은 4-point 였으므로 결과가 4개 나오나, linear convolution의 결과는 4+4 - 1 에서 총 7개가 나온다. 이때, linear convolution의 결과값을 4-point에 맞게 이동시켜 덧셈하면, circular convolution과 값이 같다.

 

 

Overlap-Add & Overlap-Save Convolution

이제 본론이다. LTI system에서는 output을 구하기 위해 linear convolution을 이용한다. 하지만, 신호의 길이가 무한히, 혹은 매우 길때, linear convolution을 하기 위해서는 해당 신호가 전부 받아질때 까지 기다려야 convolution을 시작할 수 있다. 따라서, 긴 신호를 finite하게 쪼개서 block 단위로 convolution을 진행해야 한다. 방법으로는 overlap-add 방식과 overlap-save 방식이 존재한다.

 

 

Overlap-Add

아주 긴 신호 x[n]을 아래와 같이 N개의 길이로 자르고, h[n]의 크기를 M개 라고 하자.

N개씩 나뉜 block을 h[n]과 L-point circular convolution 한다. 이때 L=N+M-1 이며, x쪽의 부족한 크기는 0으로 채운다.

 

계산 결과는 아래와 같이 N씩 delay된 convolution 값들을 모두 더하므로 overlap-add 라는 이름이 붙었다.

이때, 문제점은 첫 항 y[0]에서 overlap되는 부분이 없어 오차가 발생한다는 점이다. 이를 보완한 것이 overlap-save다.

 

Overlap-Save

우선, overlap-add의 문제를 보완하여 첫 입력신호의 앞부분을 zero padding 해버린다.

zero-padding 하는 개수는 후술하겠다.

 

 

만약 h[n]이 M개, x[n]이 N개씩인 block들 이라고 가정하면, block처리 L =  M + N - 1이다.

이때, block의 크기를 L보다 작은 값인 L'으로 하는 경우,  L'의 block처리 중, L - L' 만큼의 error가 포함되어 버리므로 이 만큼을 버린다. 이때문에 Overlap-Save 방식이라고 한다.

버리는 부분 ( L' )이 2이므로, 각 circular convolution 값 마다 결과의 두개씩 버린다.

또한, 맨 앞부분과 맨 뒷부분의 zero-padding 또한 L'에 해당하는 2씩 이다.