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

Author

Lu, Chao ; Cooley, James W. ; Tolimieri, Richard

Author_Institution

IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, USA

Volume

41

Issue

2

fYear

1993

fDate

2/1/1993 12:00:00 AM

Firstpage

638

Lastpage

648

Abstract

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

Keywords

digital arithmetic; fast Fourier transforms; microcomputer applications; FFT algorithms; IBM 3090 VF; IBM RS/6000; VAX; Winograd fast Fourier transform; arithmetic balance; floating-point addition; floating-point multiplication; floating-point multiply-add; operational counts; prime transform size; tensor product formulation; time delay; Algorithm design and analysis; Application software; Arithmetic; Chaos; Computer architecture; Concurrent computing; Delay effects; Fast Fourier transforms; Fourier transforms; Paper technology; Parallel machines; Tensile stress;

fLanguage

English

Journal_Title

Signal Processing, IEEE Transactions on

Publisher

ieee

ISSN

1053-587X

Type

jour

DOI

10.1109/78.193205

Filename

193205