org.apache.commons.math3.transform
Class FastFourierTransformer

java.lang.Object
  extended by org.apache.commons.math3.transform.FastFourierTransformer
All Implemented Interfaces:
Serializable

public class FastFourierTransformer
extends Object
implements Serializable

Implements the Fast Fourier Transform for transformation of one-dimensional real or complex data sets. For reference, see Applied Numerical Linear Algebra, ISBN 0898713897, chapter 6.

There are several variants of the discrete Fourier transform, with various normalization conventions, which are specified by the parameter DftNormalization.

The current implementation of the discrete Fourier transform as a fast Fourier transform requires the length of the data set to be a power of 2. This greatly simplifies and speeds up the code. Users can pad the data with zeros to meet this requirement. There are other flavors of FFT, for reference, see S. Winograd, On computing the discrete Fourier transform, Mathematics of Computation, 32 (1978), 175 - 199.

Since:
1.2
Version:
$Id: FastFourierTransformer.java 1385310 2012-09-16 16:32:10Z tn $
See Also:
DftNormalization, Serialized Form

Nested Class Summary
private static class FastFourierTransformer.MultiDimensionalComplexMatrix
          Deprecated. see MATH-736
 
Field Summary
private  DftNormalization normalization
          The type of DFT to be performed.
(package private) static long serialVersionUID
          Serializable version identifier.
private static double[] W_SUB_N_I
          W_SUB_N_I[i] is the imaginary part of exp(- 2 * i * pi / n): W_SUB_N_I[i] = -sin(2 * pi/ n), where n = 2^i.
private static double[] W_SUB_N_R
          W_SUB_N_R[i] is the real part of exp(- 2 * i * pi / n): W_SUB_N_R[i] = cos(2 * pi/ n), where n = 2^i.
 
Constructor Summary
FastFourierTransformer(DftNormalization normalization)
          Creates a new instance of this class, with various normalization conventions.
 
Method Summary
private static void bitReversalShuffle2(double[] a, double[] b)
          Performs identical index bit reversal shuffles on two arrays of identical size.
private  void mdfft(FastFourierTransformer.MultiDimensionalComplexMatrix mdcm, TransformType type, int d, int[] subVector)
          Deprecated. see MATH-736
 Object mdfft(Object mdca, TransformType type)
          Deprecated. see MATH-736
private static void normalizeTransformedData(double[][] dataRI, DftNormalization normalization, TransformType type)
          Applies the proper normalization to the specified transformed data.
 Complex[] transform(Complex[] f, TransformType type)
          Returns the (forward, inverse) transform of the specified complex data set.
 Complex[] transform(double[] f, TransformType type)
          Returns the (forward, inverse) transform of the specified real data set.
 Complex[] transform(UnivariateFunction f, double min, double max, int n, TransformType type)
          Returns the (forward, inverse) transform of the specified real function, sampled on the specified interval.
static void transformInPlace(double[][] dataRI, DftNormalization normalization, TransformType type)
          Computes the standard transform of the specified complex data.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

serialVersionUID

static final long serialVersionUID
Serializable version identifier.

See Also:
Constant Field Values

W_SUB_N_R

private static final double[] W_SUB_N_R
W_SUB_N_R[i] is the real part of exp(- 2 * i * pi / n): W_SUB_N_R[i] = cos(2 * pi/ n), where n = 2^i.


W_SUB_N_I

private static final double[] W_SUB_N_I
W_SUB_N_I[i] is the imaginary part of exp(- 2 * i * pi / n): W_SUB_N_I[i] = -sin(2 * pi/ n), where n = 2^i.


normalization

private final DftNormalization normalization
The type of DFT to be performed.

Constructor Detail

FastFourierTransformer

public FastFourierTransformer(DftNormalization normalization)
Creates a new instance of this class, with various normalization conventions.

Parameters:
normalization - the type of normalization to be applied to the transformed data
Method Detail

bitReversalShuffle2

