All 3 tutorials are excerpts from my book: An Introduction to Signal Processing and Fast Fourier Transform (FFT). The complete book, along with hundreds of programs is available on CD by credit card or PayPal for $20 U.S. There is no charge for shipping. To obtain your copy, click on the 'Buy Now' button under the picture below and you'll be transferred to the PayPal secure server. You do NOT need to have a PayPal account. After transferring to the PayPal secure server, follow the instructions for non-PayPal users. You should also provide an email address. PayPal emails a confirmation that your order was placed. If you have any problems ordering, please contact me: kevin@fftguru.com

By going through the PayPal secure server, your credit card information is NOT sent to the merchant.

FREQUENTLY ASKED QUESTIONS ABOUT THE BOOK

Q1: How is the book published?

A1: It's published on CD as a watermarked .pdf file. There's a lot of other material on the CD (130Mb total) and it's in .rtf, .cpp, .exe and .wav formats (see the Table of Contents in the first tutorial).

Q2: How many pages is it?

A2: 258, but the page size when printed out is 8.5" by 11". If they were printed in typical textbook size, then the page count would be about 300. And if the programs and bibliography were printed out, it would be in the thousands of pages.

Q3: How is it shipped?

A3: It goes by first class mail. 3-5 business days to the US, 5-8 days to Europe. About 9-10 days to Australia.

Q4: Is there anything new in the book?

A4: Yes, quite a bit. I had a research project on FFT for many years, and discovered a number of new things. Many of them are very useful for teaching someone about signal processing and FFT. Others relate to improving the efficiency of FFT algorithms, better ways of coding them, tonal signal estimation, etc.

Q5: Why put the first 7 Chapters on the web?

A5: Three reasons. First, I think there's a desperate need for a really good tutorial on FFT. The first 7 Chapters of my book are all relatively short, and they cover the basics up to and including inverse FFT. Second, most readers like to gauge the writing style of an author before buying a book. Third, putting it on the web is a bit of a sales pitch on my part. If you like the tutorials, you'll love the rest of the book. If anything, the later Chapters are even better than the first 7. Chapter 8, for instance, contains more content than the first 7 Chapters combined.

Q6: What operating system do I need?

A6: Windows (sorry, Mac fans). A Mac user might be able to read the .pdf file and the programs, but the compiler runs under Windows only. Of course, if you're a Mac user and you've got a C or C++ compiler on your machine, then you'll probably be OK. With a C compiler, there'll be a slight problem because in a (very) few programs, I used the C++ exponentiation function (pow). You'd have to change that code into C's double splat (x**y) for exponentiation.

Q7: With a book on CD, aren't you worried about piracy?

A7: Honest people don't steal. Unfortunately, not everyone is honest. This despite the fact that distribution or receipt of a stolen book or software is a criminal matter. The only place to get a legal copy of my book is from this web site. If you are aware of any illegal distribution/receipt of my book, please contact me using the email address shown towards the top of this web page. I would do the same if it were happening to you. Theft is a significant problem towards keeping this web page going.

Q8: What is the best way to print the tutorials?

