Block convolution인 Overlap add과 Overlap save

 

 

Block Linear Convolution

언제 사용하는가? 신호의 길이가 굉장히 길고 그에 비해 impulse response의 길이는 짧을 때

\(h[n]\)의 length는 M.

 

Overlap Add

1. \(x[n]\)을 L개씩 잘라낸다. 

2. circular convolution으로 linear convolution을 하려면 길이를 N ≥ M+L-1 로 padding하여 맞춰놓아야 한다.
이는 linear convolution을 할 때 처음 0이 아닌 값이 나오는 시점(한 샘플 겹칠 때)부터 마지막 0이 아닌 값(반대편 한 샘플 겹칠 때)을 생각하면 N이 저러한 값이 설정된다.

그러므로 h와 잘린 x에 N의 길이가 되게 zero padding을 해준다.

3. 위처럼 처리된 각 block마다 convolution을 하면 N개의 out이 나온다.

\(y_n(t)\)는 모두 N개씩 나오게 된다.

Overlap save

Overlap add에서는 딱 L씩 나눈 것에 zero padding한 신호가 convolution의 대상이었다.

Overlap save에서는 L씩 나누어서 overlap save와 같이 L개의 shift가 일어난다.

Overlap add처럼 linear convolution의 결과 길이 만치의 미리 padding을 해주어야 한다.

Overlap add에서는 각 block마다 뒤에 원하는 length N=M+L-1이 될 때까지의 M-1개 zero padding 을 해주었다.

Overlap save에서는 각 block마다 앞에, zero padding이 아닌 실제 sample을 더 취하여 원하는 length N=M+L-1을 만들어낸다. 그러므로 이전 샘플 M-1개를 덧붙인 것으로 input을 취한다.

부득이하게 제일 첫번째로 잘리는 block에 대해서는 앞에 뭐가 없으 zero padding을 해줄 수 밖에 없겠다.

 

 

결국 ovelap add, overlap save는 N(>=M+L-1)짜리의 linear convolution을 만드는 것이 목표다. 

overlap add와 save는 impulse response의 길이 M은 N-M 인 L-1만큼 padding을 하는 것 및

신호를 딱 L씩 잘라 N legnth로 padding해야하는 것까지는 같다.

 

overlap add는 뒤에 zero를 더 붙여서 N을 만들어내는 것이고 circular convolution을 하여 L보다 더 나오는 뒷 부분을 overlap add한다.

overlap save는 앞에 신호를 덧붙여서 N을 만드는 것이다(첫번째 block은 앞에 더 신호가 없으므로 zero padding). 

앞에 나오는 M-1 는 버려서 L만큼만 사용한다.

두 method 다 어떻게보면 예쁘게 제대로 나오는 부분은 L개가 되겠다.

overlap add : input에서 안겹치고 output에서 겹쳐 더한다

overlap save : input에서 겹치고 output에서 버림으로 하나도 안겹치게 더한다.

 

 

 

 

그림출처 : http://www.ee.nmt.edu/~rison/ee451_fall99/homepage.html