public class FastFourierTransform extends AbstractSpectralTransform implements SpectralTransform
Fast Fourier transform (FFT). This class implements traditional one and multidimensional FFT algorithm
over an abstract SampleArray
and 1, 2 or multidimensional AlgART numeric matrices
.
All samples must be complex to be processed by this class (areComplexSamplesRequired()
method
returns true). For needs of spectral processing real arrays and matrices, in most cases
you should use SeparableFastHartleyTransform
class.
More precisely, this class implements the classic fast "butterfly" algorithm (FFT) for calculating
discrete Fourier transform (DFT), described at
Namely, let x_{0},x_{1},...,x_{N−1} are some complex
samples (represented by abstract SampleArray
), and
F_{0},F_{1},...,F_{N−1} are their Fourier spectrum:
the result of DFT. Let i is the usual imaginary unit.
This class implements two possible definitions of DFT:
The only difference is when to normalize the result: while inverse transform (case 1) or direct transform (case 2). The Wikipedia offers formulas of the 1st case. This class allows to calculate both variants: the 1st case is chosen if the normalizeDirectTransform argument of the constructors is false or if this class is created by a constructor without this argument (it is the default behaviour), the 2nd case is chosen if the normalizeDirectTransform argument of the constructors is true.
The formulas above correspond to onedimensional transforms and specify the results of
directTransform
/ inverseTransform
methods.
They are generalized to multidimensional case by default algorithms, implemented in
AbstractSpectralTransform
class, i.e. by applying the transform separably to each dimension.
It is the traditional way of multidimensional generalizing Fourier transformations.
Onedimensional Fourier transform, defined by the formulas above, complies with the convolution theorem. Namely, let p_{0},p_{1},...,p_{N−1} is the first complex numeric function, q_{0},q_{1},...,q_{N−1} is the second function, and c_{0},c_{1},...,c_{N−1} is their convolution, defined as:
c_{k} = ∑_{(0≤n<N)} p_{n}q_{(k−n) mod N}
(here (k−n) mod N means
The similar formulas are correct for any number of dimensions: convolution of samples corresponds to complex product of spectra.
This class contains the method
spectrumOfConvolution(ArrayContext, Matrix, Matrix, Matrix, Matrix, Matrix, Matrix)
,
which calculates a spectrum of convolution C for the given spectra P and Q
of two source numeric matrices x and y according the formula A
(and its generalization for any number of dimensions).
Please note: in the onedimensional case, the spectral transofmation algorithms, implemented by
directTransformMatrix
/ inverseTransformMatrix
methods of this class, work with normal (i.e. high) performance only if
the passed SimpleMemoryModel
(more precisely, if they are directly accessible
).
In other case, each access to every sample leads to calling accessing methods
getDouble
and setDouble
,
which can work slowly in nonsimple memory models like LargeMemoryModel
. There is the same problem for
directTransform
/ inverseTransform
methods, if the passed
sample arrays are created via RealScalarSampleArray.asSampleArray
or ComplexScalarSampleArray.asSampleArray
methods on the base of
updatable AlgART arrays, created by memory model other than SimpleMemoryModel
.
For ndimensional matrices (n≥2), this problem usually does not occur at all, even for nonsimple
memory models, if you use standard implementations of
directTransformMatrix
/ inverseTransformMatrix
from AbstractSpectralTransform
class: these implementations automatically download necessary parts
of the matrix into SimpleMemoryModel
.
This problem also does not occur while using
spectrumOfConvolution(ArrayContext, Matrix, Matrix, Matrix, Matrix, Matrix, Matrix)
method,
if all processed matrices have the same float or double element types.
AlgART Laboratory 2007–2014
MIN_SPECTRAL_JAVA_MEMORY
Constructor and Description 

FastFourierTransform()
Creates a new instance of this class, performing Fourier transform according to the formula 1 from
the
comments to this class . 
FastFourierTransform(boolean normalizeDirectTransform)
Creates a new instance of this class, performing Fourier transform according either to the formula 1 from
the
comments to this class , if normalizeDirectTransform argument is
false, or to the formula 2, if this argument is true. 
FastFourierTransform(boolean normalizeDirectTransform,
long maxTempJavaMemory)
Creates a new instance of this class, performing Fourier transform according either to the formula 1 from
the
comments to this class , if normalizeDirectTransform argument is
false, or to the formula 2, if this argument is true. 
FastFourierTransform(long maxTempJavaMemory)
Creates a new instance of this class, performing Fourier transform according to the formula 1 from
the
comments to this class . 
Modifier and Type  Method and Description 

boolean 
areComplexSamplesRequired()
Returns true if the transformation methods of this class (
directTransform ,
inverseTransform , directTransformMatrix ,
inverseTransformMatrix ) can process only complex samples,
false if the real samples are also allowed. 
boolean 
isLengthAllowed(long length)
Returns true if the specified argument is an allowed dimension for arrays or matrices,
transformed by
directTransform , inverseTransform ,
directTransformMatrix or inverseTransformMatrix
method. 
void 
spectrumOfConvolution(ArrayContext context,
Matrix<? extends UpdatablePNumberArray> cRe,
Matrix<? extends UpdatablePNumberArray> cIm,
Matrix<? extends PNumberArray> pRe,
Matrix<? extends PNumberArray> pIm,
Matrix<? extends PNumberArray> qRe,
Matrix<? extends PNumberArray> qIm)
Calculates C = P*Q, i.e. multiplies each element of the complex multidimensional
matrix P to the corresponding element of the complex multidimensional matrix Q and stores
result in the corresponding element of the complex multidimensional matrix C.

protected void 
transform(ArrayContext context,
SampleArray samples,
boolean inverse)
Actually performs the 1dimensional transform of the sample array, direct or inverse.

protected java.lang.String 
unallowedLengthMessage()
Retrurns a message used while throwing IllegalArgumentException by methods of this class
in a case, when the length of the samples array or some of the matrix dimensions is not allowed
according to
AbstractSpectralTransform.isLengthAllowed(long) method. 
directTransform, directTransformMatrix, inverseTransform, inverseTransformMatrix, maxTempJavaMemory, transformMatrix
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
directTransform, directTransformMatrix, inverseTransform, inverseTransformMatrix
public FastFourierTransform()
comments to this class
.
Equivalent to FastFourierTransform(false)
.FastFourierTransform(long)
public FastFourierTransform(long maxTempJavaMemory)
comments to this class
.
The maxTempJavaMemory argument specifies the amount of Java memory (heap),
that can be used by methods of this class for internal needs. It is passed to the corresponding
constructor of AbstractSpectralTransform
: see
comments to that constructor
.
maxTempJavaMemory
 desired maximal amount of Java memory, in bytes, allowed for allocating
by methods of this class for internal needs.FastFourierTransform()
public FastFourierTransform(boolean normalizeDirectTransform)
comments to this class
, if normalizeDirectTransform argument is
false, or to the formula 2, if this argument is true.
The default value, used by the constructors without normalizeDirectTransform argument,
is false.
Please note: the value of normalizeDirectTransform argument affects only the transformation
methods directTransform
, inverseTransform
,
directTransformMatrix
, inverseTransformMatrix
.
This value does not matter in spectrumOfConvolution
method.
normalizeDirectTransform
 true if you want to perform normalization (division by the number of
samples N) after the direct transform, false (the default value)
if you want to perform normalization after the inverse transform.FastFourierTransform(boolean, long)
public FastFourierTransform(boolean normalizeDirectTransform, long maxTempJavaMemory)
comments to this class
, if normalizeDirectTransform argument is
false, or to the formula 2, if this argument is true.
The default value, used by the constructors without normalizeDirectTransform argument,
is false.
Please note: the value of normalizeDirectTransform argument affects only the transformation
methods directTransform
, inverseTransform
,
directTransformMatrix
, inverseTransformMatrix
.
This value does not matter in spectrumOfConvolution
method.
The maxTempJavaMemory argument specifies the amount of Java memory (heap),
that can be used by methods of this class for internal needs. It is passed to the corresponding
constructor of AbstractSpectralTransform
: see
comments to that constructor
.
maxTempJavaMemory
 desired maximal amount of Java memory, in bytes, allowed for allocating
by methods of this class for internal needs.normalizeDirectTransform
 true if you want to perform normalization (division by the number of
samples N) after the direct transform, false (the default value)
if you want to perform normalization after the inverse transform.FastFourierTransform(boolean)
public void spectrumOfConvolution(ArrayContext context, Matrix<? extends UpdatablePNumberArray> cRe, Matrix<? extends UpdatablePNumberArray> cIm, Matrix<? extends PNumberArray> pRe, Matrix<? extends PNumberArray> pIm, Matrix<? extends PNumberArray> qRe, Matrix<? extends PNumberArray> qIm)
comments to this class
.
The complex matrix P is represented as a pair of AlgART matrices (pRe,pIm): the corresponding elements of these 2 matrices contain the real and imaginary parts of the corresponding elements of the complex matrix P. Similarly, the complex matrix Q is represented as a pair of AlgART matrices (qRe,qIm), and the complex matrix C is represented as a pair of AlgART matrices (cRe,cIm).
All matrices, passed to this method, must have equal dimensions
.
The element type
of the passed matrices can be different, but we recommend
using the same float or double element type for all matrices.
There are no restrictions for the dimensions of the passed matrices:
isLengthAllowed(long)
method is not used here.
This method works correctly, if you pass the same complex matrix as P and Q, or as P and C, or as Q and C, or even as all three matrices. So, you can calculate and return the result in one of the source matrices.
If you need to calculate the Fourier spectrum of convolution for a case of Matrices.matrix(Array, long...)
call, for example:
Matrices.matrix
(array, array.length()).
context
 the context that will be used by this algorithm; may be null
(see comments to SpectralTransform
).cRe
 the real parts of the elements of the resulting matrix.cIm
 the imaginary parts of the elements of the resulting matrix.pRe
 the real parts of the elements of the 1st source matrix.pIm
 the imaginary parts of the elements of the 1st source matrix.qRe
 the real parts of the elements of the 2nd source matrix.qIm
 the imaginary parts of the elements of the 2nd source matrix.java.lang.NullPointerException
 if one of cRe, cIm, pRe, pIm,
qRe, qIm arguments is null.SizeMismatchException
 if some of passed matrices have different dimensions.public final boolean isLengthAllowed(long length)
SpectralTransform
directTransform
, inverseTransform
,
directTransformMatrix
or inverseTransformMatrix
method.
More precisely, if this method returns false for the length of a sample array,
passed to 1st or 2nd methods, or for some dimension of some matrix, passed to 3rd or 4th method,
then those methods throw IllegalArgumentException
.
In other case, those methods will process that passed data.
In both implementations of this interface, offered by this package, this method returns true if the passed length is a power of two (2^{k}).
If the length argument is negative, the result of this method is unspecified. It is not a problem, because lengths of sample arrays and dimensions of AlgART matrices cannot be negative.
isLengthAllowed
in interface SpectralTransform
isLengthAllowed
in class AbstractSpectralTransform
length
 the checked length or matrix dimension.public boolean areComplexSamplesRequired()
SpectralTransform
directTransform
,
inverseTransform
, directTransformMatrix
,
inverseTransformMatrix
) can process only complex samples,
false if the real samples are also allowed.
More precisely, if this method returns true,
then the methods directTransform
/ inverseTransform
checks, whether SampleArray.isComplex()
method returns true for the samples argument,
and the methods directTransformMatrix
/
inverseTransformMatrix
checks, whether the matrixIm argument is
not null. If this condition is not fulfilled, these methods throw
UnsupportedOperationException.
In other case, these methods work normally.
In implementations, offered by this package, this method returns true
in FastFourierTransform
class and false in SeparableFastHartleyTransform
class.
areComplexSamplesRequired
in interface SpectralTransform
areComplexSamplesRequired
in class AbstractSpectralTransform
protected java.lang.String unallowedLengthMessage()
AbstractSpectralTransform
AbstractSpectralTransform.isLengthAllowed(long)
method.
Typical examples of this message (implemented in FastFourierTransform
and
SeparableFastHartleyTransform
classes):
"FFT algorithm can process only 2^k elements" or
"FHT algorithm can process only 2^k elements".unallowedLengthMessage
in class AbstractSpectralTransform
AbstractSpectralTransform.isLengthAllowed(long)
method returns false.protected final void transform(ArrayContext context, SampleArray samples, boolean inverse)
AbstractSpectralTransform
It is called from directTransform
/ inverseTransform
methods. In this case, there is a guarantee that:
1) samples!=null;
2) if AbstractSpectralTransform.areComplexSamplesRequired()
, then samples.isComplex()
returns true;
3) AbstractSpectralTransform.isLengthAllowed(long)
returns true for samples.length().
transform
in class AbstractSpectralTransform
context
 the context that will be used by this algorithm; may be null
(see comments to SpectralTransform
).samples
 the transformed samples.inverse
 true if this method implements the inverse transform,
false if this method implements the direct transform.