Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Optimized DFT Algorithms Using Multiply Add Operations for Powers of 2

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

Publishing Venue

IBM

Related People

Mechentel, A: AUTHOR

Abstract

Disclosed is a procedure to derive optimized DFT algorithms when the length of the transform is a power of 2. The optimization technique maximizes the use of the multiply-add operation used in modern computers. Such an operation is expressed as Z = + X + a*Y. The discrete Fourier transform of length N is expressed as:

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

Optimized DFT Algorithms Using Multiply Add Operations for Powers of 2

      Disclosed is a procedure to derive optimized DFT
algorithms when the length of the transform is a power of 2.  The
optimization technique maximizes the use of the multiply-add
operation used in modern computers.  Such an operation is expressed
as Z = + X + a*Y.  The discrete Fourier transform of length N is
expressed as:

      The expression is broken into 2 parts.

      The first expression is a DFT of length n/2.  The second
expression will be computed using a generalized HORNER's rule in the
form: xl + al*(x2 + a2(x3 + a3...)) after all symmetries are
exhausted, and each radix is done within one module.