User:Visionat/sandbox

From Wikipedia, the free encyclopedia
Jump to: navigation, search


GNU C-Graph
GNU C-Graph Homepage Background.png
Homepage Background
Original author(s) Adrienne Gaye Thompson
Developer(s) GNU Project
Stable release 2.0 / August 26, 2011; 3 years ago (2011-08-26)
Written in Fortran
Operating system GNU
Available in English
Type Scientific Visualization
License GNU GPLv3+
Website www.gnu.org/software/c-graph


GNU C-Graph is a novel tool for visualizing the Convolution Theorem, a core theorem in functional analysis with applications in signal and image processing, computer vision, statistics, and other areas of applied mathematics. "C-Graph" is short for "Convolution Graph". The package is an effective aid for lecture demonstrations and lab work in colleges and universities.


Origin[edit]

The underlying work in C-Graph was conceived and developed by Adrienne Gaye Thompson in the Honours year, October 1982 to April 1983, of her BSc. degree in Electrical Engineering at the University of Aberdeen, Scotland. She coded the Fortran 77 program for her dissertation "Interactive Computer Package Demonstrating: Sampling Convolution and the FFT" (the Dissertation) on the University's Honeywell 66/80 mainframe centrally administered by the University Computing Centre.[1]

In November 2008, Thompson released NAILS (NAILS for Artificial Intelligence Lisp Solving), her suite of solutions to the exercises in the textbook LISP 3rd edition,[3] with the intention of offering the package to GNU. On being advised that NAILS could not be adopted by the GNU Project (as the book on which it is based is non-free) she contacted Free Software Foundation President Richard Stallman, who suggested that she consider the program from her Dissertation instead.

Thompson is sole author of both the Dissertation and the derivative work C-Graph, released as GNU C-Graph 2.0.[4]

Design[edit]

The Convolution Theorem[edit]

Main articles: Convolution and Convolution theorem

Convolution is regarded as the most significant concept underlying core techniques in digital signal processing.[5][6][7]

The Fourier transform of the convolution of two signals is equal to the product of their Fourier transforms. Conversely, the inverse Fourier transform of the product of their transforms equals their convolution.[8][9][10] We say that:


f*h= \mathcal{F}^{-1}\big\{\mathcal{F}\{f\}\cdot\mathcal{F}\{h\}\big\}


where f and h are two functions with convolution f*h, and  \mathcal{F} denotes the Fourier transform operator.

The Fast Fourier Transform (FFT) computes the Discrete Fourier Transform (DFT), which produces circular convolution when it is generally linear convolution in which we are interested. GNU C-Graph demonstrates the relationship between linear and circular convolution, showing that N-point circular convolution is equivalent to linear convolution when


N \ge L + M - 1


Where L and M are the lengths of f and h, zero-padded to length N.[11][12][13] Linear filters can then be efficiently implemented according to the Convolution Theorem by multiplying the DFTs then taking the inverse.[14]

Features[edit]

With the terminal window as the user interface, colourful displays demonstrating convolution can be mounted with just a few keystrokes, an interactive user-friendly dialogue obviating the need for learning code.

The C-Graph wave set consists of pulses, their periodic counterparts, as well as aperiodic functions. Sine, cosine, triangular, rectangular, sawtooth, exponential, ramp, and step signals comprise the wave set. Each waveform is defined as a scalable array of numbers. The size N of each array lies in the range [64, 1024] corresponding to the number of data points handed to the FFT. Pulses are of variable width as the periodic functions from which they are derived are of variable frequency. Error handling for user input is efficient. All graphs displayed may be retrieved for further viewing, or printing.

Visualization[edit]

C-Graph prompts the user to select two waveforms then compares their linear convolution with their circular convolution. The linear convolution is performed directly in the time domain while the circular convolution is obtained in the usual manner - multiplication of their frequency spectra followed by application of the inverse Fast Fourier Transform (FFT). C-Graph displays the waveforms chosen and their spectra generated by the FFT followed by their linear and circular convolutions.

The following are displays from a demonstration visualizing, for example, the response of a simple low-pass RC filter when excited by a triangular pulse signal. The circuit output is the convolution of the exponential impulse response with the triangular input. Here, the user has selected the number of samples N to be 128, a scaling coefficient of 40 for the exponential and, for the triangular pulse, a frequency of 0.8 Hz for the corresponding periodic triangular wave:



GNU C-Graph signals.png

Exponential and Triangular Pulse Waveforms


GNU C-Graph transforms.png

DFTs of the Waveforms


GNU C-Graph convolutions.png

Linear and Circular Convolutions

Dependencies[edit]

C-Graph 2.0 uses Alan Miller's fft_simple.f90,[15] Gnuplot for graphing, and ImageMagick to implement its splash screen. The package is written in modern Fortran.

Development[edit]

1983 Dissertation[edit]

In October 1982, Thompson was assigned the development of a signal theory teaching aid as her Dissertation project. The program was to be coded in Fortran, be interactive, menu-driven and her own independent work. She chose the convolution property of the Fourier Transform with which to begin - the mathematics of which she was already fascinated - coding subroutines to perform the linear convolution of two pulses followed by the menu-driven package offering sine, cosine, ramp and step functions. She continued with the design of subroutines to generate periodic triangular and rectangular waveforms, typical functions she believed ought to be part of any signal theory package. As time did not allow further development of the package, Thompson submitted the Dissertation in April 1983.

