# US 2012/0254274 A1 · Index Generation Scheme for Prime Factor Algorithm Based Mixed Radix Discrete Fourier Transform (DFT)

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0254274 A1
- Document ID: US20120254274A1
- Status: Published application
- Kind: A1
- Application number: 13/435,073
- Filed: 2012-03-30
- Published: 2012-10-04
- Earliest claimed: 2011-03-31
- Assignees: Saankhya Labs Pvt. Ltd.
- Inventors: Gururaj Padaki; Saurabh Mishra; Suman Sanisetty
- Web page: https://patentgrep.com/patent/US20120254274A1

## CPC

- G06F 17/144: {Prime factor Fourier transforms, e.g. Winograd transforms, number theoretic transforms}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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.

## Claims

### Claim 1

A processor 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 processor adapted to:
factorize an ‘N’ point PFA DFT into one or more mutually prime factors and zero or more non-prime factors;
initialize an Nmin parameter to a smallest factor from said mutually prime factors and said non-prime factors, and initialize an Index Correction (IndCor) to zero;
determine 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;
determine 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;
calculate 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;
generate 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;
perform 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
generate 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.

### Claim 2 (depends on 1)

The CPU of claim 1, wherein said method further comprises incrementing a value of ‘j’ when said Xij is calculated.

### Claim 3 (depends on 2)

The CPU of claim 2, wherein said method further comprises determining whether said value of ‘j’ is less than said ‘Lk’.

### Claim 4 (depends on 1)

The CPU of claim 1, wherein said method further comprises incrementing said value of ‘j’ when said plurality of data read indexes are generated, wherein the value of said ‘M’ is the product of said non-prime factors.

### Claim 5

A hardware accelerator comprising a set of instructions for faster generation of a plurality of pipelined data read indexes and a plurality of pipelined data write indexes for a Prime Factor Algorithm (PFA) based mixed radix Discrete Fourier Transform (DFT), said instructions comprising:
factorizing an ‘N’ point PFA DFT into one or more mutually prime factors and zero or more non-prime factors;
initializing an Nmin parameter to a smallest mutually prime factor from said mutually prime factors, and initializing an Index Correction (IndCor) to zero;
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 a 0th column index Xi0 for an ith row is calculated in accordance with an equation:
Xi0=(i*Lk*M) % N;
calculating an index correction (IndCor) of said PFA DFT when the value of said Xi0 equals zero and when said row number (i) does not equal zero, wherein said IndCor is calculated in accordance with an equation:
IndCor=(IndCor+Nmin) % (M−1),
wherein said Xij is calculated in accordance with an equation: Xij=Xij+IndCor;
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 are generated in accordance with an equation:
Xij=(Xi(j−1)+Cincr) % N;
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 an input buffer; and
generating said plurality of data write indexes for said mutually prime factors and said non-prime factors.

### Claim 6 (depends on 5)

The hardware accelerator of claim 5, wherein said instructions further comprise incrementing a value of ‘j’ when said Xij is calculated.

### Claim 7 (depends on 7)

The hardware accelerator of claim 7, wherein said instructions further comprise:
determining whether said value of ‘j’ is less than said ‘Lk’; and
incrementing said value of ‘j when said plurality of data read indexes are generated.

### Claim 8

A processor to dynamically configure a plurality of DFT stages in a communication system, said processor comprising:
a factorization unit that factorizes an N point DFT into a plurality of mutually prime factors and a plurality of non-prime factors;
a stage determination unit that determines a plurality of stages based on said mutually prime factors and said non-prime factors; and
a stage configuration unit that dynamically configures said plurality of stages based on said mutually prime factors and said non-prime factors of said N point DFT.

### Claim 9 (depends on 8)

The processor of claim 8, wherein said plurality of stages comprises a plurality of PFA stages and a plurality of Non-PFA stages.

### Claim 10 (depends on 8)

The processor of claim 8, wherein said plurality of PFA stages and said plurality of Non-PFA stages are determined based on said N point DFT.
