Browse Code
This C++ code does radix 2 & 3 multi-dimension (any) complex FFT and its inverse. Array dimensions with sizes that are not 2^m 3^n are automatically zero-padded to the nearest larger size integer of the form 2^m 3^n. The new array has the original data centered, except when a dimension size is increased by an odd number, the zero padding on the left is one less than the zero padding on the right. This FFT code is in is own namespace and is in one source file and one include file. There is a separate C++ graphical test program. There are bash .sh build scripts to build everything together, to build the static library, to build the dynamic link library, and to build the test program either statically or dynamically linked. STL libraries such as std::complex, std::vector, and std::string are used. For 2D and higher dimension FFT's, parallel concurrent execution can optionally be done using std::thread.
Features
- The FFT is mixed radix 2 and 3, multi-dimension, and complex with double precision
- The FFT code is entirely C++ with one .cpp file and one .h file, named radix2and3fft.cpp and radix2and3fft.h, respectively. The entire code is in the RADIX2AND3FFT_NS namespace.
- The code can easily be included in other C++ projects
- There is a C++ test program which in Unix uses gnuplot to plot curves and surfaces In particular, it first displays a 2D line plot or a 3D surface plot of the original data, then computes and displays the the FFT, then computes and displays the IFFT of the FFT, which is the same as the original plot or image. It is implemented un the two files test_radix2and3fft.cpp and test_radix2and3fft.h.
- In the test program, gnuplot is used by first writing the data text file and the script text file and then doing system(unix command line). The script text file has a plot or splot command. The unix command line is "gnuplot quoted_script_filename".
- Although the C++ test program is Unix only, the FFT source code is not and can be used on any platform. The test program is in a .cpp file and a .h file and the FFT source code is in another .cpp file and another .h file. Everything for the FFT is in its own namespace. The testing code is completely separate from the FFT code. The FFT code can be made into a library.
- There is a C++ Complex Calculator (c-complex-calculator) SourceForge project that makes it easy to use this FFT,.
- This C++ Complex Calculator has been used for verification of this FFT.. The continuous Fourier transform should agree with the FFT in the limit of large numbers of points over a range much larger than the function span. This requires the function to be centered with wrap around on the element with zero subscript. This shouldn't be done if there is to be zero padding.
- A real symmetric function centered on the center element will result in the FFT being real but to have alternating signs between adjacent elements.
- Optional use of C++ std::thread for faster computation for 2D and higher dimensions. Higher dimension FFT's are implemented in terms of 1D FFT's. For each axis,, and for each index on that axis, 1D FFT's are done in every possible direction. For an N dimensional FFT, this is an N-1 dimensional subspace of possible directions. So for each axis for 2D and higher dimension, the 1D FFT's are distributed amongst the threads. Threads are created and destroyed for each axis. For a 1D FFT, there is only one direction and only one thread..
- When parallelization for concurrent execution is optionally done using std::thread for 2D and higher dimensions, the number of threads is limited to four and the number of threads for each axis cannot exceed the size of that axis.
- Reference: "Digital Signal Processing" by Monson H Hayes, Schaum's Outline Series, McGraw-Hill, 1999, ISBN 0–07–027389–8, Chapter 7 : "Fast Fourier Transform"
Project Samples
