**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 format^{1}, 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.