File:Overlap-save algorithm.svg
From testwiki
Jump to navigation
Jump to search
Size of this PNG preview of this SVG file: 800 × 559 pixels. Other resolutions: 320 × 223 pixels | 640 × 447 pixels | 1,024 × 715 pixels | 1,280 × 894 pixels | 2,560 × 1,788 pixels | 855 × 597 pixels.
Original file (SVG file, nominally 855 × 597 pixels, file size: 125 KB)
This file is from Wikimedia Commons and may be used by other projects. The description on its file description page there is shown below.
Summary
| DescriptionOverlap-save algorithm.svg |
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 usable 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 |
This file was derived from: Overlap-save algorithm.png |
|||
| SVG development InfoField | ||||
| Gnu Octave source InfoField | click to expand
This graphic was created with the help of the following Octave script: % Options
edge_effects_at_end_of_filter_output = true;
frame_background_gray = true;
if frame_background_gray
graphics_toolkit("qt") % or graphics_toolkit("fltk")
frame_background = .94*[1 1 1];
d = 2; % amount to add to text sizes
else
graphics_toolkit("gnuplot") % background will be white regardless of value below
frame_background = .94*[1 1 1];
d=0;
endif
M = 16; % filter length
h = ones(1,M)/M; % filter impulse response
L = 100; % output segment length
La = 500; % input data length
% randn("seed","reset") % experiment with data generator
% seed = randn("seed") % print value, in case want to use it again
randn("seed", e) % generate same data as Overlap-add_algorithm.svg
a = 1 + randn(1,La)/3; % data to be filtered
seg = 2; % segment to be computed
N = L + M-1; % DFT size (a power-of-2 would be more efficient)
Xa = seg*L + (1:N); % indices of segment to be filtered
if edge_effects_at_end_of_filter_output
%Rotate the filter coefficients
%Simple way
% H = fft([h(M) zeros(1,N-M) h(1:M-1)]);
%Fancy way
H = fft( circshift([h zeros(1,N-M)], -(M-1)) );
Xb = (1:L); % indices of good output
else
H = fft(h,N);
Xb = M-1 + (1:L); % indices of good output
endif
% (https://octave.org/doc/v4.2.1/Graphics-Object-Properties.html#Graphics-Object-Properties)
% Speed things up when using Gnuplot
set(0, "DefaultAxesFontsize",10+d)
set(0, "DefaultTextFontsize",12+d)
set(0, "DefaultAxesYlim",[0 2])
set(0, "DefaultAxesYtick",[0:2])
set(0, "DefaultAxesYgrid","on")
set(0, "DefaultAxesXlim",[0 La])
set(0, "DefaultAxesXtick",[100:100:La])
set(0, "DefaultAxesXgrid","on")
set(0, "DefaultFigureColor",frame_background)
set(0, "DefaultAxesColor","white")
%=======================================================
hfig = figure("position",[50 30 912 650], "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("position",[x_origin y_origin width height])
plot(1:La, a, "color","blue", Xa, a(Xa), "color","red", "linewidth",2)
title("One segment of an Overlap-save algorithm", "fontsize",14+d);
text(1, 2.2, "X[n], with segment k=2 in red", "fontsize",10+d)
%=======================================================
y_origin = y_origin -dy -height;
subplot("position",[x_origin y_origin width height])
plot(1:L+M-1, a(Xa), "color","red")
text(250, 1.6, 'X_k[n]')
%=======================================================
y_origin = y_origin -dy -height;
subplot("position",[x_origin y_origin width height])
% Instead of the conv() function, we demonstrate the use of circular convolution.
% Note that length(b) is different for the two implementations. Circular convolution
% combines the edge effects into half the space of conv().
%Linear convolution
% b = conv(h,a(Xa)); % length(b) = N+M-1
% Circular convolution
b = real(ifft(H .* fft(a(Xa)))); % length(b) = L+M-1 = N
plot(1:length(b), b, "color","blue", Xb, b(Xb), "color","red", "linewidth",2);
text(250, 1.6, 'Y_k[n], output of FIR lowpass filter');
%=======================================================
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);
plot(Xc1, c(Xc1), "color","blue", Xc2, c(Xc2), "color","red", "linewidth",2)
text(250, 1.6, "Y[n], after segment k")
xlabel('\leftarrow n \rightarrow', "fontsize",12+d)
|
Captions
Add a one-line explanation of what this file represents
Items portrayed in this file
depicts
14 January 2020
image/svg+xml
127,802 byte
597 pixel
855 pixel
17187c4fd5b348a848efbda85db08b6c7363fef8
File history
Click on a date/time to view the file as it appeared at that time.
| Date/Time | Thumbnail | Dimensions | User | Comment | |
|---|---|---|---|---|---|
| current | 18:30, 24 January 2020 | 855 × 597 (125 KB) | wikimediacommons>Bob K | change frame color from white to gray |
File usage
The following page uses this file: