DERIVATION AND IMPLEMENTATION OF AN EFFICIENT FAST FOURIER-TRANSFORM ALGORITHM (EFFT)

An analysis of the sequence of calculations during a standard radix-2 Fast Fourier Transform (FFT) computer algorithm reveals that additional multiplications beyond those normally eliminated by the conventional algorithms are also found to be unnecessary. In particular, the arguments for the trigonometric functions are always used in a well-defined 'modified' bit-inverted order. The first four arguments within any pass yield reductions of multiplications via trigonometric identities. Further, by placing the trigonometric parameters in a look-up table in the same modified order, the minimum number of multiplications for a radix-2 FFT is performed by a simplified algorithm termed the EFFT (Efficient Fast Fourier Transform). This algorithm requires no reference to a bit-inversion procedure or look-up table until the output points are 'unscrambled' at the conclusion.