private static void bitReversalShuffle2(double[] a,
                                        double[] b)
Performs identical index bit reversal shuffles on two arrays of identical size. Each element in the array is swapped with another element based on the bit-reversal of the index. For example, in an array with length 16, item at binary index 0011 (decimal 3) would be swapped with the item at binary index 1100 (decimal 12).

Parameters:
a - the first array to be shuffled
b - the second array to be shuffled

normalizeTransformedData

private static void normalizeTransformedData(double[][] dataRI,
                                             DftNormalization normalization,
                                             TransformType type)
Applies the proper normalization to the specified transformed data.

Parameters:
dataRI - the unscaled transformed data
normalization - the normalization to be applied
type - the type of transform (forward, inverse) which resulted in the specified data

transformInPlace

public static void transformInPlace(double[][] dataRI,
                                    DftNormalization normalization,
                                    TransformType type)
Computes the standard transform of the specified complex data. The computation is done in place. The input data is laid out as follows

Parameters:
dataRI - the two dimensional array of real and imaginary parts of the data
normalization - the normalization to be applied to the transformed data
type - the type of transform (forward, inverse) to be performed
Throws:
DimensionMismatchException - if the number of rows of the specified array is not two, or the array is not rectangular
MathIllegalArgumentException - if the number of data points is not a power of two

transform

public Complex[] transform(double[] f,
                           TransformType type)
Returns the (forward, inverse) transform of the specified real data set.

Parameters:
f - the real data array to be transformed
type - the type of transform (forward, inverse) to be performed
Returns:
the complex transformed array
Throws:
MathIllegalArgumentException - if the length of the data array is not a power of two

transform

public Complex[] transform(UnivariateFunction f,
                           double min,
                           double max,
                           int n,
                           TransformType type)
Returns the (forward, inverse) transform of the specified real function, sampled on the specified interval.

Parameters:
f - the function to be sampled and transformed
min - the (inclusive) lower bound for the interval
max - the (exclusive) upper bound for the interval
n - the number of sample points
type - the type of transform (forward, inverse) to be performed
Returns:
the complex transformed array
Throws:
NumberIsTooLargeException - if the lower bound is greater than, or equal to the upper bound
NotStrictlyPositiveException - if the number of sample points n is negative
MathIllegalArgumentException - if the number of sample points n is not a power of two

transform

public Complex[] transform(Complex[] f,
                           TransformType type)
Returns the (forward, inverse) transform of the specified complex data set.

Parameters:
f - the complex data array to be transformed
type - the type of transform (forward, inverse) to be performed
Returns:
the complex transformed array
Throws:
MathIllegalArgumentException - if the length of the data array is not a power of two

mdfft

@Deprecated
public Object mdfft(Object mdca,
                               TransformType type)
Deprecated. see MATH-736

Performs a multi-dimensional Fourier transform on a given array. Use transform(Complex[], TransformType) in a row-column implementation in any number of dimensions with O(N×log(N)) complexity with N = n1 × n2 ×n3 × ... × nd, where nk is the number of elements in dimension k, and d is the total number of dimensions.

Parameters:
mdca - Multi-Dimensional Complex Array, i.e. Complex[][][][]
type - the type of transform (forward, inverse) to be performed
Returns:
transform of mdca as a Multi-Dimensional Complex Array, i.e. Complex[][][][]
Throws:
IllegalArgumentException - if any dimension is not a power of two

mdfft

@Deprecated
private void mdfft(FastFourierTransformer.MultiDimensionalComplexMatrix mdcm,
                              TransformType type,
                              int d,
                              int[] subVector)
Deprecated. see MATH-736

Performs one dimension of a multi-dimensional Fourier transform.

Parameters:
mdcm - input matrix
type - the type of transform (forward, inverse) to be performed
d - index of the dimension to process
subVector - recursion subvector
Throws:
IllegalArgumentException - if any dimension is not a power of two


Copyright (c) 2003-2013 Apache Software Foundation