File:Overlap-save algorithm.png
Original file (912 × 548 pixels, file size: 110 KB, MIME type: image/png)
Captions
Summary[edit]
DescriptionOverlap-save algorithm.png |
English: 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. |
|||||
Date | ||||||
Source | Own work | |||||
Author | Bob K | |||||
Permission (Reusing this file) |
I, the copyright holder of this work, hereby publish it under the following license:
|
|||||
Other versions |
|
|||||
PNG development InfoField | This PNG graphic was created with LibreOffice. |
|||||
Octave/gnuplot source InfoField | click to expand
This graphic was created with the help of the following Octave script: graphics_toolkit gnuplot
M = 16; % filter length
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 = 2; % segment to be computed
N = L + M-1; % DFT size
Xa = seg*L + (1:N); % indices of segment to be filtered
frame_background = .95*[1 1 1];
%=======================================================
hfig = figure("position",[100 100 912 650], "color",frame_background);
set(gca,"color",frame_background)
set(gcf,"color",frame_background)
x1 = .02; % left margin
x2 = .02; % right margin
y1 = .09; % bottom margin for annotation
y2 = .08; % top margin for title
dy = .05; % vertical space between rows
width = 1-x1-x2;
height= (1-y1-y2-3*dy)/4; % space allocated for each of 4 rows
x_origin = x1;
y_origin = 1; % start at top of graph area
%=======================================================
y_origin = y_origin -y2 -height; % position of top row
% subplot() undoes all the "color" attempts above. (gnuplot bug)
subplot("position",[x_origin y_origin width height])
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, "X[n], with segment k=2 in red")
xlim([0 La])
ylim([0 2])
set(gca, "ytick",[0:2])
set(gca, "xtick",[100:100:La])
grid("on")
%=======================================================
y_origin = y_origin -dy -height;
subplot("position",[x_origin y_origin width height])
set(gca,"fontsize",10)
plot(1:L+M-1, a(Xa), "color", "red")
set(gca, "color", "white")
text(250, 1.6, 'X_k[n]', "fontsize",12)
xlim([0 La])
ylim([0 2])
set(gca, "ytick",[0:2])
set(gca, "xtick",[100:100:La])
grid("on")
%=======================================================
y_origin = y_origin -dy -height;
subplot("position",[x_origin y_origin width height])
% 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.
% 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.
% Circular convolution
% H = fft(h,N);
% b = real(ifft(H .* fft(a(Xa)))); % length(b) = L+M-1 = N
%Linear convolution
b = conv(h,a(Xa)); % length(b) = N+M-1
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_k[n], 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")
%=======================================================
y_origin = y_origin -dy -height;
subplot("position",[x_origin y_origin width height])
c = conv(h,a);
Xc1 = 1 : M-1 + (seg+1)*L;
Xc2 = M-1 + seg*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, "Y[n], 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)
|
File history
Click on a date/time to view the file as it appeared at that time.
Date/Time | Thumbnail | Dimensions | User | Comment | |
---|---|---|---|---|---|
current | 00:00, 15 April 2015 | 912 × 548 (110 KB) | Bob K (talk | contribs) | Annotate the portion of the current segment that is "saved" for the next segment. | |
16:11, 19 February 2013 | 1,133 × 681 (63 KB) | Bob K (talk | contribs) | Change figure background to a light gray. | ||
01:00, 17 February 2013 | 1,122 × 684 (26 KB) | Bob K (talk | contribs) | User created page with UploadWizard |
You cannot overwrite this file.
File usage on Commons
The following 2 pages use this file:
Metadata
This file contains additional information such as Exif metadata which may have been added by the digital camera, scanner, or software program used to create or digitize it. If the file has been modified from its original state, some details such as the timestamp may not fully reflect those of the original file. The timestamp is only as accurate as the clock in the camera, and it may be completely wrong.
PNG file comment |
|
---|---|
Horizontal resolution | 28.35 dpc |
Vertical resolution | 28.35 dpc |
File change date and time | 23:53, 14 April 2015 |