File:Overlap-save algorithm.svg
Summary
Description |
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 Category:Derivative versions |
|||
SVG development | ||||
Gnu Octave source | 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)
|
Category:CC-Zero
Category:Created with GNU Octave
Category:Derivative versions
Category:Digital signal processing
Category:Images with Gnuplot source code
Category:Images with Octave source code
Category:Invalid SVG created with LibreOffice
Category:Overlap-save method
Category:Pages using deprecated source tags
Category:Self-published work