Overlap Add, Overlap Save(digital signal processing)

In DSP to solve a convolution of a long duration sequence there are two popular methods. Overlap Add, Overlap Save. In this presentation i've discussed about both.
- Gourab Ghosh

1. OVERLAP SAVE OVERLAP ADD METHOD Gourab Chandra Ghosh Surendra Institute of Engineering & Management

2. CONTENTS: Why overlap save & overlap add method ? Steps to perform overlap save method. Example of overlap save method. Steps to perform overlap add method. Example of overlap add method. Difference between overlap save & add method. Reference Q & A 2

3. FILTERING USING DFT: In practical application we often come across linear filtering of long data sequences. DFT involves operation on block of data. The block size of data should minimum because digital processors have limited memory. Two methods of filtering: 3

4. FILTERING USING DFT: In practical application we often come across linear filtering of long data sequences. DFT involves operation on block of data. The block size of data should minimum because digital processors have limited memory. Two methods of filtering: OVERLAP SAVE METHOD OVERLAP ADD METHOD 4

5. 5

6. OVERLAP SAVE METHOD STEP-1: Determine length ‘M’ , which is the length of the impulse response data sequences i.e. h[n] & determine ‘M-1’ . STEP-2: Given input sequence x[n] size of DFT is ‘N’ . let assume, N=5 6

7. OVERLAP SAVE METHOD STEP-3: Determine the length of the new data, ‘L’ => N=(L+M-1) STEP-4: Pad ‘L-1’ zeros to h[n] 7

8. OVERLAP SAVE METHOD STEP-3: Determine the length of the blocks, ‘L’ STEP-4: Pad ‘L-1’ zeros to h[n] 8 h[n] ‘L-1’ zeros (padded)

9. OVERLAP SAVE METHOD Input Data Sequence x[n ] 9 x1[n] x2[n] x4[n] x3[n] M-1 zeros M-1 data M-1 data M-1 data L L L L

10. OVERLAP SAVE METHOD STEP-4: Perform Circular Convolution of h[n] & blocks of x[n ] i.e. y1[n ]= x1[n ] h[n] y2[n ]= x2[n ] h[n] y3[n ]= x3[n ] h[n] y4[n ]= x4[n ] h[n] 10 N N N N

11. OVERLAP SAVE METHOD 11 y1[n] y2[n] y4[n] y3[n] M-1 data M-1 data M-1 data M-1 data X X X X X => discard

12. OVERLAP SAVE METHOD 12 y1[n] y2[n] y4[n] y3[n] M-1 data M-1 data M-1 data Final Output Data Sequence y[n] M-1 data X X X X X => discard

13. OVERLAP SAVE EXAMPLE Ques. Given x[n]={3,-1,0,1,3,2,0,1,2,1} & h[n]={1,1,1} Let, N=5 Length of h[n], M= 3 Therefore, M-1= 2 We know, N=(L+M-1) 5=L+3-1 L=3 ∴Pad L-1=2 zeros with h[n] i.e. h[n]={1,1,1,0,0} 13

14. OVERLAP SAVE EXAMPLE 3 -1 1 3 2 1 2 1 14 3 -1 -1 1 3 2 3 2 1 2 1 2 1 x1[n] x2[n] x4[n] x3[n] M-1 (=2) no. of previous data L (=3) no. of new data

15. OVERLAP SAVE EXAMPLE Performing y k [n]= x k [n] h[n], where k=1,2,3,4 y 1 [n]= {-1,0,3,2,2} y 2 [n]= {4,1,0,4,6} y 3 [n]= {6,7,5,3,3} y 4 [n]= {1,3,4,3,1} 15 N

16. OVERLAP SAVE EXAMPLE -2 -1 1 2 3 4 5 6 7 8 9 10 11 16 3 2 2 4 6 5 3 3 4 3 1 -1 4 1 6 7 1 3 X => discard X X X X n- y 1 [n] y 1 [n] y 1 [n] y 1 [n]

17. OVERLAP SAVE EXAMPLE -2 -1 1 2 3 4 5 6 7 8 9 10 11 17 3 2 2 4 6 5 3 3 4 3 1 -1 4 1 6 7 1 3 X => discard X X X X n- y 1 [n] y 1 [n] y 1 [n] y 1 [n] y[n] 3 2 2

18. OVERLAP SAVE EXAMPLE -2 -1 1 2 3 4 5 6 7 8 9 10 11 18 3 2 2 4 6 5 3 3 4 3 1 -1 4 1 6 7 1 3 X => discard X X X X n- y 1 [n] y 1 [n] y 1 [n] y 1 [n] y[n] 3 2 2 4 6

19. OVERLAP SAVE EXAMPLE -2 -1 1 2 3 4 5 6 7 8 9 10 11 19 3 2 2 4 6 5 3 3 4 3 1 -1 4 1 6 7 1 3 X => discard X X X X n- y 1 [n] y 1 [n] y 1 [n] y 1 [n] y[n] 3 2 2 4 6 5 3 3

