FFT algorithms for prime transform sizes and their implementations on VAX, IBM3090VF, and IBM RS/6000

摘要

Variants of the Winograd fast Fourier transform (FFT) algorithm for prime transform size that offer options as to operational counts and arithmetic balance are derived. Their implementations on VAX, IBM 3090 VF, and IBM RS/6000 are discussed. For processors that perform floating-point addition, floating-point multiplication, and floating-point multiply-add with the same time delay, variants of the FFT algorithm have been designed such that all floating-point multiplications can be overlapped by using multiply-add. The use of a tensor product formulation, throughout, gives a means for producing variants of algorithms matching computer architectures.