gov.sandia.cognition.math.signals

Class FourierTransform

java.lang.Object

gov.sandia.cognition.util.AbstractCloneableSerializable

gov.sandia.cognition.math.signals.FourierTransform

All Implemented Interfaces:

Evaluator<java.util.Collection<java.lang.Double>,java.util.Collection<ComplexNumber>>, CloneableSerializable, java.io.Serializable, java.lang.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<java.util.Collection<java.lang.Double>,java.util.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

Nested Classes

Modifier and Type	Class and Description
static class	FourierTransform.Inverse Evaluator that inverts a Fourier transform.

Constructor Summary

Constructors

Constructor and Description
FourierTransform() Creates a new instance of FourierTransform

Method Summary

Modifier and Type	Method and Description
protected static java.util.ArrayList<ComplexNumber>	convertToComplex(java.util.Collection<java.lang.Double> data) Converts the Collection of real data to complex numbers
protected static ComplexNumber[]	cooleyTukeyFFT(java.util.ArrayList<ComplexNumber> data) Computes the Cooley-Tukey Radix-2 Fast Fourier Transform (FFT).
static ComplexNumber[]	discreteFourierTransform(java.util.ArrayList<java.lang.Double> data) Computes the brute-force discrete Fourier transform of the input data.
protected static ComplexNumber[]	discreteFourierTransformComplex(java.util.ArrayList<ComplexNumber> data) Computes the brute-force discrete Fourier transform of the input data.
java.util.List<ComplexNumber>	evaluate(java.util.Collection<java.lang.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 java.util.ArrayList<java.lang.Double>	inverse(java.util.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 java.util.ArrayList<ComplexNumber> convertToComplex(java.util.Collection<java.lang.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(java.util.ArrayList<java.lang.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(java.util.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

@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(java.util.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 java.util.List<ComplexNumber> evaluate(java.util.Collection<java.lang.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<java.util.Collection<java.lang.Double>,java.util.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 java.util.ArrayList<java.lang.Double> inverse(java.util.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.