Address generators integrated with parallel FFT for mapping arrays in bit reversed order

Abstract

Reducing the amount of required memory and instruction cycles when implementing Fast Fourier Transforms (FFTs) on a computer system is described. The invention optimizes FFT software using in-place bit reversal (IPBR) implemented on a processor capable of bit reversed incrementation. Enables the design of address generators that combine IPBR and one FFT stage in parallel. Increases efficiency by removing instructions to store output from a stand-alone IPBR mapping and then fetch the same data as input for the FFT stage.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS [0001] This application is a continuation-in-part of U.S. patent application Ser. No. 10 / 097,407, entitled “ADDRESS GENERATORS FOR MAPPING ARRAYS IN BIT REVERSED ORDER,” filed on Mar. 15, 2002.FIELD OF THE INVENTION [0002] The present invention is a method and apparatus to reduce the amount of required memory and instruction cycles when implementing Fast Fourier Transforms (FFTs) on a computer system. More particularly, the preferred embodiment of the present invention optimizes FFT software using in-place bit reversal (IPBR) implemented on a processor capable of bit reversed incrementation. BACKGROUND OF THE INVENTION [0003] Algorithms that perform discrete transforms such as Fast Fourier Transforms (FFTs) are well known. The Fourier transform is a mathematical operator for converting a signal from a time-domain representation to a frequency-domain representation. The inverse Fourier transform is an operator for converting a signal from a fre...

AI Technical Summary

Benefits of technology

[0020] The process facilitates the identification of computationally efficient patterns for sequentially generating a unique set of bit reversed address pairs. Five exemplary new IPBR methods and modifications of these methods are presented. The size of the array to be bit reversed is 2{circumflex over ( )}(log2N). For use on a DSP capable of bit reversed incrementation of address registers but having only one address increment register, optimized program code implementing Method 1 requires minor changes to work for odd and even log2N. For processors with more than one address increment register available, optimized code implementing Method 1 works for all values of log2N. Method 2 further reduces cycles for odd log2N. Method 3 reduces cycles for the even log2N arrays relative to Method 1. Method 4 is similar to Method 1, however Method 4 does not pose any problem for processors with only one address increment register. Method 1 is unique in that it reduces the alignment requirement. Method 5 extends Method 3 to work for odd log2N.

[0021] Methods 1m, 2m, 3m, and 4m are modifications of Method 1, 2, 3, and 4 respectively. All these modified Methods require only two address registers. The cycle count for Method 2m and Method 2 will be very close, if not identical. The other modified methods require fewer address registers, but increase the number of nested inner loops. Thus Methods 1m, 3m and 4m may reduce or increase cycles relative to their un-modified counterparts, depending on the processor.

[0023] The present invention improves the in-place bit reversal (IPBR) process on computer processors and systems by defining an address generator for generating address pairs used for processing an input array using IPBR in parallel with processing a stage of a Fast Fourier Transform (FFT). The method optimizes FFT software using IPBR that can be implemented on a processor.

[0024] The present invention creates an address pair generator that is used to combine IPBR and one FFT stage. Computing the IPBR and the first FFT stage in parallel increase processing efficiency by removing instructions to store output from a stand-alone IPBR mapping and then fetch the same data as input for the FFT stage.

Problems solved by technology

An FFT using OOPBR may have a hidden cycle penalty beyond the bit reversal itself, when the output is eventually copied back to the location of the input array.

Computational processes that use more of the available scratch memory than necessary can lead to future problems when converting to an operating system that permits multiple computational processes to interrupt each other.

In the event that the cycles required for IPBR can be made more competitive relative to OOPBR, for many applications the additional data memory requirement of OOPBR cannot be justified.

The conventional IPBR method is inefficient because it relies on an address pair generator that yields extraneous address pairs.

Images