org.openuat.features
Class FFT

java.lang.Object
  org.openuat.features.FFT

public class FFT
extends java.lang.Object

Compute the FFT and inverse FFT of a length N complex sequence. Bare bones implementation that runs in O(N log N) time. Our goal is to optimize the clarity of the code, rather than performance. Limitations ----------- - assumes N is a power of 2 - not the most memory efficient algorithm (because it uses an object type for representing complex numbers and because it re-allocates memory for the subarray, instead of doing in-place or reusing a single temporary array)

Author:

Adapted by Rene Mayrhofer, very heavily based on code by Robert Sedgewick and Kevin Wayne

Constructor Summary

FFT()

Method Summary

static Complex[]	cconvolve(Complex[] x, Complex[] y) compute the circular convolution of x and y.
static Complex[]	convolve(Complex[] x, Complex[] y) compute the linear convolution of x and y.
static Complex[]	fft(Complex[] x) compute the FFT of x[], assuming its length is a power of 2.
static double[]	fftPowerSpectrum(double[] x, int offset, int len) This is a helper function which computes the FFT power spectrum coefficients of a signal in time domain.
static Complex[]	ifft(Complex[] x) compute the inverse FFT of x[], assuming its length is a power of 2.
static void	main(java.lang.String[] args)
static double[]	powerSpectrum(Complex[] x) Computes the power spectrum of a complex signal, see e.g.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

FFT

public FFT()

Method Detail

fft

public static Complex[] fft(Complex[] x)

compute the FFT of x[], assuming its length is a power of 2.

ifft

public static Complex[] ifft(Complex[] x)

compute the inverse FFT of x[], assuming its length is a power of 2.

cconvolve

public static Complex[] cconvolve(Complex[] x,
                                  Complex[] y)

compute the circular convolution of x and y.

convolve

public static Complex[] convolve(Complex[] x,
                                 Complex[] y)

compute the linear convolution of x and y.

powerSpectrum

public static double[] powerSpectrum(Complex[] x)

Computes the power spectrum of a complex signal, see e.g. http://www.mathworks.com/access/helpdesk/help/techdoc/ref/fft.html

fftPowerSpectrum

public static double[] fftPowerSpectrum(double[] x,
                                        int offset,
                                        int len)

This is a helper function which computes the FFT power spectrum coefficients of a signal in time domain. It first creates a Complex array out of the double array (with imaginary parts set to 0), then computes the complex FFT coefficients and finally returns the power spectrum of these coefficients.

Parameters:

x - The input time series.

offset - Values will be taken from the time series starting at this offset.

len - This number of values will be used from the time series.

main

public static void main(java.lang.String[] args)