Fast Fourier Transform

Houtan Rezaei

Project:

To write a C++ Program which will take an array of complex or real numbers and produce their fourier transform using the Danielson-Lanczon routine for Fast Fourier Transform taken from Numerical Recipies in C.

 

I/O:

The input and output of the program will most likely be as follows:

This actual length of the real array (data[1..2*nn]) is 2 times nn, with each complex value occupying two consecutive locations. In other words, data[1] is the real part of f0 , data[2] is the imaginary part of f0 , and so on up to data[2*nn-1],which is the real part of fN-1, and data[2*nn], which is the imaginary part of fN-1 The FFT routine gives back the Fn ’s packed in exactly the same fashion, as nn complex numbers. The real and imaginary parts of the zero frequency component F0 are in data[1] and data[2]; the smallest nonzero positive frequency has real and imaginary parts in data[3] and data[4]; the smallest (in magnitude) nonzero negative frequency has real and imaginary parts in data[2*nn-1] and data[2*nn]. Positive frequencies increasing in magnitude are stored in the real-imaginary pairs data[5], data[6] up to data[nn-1], data[nn]. Negative frequencies of increasing magnitude are stored in data[2*nn-3], data[2*nn-2] down to data[nn+3], data[nn+4]. Finally, the pair data[nn+1], data[nn+2] contain the real and imaginary parts of the one aliased point that contains the most positive and the most negative frequency. The input and output are but done in the same manner so that the output can be used as an input again (Inverse transform).

Classes and things:

The following are the classes that I anticipate:

1) Class BitShift : This class Does the bit-shifting necessary for the routine

2) Class Transform : This class Calculates the Fourier Transform of a given array of numbers.

3) Class InverseTransform : Public class transform : This class calculates the Inverse Fourier transform of a given array of numbers. (Using inheritance since inverse in a form of Transform)

4) Maybe a class Complex Array if I feel that it will make things easier to deal with.