A8: The tutorials will print out fine using the normal Adobe reader print command. The complete book, however, has to be printed somewhat differently so as to accomodate the large FFT graphs in later Chapters. Those instructions are now included in the cover letter that is shipped with the CD (and if you've lost yours, just send me an email).

Q9: Can you give a more detailed description of the Table of Contents for the later chapters?

A9: Sure. Chapter 8 introduces a variety of 8 point radix 2 decimation-in-frequency graphs. Their properties are discussed. Then a very simple graphical manipulation is used to derive decimation-in-time graphs. The same technique is used to develop higher radix and mixed radix graphs. This is followed by numerous coding examples using methods developed by the author. After that, ways of improving the efficiency of an FFT are explored in detail, along with more coding examples. Chapter 9 explores FFTs for real valued inputs. It contains a number of techniques and provides some coding examples. After that, it describes some old techniques for doing real valued FFTs via complex FFTs that are very often done inefficiently and/or wrong (the 2nd tutorial covers some of it). Numerous programming examples are provided, and other implementations are investigated. Chapter 10 deals with integer arithmetic in the FFT. Can you calculate an integer division approximation for a twiddle factor? Can you do it with a power of 2 denominator so you can right shift to divide? The chapter provides a program to do so. Chapter 11 explores FFT math. You'll learn a lot about DFT here, and see a lot of programming examples. An appendix covers sliding DFT. Chapter 12 explores windowing, convolution and FFT filtering. I use graphical interpretations as much as possible. There are programs on the CD that compute a lot of different windows, and you need to know why you need them, how they work, and when to use one versus another. This is followed by the overlap-add FFT filtering method. Several appendices follow Chapter 12, and they cover zero padding in the time or frequency domain, plus three practical examples of estimating the frequencies, amplitudes and phases of tonal input signals. The examples use an outstanding technique that will serve you well in many applications. Chapter 13 is about FIR filters. It's shown in the conventional sum-of-products form, because you need to know that you can also do filtering that way. Chapter 14 explores Autocorrelation and Cross Correlation. They are similar to convolution, but with some very important differences. Chapter 15 is about bandshifting and decimation. Specific examples are used to illustrate how they work. Chapter 16 is about FFT beamforming. The basic principles are shown with an emphasis on a graphical interpretation. A specific example based on the literature is provided. Chapter 17 deals with image processing. It uses a coding example to show how a 2 dimensional FFT works. Then it looks at where the frequency content lies in the transformed image so you can see how to filter it. After that, there are numerous examples of cross correlation for both motion detection and template matching. Certain common errors in doing cross correlations are noted. After that, whitening filters are briefly described, followed by a very important section on improving the efficiency of 2 dimensional transforms. Chapter 18 is an overview of the relation between FFT and Error Correction Coding. The latter can be interpreted using FFT related concepts. Chapter 19 contains more roulette related stuff, like bounce statistics and other things. This is followed by the References. Then an Index. Then 'Notes for the CD.' It includes descriptions of what's in the various program folders on the CD, what programs are most or least efficient, special precautions for specific programs, how to install and use the compiler, etc. Finally, there's an Afterword with a list of web links to look into - Here's a few of them:

Kevin J. McGee is the principal consultant of the company. He is available for teaching an intensive short course on Signal Processing and FFT, or to provide expert consulting/programming services. He has extensive software and hardware experience in signal processing and FFT. For 22 years, he was with the Naval Undersea Warfare Center in Newport, Rhode Island, USA. His experience includes: FFT processors (NMOS, CMOS, FPGA), beamformers, target tracking algorithms, time delay estimators, multiprocessor signal processors. In addition, many years of C, FORTRAN, BASIC and assembly programming experience. More than 50 publications - some are restricted, so they aren't available to the general public. However, a few open literature items are listed below:

K. J. McGee, "Comments on 'A 64-Point Fourier Transform Chip for Video Motion Compensation Using Phase Correlation'," IEEE J. Solid-State Circuits, vol. 33, no. 6, June 1998, pp. 928-932. (describes some transpose, bit reverse and FFT processor architectures and algorithms discovered by the author. In addition, reiterates that higher radix graphs are NOT more efficient than modified lower radix graphs - any lower radix graph can be easily modified to have the exact same computational complexity as a higher radix graph. Furthermore, a tremendous number of FFT related ideas are valuable to other processing areas).

K. J. McGee, "Comments on 'In-Place Updating of Path Metrics in Viterbi Decoders'," IEEE J. Solid-State Circuits, vol. 25, no. 4, Aug. 1990, pp. 1039-1040.

U. S. Patent 4,534,009, Pipelined FFT Processor, Aug. 6, 1985.

K. J. McGee, "Pipelined FFT Processors," IEEE Proc. 17th Asilomar Conf., Oct. 1983, pp.194-198 (the presentation and 35 handouts were correct, but the published version has an error in figures 2 and 6 - twiddle factors arrowheads are shown on the wrong side of the butterfly intersection - they should be on the left. The published text is correct. This paper also showed why higher radix graphs are NOT more computationally efficient than modified lower radix; modified lower radix complexity can be = higher radix complexity).

For business inquiries, you can contact me at:

© 2008-2011 by Kevin J. McGee