Address generators for mapping arrays in bit reversed order

Details Address generators for mapping arrays in bit reversed order Address generators for mapping arrays in bit reversed order

2006-05-16

2006-05-16

Mai, Tan V. (Department: 2193)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S400000

Reexamination Certificate

active

07047268

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.

REFERENCES:
patent: 3673399 (1972-06-01), Hancke et al.
patent: 4547862 (1985-10-01), McIver et al.
patent: H570 (1989-01-01), Tylaska et al.
patent: 4823297 (1989-04-01), Evans
patent: 4916649 (1990-04-01), Yorozu et al.
patent: 4977533 (1990-12-01), Miyabayashi et al.
patent: 5329474 (1994-07-01), Yamada
patent: 5473556 (1995-12-01), Aguilar et al.
patent: 5682340 (1997-10-01), Arends et al.
patent: 6035313 (2000-03-01), Marchant
patent: 6247034 (2001-06-01), Nakai et al.
patent: 6279096 (2001-08-01), McCoy et al.
patent: 6304887 (2001-10-01), Ju et al.
patent: 6351758 (2002-02-01), Courtney et al.
patent: 6366937 (2002-04-01), Shridhar et al.
patent: 6430587 (2002-08-01), Orling
patent: 6609140 (2003-08-01), Greene
patent: 6643761 (2003-11-01), Berg et al.
patent: 6789097 (2004-09-01), Jin
patent: 2002/0194235 (2002-12-01), Yamamoto et al.
patent: 2003/0131032 (2003-07-01), Vinitzky
J.W. Cooley and J.W. Tukey, An Algorithm for the Machine Calculation of Complex Fourier Series, Mathematics of Computationn (1965), vol. 19, No. 90, pp. 297-301.

Affiliated with

Also associated with

Rating

Address generators for mapping arrays in bit reversed order does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Address generators for mapping arrays in bit reversed order, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Address generators for mapping arrays in bit reversed order will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3600627