Index generation scheme for prime factor algorithm based mixed radix discrete fourier transform (DFT)
US8832171B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Mar 30, 2012 |
| Grant date | Sep 9, 2014 |
| Priority date | — |
| Expiry date | Apr 23, 2033 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F17/144
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.