Years ago I worked for a company that made signal processing hardware for telemetry (I was working on a project to implement a data flow parallel processor). I worked with one engineer who would frequently drop references to FFTs and convolutions into conversations. The purpose of these references was to mention something that the listener probably did not understand but, by implication, the engineer who dropped these references did. Whether my colleague actually understood Fourier transforms and digital signal processing is an open question. But it was a successful way to "count coup" on the listener.
One reason that my ex-colleague was able to use this technique to "count coup" on his fellow engineers is that most material on Fourier analysis is daunting for those of us with only a basic college calculus background. A lot of it looks like a long series of infinite integrals, theorems and proofs, interspersed with a few narrative paragraphs. Even books on applications of Fourier transforms tend to fall into this category (for example, Chapter 10, The Fourier Transform, in Digital Image Processing by Kenneth Castleman).
I never made much progress with the material on Fourier analysis. I came to believe that Fourier analysis, like microwave antenna design, was something that only the more mathematically gifted could understand. Then I started studying wavelet transforms. From reading through the wavelet literature it became clear that the Fourier transform and related digital signal processing filters provided an intellectual foundation for wavelets. In fact, several books on wavelets have chapters or sections on Fourier analysis. But like the references I'd seen before, this material is heavy on integrals and lighter on explanation.
Amazon has gotten very good at pointing their customers to books that they did not previously know they wanted to buy. One way they do this is via book lists, submitted by Amazon customers. While searching for wavelet references I found a recommendation for Richard G. Lyons' fantastic (stellar, wonderful) book Understanding Digital Signal Processing. This is the best introduction to digital signal processing I've ever seen. Its possible that it is the best introduction to digital signal processing ever written. The book is written in a light style and concentrates on application. Lyons is a practicing DSP engineer, not an academic. Important theorems are mentioned, but not proved (for those who want a mathematically "rigorous" introduction to Fourier analysis there are many other books available). Lyons totally de-mystifies Fourier Analysis. He writes for the DSP software engineer who, like me, has only a basic college math background.
This web page might be considered an on-line notebook that I've compiled while reading Understanding Digital Signal Processing by Lyons. As Lyons notes in the beginning of the book, a real understanding of digital signal processing algorithms cannot be developed without applying them. This web page published various Java classes that I've developed with reading Lyons' book. My intent is not to explain digital signal processing. For that you should buy Lyons' book. But it is possible that if you are studying this book, the software here will save you some time. If nothing else this web page, and the related software will be a useful reference for me.
Obviously any errors, inaccuracies or misunderstandings are mine and cannot be attributed to Understanding Digital Signal Processing.
My interest in Fourier analysis and digital filters comes from my interest in wavelets. And my interest in wavelets was motivated by their possible application to financial time series. This has given my approach to Fourier analysis a certain bias. I am not particularly interested issues regarding sampled frequency. I am much more interested in the components that make up a time series (or signal) and how some components can be emphasized over others (e.g., digital filtering). If I were designing digital signal processing hardware this would not be the case. Lyons does an excellent job covering sampling frequency issues. These issues are not covered much here because they don't correspond to my current application of Fourier analysis.
The graphs on these web pages were generated with gnuPlot. GnuPlot is reasonably good at generating 2-D plots, although it is weak when it comes to 3-D plots. Click here for my notes on gnuPlot.
A number of the web pages below contain links to Java source code. Obviously familiarity with Java is needed to fully understand this code, although I hope it will be readable for anyone who knows C++. I've provided this code for reference. I hope that by looking at the relatively simple functions it will be obvious how I implemented the algorithms.
The code is divided into two Java packages: util and fourier. The util package contains the class defintions for the complex number container and similar support classes. The fourier package contains the Fourier transform related classes. These can be found on the web pages that cover related topics. In Java the classes that make up a package are placed in a sub-directory, which has the same name as the package. You can collect the various Java files you find useful in the package directories and write your own code to use these classes (this code would be placed in the directory above the package directories).
As I wrote above, the Java code is for reference. I don't provide support for this code. If there are bugs or errors in the algorithms I'd like to know. But compiling and using this code is up to you, dear reader.
Some of the software published on these pages is packaged in "tar" format. The tar program is a UNIX archiving program. Perhaps because I'm a long time UNIX hacker, I prefer it to the zip utilities, at least for small amounts of data where compression is not a concern (and then I prefer gzip, the GNU compression program). The tar program can be found on all UNIX systems, Linux and, I assume, Apple's OS X. You can down load tar for Windows NT (Win32) here.
Every once in a while I get e-mail from university students about these web pages. So I'm going to offer some unasked for advice (older people are a pain, aren't they).
I have never taken a class in DSP. With the help of Lyons' wonderful book I was able to teach myself the material that is discussed on these pages. In fact, these pages are my notes that I wrote up while learning this material.
The ideas and language of DSP and DSP filters underlies wavelets, which is how I came to study Lyons' stellar book. I have found DSP (both Fourier and wavelet based) fascinating. My strange journey into signal processing has taken over a year, much of this after work and on weekends. Some of this developed into a five month project at my "day job". Especially in the case of wavelets there have been times when I have been frustrated, but over all I recommend what has been, for me, a fascinating journey.
I hope that these web pages will help you understand the DFT faster. If you don't have a copy of Lyons' book, I enthusiastically recommend it (you probably already guessed this). It is a great book by a wonderful man. Use the source code published here for reference, but write your own code. Get experience applying these algorithms (or the FFT) and the more complex filers. If you do not do this, you will only be robbing yourself. I've been through the University grind too. To survive you need to get the grades. But in the long run what you take with you is between your ears, not on your transcript.
Foundations: complex numbers and signal generators
This web page contains the util package which is used by the other Java packages. So I recommend downloading this code if you plan to compile the other code published here.
Ian Kaplan, September 2001
Revised: January 2002