MAKE A MEME
View Large Image
| View Original: | Overlap-save algorithm.png (912x548) | |||
| Download: | Original | Medium | Small | Thumb |
| Courtesy of: | commons.wikimedia.org | More Like This | ||
| Keywords: Overlap-save algorithm.png en A sequence of 4 plots depicts one cycle of the Overlap-save convolution algorithm The first plot is a long sequence of data to be processed with a lowpass FIR filter The 2nd plot is one segment of the data to be processed in piecewise fashion The 3rd plot is the filtered segment with the useable portion colored red The 4th plot is the output stream with the filtered segment appended to it 2013-02-16 19 53 46 own Bob K Octave script <source lang Matlab > graphics_toolkit gnuplot M 16; h ones 1 M /M; filter impulse response L 100; output segment length La 500; input data length a 1 + randn 1 La /3; data to be filtered seg 3; segment to be computed Xa seg-1 L + 1 L+M-1 ; indices of segment to be filtered figure 1 'color' 95 1 1 1 subplot 4 1 1 set gca 'FontSize' 10 plot 1 La a 'Color' 'blue' Xa a Xa 'color' 'red' 'linewidth' 2 set gca 'color' 'white' title 'One segment of an Overlap-save algorithm' 'FontSize' 14 ; text 1 2 2 'Xn with segment k 3 in red' xlim 0 La ylim 0 2 set gca 'XTick' 100 100 La set gca 'YTick' 0 2 grid 'on' subplot 4 1 2 set gca 'FontSize' 10 plot 1 L+M-1 a Xa 'Color' 'red' set gca 'color' 'white' text 250 1 6 'X_kn' 'FontSize' 12 xlim 0 La ylim 0 2 set gca 'YTick' 0 2 set gca 'XTick' 100 100 La grid 'on' Here we use the conv function to demonstrate just the overlap discard part of the process The efficiency of the algorithm is realized by replacing conv with circular convolution H fft h zeros 1 length Xa -M ; done only once in an iterative implementation b ifft H fft a Xa ; Note that length b is different for the two implementations Circular convolution folds the trailing transition region fall time back onto the rise time transition region subplot 4 1 3 b conv a Xa h ; Xb M-1 + 1 L ; set gca 'FontSize' 10 plot 1 length b b 'Color' 'blue' Xb b Xb 'Color' 'red' 'linewidth' 2 ; set gca 'color' 'white' text 250 1 6 'Y_kn output of FIR lowpass filter' 'FontSize' 12 ; xlim 0 La ylim 0 2 set gca 'YTick' 0 2 set gca 'XTick' 100 100 La grid 'on' subplot 4 1 4 c conv a h ; Xc1 1 M-1 + seg L; Xc2 M-1 + seg-1 L + 1 L ; set gca 'FontSize' 10 plot Xc1 c Xc1 'Color' 'blue' Xc2 c Xc2 'Color' 'red' 'linewidth' 2 set gca 'color' 'white' text 250 1 6 'Yn after segment k' xlim 0 La ylim 0 2 set gca 'YTick' 0 2 set gca 'XTick' 100 100 La grid 'on' xlabel '\leftarrow n \rightarrow' 'FontSize' 12 </source> cc-zero Uploaded with UploadWizard Signal processing Convolution | ||||
