\input texinfo @c -*-texinfo-*-
@c %**start of header
@setfilename c-graph.info
@include version.texi
@settitle GNU C-Graph @value{VERSION}
@c Uncomment the next line to print each chapter on a new odd-numbered page.
@setchapternewpage odd
@c @setchapternewpage on
@paragraphindent none
@defindex cg
@syncodeindex cg cp
@footnotestyle end
@c %**end of header
@macro dedicate
@sp 45
@center @emph{for} @strong{ALL the VICTIMS of APARTHEID STRUGGLING to be FREE}
@sp 1
@center @emph{and}
@sp 1
@center @emph{to} @strong{REGNIER}
@sp 2
@center @emph{You're sending me discrete signals from across the room,}
@sp 1
@center @emph{I respond on impulse, reflecting on the sampling of events}
@sp 1
@center @emph{That were a dichotomy from the day you left your mother's womb;}
@sp 1
@center @emph{Multiplied in frequency, integrated in time, a weighted confluence}
@sp 1
@center @emph{Of sliding, shifting trains of thought, alternative messages under transformation;}
@sp 1
@center @emph{Counterpoint, duality, involution, contradistinction without confusion;}
@sp 1
@center @emph{Independence in summation. Silence - this is convoluted conversation.}
@sp 5
@page
@end macro
@copying
This is a manual for GNU C-Graph version @value{VERSION}, a tool for
learning about convolution.
Copyright @copyright{} 1982, 1983, 1996, 2008, 2009, 2010, 2011 Adrienne
Gaye Thompson, Sole Author. GNU C-Graph version 2.0. Derived from
BSc. dissertation "Interactive Computer Package Demonstrating: Sampling
Convolution and the FFT", University of Aberdeen, Scotland (1983). For
the code from the dissertation, visit
.
@quotation
Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.2 or
any later version published by the Free Software Foundation; with no
Invariant Sections, with no Front-Cover Texts, and with no Back-Cover
Texts. A copy of the license is included in the section entitled
``GNU Free Documentation License''.
@end quotation
@end copying
@dircategory Mathematics
@direntry
* C-Graph:: Tool for demonstrating convolution.
@end direntry
@c prevent TEX from inserting black rectangle for overfull xboxes.
@finalout
@titlepage
@title GNU C-Graph
@subtitle A Tool for Learning about Convolution
@subtitle GNU C-Graph version @value{VERSION}, @value{UPDATED}
@author Adrienne Gaye Thompson (@email{agt@@codeartnow.com})
@page
@vskip 0pt plus 1filll
@insertcopying
@end titlepage
@dedicate
@contents
@ifnottex
@node TOP
@top C-Graph:
This is a manual for GNU C-Graph version @value{VERSION}, a tool for
learning about convolution.
@end ifnottex
@menu
* Foreword:: Origin and Motivaton
* Overview:: Description of C-Graph
* Invoking C-Graph:: How to Run C-Graph
* The Signals:: Selecting the Signals
* A C-Graph Session:: A Typical C-Graph Session
* Reporting Bugs:: Bug Reports and Suggestions
* Appendix A:: A Sketch of Convolution Theory
* Appendix B:: References
* GNU Free Documentation License:: Sharing This Document
* Index:: Index
@end menu
@node Foreword
@chapter Foreword
@cindex convolution
@cindex Dissertation
@cindex Thesis, see Dissertation
From the shadow cast by light to the echo in a cave convolution, like
the ubiquitous Fibonacci series, is a mathematical description of
naturally ocurring physical phenomena in any linear, time-invariant
system capable of responding to an input signal. Today, convolution -
the combination of two signals to produce a third - has wide ranging
applications. Edge detection in computer vision, algorithms for robot
motion, signal and image processing, crystallography, statistics and
probability theory, differential equations, linear algebra, numerical
analysis, and even recent innovations in music production - all utilise
techniques involving convolution.
GNU C-Graph (for Convolution Graph) is a tool for visualizing the
convolution of two signals. The package is a reproduction of the Fortran
77 program in my BSc. Electrical Engineering (Honours) dissertation
"Interactive Computer Program Demonstrating: Sampling Convolution and
the FFT", University of Aberdeen, Scotland, 1983. In this version I have
included pulses, scaling of the signals, and error-handling - features
that were not part of my original Thesis.
Whether student engineer or scientist, aspiring special-effects animator
or roboticist, GNU C-Graph will help you find the adventure in the
mathematics of convolution.
-- @emph{Adrienne Gaye Thompson}
@node Overview
@chapter Overview
@menu
* About:: About C-Graph
* Required Software:: Dependencies
@end menu
@node About
@section About
@cindex FFT
@cindex DFT
@cindex Fast Fourier Transform, see FFT
@cindex discrete Fourier transform, see DFT
@cindex convolution
GNU C-Graph computes the linear convolution of two signals in the time
domain then compares their circular convolution by demonstrating the
@dfn{convolution theorem} - convolution of two signals in the time
domain corresponds to multiplication in the frequency domain. Each
signal is modelled by a register of discrete values simulating samples
of a signal, and the discrete Fourier transform (DFT) computed by means
of the Fast Fourier Transform (@dfn{FFT}). @xref{Appendix A}, for an
explanation of the convolution theorem.
GNU C-Graph is interactive, prompting the user to enter single character
or numerical values from the keyboard, thereby dispensing with the
learning curve for coding formulae. The user chooses 2 from a menu of 8
signal types, and up to 5 parameters to define the waveforms. The
signals chosen may be periodic, aperiodic, or pulses. C-Graph then plots
3 graphs:
@enumerate
@item The time domain representation of both signals;
@item Their Fourier transforms;
@item A comparison of their linear and circular convolution.
@end enumerate
@xref{A C-Graph Session}, for a typical C-Graph session.
@cindex FFT
GNU C-Graph will be useful to students of signal theory in the study of
convolution and spectral analysis. This version (2.0) uses a simple FFT
written by Arthur Wouk and converted to Fortran 90 by Alan Miller
(@pxref{Appendix B}).
@node Required Software
@section Required Software
GNU C-Graph is written in contemporary Fortran. The package runs on
GNU/Linux, was developed with GFortan and G95, and uses Gnuplot 4.2 as
well as Image Magick 6.6.
Experienced users wishing to use other compilers may supply the
necessary command-line options to @command{configure} during
installation. See the file @file{INSTALL} for basic installation
instructions.
@node Invoking C-Graph
@chapter Invoking C-Graph
To run GNU C-Graph, open up a terminal in X and type
@command{c-graph}. C-Graph supports the following options:
@table @option
@item --dedicate
@itemx -d
@cgindex --dedicate
@cgindex -d
Print the dedication and exit.
@item --help
@itemx -h
@cgindex --help
@cgindex -h
Print a summary of the command line options and exit.
@item --no-splash
@itemx -n
@cgindex --no-splash
@cgindex -n
Invoke GNU C-Graph with no splash screen.
@item --version
@itemx -v
@cgindex --version
@cgindex -v
Print the version number and licensing information of GNU C-Graph, then
exit.
@end table
@node The Signals
@chapter The Signals
@cindex signals, types of waveforms
@menu
* The Menu:: Available signals for convolution
* Parameters:: Input parameters for signal generation
* Defaults & Error Handling:: Assumptions for unexpected input
* Frequency Selection:: Frequency arithmetic
@end menu
@node The Menu
@section The Menu
C-Graph presents the following menu of signals from which the user
chooses 2:
@multitable {Exponential ...} {CODE}
@headitem @code{SIGNAL} @tab @code{CODE}
@item @code{Sine}
@tab @code{A}
@item @code{Cosine}
@tab @code{B}
@item @code{Triangle}
@tab @code{C}
@item @code{Square}
@tab @code{D}
@item @code{Sawtooth}
@tab @code{E}
@item @code{Exponential}
@tab @code{F}
@item @code{Ramp}
@tab @code{G}
@item @code{Step}
@tab @code{H}
@end multitable
@cindex periodic signals
@cindex aperiodic signals
@cindex pulse signals
Signals @samp{A} to @samp{E} are periodic, while @samp{F}, @samp{G},
and @samp{H} are aperiodic. Pulses may also be chosen; these are
a half period in duration @math{1/2f}, where @math{f} is the
frequency of the corresponding cyclical waveform.
@node Parameters
@section Parameters
@cindex waveform parameters
@cindex parameters
@cindex number of samples
@cindex samples, number of
@cindex pulses, selecting
@cindex periodic wavform, selecting
@cindex frequency, selecting
@cindex scaling the signals
The user enters up to 5 parameters to generate the signals, their FFTs
and their convolution:
@enumerate
@item The number of samples @samp{N}
@item The code for the signal @samp{A} to @samp{H}
@item The wave/pulse parameter @samp{w} or @samp{p}
@item The frequency @samp{f}
@item The scaling coefficient @samp{sc}
@end enumerate
Both signals are constructed from the same number of samples
@samp{N}. If the user chooses a periodic signal, then he/she is prompted
to select either the cyclical waveform or a derived pulse, i.e.,
@samp{w} or @samp{p}. For each periodic signal chosen the user is
prompted to enter its frequency @samp{f} and a scale factor
@samp{sc}.
Pulses are monophasic and are defined on half the period of the
modulus of the corresponding periodic waveform.
@node Defaults & Error Handling
@section Defaults & Error Handling
@cindex default values
@cindex erroneous data
If the required parameter is a number and the user has erroneously
entered character data, C-Graph generates an error message and gives the
user another try to enter a number. Otherwise, for input outside the
expected ranges C-Graph assumes default values.
@table @code
@item Number of samples @samp{N}
@samp{N} must lie in the range [64, 1024]. Values entered outside of
this range will default to 512. @samp{N} is defined to be a power of
2. If the user enters a value that is not a power of 2 C-Graph will
choose the nearest power of 2.
@item Signal code @samp{A} to @samp{H}
For input outside the range @samp{A} to @samp{H}, the default codes are
@samp{C} for the first signal, and @samp{D} for the second.
@item Wave/Pulse parameter @samp{w} or @samp{p}
The default waveform is a pulse.
@item Frequency @samp{f}
C-Graph assumes a default frequency of 1Hz for values of @samp{f}
entered outside the range [0.5, @math{N/4}].
@item Scaling coefficient @samp{sc}
The scaling coefficient @samp{sc} may be positive or negative. The
maximum absolute value of @samp{sc} for signals a, b, f, and h is
@samp{N},while that for signals c,d,e, and g is 1. All signals will be
scaled to unity for input values of @samp{sc} outside the permitted
range.
With the default scaling coefficient of 1, signals a, b, f, and h are
unit functions; signals d (square) an e (sawtooth) have a maximum
amplitude of half the period (1/(2f)) while that of c (triangle) is
one-quarter the period (1/(4f)).
@end table
@node Frequency Selection
@section Frequency Selection
@cindex frequency
We can express the period @math{P} of a periodic signal as
@example
@group
@multitable {@math{P}} {@math{= T/(number of cycles)}}
@item @math{P} @tab @math{= N/(number of cycles)}
@item @tab @math{= T/(N/n)}
@end multitable
@end group
@end example
where @math{T} is the duration ofthe signal register in seconds,
@math{N} is the number of samples in the register (window length), and
@math{n} is the number of samples in 1 period.
The frequency of the signal @math{f} is the reciprocal of the period, so
@example
@multitable {@math{f}} {@math{= N/(nT) samples/seconds or Hz}}
@item @math{f} @tab @math{= N/(nT) samples/seconds or Hz}
@end multitable
@end example
C=Graph assumes that the duration of the signal register is 1 second, so
@example
@multitable {@math{f}} {@math{= N/n) Hz}}
@item @math{f} @tab @math{= N/n) Hz}
@end multitable
@end example
@cindex sampling rate
The sampling rate @math{f_s} is given by
@example
@multitable {@math{f_s}} {@math{= N/T Hz}}
@item @math{f_s} @tab @math{= N/T Hz}
@end multitable
@end example
The interval @math{h} between successive samples being the reciprocal
@example
@multitable {h} {@math{= 1/f_s seconds}}
@item @math{h} @tab @math{= 1/f_s seconds}
@end multitable
@end example
@need 2000
If the window length and frequency chosen are 512 and 20 Hz
(approximately the lower limit of the human audible range) then the number
of samples @math{n} in each period would therefore be
@example
@group
@multitable {@math{n}} {@math{= 512/20}}
@item @math{n} @tab @math{= N/f}
@item @tab @math{= 512/20}
@item @tab @math{= 25.6}
@end multitable
@end group
@end example
@need 2000
C-Graph requires that @math{n} be a multiple of 4. For each periodic
signal, the frequency entered by the user is accordingly adjusted so
that @math{n} approximates to the nearest multiple of 4. So the frequency
of the signal used by C-Graph would become
@example
@group
@multitable {@math{f}} {@math{= 512/26}}
@item @math{f} @tab @math{= N/n}
@item @tab @math{= 512/26}
@item @tab @math{= 19.7 Hz}
@end multitable
@end group
@end example
@node A C-Graph Session
@chapter A C-Graph Session
@cindex example run
@cindex splash screen
In this session, we run C-Graph twice to compare the convolution of 2
signals of equal length:
@enumerate
@item When the signals are finite sequences and the remaining interval
is zero padded to the @samp{N} with at least the same number of zeros
as samples in each signal;
@item When both signals extend across the full register of @samp{N} samples.
@end enumerate
We use a sawtooth pulse for the first signal, and a rectangular pulse
half the amplitude of the sawtooth for the second signal. We also
demonstrate the use of default values for unexpected input. The keychord
@kbd{ALT-@key{TAB}} is used to toggle the terminal and the Gnuplot
window.
In X, type @command{c-graph}. The splash screen will appear for a few
seconds. Pressing @kbd{ESC} will kill the display, but you may invoke
C-Graph without the splash screen with the @command{--no-splash}
option. When the splash screen disappears, the following text will
appear:
@example
GNU C-Graph version 2.0
Dedicated to Eliezer Regnier and all victims of apartheid.'
Copyright @copyright{} 1982, 1983, 1996, 2008, 2009, 2010, 2011 Adrienne
Gaye Thompson, Sole Author. GNU C-Graph version 2.0. Derived from
BSc. dissertation "Interactive Computer Package Demonstrating: Sampling
Convolution and the FFT", University of Aberdeen, Scotland (1983). For
the code from the dissertation, visit
.
GNU C-Graph is free software licensed under the terms of the GNU General
Public License (the GPL) version 3 or later. You are welcome to
distribute it under certain conditions.
GNU C-Graph is distributed WITHOUT ANY WARRANTY
without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE.
See the GPL section 15 regarding disclaimer of warranty.
Press then to display the GPL, or just press to
continue.
C-Graph:>> @kbd{RET}
THIS IS GNU C-Graph - a tool for visualizing convolution.
Compare the linear convolution of two signals with their circular
convolution.
@group
Signal Code
====== ====
Sine A
Cosine B
Triangle C
Square D
Sawtooth E
Unit-Exponential F
Unit-Ramp G
Unit-Step H
@end group
@group
Generate 2 signals from the above menu with up to 5 parameters:
1. Number of samples @samp{N}
2. Signal code @samp{A} to @samp{H}
3. Whether the signal, ifperiodic, is a wave @samp{w} or a pulse @samp{p}
4. The frequency @samp{f}
5. The scaling coefficient @samp{sc}
@end group
Choose a value for "N" between 64 and 1024.
C-Graph:>> @kbd{51}
The number of samples "N" is: 512
@group
Signal Code
====== ====
Sine A
Cosine B
Triangle C
Square D
Sawtooth E
Unit-Exponential F
Unit-Ramp G
Unit-Step H
@end group
Enter code for first signal
C-Graph:>> @kbd{e}
Is the signal periodic or is it a pulse?
Type "w" for periodic wave, or "p" for pulse
C-Graph:>> @kbd{p}
Select the frequency "f" of this signal.
C-Graph:>> @kbd{1.0}
The frequency of this signal is 1.00 Hz.
Do you wish to scale this signal?
Enter a value for the scaling coefficient "sc".
A coefficient of 1 will give the unit function.
C-Graph:>> @kbd{1}
@group
Signal Code
====== ====
Sine A
Cosine B
Triangle C
Square D
Sawtooth E
Unit-Exponential F
Unit-Ramp G
Unit-Step H
@end group
Enter code for second signal
C-Graph:>> @kbd{s}
Is the signal periodic or is it a pulse?
Type "w" for periodic wave, or "p" for pulse
C-Graph:>> @kbd{p}
Select the frequency "f" of this signal.
C-Graph:>> @kbd{1}
The frequency of this signal is 1.00 Hz.
Do you wish to scale this signal?
Enter a value for the scaling coefficient "sc".
A coefficient of 1 will give the unit function.
C-Graph:>> @kbd{.5}
You selected a square signal by default.
Press to see the signals in the time domain:>> @key{RET}
@image{signals}
@kbd{ALT-@key{TAB}}
Hit to continue:>> @key{RET}
View the frequency-domain representation of the signals.
Press to see their FFTs:>> @key{RET}
@image{transforms}
@kbd{ALT-@key{TAB}}
Hit to continue:>> @key{RET}
Press to compare linear and circular convolution:>> @key{RET}
@image{convolutions}
@kbd{ALT-@key{TAB}}
Hit to continue:>> @key{RET}
Exiting GNU C-Graph ...
Bye.
galactica@@regnier:~$ @command{c-graph --no-splash}
GNU C-Graph version 2.0
Dedicated to Eliezer Regnier and all victims of apartheid.'
Copyright @copyright{} 1982, 1983, 1996, 2008, 2009, 2010, 2011 Adrienne
Gaye Thompson, Sole Author. GNU C-Graph version 2.0. Derived from
BSc. dissertation "Interactive Computer Package Demonstrating: Sampling
Convolution and the FFT", University of Aberdeen, Scotland (1983). For
the code from the dissertation, visit
.
GNU C-Graph is free software licensed under the terms of the GNU General
Public License (the GPL) version 3 or later. You are welcome to
distribute it under certain conditions.
GNU C-Graph is distributed WITHOUT ANY WARRANTY
without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE.
See the GPL section 15 regarding disclaimer of warranty.
Press then to display the GPL, or just press to
continue.
C-Graph:>> @kbd{RET}
THIS IS GNU C-Graph - a tool for visualizing convolution.
Compare the linear convolution of two signals with their circular
convolution.
@group
Signal Code
====== ====
Sine A
Cosine B
Triangle C
Square D
Sawtooth E
Unit-Exponential F
Unit-Ramp G
Unit-Step H
@end group
@group
Generate 2 signals from the above menu with up to 5 parameters:
1. Number of samples @samp{N}
2. Signal code @samp{A} to @samp{H}
3. Whether the signal, ifperiodic, is a wave @samp{w} or a pulse @samp{p}
4. The frequency @samp{f}
5. The scaling coefficient @samp{sc}
@end group
Choose a value for "N" between 64 and 1024.
C-Graph:>> @kbd{521}
The number of samples "N" is: 512.
@group
Signal Code
====== ====
Sine A
Cosine B
Triangle C
Square D
Sawtooth E
Unit-Exponential F
Unit-Ramp G
Unit-Step H
@end group
Enter code for first signal
C-Graph:>> @kbd{g}
Do you wish to scale this signal?
Enter a value for the scaling coefficient "sc".
A coefficient of 1 will give the unit function.
C-Graph:>> @kbd{1}
@group
Signal Code
====== ====
Sine A
Cosine B
Triangle C
Square D
Sawtooth E
Unit-Exponential F
Unit-Ramp G
Unit-Step H
@end group
Enter code for second signal
C-Graph:>> @kbd{h}
Do you wish to scale this signal?
Enter a value for the scaling coefficient "sc".
A coefficient of 1 will give the unit function.
C-Graph:>> @kbd{q56}
That was not a number. Try again!
C-Graph:>> @kbd{256}
Press to see the signals in the time domain:>> @key{RET}
@image{signals1}
@kbd{ALT-@key{TAB}}
Hit to continue:>> @key{RET}
View the frequency-domain representation of the signals.
Press to see their FFTs:>> @key{RET}
@image{transforms1}
@kbd{ALT-@key{TAB}}
Hit to continue:>> @key{RET}
Press to compare linear and circular convolution:>> @key{RET}
@image{convolutions1}
@kbd{ALT-@key{TAB}}
Hit to continue:>> @key{RET}
Exiting GNU C-Graph ...
Bye.
@end example
@cindex graphs, printing
@cindex printing graphs
On exit, the directory @code{c-graphs} will be created. Directory
@code{c-graphs} will have 2 subdirectories containing the graphs,
Gnuplot command files, and the data used for plotting generated by the
last run. The subdirectories and files are:
@itemize @bullet
@item c-graphs/graphs: signals.png, transforms.png, convolutions.png
@item c-graphs/coms: signals.cg, transforms.cg, convolutions.cg time.dat trans.dat
@end itemize
One can then print the graphs and display them either by using a
graphics editor like Image Magick, or by executing the command files
with Gnuplot.
@node Reporting Bugs
@chapter Reporting Bugs
@cindex bugs, reporting
To report bugs or suggest enhancements for GNU C-Graph, please send
electronic mail to @email{agt@@codeartnow.com}.
@cindex checklist for bug reports
For bug reports, please include enough information for the maintainers
to reproduce the problem. Generally speaking, that means:
@itemize @bullet
@item The version numbers of GNU C-Graph (which you can find by running
@w{@samp{c-graph --version}}) and any other program(s) or
manual(s) involved.
@item Hardware and operating system names and versions.
@item The contents of any input files necessary to reproduce the bug.
@item The expected behavior and/or output.
@item A description of the problem and samples of any erroneous output.
@item Options you gave to @command{configure} other than specifying
installation directories.
@item Anything else that you think would be helpful.
@end itemize
When in doubt whether something is needed or not, include it. It's
better to include too much than to leave out something important.
@cindex patches, contributing
Patches are welcome. Please follow the existing coding style.
@node Appendix A
@appendix Sketch of Convolution Theory
@menu
* Introductory Ideas:: The idea of convolution
* The Mathematics:: The mathematics of convolution
* Linear and Circular Convolution:: Modes of convolution
@end menu
@node Introductory Ideas
@section Introductory Ideas
@cindex FFT
@cindex convolution
@cindex linear convolution
@cindex circular convolution
@cindex convolution theorem
@cindex subroutine @code{convo}
@cindex impulse response
@cindex point spread function
@cindex computer vision
GNU C-Graph compares the linear and circular convolution of two
signals. Subroutine @code{convo} computes the linear convolution
directly in the time domain, while the FFT is exploited to compute
circular convolution through the convolution theorem, which is defined
below (@pxref{The Convolution Theorem}).
Convolution is an operation by which two functions combine to produce a
third that represents a kind of moving average. This is a naturally
ocurring phenomenon that presents itself whenever there is a linear
system obeying the principles of superposition and shift/time
invariance. Accordingly, the mathematics of convolution has found
application to much of science and engineering in areas ranging from
statistics to computer vision.
The output of any linear shift invariant system may be described as the
convolution of the input with the impulse response of the system. In
computer vision, for example, where the system being considered is a
2-dimensional image, the output of the system may be blurred as a result
of the relative motion of the camera and the object. This blurred image
can be modelled by convolution of the static image with the
2-dimensional impulse response.
The 2-dimensional impulse response is called a @dfn{pointspread function}
(PSF). Each pixel in the image produces a copy of the PSF, scaled
according to the strength of the pixel and spatially
shifted. Superposition of these copies form the resultant output signal,
the system being linear and shift invariant. The output blurred image
is then a convolution that is, in fact, a linear combination of the
PSFs. The design of a filter for image restoration must then rely on
inverse convolution.
A thorough treatment of the mathematics of convolution is beyond the
scope of this manual. @xref{Appendix B}, for some references on the
subject, and related engineering theory.
@node The Mathematics
@section The Mathematics
@menu
* Deriving the Convolution Sum:: Deriving the convolution expression
* The Convolution Theorem:: The Fourier Transform
@end menu
Consideration of the 1-dimensional case simplifies the arithmetic. To
prove the convolution theorem, we first derive an expression for the
convolution of 2 signals, then apply the Fourier transform to this
expansion.
@node Deriving the Convolution Sum
@subsection Deriving the Convolution Sum
@cindex impulse signal
@cindex delta function
@cindex impulse response
@cindex convolution sum
A discrete-time signal may be modelled as a series of piecewise
rectangular pulses. The summation of all such rectangular pulses
approximates the signal @math{f}:
@example
@multitable {@math{f(n)}} {@math{= \sum_m f(m) rect(n - m) }}
@item @math{f(n)} @tab @math{= \sum_m f(m) rect(n - m)}
@end multitable
@end example
where @math{n - m} denotes the rectangle whose base on the @math{n} axis
is centred at sample @math{n=m}.
In the limit, the series of rectangular pulses approaches a continuous
signal as the pulse width tends to zero and each pulse becomes an
impulse signal. Each impulse signal can then be represented
as a scaled and shifted unit impulse simulating one sample of the
discrete signal.
@example
@multitable {@math{f(n)}} {@math{= \sum_m f(m) \delta(n - m)}}
@item @math{f(n)} @tab @math{= \sum_m f(m) \delta(n - m)}
@end multitable
@end example
@need 2000
Applying a system transform @math{M} that maps the input signal @math{f}
to the output signal @math{g},
@example
@group
@multitable {@math{g(n)}} {@math{= M [f(n) = \sum_m f(m) \delta(n - m)]}}
@item @math{g(n)} @tab @math{= M[f(n)]}
@item @math{g(n)} @tab @math{= M [f(n) = \sum_m f(m) \delta(n - m)]}
@item @tab @math{= \sum_m f(m) M[\delta(n - m)]}
@end multitable
@end group
@end example
Since the system transforms a delta function to the system @dfn{impulse
response} @math{h}
@iftex
@example
@multitable {@math{g(n)}} {@math{= \sum_m f(m) h(n - m)} @w{ } @math{(1)}}
@item @math{g(n)} @tab @math{= \sum_m f(m) h(n - m)} @w{ } @math{(1)}
@end multitable
@end example
@end iftex
@ifnottex
@example
@multitable {g[n] =} {/__ f[m] h[n - m] @w{ } (1)}
@item
@tab ___
@item
@tab \
@item g[n] =
@tab /__ f[m] h[n - m] @w{ } (1)
@item
@tab @tie{} m
@end multitable
@end example
@end ifnottex
The above expression called the @dfn{convolution sum}, denoted by
@math{f(*)h}, defines the output @math{g(n)} of the system.
@node The Convolution Theorem
@subsection The Convolution Theorem
@cindex time domain
@cindex frequency domain
@cindex convolution
@cindex convolution theorem
@cindex Euler's identity
@cindex Fourier coefficient
@cindex Fourier transform
@cindex inverse Fourier transform
@cindex system impulse response
GNU C-Graph demonstrates the @dfn{convolution theorem}. The convolution of 2
signals in the time domain is equal to the inverse Fourier transform
of the product of their transforms in the frequency domain.
Just as a signal can be represented by a linear combination of scaled
and shifted impulses, we can also describe the signal as a linear
combination of sinusoidal basis functions. The Fourier transform
exploits this representation to deconstruct the signal into frequency
components, each corresponding to a basis sinusoid.
Using Euler's identity
@example
@multitable {@math{e^{j\theta}}} {@math{= cos(\theta) + j \sin(\theta)}}
@item @math{e^{j\theta}} @tab @math{= cos(\theta) + j \sin(\theta)}
@end multitable
@end example
The sinusoidal sum representing the discrete time signal may be written
in the form
@example
@multitable @columnfractions .07 .9
@item @math{f(n)} @tab @math{= 1/N \sum\limits_{k=0}^{N-1} F(k) e^{j\omega_kn}}
@end multitable
@end example
where @math{\omega_k = 2k\pi/N}, and the @math{F(k)} are Fourier
transform coefficients indicating the strength of the kth spectral
sample of frequency @math{\omega_k} (how much of the each basis sinusoid
is present in the signal).@footnote{For a periodic signal, these
coefficients are the @math{\delta} functions of the Fourier transform.}
Accordingly, the @math{F(k)} may be computed from the signal
@example
@multitable @columnfractions .07 .9
@item @math{F(k)}
@tab @math{= \sum\limits_{n=0}^{N-1} f(n) e^{-j\omega_kn}}
@end multitable
@end example
This is the Fourier transform description of the signal as a function of
frequency.
From eqn (1), the convolution of an input signal @math{f} with the
system impulse response @math{h} to give an output @math{g} is defined
as:
@example
@multitable {@math{g(n)}} {@math{= f(*)h = \sum_m f(m) h(n - m)}}
@item @math{g(n)} @tab @math{= f(*)h = \sum_m f(m) h(n - m)}
@end multitable
@end example
@need 2000
Let the Fourier transform of @math{g(n)} be denoted by
@example
@group
@multitable @columnfractions .07 .9
@item @math{\Gamma[g(n)]} @tab @math{= g(n) e^{-j{\omega}n}}, then
@item @math{\Gamma[f(*)g]} @tab @math{= \sum_n [f(*)g] e^{-j{\omega}n}}
@item @math{\Gamma[f(*)h]}
@tab @math{= \sum_n \sum_m f(m) h(n - m)] e^{-j{\omega}n}}
@item @tab @math{= \sum_m f(m) \sum_n h(n - m) e^{-j{\omega}n}}
@end multitable
@end group
@end example
@need 2000
Changing the variable to @math{p = n - m}
@example
@group
@multitable @columnfractions .07 .9
@item @math{\Gamma[g(n)]}
@tab @math{= \sum_m f(m) \sum_p h(p) e^{-j{\omega}(m+p)}}
@item @tab @math{= \sum_m f(m)e^{-jm\omega} \sum_p h(p)e^{-j{\omega}p}}
@end multitable
@end group
@end example
Taking the inverse Fourier transform,
@example
@multitable {@math{f(*)g}} {@math{= \Gamma^{-1}[ \Gamma[f] \Gamma[h]}}
@item @math{f(*)g} @tab @math{= \Gamma^{-1}[ \Gamma[f] \Gamma[h]}
@end multitable
@end example
This is the convolution theorem.
@node Linear and Circular Convolution
@section Linear and Circular Convolution
@cindex vision, robotic
@cindex vision, computer
@cindex convolution, linear
@cindex convolution, circular
@cindex FFT
@cindex DFT
@menu
* Linear Convolution:: Actual Convolution
* Circular Convolution:: Convolution via the FFT
@end menu
The simulation of actual or linear convolution requires a sequence of
multiplications and additions that are computationally too slow for high
speed operations such as deblurring filters for precision robotic
vision control systems. The @dfn{FFT}, an algorithm for efficiently
computing the DFT, dramatically overcomes the computational load by
successively decomposing the multiplication of two sequences into
subsequences of half the length thereby reducing the number of
artithmetic operations by roughly @math{N/logN}.
The cost of this additional computational power is the treatment of the
convolving signals as periodic with @math{N} samples per period. The
resulting convolution is termed @emph{circular convolution}. It can be
shown that circular convolution and linear convolution are equivalent if
@math{N \ge L + P -1} where @math{L}, @math{M} are the unpadded lengths
of the sequences being convolved.
We illustrate the difference between linear and circular convolution
using abbreviated sequences for the pulses demonstrated in @ref{A
C-Graph Session}
@node Linear Convolution
@subsection Linear Convolution
@cindex linear convolution
As noted above (@pxref{Introductory Ideas}), in linear convolution,
each sample of @math{f} contributes a scaled and shifted copy of
the @math{h}. This is accomplished by the multiplication of the
particular sample @math{m} of @math{f} by each sample of @math{h}.
This sequential multiplication can be visualized as a physical
reflection of @math{h(m)}) about the vertical axis to obtain
@math{h(-m)} followed by discrete shifts of 1 sample interval
(@math{\delta n = 1}) along the time axis with no overlap of the signals
at the beginning and end of the translation. As the impulse response
moves along the time axis, the point by point multiplication of
coincident samples is summed. The sum at each point in the translation
is the value of the convolution sum @math{g(n)} at that point, and the
length of the convolution is @math{L + M}.
For the sequences
@example
@multitable {@math{f(m)}} {@math{= [1,1,1]}, and}
@item @math{f(m)} @tab @math{= [1,1,1]}, and
@item @math{h(m)} @tab @math{= [0,1,2]}
@end multitable
@end example
The series of operations for linear convolution
@example
@multitable {@math{f(*)h}} {@math{= [0 1 3 3 2]}, are:}
@item @math{f(*)h} @tab @math{ = [0 1 3 3 2]}, are:
@end multitable
@end example
@example
@group
@multitable {g(o) = f(m)h(0-m) =}{@w{ }0+0+0+0+0 = 0}
@item 0. @tab @w{ }1 1 1
@item @tab @w{ }2 1 0
@item @tab @w{ }---------
@item g(0) = f(m)h(0-m)
@tab @w{ }0+0+0+0+0 = 0
@end multitable
@end group
@end example
@example
@group
@multitable {g(0) = f(m)h(0-m) =}{@w{ }0+0+0+0+0 = 0}
@item 1. @tab @w{ }1 1 1
@item @tab @w{ }2 1 0
@item @tab @w{ }-------
@item g(1) = f(m)h(1-m)
@tab @w{ }0+1+0+0 = 1
@end multitable
@end group
@end example
@example
@group
@multitable {g(0) = f(m)h(0-m) =}{@w{ }0+0+0+0+0 = 0}
@item 2. @tab @w{ }1 1 1
@item @tab @w{ }2 1 0
@item @tab @w{ }-----
@item g(2) = f(m)h(2-m) =
@tab @w{ }2+1+0 = 3
@end multitable
@end group
@end example
@example
@group
@multitable {g(0) = f(m)h(0-m) =}{@w{ }0+0+0+0+0 = 0}
@item 3. @tab @w{ }1 1 1
@item @tab @w{ }2 1 0
@item @tab @w{ }-------
@item g(3) = f(m)h(3-m) =
@tab @w{ }0+2+1+0 = 3
@end multitable
@end group
@end example
@example
@group
@multitable {g(0) = f(m)h(0-m) =}{@w{ }0+0+0+0+0 = 0}
@item 4. @tab @w{ }1 1 1
@item @tab @w{ }2 1 0
@item @tab @w{ }---------
@item g(4) = f(m)h(4-m) =
@tab @w{ }0+0+2+0+0 = 2
@end multitable
@end group
@end example
@node Circular Convolution
@subsection Circular Convolution
@cindex circular convolution
We can imagine circular convolution in terms of the relative rotation of
two concentric cylinders whose circumferences are of length @math{N}. A
copy of the @math{N} samples comprising @math{f} is wrapped
anticlockwise round one cylinder, while a copy of @math{h} is wrapped
clockwise round the other cylinder, reflecting @math{h} . Rotating the
second cylinder anticlockwise by 1 sample interval each time,
multiplying the coincident samples and summing will give corresponding
values of the convolved signal @math{g}.
@example
@multitable {@math{f(m)}} {@math{= [1,1,1]}, and}
@item @math{f(m)} @tab @math{= [1,1,1]}, and
@item @math{h(m)} @tab @math{= [0,1,2]}
@end multitable
@end example
The series of operations for circular convolution
@example
@multitable {@math{f(*)h}} {@math{= [0 1 3 3 2]}, are:}
@item @math{f(*)h} @tab @math{= [0 1 3 3 2]}, are:
@end multitable
@end example
@example
@group
@multitable {g(o) = f(m)h(0-m) =}{@w{ }0+0+0 = 0}
@item 0. @tab @w{ }1 1 1
@item @tab @w{ }0 2 1
@item @tab @w{ }-----
@item g(0) = f(m)h(0-m)
@tab @w{ }0+2+1 = 3
@end multitable
@end group
@end example
@example
@group
@multitable {g(o) = f(m)h(0-m) =}{@w{ }0+0+0 = 0}
@item 1. @tab @w{ }1 1 1
@item @tab @w{ }1 0 2
@item @tab @w{ }-----
@item g(1) = f(m)h(1-m)
@tab @w{ }1+0+2 = 3
@end multitable
@end group
@end example
@example
@group
@multitable {g(o) = f(m)h(0-m) =}{@w{ }0+0+0 = 0}
@item 2. @tab @w{ }1 1 1
@item @tab @w{ }2 1 0
@item @tab @w{ }-----
@item g(2) = f(m)h(2-m)
@tab @w{ }2+1+0 = 3
@end multitable
@end group
@end example
By zero-padding each sequence of length @math{L = 3} to length @math{N}
so that @math{N\ge L + L -1} (@pxref{Linear and Circular Convolution}),
we obtain the sequences
@example
@multitable {@math{f(m)}} {@math{= [1,1,1,0,0]}}
@item @math{f(m)} @tab @math{= [1,1,1,0,0]}
@item @math{h(m)} @tab @math{= [0,1,2,0,0]}
@end multitable
@end example
Circular convolution then achieves the same as result as linear
convolution:
@example
@multitable {@math{f(*)h}} {@math{= [0 1 3 3 2]}}
@item @math{f(*)h} @tab @math{= [0 1 3 3 2]}
@end multitable
@end example
The operations are:
@example
@group
@multitable {g(o) = f(m)h(0-m) =}{@w{ }0+0+0+0+0 = 0}
@item 0. @tab @w{ }1 1 1 0 0
@item @tab @w{ }0 0 0 2 1
@item @tab @w{ }---------
@item g(0) = f(m)h(0-m)
@tab @w{ }0+0+0+2+1 = 0
@end multitable
@end group
@end example
@example
@group
@multitable {g(o) = f(m)h(0-m) =}{@w{ }0+0+0+0+0 = 0}
@item 1. @tab @w{ }1 1 1 0 0
@item @tab @w{ }1 0 0 0 2
@item @tab @w{ }-----
@item g(1) = f(m)h(1-m)
@tab @w{ }1+0+0+0+2 = 1
@end multitable
@end group
@end example
@example
@group
@multitable {g(o) = f(m)h(0-m) =}{@w{ }0+0+0+0+0 = 0}
@item 2. @tab @w{ }1 1 1 0 0
@item @tab @w{ }2 1 0 0 0
@item @tab @w{ }---------
@item g(2) = f(m)h(2-m)
@tab @w{ }2+1+0+0+0 = 3
@end multitable
@end group
@end example
@example
@group
@multitable {g(o) = f(m)h(0-m) =}{@w{ }0+0+0+0+0 = 0}
@item 3. @tab @w{ }1 1 1 0 0
@item @tab @w{ }0 2 1 0 0
@item @tab @w{ }---------
@item g(3) = f(m)h(3-m)
@tab @w{ }0+2+1+0+0 = 3
@end multitable
@end group
@end example
@example
@group
@multitable {g(o) = f(m)h(0-m) =}{@w{ }0+0+0+0+0 = 0}
@item 4. @tab @w{ }1 1 1 0 0
@item @tab @w{ }0 0 2 1 0
@item @tab @w{ }---------
@item g(4) = f(m)h(4-m)
@tab @w{ }0+0+2+1+0 = 2
@end multitable
@end group
@end example
@node Appendix B
@appendix References
@cindex Dissertation
@cindex Thesis, see Dissertation
The sources below were consulted in the preparation of GNU C-Graph and/or
the 1983 dissertation [1] from which GNU C-Graph is derived.
@sp 1
@enumerate
@item Thompson, Adrienne G. ''Interactive Computer Package
Demonstrating: Sampling Convolution and the FFT'', BSc. Engineering
Honours thesis, University of Aberdeen (Scotland),
1983, see @uref{http://codeartnow.com/law-project}.
@item Horn, Berthold, K. P. @emph{Robot Vision}. MIT Press, Cambridge,
Massachusetts, 1986.
@item McGillem, Clare D., and Cooper, George R. @emph{Continuous and
Discrete Signal and System Analysis}. Holt, Rinehart and Winston, Inc.,
1990.
@item Oppenheim, Alan V., and Schafer, Ronald W. @emph{Digital Signal
Processing}. Prentice-Hall, Englewood Cliffs, N.J., 1975.
@item Smith, Steven W. @emph{The Scientist and Engineer's Guide to Digital
Signal Processing} @uref{http://www.dspguide.com}
@item Stremler, Ferrel G. @emph{Introduction to Communication
Systems}. Addison-Wesley Publishing Co. Inc, 1977.
@item Wouk, Arthur. @emph{fft-simple.f90}. Ed. Alan
Miller. 2003. Retrieved from
@uref{http://jblevins.org/mirror/amiller/fft_simple.f90}
@item Yuen, C. K. and Fraser, D. @emph{Digital Spectral Analysis}.
CSIRO/Pitman, East Melbourne, Australia, 1979.
@item Ziemer, Rodger E., Tranter, William H., Fannin,
D. Ronald. @emph{Signals Systems Continuous and Discrete}. 4th
ed. Prentice Hall, Upper Saddle River, NJ 07458 1998.
@end enumerate
@node GNU Free Documentation License
@appendix GNU Free Documentation License
@include fdl.texi
@node Index
@unnumbered Index
@printindex cp
@bye