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 Prime Length

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

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 prime number. 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 Prime
Length

      Disclosed is a procedure to derive optimized DFT
algorithms when the length of the transform is a prime number.  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 expressed as a sum of 2 entities depending
only on real numbers.

      A scaling of y2 is performed using sin(l*r), and the final
result is obtained as: