Edinburgh Speech Tools  2.1-release
 All Classes Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Functions
Fast Fourier Transform functions
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.
 
int slowIFFT (EST_FVector &real, EST_FVector &imag)
 Basic inverse in-place FFT.
 
int IFFT (EST_FVector &real, EST_FVector &imag)
 Alternate name for slowIFFT.
 
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.
 
int fastFFT (EST_FVector &invec)
 Fast FFT An optimised implementation by Tony Robinson to be used in preference to slowFFT.
 
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 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.