Address generators for mapping arrays in bit reversed order

Abstract

A method and apparatus to reduce 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. Alternative embodiments implement the invention for out of place bit reversal (OOPBR) and on processors that do not support special instructions for bit reversed incrementation. The invention only generates unique bit-reversed address pairs and avoids generation of self-reversed addresses. To optimize the invention for in place bit reversal, every non-self bit reversed address in the input array is generated only once, while making simple, computationally efficient increments away from the previous pair of bit reversed addresses. The address pair generator can independently advance only one address in each address pair, and bit reversal of one address uniquely defines the other address.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS[0001]NoneFIELD 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. Alternative embodiments implement the invention for out of place bit reversal (OOPBR) and on processors that do not support special instructions for 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 frequency-doma...

AI Technical Summary

Benefits of technology

"The present invention is a method and apparatus to optimize in place bit reversal (IPBR) in computer systems. The invention reduces the amount of required memory and instruction cycles when implementing Fast Fourier Transforms (FFTs) on a computer system. The preferred embodiment optimizes FFT software using IPBR implemented on a processor capable of bit reversed incrementation, such as the Texas Instruments (TI) C54x digital signal processor (DSP). However, alternative embodiments implement the invention for out of place bit reversal (OOPBR) and on processors that do not support special instructions for bit reversed incrementation. The invention facilitates the identification of computationally efficient patterns for sequentially generating a unique set of bit reversed address pairs. The size of the array to be bit reversed is 2^(log 2N). The invention reduces the alignment requirement for input buffer alignment and also reduces OOPBR cycles for processors that do not support bit reversed address register incrementation."

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