<- 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.
This is short_count.wav one, two, three
short_count.wav
The basic FFT plotting the magnitude of each bin is:
Using fftshift to center the zero frequency:
Then taking the log of the amplitude:
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 and understanding modulation.
A few, non fast, programs that compute Fourier Series coefficients for
unequally spaced samples, read from a file, are:
fourier.c
fourier.java
sin(2x) data sin2.dat
test on sine2.dat fourier_java.out
More detail of the basic Fourier transforms and series,
both continuous and discrete is fourier.pdf
square_wave_gen.c using series
square_wave_gen_c.out cos and sin
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
A more general program for the FFT of large data in Java is:
Cxfft.java
read_wav.java reads and writes .wav
read_wave_java.out output
these may be combined for use in HW5.
fft_wav.java transform and inverse
fft_frame.java with a very crude frequency plot
For Matlab, fft_wav.m may be useful for HW5
fft_wav.m transform and inverse, frequency plot
Another version in "C" and Java, the Java demonstrates convolution
fftd.h
fftd.c
test_fft.c
test_fft_c.out
Cxfft.java
TestCxfft.java
TestCxfft.out
Python using downloaded numpy has fft
testfft.py
testfft.out
MatLab has fft as well as almost every other function
test_fft.m
test_fft_m.out
test_fft2.m
test_fft2_m.out
In order to get better accuracy on predicted coefficients
for square wave, triangle wave and saw tooth wave, 1024 points.
The series are shown as comments in the code.
Also shown, is the anti aliasing and normalization needed to
get the coefficients for the Fourier series.
test_fft_big.c
test_fft_big_c.out
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. (not all the .wav files listed below)
read_wav.c
read_wav.out
train1.wav
short_count.wav
rocky4.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.
Your web browser can usually play .wav files.
Use file:/// path to your directory /xxx.wav
In Java, ClipPlayer.java reads and
plays .wav and other files. The driver program is ClipPlayerTest.java
In Python, with the WX graphics available, play .wav files with
sound.py
In MatLab play .wav files with
waveplay.m
short_count.wav
Im MatLab play .dat files that have a value for each
sample.
soundplay.m
short_count.dat
For students running Ubuntu, this sequence of "C" programs
demonstrate direct use of playing sampled amplitude sound.
These do not require generating a .wav or other type sound file.
pcm_min.c
pcm_sin.c
pcm_dat.c
Makefile_sound
short_count.dat
long_count.dat
You may modify any of these to suit your needs.
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.
Now you can do homework 5
<- previous index next ->