Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
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.
Harley Thomas
Maheshwaramurthy Giriyapura Panchaksharaiah
Mai Tan V.
Zindani Abdul
LandOfFree
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.
Profile ID: LFUS-PAI-O-3600627