Variants of the Winograd multiplicative FFT algorithms and their implementation on IBM RS/6000

Author

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

Author_Institution

Dept. of Comput. Sci., Towson State Univ., MD, USA

fYear

1991

fDate

14-17 Apr 1991

Firstpage

2185

Abstract

Variants of the Winograd (1976, 1980) multiplicative FFT (fast Fourier transform) algorithm for transform sizes of primes and product of primes are derived, which take advantage of a computer architecture with a multiply-add feature. For processors which perform floating-point addition, floating-point multiplication, and the floating-point multiply-add in one computer clock cycle, FFT algorithms can be designed such that all the floating-point multiplications can be overlapped by using multiply-adds. Implementation of multiply-add algorithms on an IBM RS/6000 is discussed. The use of a tensor product formulation throughout gives a means for producing variants of algorithms matching computer architectures

Keywords

IBM computers; digital arithmetic; fast Fourier transforms; reduced instruction set computing; IBM RS/6000; RISC architecture; Winograd multiplicative FFT algorithms; computer architecture; computer clock cycle; fast Fourier transform; floating-point addition; floating-point multiplication; floating-point multiply-add; prime products; prime sizes; tensor product; Algorithm design and analysis; Chaos; Clocks; Computer architecture; Force measurement; Indexing; Large-scale systems; Military computing; Monitoring; Tensile stress;

fLanguage

English

Publisher

ieee

Conference_Titel

Acoustics, Speech, and Signal Processing, 1991. ICASSP-91., 1991 International Conference on

Conference_Location

Toronto, Ont.

ISSN

1520-6149

Print_ISBN

0-7803-0003-3

Type

conf

DOI

10.1109/ICASSP.1991.150847

Filename

150847