The 1st tutorial consists of the first 7 chapters of my book: An Introduction to Signal Processing and Fast Fourier Transform (FFT). The 2nd tutorial comes from Chapter 9 - FFT for Real Valued Inputs. The 3rd tutorial is from the Chapter on Image Processing. The complete book, along with hundreds of programs, C++ compiler and much more 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. I also need it to send updates. 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.

You can also order by mail by sending a check or money order for $20 U.S. to:

Please make sure that your shipping address is correct and include an email address. I need a way to contact you if there is any problem with shipping.

FREQUENTLY ASKED QUESTIONS ABOUT THE BOOK

Q1: How is the book published?

A1: It's published on CD as a .pdf file, but it's best viewed by printing it out - text and figures are sharper (see printing instructions in Q+A6 below). There's a lot of other material on the CD and it's in .rtf, .cpp, .exe and .wav formats (see the Table of Contents in the tutorial).

Q2: How many pages is it?

A2: 240, 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 290. And if the programs and bibliography were printed out, it would be in the thousands of pages.

Q3: Is there anything new in the book?

A3: 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, etc.

Q4: Why put the first 7 chapters on the web?

A4: 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.

Q5: What operating system do I need for the C++ compiler that comes with the CD?

A5: 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.

Q6: What is the best way to print the tutorials or book?

A6: You can print it out and put it in a 3 ring binder using the following instructions. Just make sure that you're using the highest quality print preferences. Using the Adobe Reader, click on 'File' and scroll down to 'Print Setup' and click on it. When the 'Print Setup' screen appears, click on 'Properties'. The 'Printer Properties' screen appears. For my printer, I select 'high' under the 'print quality' heading, and also choose 'grayscale.' After that, I click OK on the 'Print Properties' and 'Print Set-up' screens. After that, click on the Adobe 'File' again and scroll down to 'Print' - click on it. The 'Print' screen comes up, and I choose 'none' under 'page scaling' (very important). Your printer may work differently. When done correctly, the page numbers should be 3/4" or less from the bottom of the page. The printed results should be sharper than what's seen on the screen. One more item - the Adobe Reader will let you print odd/even pages so you can print double sided. Make sure you understand how to place the paper in your printer so that you can do it properly. Also, Chapters 1 and 2 are intended to begin on a left side page. All the others should start on a right side page.

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

A7: 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:

© 2009 by Kevin J. McGee