Class FastFourierTransformer
- java.lang.Object
-
- org.apache.commons.math3.transform.FastFourierTransformer
-
- All Implemented Interfaces:
java.io.Serializable
public class FastFourierTransformer extends java.lang.Object implements java.io.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
- See Also:
DftNormalization
, Serialized Form
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
FastFourierTransformer.MultiDimensionalComplexMatrix
Deprecated.see MATH-736
-
Field Summary
Fields Modifier and Type Field Description 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 ofexp(- 2 * i * pi / n)
:W_SUB_N_I[i] = -sin(2 * pi/ n)
, wheren = 2^i
.private static double[]
W_SUB_N_R
W_SUB_N_R[i]
is the real part ofexp(- 2 * i * pi / n)
:W_SUB_N_R[i] = cos(2 * pi/ n)
, wheren = 2^i
.
-
Constructor Summary
Constructors Constructor Description FastFourierTransformer(DftNormalization normalization)
Creates a new instance of this class, with various normalization conventions.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Deprecated Methods Modifier and Type Method Description private static void
bitReversalShuffle2(double[] a, double[] b)
Performs identical index bit reversal shuffles on two arrays of identical size.java.lang.Object
mdfft(java.lang.Object mdca, TransformType type)
Deprecated.see MATH-736private void
mdfft(FastFourierTransformer.MultiDimensionalComplexMatrix mdcm, TransformType type, int d, int[] subVector)
Deprecated.see MATH-736private static void
normalizeTransformedData(double[][] dataRI, DftNormalization normalization, TransformType type)
Applies the proper normalization to the specified transformed data.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.Complex[]
transform(Complex[] f, TransformType type)
Returns the (forward, inverse) transform of the specified complex data set.static void
transformInPlace(double[][] dataRI, DftNormalization normalization, TransformType type)
Computes the standard transform of the specified complex data.
-
-
-
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 ofexp(- 2 * i * pi / n)
:W_SUB_N_R[i] = cos(2 * pi/ n)
, wheren = 2^i
.
-
W_SUB_N_I
private static final double[] W_SUB_N_I
W_SUB_N_I[i]
is the imaginary part ofexp(- 2 * i * pi / n)
:W_SUB_N_I[i] = -sin(2 * pi/ n)
, wheren = 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 shuffledb
- 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 datanormalization
- the normalization to be appliedtype
- 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 followsdataRI[0][i]
is the real part of thei
-th data point,dataRI[1][i]
is the imaginary part of thei
-th data point.
- Parameters:
dataRI
- the two dimensional array of real and imaginary parts of the datanormalization
- the normalization to be applied to the transformed datatype
- 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 rectangularMathIllegalArgumentException
- 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 transformedtype
- 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 transformedmin
- the (inclusive) lower bound for the intervalmax
- the (exclusive) upper bound for the intervaln
- the number of sample pointstype
- 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 boundNotStrictlyPositiveException
- if the number of sample pointsn
is negativeMathIllegalArgumentException
- if the number of sample pointsn
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 transformedtype
- 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 java.lang.Object mdfft(java.lang.Object mdca, TransformType type)
Deprecated.see MATH-736Performs a multi-dimensional Fourier transform on a given array. Usetransform(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:
java.lang.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-736Performs one dimension of a multi-dimensional Fourier transform.- Parameters:
mdcm
- input matrixtype
- the type of transform (forward, inverse) to be performedd
- index of the dimension to processsubVector
- recursion subvector- Throws:
java.lang.IllegalArgumentException
- if any dimension is not a power of two
-
-