Fft pointer mechanism for fft memory management

Abstract

A method for advancing pointers in a memory including 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 including N/2 a data points and N/2 B data points, the N data points are stored in the memory in 2 groupings of a data points, each of the groupings having 2 data points, and each of the groupings is followed by a grouping of 2 B data points, the method including the steps of a) setting a pointer index A equal to the binary value of the data point memory index corresponding to the first A data point in the memory, b) setting a pointer index B equal to the binary value of the data point memory index corresponding to the first B data point in the memory, c) setting a first binary bit mask value R equal to 2 +1, d) setting a second binary bit mask value R equal to 2 , e) advancing the B pointer index to the data point memory index corresponding to the next B data point in the memory by e1) adding the A pointer index value to R , e2) ORing the results of step e1) with R , and e3) setting the B pointer index value equal to the results of step e2), and f) advancing the A pointer index to the data point memory index corresponding to the next A data point in the memory by f1) adding the A pointer index value to R , f2) ANDing the results of step f1) with the bit-inverted value of R , and f3) setting the A pointer index value equal to the results of step f2).