File:Overlap-save algorithm.svg

Page contents not supported in other languages.
This is a file from the Wikimedia Commons
From Wikipedia, the free encyclopedia

Original file(SVG file, nominally 855 × 597 pixels, file size: 125 KB)

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:
Creative Commons CC-Zero This file is made available under the Creative Commons CC0 1.0 Universal Public Domain Dedication.
The person who associated a work with this deed has dedicated the work to the public domain by waiving all of their rights to the work worldwide under copyright law, including all related and neighboring rights, to the extent allowed by law. You can copy, modify, distribute and perform the work, even for commercial purposes, all without asking permission.

Other versions This file was derived from: Overlap-save algorithm.png
SVG development
InfoField
 
The source code of this SVG is invalid due to 5 errors.
 
This W3C-invalid vector image was created with LibreOffice.
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

File history

Click on a date/time to view the file as it appeared at that time.

Date/TimeThumbnailDimensionsUserComment
current17:30, 24 January 2020Thumbnail for version as of 17:30, 24 January 2020855 × 597 (125 KB)Bob Kchange frame color from white to gray
15:06, 23 January 2020Thumbnail for version as of 15:06, 23 January 2020855 × 607 (101 KB)Bob Ktrace 3: edge effects moved to end of filter output
14:12, 19 January 2020Thumbnail for version as of 14:12, 19 January 2020855 × 607 (102 KB)Bob Kchange seed value to "e"
15:37, 18 January 2020Thumbnail for version as of 15:37, 18 January 2020855 × 607 (101 KB)Bob Kincrease a font size
13:13, 17 January 2020Thumbnail for version as of 13:13, 17 January 2020855 × 630 (104 KB)Bob Kdemonstrate circular convolution
02:48, 15 January 2020Thumbnail for version as of 02:48, 15 January 2020855 × 630 (104 KB)Bob Kmore interesting signal specimen
01:41, 15 January 2020Thumbnail for version as of 01:41, 15 January 2020855 × 630 (100 KB)Bob KUser created page with UploadWizard
The following pages on the English Wikipedia use this file (pages on other projects are not listed):

Metadata