<- previous index next ->
A basic Fourier transform can convert a function in the time domain
to a function in the frequency domain. For example, consider a sound
wave where the amplitude is varying with time. We can use a discrete
Fourier transform on the sound wave and get the frequency spectrum.
Of course there is an inverse Fourier transform that converts
the frequency spectrum back to the time domain.
The spectrum of F(t)=sin(2 Pi f t) t=0..1 is a single frequency f.
The discrete transform assumes the function is repeated for all t.
The amplitude values must be sampled at equal time increments for
the spectrum to be valid.
It turns out that a signal an some frequency has an amplitude and
a phase, or an in-phase and quadrature value. The convenient
implementation is to consider these values as complex numbers.
It turns out that some input can be collected as complex values and
thus most implementations of the FFT take an array of complex numbers
as input and produce the same size array of complex numbers as output.
For technical reasons, a simple FFT requires the size of the input
and output must be a power of 2. Special versions of the FFT as found in
FFTW the fastest Fourier transform in the west
handle arbitrary sizes. We just pad out our input data with zeros to make
the size of the array a power of 2.
Fourier transforms have many other uses such as image filtering and
pattern matching, convolution.
There are many many implementations of the FFT, the n log_2 n
complexity method of computing the discrete Fourier transform.
Two of the many methods are shown below.
One method has the coefficients precomputed in the source code.
A second method computes the coefficients as they are needed.
Precomputed constants for each size FFT
fft16.c fft16.adb
fft32.c fft32.adb
fft64.c fft64.adb
fft128.c fft128.adb
fft256.c fft256.adb
fft512.c fft512.adb
fft1024.c fft1024.adb
fft2048.c fft2048.adb
fft4096.c fft4096.adb
Precomputed constants of each size inverse FFT
ifft16.c ifft16.adb
ifft32.c ifft32.adb
ifft64.c ifft64.adb
ifft128.c ifft128.adb
ifft256.c ifft256.adb
ifft512.c ifft512.adb
ifft1024.c ifft1024.adb
ifft2048.c ifft2048.adb
ifft4096.c ifft4096.adb
Header file and timing program
fftc.h
fft_time.c fft_time.adb
fft_time_c.out fft_time_ada.out
A more general program that can compute the fft and inverse fft for
an n that is a power of two is:
fft.h
fft.c
fftest.c
fftin.dat binary data
fftin.out binary data
Here is a program that just reads a .wav file and writes a copy,
and does a little printing. This with extensions can be the basis
of Homework 5. I can only provide a "C" version. You may translate
to suit your desires. These only work for single channel, 8 bit
per sample PCM .wav files.
read_wav.c
read_wav.out
train1.wav
And here are three .wav files from very small to larger for testing:
ok.wav
train.wav
roll.wav
Suppose you wanted to compute a sound. Here is a generator for
a simple sine wave. It sounds cruddy.
sine_wav.c
sine_wav.out
sine.wav
For the homework, one example using a 64 point FFT and just doing
the transform and inverse transform, essentially no change, is
fft1_wav.c
fft1_wav.out
trainf.wav
Hopefully you can find some more interesting .wav files.
P.S. When using MediaPlayer or QuickTime be sure to close the
file before trying to rewrite it.
An interactive WEB site with with a few functions and their spectrum is
heliso.tripod.com/java_hls/gccs/spectrum1.htm
Here is Rocky speaking and the dynamic spectrum
rocky4.wav
This needs modifications for 2 channel and 16 bits per sample.
<- previous index next ->