Patent ID: 6760741
Filing Date: 2004-07-06
Classification: G06F

Abstract:
A method for advancing pointers in a memory comprising a sequence of N data points of a stage M of a Fast Fourier Transform (FFT) whose first stage is stage 0, the N data points comprising N/2 A data points and N/2 B data points, wherein said N data points are stored in said memory in 2M groupings of A data points, each of said groupings having 2(Log2N)âˆ’1âˆ’M data points, and wherein each of said groupings is followed by a grouping of 2(Log2N)âˆ’1âˆ’M B data points, the method comprising the steps of:a) setting a pointer index Ap equal to a binary value of a data point memory index corresponding to a first of said A data points in said memory; b) setting a pointer index Bp equal to a binary value of a data point memory index corresponding to a first of said B data points in said memory; c) setting a first binary bit mask value R1 equal to 2(Log2N)âˆ’1âˆ’M+1; d) setting a second binary bit mask value R2 equal to 2(Log2N)âˆ’1âˆ’M; e) advancing said Bp pointer index to the data point memory index corresponding to the next B data point in said memory by: e1) adding said Ap pointer index value to R1; e2) ORing results of step e1) with R2; and e3) setting said Bp pointer index value equal to results of step e2); and f) advancing said Ap pointer index to the data point memory index corresponding to the next A data point in said memory by: f1) ANDing results of step e1) with the bit-inverted value of R2; and f2) setting said Ap pointer index value equal to results of step f1).