gov.sandia.cognition.math.signals
Class FourierTransform

java.lang.Object
  extended by gov.sandia.cognition.util.AbstractCloneableSerializable
      extended by gov.sandia.cognition.math.signals.FourierTransform
All Implemented Interfaces:
Evaluator<Collection<Double>,Collection<ComplexNumber>>, CloneableSerializable, Serializable, Cloneable

@PublicationReference(author="Wikipedia",
                      title="Fast Fourier transform",
                      type=WebPage,
                      year=2009,
                      url="http://en.wikipedia.org/wiki/Fast_Fourier_transform")
public class FourierTransform
extends AbstractCloneableSerializable
implements Evaluator<Collection<Double>,Collection<ComplexNumber>>

Computes the Fast Fourier Transform, or brute-force discrete Fourier transform, of a discrete input sequence.

Since:
3.0
Author:
Kevin R. Dixon
See Also:
Serialized Form

Nested Class Summary
static class FourierTransform.Inverse
          Evaluator that inverts a Fourier transform.
 
Constructor Summary
FourierTransform()
          Creates a new instance of FourierTransform
 
Method Summary
protected static ArrayList<ComplexNumber> convertToComplex(Collection<Double> data)
          Converts the Collection of real data to complex numbers
protected static ComplexNumber[] cooleyTukeyFFT(ArrayList<ComplexNumber> data)
          Computes the Cooley-Tukey Radix-2 Fast Fourier Transform (FFT).
static ComplexNumber[] discreteFourierTransform(ArrayList<Double> data)
          Computes the brute-force discrete Fourier transform of the input data.
protected static ComplexNumber[] discreteFourierTransformComplex(ArrayList<ComplexNumber> data)
          Computes the brute-force discrete Fourier transform of the input data.
 List<ComplexNumber> evaluate(Collection<Double> data)
          Computes the Fast Fourier Transform of the given input data using the Cooley-Tukey Radix-2 FFT, with brute-force DFT computation on odd subsequence computation.
static ArrayList<Double> inverse(Collection<ComplexNumber> transformCoefficients)
          Static function that inverts a Fourier transform.
 
Methods inherited from class gov.sandia.cognition.util.AbstractCloneableSerializable
clone
 
Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

FourierTransform

public FourierTransform()
Creates a new instance of FourierTransform

Method Detail

convertToComplex

protected static ArrayList<ComplexNumber> convertToComplex(Collection<Double> data)
Converts the Collection of real data to complex numbers

Parameters:
data - Real data to convert
Returns:
ArrayList of ComplexNumbers with the real parts given by "data" and zeros for imaginary parts.

discreteFourierTransform

public static ComplexNumber[] discreteFourierTransform(ArrayList<Double> data)
Computes the brute-force discrete Fourier transform of the input data. This algorithm takes O(n^2) time to compute and is MUCH slower than the Cooley-Tukey FFT.

Parameters:
data - Real data to compute the FFT of.
Returns:
Complex-number coefficients of the data, where the zeroth element is the DC offset, the element at index 1 is the first component, etc. There will be as many frequency components as the length of "data".

discreteFourierTransformComplex

@PublicationReference(author="Wikipedia",
                      title="Discrete Fourier transform",
                      type=WebPage,
                      year=2009,
                      url="http://en.wikipedia.org/wiki/Discrete_Fourier_transform")
protected static ComplexNumber[] discreteFourierTransformComplex(ArrayList<ComplexNumber> data)
Computes the brute-force discrete Fourier transform of the input data. This algorithm takes O(n^2) time to compute and is MUCH slower than the Cooley-Tukey FFT.

Parameters:
data - Data to compute the FFT of.
Returns:
Complex-number coefficients of the data, where the zeroth element is the DC offset, the element at index 1 is the first component, etc. There will be as many frequency components as the length of "data".

cooleyTukeyFFT

@PublicationReferences(references={@PublicationReference(author="Wikipedia",title="Cooley-Tukey FFT algorithm",type=WebPage,year=2009,url="http://en.wikipedia.org/wiki/Cooley-Tukey_FFT_algorithm"),@PublicationReference(author={"Robert Sedgewick","Kevin Wayne"},title="FFT.java",type=WebPage,year=2007,url="http://www.cs.princeton.edu/introcs/97data/FFT.java.html")})
protected static ComplexNumber[] cooleyTukeyFFT(ArrayList<ComplexNumber> data)
Computes the Cooley-Tukey Radix-2 Fast Fourier Transform (FFT). In its pure form, the Cooley-Tukey FFT requires the length of data to transform be a power of 2 (1, 2, 4, 8, 16, ... 1024, ... ). If given data that's a power of 2, then the algorithm computes the FFT in O(n log(n)) time. We have made a slight modification that allows the FFT to fall back on brute-force O(n^2) discrete Fourier transform when it encounters a subset with an odd number. For example, if supplied data of length 576, then the algorithm will divide and conquer as: 576, 288, 144, 72, 36, 18, 9. When the algorithm gets to FFTs of length 9, then the algorithm falls back to using the brute-force DFT. This allows the FFT to retain its divide-and-conquer approach as much as possible without using sophisticated bit-flipping FFTs.

Parameters:
data - Data to compute the FFT of.
Returns:
Complex-number coefficients of the data, where the zeroth element is the DC offset, the element at index 1 is the first component, etc. There will be as many frequency components as the length of "data".

evaluate

public List<ComplexNumber> evaluate(Collection<Double> data)
Computes the Fast Fourier Transform of the given input data using the Cooley-Tukey Radix-2 FFT, with brute-force DFT computation on odd subsequence computation.

Specified by:
evaluate in interface Evaluator<Collection<Double>,Collection<ComplexNumber>>
Parameters:
data - Input data to compute the FFT of.
Returns:
Complex-number coefficients of the data, where the zeroth element is the DC offset, the element at index 1 is the first component, etc. There will be as many frequency components as the length of "data".

inverse

public static ArrayList<Double> inverse(Collection<ComplexNumber> transformCoefficients)
Static function that inverts a Fourier transform.

Parameters:
transformCoefficients - Transform coefficients to invert back into a scalar data set.
Returns:
Scalar data represented by the given Fourier coefficients.