20. OVERLAP SAVE EXAMPLE -2 -1 1 2 3 4 5 6 7 8 9 10 11 20 3 2 2 4 6 5 3 3 4 3 1 -1 4 1 6 7 1 3 X => discard X X X X n- y 1 [n] y 1 [n] y 1 [n] y 1 [n] y[n] 3 2 2 4 6 5 3 3 4 3 1

21. 21

22. OVERLAP ADD METHOD STEP-1: Determine length ‘M’ , which is the length of the impulse response data sequences i.e. h[n] & determine ‘M-1’ . STEP-2: Given input sequence x[n] size of DFT is ‘N’ . let assume, N=5 22

23. OVERLAP ADD METHOD STEP-3: Determine the length of the new data, ‘L’ STEP-4: Pad ‘M-1’ zeros to x k [n] Pad ‘L-1’ zeros to h[n] 23 x k [n] ‘M-1’ zeros (padded) h[n] ‘L-1’ zeros (padded)

24. OVERLAP ADD METHOD Input Data Sequence x[n] 24 x1[n] x2[n] x4[n] x3[n] M-1 zeros M-1 zeros M-1 zeros M-1 zeros L L L L

25. OVERLAP ADD METHOD STEP-4: Perform Circular Convolution of h[n] & blocks of x[n ] i.e. y1[n ]= x1[n ] h[n] y2[n ]= x2[n ] h[n] y3[n ]= x3[n ] h[n] y4[n ]= x4[n ] h[n] 25 N N N N

26. OVERLAP ADD METHOD 26 y1[n] y2[n] y4[n] y3[n] M-1 data M-1 data M-1 data Final Output Data Sequence y[n] M-1 data add add add

27. OVERLAP ADD EXAMPLE Ques. Given x[n]={3,-1,0,1,3,2,0,1,2,1} & h[n]={1,1,1} Let, N=5 Length of h[n], M= 3 Therefore, M-1= 2 We know, N=(L+M-1) 5=L+3-1 L=3 ∴Pad L-1=2 zeros with h[n] i.e. h[n]={1,1,1,0,0} 27

28. OVERLAP ADD EXAMPLE 3 -1 1 3 2 1 2 1 28 3 -1 1 3 2 1 2 1 x1[n] x2[n] x4[n] x3[n] M-1 (=2) no. of zeros L (=3) no. of new data Input sequence x[n]

29. OVERLAP ADD EXAMPLE Performing y k [n]= x k [n] h[n], where k=1,2,3,4 y 1 [n]= {3,2,2,-1,0} y 2 [n]= {1,4,6,5,2} y 3 [n]= {0,1,3,3,2} y 4 [n]= {1,1,1,0,0} 29 N

30. OVERLAP ADD EXAMPLE 1 2 3 4 5 6 7 8 9 10 11 12 13 30 3 2 2 6 5 2 3 3 2 1 -1 1 4 1 1 1 + => add + n- y 1 [n] y 1 [n] y 1 [n] y 1 [n] + + + + + 3 2 2 y[n]

31. OVERLAP ADD EXAMPLE 1 2 3 4 5 6 7 8 9 10 11 12 13 31 3 2 2 6 5 2 3 3 2 1 -1 1 4 1 1 1 + => add + n- y 1 [n] y 1 [n] y 1 [n] y 1 [n] + + + + + 3 2 2 4 6 y[n]

32. OVERLAP ADD EXAMPLE 1 2 3 4 5 6 7 8 9 10 11 12 13 32 3 2 2 6 5 2 3 3 2 1 -1 1 4 1 1 1 + => add + n- y 1 [n] y 1 [n] y 1 [n] y 1 [n] + + + + + 3 2 2 4 6 5 3 3 y[n]

33. OVERLAP ADD EXAMPLE 1 2 3 4 5 6 7 8 9 10 11 12 13 33 3 2 2 6 5 2 3 3 2 1 -1 1 4 1 1 1 + => add + n- y 1 [n] y 1 [n] y 1 [n] y 1 [n] + + + + + 3 2 2 4 6 5 3 3 4 3 y[n]

34. OVERLAP ADD EXAMPLE 1 2 3 4 5 6 7 8 9 10 11 12 13 34 3 2 2 6 5 2 3 3 2 1 -1 1 4 1 1 1 + => add + n- y 1 [n] y 1 [n] y 1 [n] y 1 [n] + + + + + 3 2 2 4 6 5 3 3 4 3 1 y[n]

35. OVERLAP ADD EXAMPLE 1 2 3 4 5 6 7 8 9 10 11 12 13 35 3 2 2 6 5 2 3 3 2 1 -1 1 4 1 1 1 + => add + n- y 1 [n] y 1 [n] y 1 [n] y 1 [n] + + + + + 3 2 2 4 6 5 3 3 4 3 1 y[n]

36. OVERLAP SAVE vs ADD METHOD Overlap Save Overlapped values has to be discarded. It does not require any addition. It can be computed using linear convolution Overlap Add Overlapped values has to be added. It will involve adding a number of values in the output. Linear convolution is not applicable here. 36

37. CONCLUSION: 37 Overlap Add and Save methods are almost similar. From the differences one can choose any of the methods, which is suitable at that time.

38. REFERENCE: Digital Signal Processing - P. Rameshbabu Discrete Time Signal Processing - Oppenheim & Schafer 38

39. 39