Patent ID: 8832171
Filing Date: 2014-09-09
Classification: G06F

Abstract:
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: 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: 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: 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.