10.1 Fast Fourier Transforms (.NET, C#, CSharp, VB, Visual Basic, F#)
Fast Fourier Transforms (FFTs) are efficient algorithms for calculating the discrete fourier transform (DFT) and its inverse. NMath provides classes for performing FFTs on real and complex 1D and 2D data.
The classes that perform FFTs in NMath are named in the form <Type><Direction><Dimensionality>FFT, where
● <Type> is Float, Double, FloatComplex, or DoubleComplex based on the precision of the data and the forward domain of the FFT, either real or complex.
● <Direction> is Forward for calculating the DFT, and Backward for calculating its inverse.
● <Dimensionality> is 1D or 2D, depending on the dimensionality of the signal data.
For example, class DoubleForward2DFFT performs the forward DFT on 2D double-precision real signal data. Class FloatComplexBackward1DFFT represents the backward DFT of a 1D single-precision complex signal vector.
This set of classes elegantly supports all common 1D and 2D FFT computations in a robust, easy to use, object-oriented interface.
FFT instances are constructed by specifying the size of the signal data. For example, this code constructs a DoubleForward1DFFT for a signal vector of length 1024:
Code Example – C# FFT
var fft = new DoubleForward1DFFT( 1024 );
Code Example – VB FFT
Dim FFT As New DoubleForward1DFFT(1024)
This creates a DoubleComplexBackward2DFFT for a 500 x 500 data matrix:
Code Example – C# FFT
var fft = new DoubleComplexBackward2DFFT( 500, 500 );
Code Example – VB FFT
Dim FFT As New DoubleComplexBackward2DFFT(500, 500)
FFT instances can also be created by copying the configuration from another FFT instance. For example:
Code Example – C# FFT
var fft2 = new FloatForward1DFFT( fft1 );
Code Example – VB FFT
Dim FFT2 As New FloatForward1DFFT(FFT1)
An NMathFormatException is raised if the given FFT is not of a compatible precision, domain, and dimensionality. You can, however, create a forward FFT from a backward FFT instance, and vice versa.
FFT classes provide properties for setting the scale factor of the FFT:
● Forward FFT classes provide a ForwardScaleFactor property.
● Backward FFT classes provide a BackwardScaleFactor property.
The default scale factor is 1.0. This code sets the scale factor on a DoubleForward1DFFT instance to 2.0:
Code Example – C# FFT
var fft = new DoubleForward1DFFT( 1024 );
fft.ForwardScaleFactor = 2.0;
Code Example – VB FFT
Dim FFT As New DoubleForward1DFFT(1024)
FFT.ForwardScaleFactor = 2.0
As a convenience, backward FFT classes also provide a SetScaleFactorByLength() method which sets the scale factor to the inverse of the signal length. If the forward FFT scale factor is 1.0, using this backward scale factor guarantees that backwardFFT(forwardFFT(signal)) = signal. Note that MATLAB uses this scale factor by default.
FFTs can be computed either in place, overwriting the input data, or with the result placed in a separate, pre-allocated data structure passed by reference.
The FFTInPlace() method computes the FFT in place, while the FFT() method places the result in a second data structure. For example, this code compute an FFT in place:
Code Example – C# FFT
var data = new DoubleVector( 1024, new RandGenUniform() );
var fft = new DoubleForward1DFFT( 1024 );
fft.FFTInPlace( data );
Code Example – VB FFT
Dim data As New DoubleVector(1024, New RandGenUniform())
Dim FFT As New DoubleForward1DFFT(1024)
FFT.FFTInPlace(data)
This code places the result in a second data structure:
Code Example – C# FFT
var data = new FloatMatrix( 5, 5, new RandGenUniform() );
var result = new FloatMatrix( 5, 5 );
var fft = new FloatForward2DFFT( 5, 5 );
fft.FFT( data, ref result );
Code Example – VB FFT
Dim Data As New FloatMatrix(5, 5, New RandGenUniform())
Dim Result As New FloatMatrix(5, 5)
Dim FFT As New FloatForward2DFFT(5, 5)
FFT.FFT(data, Result);
Data can be supplied either using NMath vector and matrix types, or using arrays. For NMath types, an offset into the data can be specified on the vector or matrix instance. For arrays, a separate integer offset may be passed to the FFT methods.
NOTE—In general, the FFT classes require that all input signal data be in contiguous (packed) storage—that is, have positive or negative unit stride. More complex memory layouts can be handled with class DoubleGeneral1DFFT (see "Strided Signals" below).
Results from computing an FFT on real signal data are returned in MKL Pack format1, a compact representation of a complex conjugate-symmetric sequence. The result is the same size as the original signal data.
For convenience, reader classes are provided for unpacking the results. The FFT instance used to generated the result can be queried for the appropriate reader using the GetSignalReader() method. This guarantees that the correct packed signal reader is constructed.
For example:
Code Example – C# FFT
var data = new DoubleVector( 1024, new RandGenUniform() );
var fft = new DoubleForward1DFFT( 1024 );
fft.FFTInPlace( data );
DoubleSymmetricSignalReader reader = fft.GetSignalReader( data );
Code Example – VB FFT
Dim Data As New DoubleVector(1024, New RandGenUniform())
Dim FFT As New DoubleForward1DFFT(1024)
FFT.FFTInPlace(Data)
Dim Reader As DoubleSymmetricSignalReader = FFT.GetSignalReader(Data)
Readers provide random access to any element in the pack FFT result:
Code Example – C# FFT
DoubleComplex thirdelement = reader[2];
Code Example – VB FFT
Dim ThirdElement As DoubleComplex = Reader(2)
Reader classes also provide methods for unpacking the entire result:
● The full unpack methods—such as UnpackFullToArray() and UnpackFullToMatrix()—build the unpacked signal representation of the entire packed complex symmetric signal.
● The symmetric half unpack methods—such as UnpackSymmetricHalftoArray() and UnpackSymmetricHalfToMatrix()—build the unpacked signal representation of the symmetric leading half of the packed signal.
For instance, this code unpacks the entire signal:
Code Example – C# FFT
DoubleSymmetric2DSignalReader reader =
fft.GetSignalReader( ref result );
DoubleComplexMatrix unpacked = reader.UnpackFullToMatrix();
Code Example – VB FFT
Dim Reader As DoubleSymmetric2DSignalReader =
FFT.GetSingalReader(Result)
Dim Unpacked As DoubleComplexMatrix = reader.UnpackFullToMatrix()
NOTE—Complex FFTs do not create packed results. The result is already the same size as the signal data.
Results from computing an FFT on real signal data are returned in symmetric complex conjugate form, and NMath provides special classes for inverting this data back to the real domain.
For example, this code computes a forward FFT on real 1D signal data:
Code Example – C# FFT
var data = new DoubleVector( "[ 1 2 2 1 ]" );
var result = new DoubleVector( 4) ;
var fft = new DoubleForward1DFFT( 4 );
fft.FFT( data, ref result );
Code Example – VB FFT
Dim Data As New DoubleVector("[ 1 2 2 1 ]")
Dim Result As New DoubleVector(4)
Dim FFT As New DoubleForward1DFFT(4)
FFT.FFT(data, Result)
This code uses class DoubleSymmetricBackward1DFFT to invert the result:
Code Example – C# FFT
var reverse = new DoubleVector( 4 );
var rfft = new DoubleSymmetricBackward1DFFT( 4 );
rfft.SetScaleFactorByLength();
rfft.FFT( result, ref reverse );
Code Example – VB FFT
Dim Reverse As New DoubleVector(4)
Dim RFFT As New DoubleSymmetricBackward1DFFT(4)
RFFT.SetScaleFactorByLength()
RFFT.FFT(Result, Reverse)
Symmetric backward FFT classes, such as DoubleSymmetricBackward1DFFT, exploit the complex conjugate symmetry of the forward FFT result. The scaling is necessary for reverse to match data. (See "Scale Factors"above.)
In general, the FFT classes require that all input signal data be in contiguous (packed) storage—that is, have unit stride. When working with strided signals, the FFT must be configured separately, and then used to create an advanced general FFT instance.
NOTE—Strided signals are supported for 1D signals only.
For example, suppose we have the following signal data, and wish to perform an FFT on the subset of the data specified by an offset of 3 and a stride of 2:
Code Example – C# FFT
double[] data =
{ 94423, -341, 42343, 1, -1, 2, -1, 2, -1, 1, -85, 22 };
Code Example – VB FFT
Dim Data() As Double =
{94423.0, -341.0, 42343.0, 1.0, -1.0, 2.0, -1.0, 2.0, -1.0, 1.0,
-85.0, 22.0}
The desired subset has a length of 4. To perform an FFT on this subset:
1. Build an FFTConfiguration instance which describes the FFT to be computed, including the stride and offset:
Code Example – C# FFT
int dimension = 1;
int length = 4;
var config = new FFTConfiguration(
FFTDirection.FORWARD,
FFTPrecision.DOUBLE,
FFTDomain.REAL,
dimension,
length );
configcomplex.DataOffset = 3;
configcomplex.DataStride = 2;
configcomplex.InPlace = true;
Code Example – VB FFT
Dim Dimension As Integer = 1
Dim Length As Integer = 4
Dim Config As New FFTConfiguration(
FFTDirection.FORWARD,
FFTPrecision.DOUBLE,
FFTDomain.REAL,
Dimension,
Length)
ConfigComplex.DataOffset = 3
ConfigComplex.DataStride = 2
ConfigComplex.InPlace = True
2. Build a DoubleGeneral1DFFT instance from the configuration:
Code Example – C# FFT
var fft = new DoubleGeneral1DFFT( ref config );
Code Example – VB FFT
Dim FFT As New DoubleGeneral1DFFT(Config)
3. Create an array to hold the result, and compute the FFT:
Code Example – C# FFT
var result = new double[4];
fft.FFT( signal, ref result );
Code Example – VB FFT
Dim Result(4) As Double
FFT.FFT(Signal, Result)
Class DoubleGeneral1DFFT is intended for advanced users. If the provided configuration does not correctly match the layout and type of the input signal data, exceptions and erroneous outputs will result.