Collaboration diagram for Fast Fourier Transform functions:

Functions
int	slowFFT (EST_FVector &real, EST_FVector &imag)
	Basic in-place FFT. More...

int	FFT (EST_FVector &real, EST_FVector &imag)
	Alternate name for slowFFT. More...

int	slowIFFT (EST_FVector &real, EST_FVector &imag)
	Basic inverse in-place FFT. More...

int	IFFT (EST_FVector &real, EST_FVector &imag)
	Alternate name for slowIFFT. More...

int	power_spectrum (EST_FVector &real, EST_FVector &imag)
	Power spectrum using the fastFFT function. More...

int	power_spectrum_slow (EST_FVector &real, EST_FVector &imag)
	Power spectrum using the slowFFT function. More...

int	fastFFT (EST_FVector &invec)
	Fast FFT An optimised implementation by Tony Robinson to be used in preference to slowFFT. More...

int	fastlog2 (int)

Detailed Description

These are the low level functions where the actual FFT is performed. Both slow and fast implementations are available for historical reasons. They have identical functionality. At this time, vectors of complex numbers are handled as pairs of vectors of real and imaginary numbers.

What is a Fourier Transform ?

The Fourier transform of a signal gives us a frequency-domain representation of a time-domain signal. In discrete time, the Fourier Transform is called a Discrete Fourier Transform (DFT) and is given by:

$y_k = \sum_{t=0}^{n-1} x_t \; \omega_{n}^{kt} \; ; \; k=0...n-1$

where $y = (y_0,y_1,... y_{n-1})$ is the DFT (of order $n$ ) of the signal $x = (x_0,x_1,... x_{n-1})$ , where $\omega_{n}^{0},\omega_{n}^{1},... \omega_{n}^{n-1}$ are the n complex nth roots of 1.

The Fast Fourier Transform (FFT) is a very efficient implementation of a Discrete Fourier Transform. See, for example "Algorithms" by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest (pub. MIT Press), or any signal processing textbook.

Function Documentation

int slowFFT	(	EST_FVector &	real,
		EST_FVector &	imag
	)

Basic in-place FFT.

There's no point actually using this - use fastFFT instead. However, the code in this function closely matches the classic FORTRAN version given in many text books, so is at least easy to follow for new users.

The length of real and imag must be the same, and must be a power of 2 (e.g. 128).

See also: slowIFFT; FastFFT

Definition at line 173 of file fft.cc.

int FFT	(	EST_FVector &	real,
		EST_FVector &	imag
	)

inline

Alternate name for slowFFT.

Definition at line 91 of file EST_fft.h.

int slowIFFT	(	EST_FVector &	real,
		EST_FVector &	imag
	)

Basic inverse in-place FFT.

Definition at line 179 of file fft.cc.

int IFFT	(	EST_FVector &	real,
		EST_FVector &	imag
	)

inline

Alternate name for slowIFFT.

Definition at line 101 of file EST_fft.h.

int power_spectrum	(	EST_FVector &	real,
		EST_FVector &	imag
	)

Power spectrum using the fastFFT function.

The power spectrum is simply the squared magnitude of the FFT. The result real and imaginary parts are both set equal to the power spectrum (you only need one of them!)

Definition at line 222 of file fft.cc.

int power_spectrum_slow	(	EST_FVector &	real,
		EST_FVector &	imag
	)

Power spectrum using the slowFFT function.

Definition at line 209 of file fft.cc.

int fastFFT ( EST_FVector & invec )

Fast FFT An optimised implementation by Tony Robinson to be used in preference to slowFFT.

Definition at line 256 of file fft.cc.

int fastlog2 ( int )

Definition at line 555 of file fft.cc.

Functions

Detailed Description

What is a Fourier Transform ?

Function Documentation