Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-06-16
2004-04-06
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06718356
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to radix-r FFTs (Fast Fourier Transforms), and more particularly to a method and an apparatus for assigning data. samples to memory when computing a radix-r FFT.
2. Background of the Invention
Generally, the performance of computer systems is strongly related to memory access speeds. In particular, the present calculation of FFT algorithms requires, intensive memory access and storage operations.
The FFT is a class of algorithms widely used in the field of digital signal processing that break down complex signals into elementary components. The FFT is a discrete fourier transform (DFT) algorithm, which reduces the number of computations needed for N points from 2N
2
to 2NlgN, where lg is the base-2.
Radix-r, N-point FFTs can be described by SDF (synchronous data flow) graphs consisting of vertices performing butterfly operations and arcs denoting data transfers between them. A butterfly operation is the smallest constituent part of a FFT and represents a cross multiplication incorporating multiplication, sum and difference operations. The name is derived from the shape of the signal flow diagram. For a radix-2 FFT, the smallest transform or butterfly operation (basic computational unit) used is the 2-point DFT. Each FFT vertex consumes a different set of data and thus, in data processing applications in a computer, accesses a different set of memory locations.
In state of the art FFT computation systems, successive memory accesses to the same memory bank may occur, which will impose the execution of wait states as part of the butterfly operations. An alternative for avoiding such successive accesses is to provide additional memory for temporary storage. This leads to higher costs or the performance of such systems decreases.
It is therefore desirable to minimize or eliminate wait states and to minimize the total memory required when computing a radix-r FFT.
SUMMARY OF THE INVENTION
The present invention provides a method and apparatus for assigning data samples to memory when computing a radix-r FFT. This method includes the steps of incrementing a memory bank counter if the fractional part of a data sample divided by a region difference of a butterfly stage equals zero, assigning the data sample to a memory bank indicated by the memory bank counter, executing the first step if the total number of data samples is not reached by a region difference counter counting a region difference change of a butterfly stage, and executing the last step until the total number of data samples is reached by a data sample counter.
The present invention also provides an apparatus for assigning data samples to memory when computing a radix-r FFT, comprising a plurality of memory banks for storing the data samples, a memory bank counter indicating the memory banks, a data sample counter for counting an increment of the data samples, a region difference counter for counting a region difference change of a butterfly stage, a computer program having the current values of the data sample counter and the region difference counter as input values for determining whether the fractional part of the current data sample index divided by the current region difference value equals zero, and a multiplexer for multiplexing the current data sample to an assigned memory bank if the fractional part is not equal zero.
Generally, the present invention minimizes memory and wait states required to implement a FFT in a computer system, while still allowing maximum throughput (single cycle) through the vertices or a butterfly operation. Moreover, the present invention optimizes the trade-off of memory size versus FFT performance.
REFERENCES:
patent: 6122703 (2000-09-01), Nasserbakht
patent: 0805401 (1997-11-01), None
Bailey D.H.: “A High-Performance Fast Fourier Transform Algorithm for the Cray-2,”Journal of Supercomputing, vol. 1, No. 1, pp. 43-60, Netherlands 1987.
Johnson L.G.: “Conflict Free Memory Addressing for Dedicated FFT Hardware,”IEEE, Inc. Transactions on Circuits and Systems II: Analog and Digital Signal Processing, IEEE Inc. New York, US., vol. 39, No. 5, New York, USA 1992.
International Search Report dated Sep. 17, 2001.
Barth Frank
Rosner Stephan
Advanced Micro Devices , Inc.
Ngo Chuong Dinh
Williams Morgan & Amerson
LandOfFree
In-place operation method and apparatus for minimizing the... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with In-place operation method and apparatus for minimizing the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and In-place operation method and apparatus for minimizing the... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3266315