The next release of Center Space’s NMATH .NET libraries will contain high performance, multi-core aware, fast fourier transform classes. This set of classes will elegantly support all common 1D and 2D FFT computations in a robust easy to use object-oriented interface.
The following FFT classes will be available.
- DoubleComplexForward1DFFT
- DoubleComplexBackward1DFFT
- DoubleComplexForward2DFFT
- DoubleComplexBackward2DFFT
- DoubleForward1DFFT
- DoubleSymmetricBackward1DFFT
- DoubleForward2DFFT
- DoubleGeneral1DFFT (for computing FFT's of data with offset & strided memory layouts)
All classes efficiently support FFT’s of arbitrary length, with a simple interface for both in-place and out-of-place computations. Additionally, there is a parallel set of classes for single precision computation.
Example
Here is a simple example computing a 1000-point forward 1D FFT.
// Create some random signal data.
RandomNumberGenerator rand = new RandGenMTwist(427);
DoubleVector data = new DoubleVector(1000, rand);
// Create the 1D real FFT instance
DoubleForward1DFFT fft1000 =
new DoubleForward1DFFT(1000);
// Compute the FFT
fft1000.FFTInPlace(data);
The FFT of Real (non-Complex) data results in a FFT signal of complex-conjugate symmetric data. For memory efficiency this is returned to the user in a packed format (making in-place computation possible). To facilitate the unpacking of this data, signal reader classes are supplied that support random-access indexers into the packed data. Continuing with the example above.
// Ask the FFT instance for the correct reader,
// passing in the FFT data.
DoubleSymmetricSignalReader reader
= fft1000.GetSignalReader(data);
// Now we can access any element from the
// packed complex-conjugate symmetric FFT data set
// using common random-access index sematics.
DoubleComplex thirdelement = reader[2];
// Also the entire result can be unpacked
DoubleComplex[] unpackedfft =
reader.UnpackFullToArray();
The readers are not necessary for the Complex versions of the FFT classes because FFT’s of Complex data is Complex and so no data packing is possible (for memory savings).
Packing Format Notes
As mentioned above, the Fourier transform of a real signal, results in a complex-conjugate symmetric signal. This symmetry is used by CenterSpace to pack the Fourier transform into an array which is the same size as the signal array.
The following table describes the layout of the packed complex-conjugate symmetric signal, of length N, in one dimension.
If we were to unroll the array, where each element in the array contains alternating real and complex values, for the case of N even, we would have an array of length 2*N.
The complexities of the packing in two dimensions increase substantially, and will not be recorded here. All NMath FFT users are encourage to use the readers to unwind packed results. Not only does this reduce coding complexity, if the underlying packing format changes, the readers will still provide the expected functionality.
Finally, when inverting complex-conjugate symmetric signals, using the DoubleSymmetricBackward1DFFT class, the input signals are expect be packed.
-Paul