Browse Prior Art Database

FFTs for Fused Multiply/ Add Architectures

IP.com Disclosure Number: IPCOM000121274D
Original Publication Date: 1991-Aug-01
Included in the Prior Art Database: 2005-Apr-03
Document File: 2 page(s) / 45K

Publishing Venue

IBM

Related People

Feig, E: AUTHOR [+2]

Abstract

Many of today's advanced workstations and signal processors are designed for efficient fused multiply/add operations. Disclosed here are Split-Radix, radix-2, 4, and 8 decimation in time and decimation in frequency FFT algorithms optimized for such architectures.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 62% of the total text.

FFTs for Fused Multiply/ Add Architectures

      Many of today's advanced workstations and signal
processors are designed for efficient fused multiply/add operations.
Disclosed here are Split-Radix, radix-2, 4, and 8 decimation in time
and decimation in frequency FFT algorithms optimized for such
architectures.

      Standard FFT algorithms are based on factorizations of the FFT
matrix into products of sparse matrices, alternating between addition
matrices and twiddle factors.  All the computations come as pairs of
the form
                               ax + by
                               ax - by
where a, b are fixed real constants and x, y are real variables in
the computation.  The computation is replaced by either
                               x + (b/a)y
                               x - (b/a)y
or
                               (a/b)x + y
                               (a/b)x - y
and the scaled factor is propagated to the ensuing computation.  It
can be shown that for the FFT factorization, when the denominator is
chosen so that it is always the smaller value in absolute value, the
final scaling is always 1, so that no final scaling is required.

      The total number of instructions used by the disclosed split-
radix algorithms is (8/3)nlog2n - (16/9)n + (20/9) for log2n...