Dismiss
The Prior Art Database and Publishing service will be updated on Sunday, February 25th, from 1-3pm ET. You may experience brief service interruptions during that time.
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

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.
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...