The use of the periodic triangular and rectangular waveforms in the background image of C-Graph's homepage (also displayed in the infobox at the top of this page) is a symbolic reference to the special interest they received.


C-Graph[edit]

Encouraged by Stallman, Thompson began the project to relearn Fortran on 5 February 2009. She originally intended to reconstruct her Dissertation code again using Fortran 77 as that seemed more efficient than learning Fortran 90/95, but members of the Usenet group comp.lang.fortran persuaded her otherwise.[16][17] Using Andy Vaught's G95 compiler, Thompson developed a preview release of C-Graph 2.0 to the stage at which she had terminated her Dissertation, releasing the preview code on 24 April 2009.[18][19]

Thompson resumed work on the package in December 2010, concluding development in March 2011. While C-Graph adverts to the "structure, sequence and organization" of the program in the Dissertation, no part of C-Graph's code is copied from the underlying work;[1] the package's features transform those of the Dissertation. Having released NAILS before embarking on the C-Graph project, her coding style is influenced by Lisp.

Plans for the next release include upgrading the implementation of the FFT algorithm, and a custom command line interface.

Reception[edit]

Download statistics suggest a worldwide C-Graph user base in the tens of thousands since the release of the package on 26 August 2011. GNU C-Graph is part of Fedora 18.

License[edit]

C-Graph is licensed under the GNU General Public License (the GPL) version 3 or any later version. In respect of identification of her Dissertation as the underlying work, the license takes advantage of the provisions of section 7 of the GPL, imposing additional terms in respect of author attribution and misrepresentation of origin.

[edit]

Thompson (who is black, a Jamaican of African descent) dedicated GNU C-Graph to all victims of apartheid and her former fiance, Eliezer Regnier, a popular Haitian-Bahamian attorney-at-law and human rights advocate who devoted his professional life to championing the cause of Haitian people in the Bahamas. Regnier died suddenly on 27 February 2010. In C-Graph, function Eliezer and subroutine Regnier (which define scaling and error handling protocols) honour him.

The C-Graph logo is a work in progress inspired by computer vision, the movie Blade Runner, and the copyright symbol.

See also[edit]

Notes[edit]

  1. ^ a b Thompson 1983. Code from BSc. Honours Dissertation.
  2. ^ Winston, P. H., & Horn, B.K.P. 1989. LISP 3rd ed. Reading, MA: Addison-Wesley. ISBN 0-201-08319-1.
  3. ^ Thompson 2008. NAILS, a software package of solutions to the exercises in LISP 3rd ed.[2]
  4. ^ Thompson, Adrienne G (2009). See the C-Graph Additional Terms pursuant to the provisions of section 7 of the GPL in respect of author attribution and misrepresentation of origin.
  5. ^ McGillem, & Cooper 1991, chap. 2 Convolution.
  6. ^ Freeman 2011, lecture 8: Convolution.
  7. ^ Smith S. W. 1997, Ch6:Convolution. Retrieved 18 March 2013.
  8. ^ McGillem, & Cooper 1991, chap. 3-10 System Function.
  9. ^ Smith, J. O. 2007 The Convolution Theorem.
  10. ^ Smith S. W. 1997, Convolution via the Frequency Domain in Ch9:Applications of the DFT; Ch18:FFT Convolution. Retrieved 18 March 2013.
  11. ^ Jones, D. 2006. Fast Convolution.
  12. ^ Oppenheim 2005, lecture 16: Linear Filtering with the DFT.
  13. ^ McGillem, & Cooper 1991, chap. 4-6 Applications of the FFT.
  14. ^ Smith, J. O. 2007. Convolution as a Filtering Operation; Filters and Convolution.
  15. ^ Alan Miller, fft_simple.f90. Derived from fft.f by Arthur Wouk.
  16. ^ Thompson (viper-2) 11 - 18 February 2009. Posts to comp.lang.fortran thread Fortran Lesson: Are these Equivalent? Members of the group persuaded Thompson to use a modern Fortran compiler.
  17. ^ a b Thompson (viper-2) 9 April 2009. Posts to comp.lang.fortran thread Petition against FORTRAN the statement "Fortress is intended to be a successor to Fortran" gave the impression that Fortran (was outmoded, doomed to be replaced by Fortress,Fortress, Language features in Wikipedia (retrieved 9 April 2009), subsequently edited with the replacement text "The name 'Fortress' is intended to connote a secure Fortran".
  18. ^ Thompson 24 April 2009. C-Graph 2.0 preview release.
  19. ^ Thompson 11 April 2009. Posts to comp.lang.fortran offered a "sneak peek" at the C-Graph 2.0 preview release.[17]

References[edit]

  • Freeman, Dennis M. (Fall 2011). 6.003 Signals and Systems. (Massachusetts Institute of Technology: MIT OpenCourseWare). License: Creative Commons BY-NC-SA.
  • McGillem, Claire D. & Cooper, George R. (1991). Continuous and Discrete Signal and System Analysis (3rd.ed.). USA: Saunders College Publishing ISBN 0030510198.
  • Thompson, Adrienne G. (1983) Interactive Computer Package Demonstrating: Sampling Convolution and the FFT, BSc. dissertation, submitted in partial fulfillment for the degree of Bachelor of Science in Engineering (Honours) University of Aberdeen, Scotland.

External Links[edit]

C-Graph Category:Free data visualization software Category:Theorems in Fourier analysis Category:Free educational software Category:Free science software Category:Free mathematics software Category:Free software programmed in Fortran