These are the supporting examples for the paper "BRUTE-FORCE SEARCH OF FAST CONVOLUTION ALGORITHMS." You will need to install Python (www.python.org) and SciPy (www.scipy.org) to execute these examples. They have been tested under Linux, but should work on Windows and Mac OS X platforms. To execute an example:

python WFFTSz64_1136a.py

You should see a report similar to:

X(1)	residual weight is -12
X(33)	residual weight is -12
X(17)	residual weight is -12
X(49)	residual weight is -12
X(9)	residual weight is -12
X(41)	residual weight is -12
X(25)	residual weight is -12
X(57)	residual weight is -12
X(3)	residual weight is -12
X(35)	residual weight is -12
X(19)	residual weight is -12
X(51)	residual weight is -12
X(11)	residual weight is -12
X(43)	residual weight is -12
X(27)	residual weight is -12
X(59)	residual weight is -12
FFT

N		= 256
FLOPS	= 6664
MAE   	= 2.53781370918e-14

N is the size of the FFT. FLOPS is the the FLOP count. MAE is the mean absolute error when all output values of this FFT are compared to a the SciPy "golden" FFT. The MAE should be a very small number. The initial input operands for the FFT are random and consequently the MAE will be different for every execution of the script.

There are five example weighted FFTs and IFFTs included:


WFFTSz64_1136a.py	Weighted size-64 FFT requiring 1136 FLOPs
WFFTSz64_1136b.py   Another Weighted size-64 FFT, can be used with above FFT as weights multiply to 1 
WIFFTSz64_1136.py   Weighted size-64 IFFT requiring 1136 FLOPs
WFFTSz128_2744.py	Weighted size-128 FFT requiring 2744 FLOPs
WIFFTSz128_2744.py	Weighted size-128 IFFT requiring 2744 FLOPs


All FFTs are inplace and executed by repeated calls of size-2 butterflies with different twiddle factors. All FFTs are flat and unrolled. These FFTs are not general algorithms but meant for illustration and clarity. See the file TestFFT.py for details regarding the Butterfly (BF) method.

The file TestFFT.py contains code that executes the FFTs via the size-2 butterfly calls. It does the following:

* Creates initial random complex data for the FFT
* Computes size-2 butterflies and stores the result in place.
* Tallies all floating point operations. 
* Compares the final concrete result with a result from SciPy and reports the mean absolute error.
* Performs symbolic checks of the graph structure and computations.

TestFFT.py is a script and is best understood by reading it. It is instructive to copy one of the five example FFTs and randomly change some of the twiddle factors to see how errors are detected and FLOP counts change.

Please e-mail any questions to: steve@softerhardware.com.



