Discrete Fast Fourier TransformsFast Fourier Transformsby Don Cross - dcrossintersrv.comLast update to this page: 15 February 2000French Version of this page, translated by Jean Debord (many thanks!)IMPORTANT NOTE for MATLAB users! List of other pages which link to this one: G Turbo Pascal Programmers Page. G FXT Page from Jrgs “Useful and Ugly Pages“ G Numerical Methods in Pascal code download page. Table of ContentsG C/C+ FFT Source Code by Don CrossG Turbo Pascal FFT Source Code by Don CrossG Visual Basic FFT Source Code by Murphy McCauleyG Ada FFT Source Code by Brian Neal G FFT Tutorial 1. Introduction to digital audio 2. Frequency information in a function of time 3. The Fourier Transform as a mathematical concept 4. The Discrete Fast Fourier Transform algorithm 5. Applications of the FFTG Other FFT SitesG Other Related SitesC/C+ source codehttp:/www.intersrv.com/dcross/fft.html (1 of 7) 12/19/2001 1:09:36 AMDiscrete Fast Fourier Transformsfft.zip - last update: 15 March 1998. This file contains C code I wrote for performing Fast Fourier Transforms (FFTs). This code is C+ callable also. My implementation is based on ideas from the book Numerical Recipes in Fortran by Press, Teukolsky, Vetterling, and Flannery, published by Cambridge University Press. Note: There is a version of this book called Numerical Recipes in C which contains the same information with C source code instead of Fortran. This source code contains one implementation for arrays of type float and one for arrays of double. Both functions can perform the transform or the inverse transform, depending on a flag passed as a parameter. fftdom.cpp - This is a sample C+ function which shows how to find the peak power frequency in the output arrays produced by the FFT. This function returns the frequency in Hz of the part of the frequency spectrum which has maximum power. Note that the returned value can actually be between the integer multiples of the Fourier base frequency f0 = samplingRate / numSamples. This code calculates a weighted average of the power spectrum around the peak frequency, to more accurately determine the true peak frequency. This technique is similar to calculating the center of gravity of a horizontal beam with continuously varying linear density along its length. Turbo Pascal source codefourier.pas - last update: 11 December 1996. Here is the Fast Fourier Transform algorithm in a Turbo Pascal unit. Use the procedure fft to perform the forward transform, and ifft for the inverse transform. testfft.pas - This is a little test program for fourier.pas, which also serves as a demo of how to use the code. testfft.zip - This zip file contains testfft.exe and egavga.bgi. Download this if you want to run the testfft program but do not have access to Borlands Turbo Pascal compiler. Visual Basic FFT source codevbfft.bas - last update: 1 August 1999. This is a Visual Basic implementation of the FFT algorithm, ported by Murphy McCauley from my Turbo Pascal code. Using this code is probably the simplest way to get FFT functionality into your VB project. If you are using a VB older than Version 5, this code may run quite slowly due to the fact that it will be interpreted instead of compiled. In this case, you may want to use the following: fftdll.zip - last update: 1 August 1999. This ZIP file contains a DLL which can be linked into a VB project, along with the C source code to the DLL. Instructions are included in the file. Be sure to expand with subdirectory information when you unzip this file (e.g. pkunzip -d fftdll). Please note: I, Don Cross, do not know anything about Visual Basic. If you have any questions or comments about this VB code, please email Murphy McCauley at MurphyMcConcentric.NET, or visit his web site. Whenever Murphy has a new version, he will get it to me and I will post it here. Thanks! http:/www.intersrv.com/dcross/fft.html (2 of 7) 12/19/2001 1:09:36 AMDiscrete Fast Fourier TransformsAda FFT source codeadafft.zip - last update: 13 December 1999. adafft.tar.gz - last update: 13 December 1999. Thanks to the efforts of Brian Neal we now have an Ada version of the FFT algorithm! These two files contain the same thing, just compressed two different ways: zip format and tar+gzip. Theyre both small (about 6K), so pick the one you can decompress most easily. See also: time domain filtering techniques.A Tutorial on the Fast Fourier Transform1. Introduction to digital audioIf you are already familiar with general digital audio concepts, you can skip this section. The most common type of digital audio recording is called pulse code modulation (PCM). Pulse code modulation is what compact discs and most WAV files use. In PCM recording hardware, a microphone converts a varying air pressure (sound waves) into a varying voltage. Then an analog-to-digital converter measures (samples) the voltage at regular intervals of time.