Index generation scheme for prime factor algorithm based mixed radix discrete fourier transform (DFT)

摘要

In one embodiment, a processor performs a method of generating pipelined data read indexes and data write indexes for a Prime Factor Algorithm (PFA) Discrete Fourier Transform (DFT) without look-up tables. The processor is adapted to factorize an ‘N’ point PFA DFT into one or more mutually prime factors and zero or more non-prime factors, calculate a 0th column index for an ith row (Xi0), calculate an IndCor when the value of Xi0 equals zero and when a row number (i) does not equal zero, calculate Xij, generate the data read indexes, perform a DFT kernel computation on Lk point for the mutually prime factors and the non-prime factors, and generate the data write indexes for the mutually prime factors and the non-prime factors. Xij represents ith row and jth column of 2D input Buffer and enables a selection of a linear index from the 2D input buffer.

主权项

1. A machine configured to perform a method of generating a plurality of pipelined data read indexes and a plurality of pipelined data write indexes for Prime Factor Algorithm (PFA) based mixed radix Discrete Fourier Transform (DFT), said machine comprising:
means for factorizing an ‘N’ point PFA DFT into one or more mutually prime factors and zero or more non-prime factors; means for initializing an Nmin parameter to a smallest factor from said mutually prime factors and said non-prime factors, and initializing an Index Correction (IndCor) to zero; means for determining whether a value of ‘k’ is less than a value of ‘n’, wherein ‘k’ is a variable and ‘n’ corresponds to the number of said mutually prime factors; means for determining whether a row number (i) of said PFA DFT is less than a Column increment index (Cincr) of said PFA DFT, wherein said Column increment index (Cincr) equals N divided by Lk (N/Lk), wherein Lk is the ‘kth’ mutually prime factor of said mutually prime factors, wherein a 0th column index Xi0 for an ith row of said PFA DFT is calculated in accordance with an equation:
Xi0=(i*Lk*M)%N, where M is the product of the non-prime factors; means for calculating an index correction (IndCor) of said PFA DFT when a value of said Xi0 equals zero and when said row number (i) does not equal zero, wherein said IndCor is calculated to obtain a source mapping of linear indexes in accordance with an equation:
IndCor=(IndCor+Nmin)%(M−1), wherein said Xij is calculated in accordance with an equation: Xij=Xij+IndCor, wherein said Xij represents the ith row and jth column of a 2-Dimensional input Buffer X, wherein said Xij enables a selection of said linear index from said 2D input buffer; means for generating said plurality of data read indexes based on said mutually prime factors and said non-prime factors, wherein said plurality of data read indexes Xij are generated in accordance with an equation:
Xij=(Xi(j−1)+Cincr)%N, wherein each of said data read indexes is generated per stage to correspond to at least one of said mutually prime factors or at least one of said non-prime factors; means for performing a DFT kernel computation on said Lk point for each of said mutually prime factors and each of said non-prime factors using said plurality of data read indexes that are generated and obtained from said 2D input buffer; and means for generating said plurality of data write indexes for said mutually prime factors and said non-prime factors, wherein said plurality of data write indexes are stored in an output buffer or an input buffer of a next stage.