Methods and Apparatus for Providing a Programmable Mixed-Radix DFT/IDFT Processor Using Vector Engines

Patent metadata

Field	Value
Publication number	US-2017192936-A1
Application number	US-201615272332-A
Country	US
Kind code	A1
Filing date	Sep 21, 2016
Priority date	Dec 31, 2015
Publication date	Jul 6, 2017
Grant date	—

Abstract

A programmable vector processor (“PVP”) capable of calculating discrete Fourier transform (“DFT/IDFT”) values is disclosed. In an exemplary embodiment, an apparatus includes a memory bank and a vector data path pipeline coupled to the memory bank. The apparatus also includes a configurable mixed radix engine coupled to the vector data path pipeline. The configurable mixed radix engine is configurable to perform a selected radix computation selected from a plurality of radix computations. The configurable mixed radix engine performs the selected radix computation on data received from the memory bank through the pipeline to generate a radix result. The apparatus also includes a controller that controls how many radix computation iterations will be performed to compute an N-point DFT/IDFT based on a radix factorization.

First claim

What is claimed is:

1 . An apparatus, comprising:
a memory bank; a vector data path pipeline coupled to the memory bank; and a configurable mixed radix engine coupled to the vector data path pipeline, wherein the configurable mixed radix engine is configurable to perform a radix computation selected from a plurality of radix computations, and wherein the configurable mixed radix engine performs the selected radix computation on data received from the memory through the pipeline to generate a radix result.

2 . The apparatus of claim 1 , wherein the radix computation is selected from a set of radix computations comprising radix3, radix4, radix5, and radix6 computations.

3 . The apparatus of claim 2 , further comprising a controller that generates a radix factorization to compute an N-point digital Fourier transform (DFT).

4 . The apparatus of claim 3 , wherein the controller controls how many radix computation iterations will be performed to compute the N-point DFT based on the radix factorization, wherein for each iteration data is moved from the memory bank through the vector data path pipeline to the configurable mixed radix engine to perform a radix computation determined by the radix factorization.

5 . The apparatus of claim 1 , further comprising a vector feedback data path, and wherein the configurable mixed radix engine writes radix results to the memory bank using the vector feedback data path.

6 . The apparatus of claim 1 , further comprising an output buffer, and wherein the configurable mixed radix engine outputs a final DFT result using the output buffer.

7 . The apparatus of claim 1 , wherein the vector data path pipeline comprises a vector scaling unit that receives vector data from the memory bank and outputs scaled vector data.

8 . The apparatus of claim 7 , wherein the vector data path pipeline comprises a twiddle multiplier that multiples the scaled vector data by twiddle factors.

9 . The apparatus of claim 8 , further comprising a twiddle generator that generates the twiddle factors.

10 . The apparatus of claim 5 , wherein the vector feedback data path comprises a scaling factor calculator that determines scaling factors from the radix results.

11 . The apparatus of claim 1 , further comprising a vector memory address generator that generates addresses used to write data into the memory bank and read data from the memory bank.

12 . The apparatus of claim 1 , wherein the vector data path pipeline carries twelve data values per clock cycle.

13 . A method for performing an N-point DFT, comprising:
determining a radix factorization to compute the N-point DFT, the radix factorization determining one or more radix calculations to be performed; and performing an iteration for each radix calculation, wherein each iteration comprises:
reading data from a memory bank into a vector data path pipeline;
configuring a configurable mixed radix engine to perform a selected radix calculation;
performing the selected radix calculation on the data in the vector data path pipeline;
storing a radix result of the selected radix calculation back into the memory bank, if the current iteration is not the last iteration; and
outputting the radix result of the selected radix calculation as the N-point DFT result, if the current iteration is the last iteration.

14 . The method of claim 13 , wherein the operation of configuring the configurable mixed radix engine comprises configuring the configurable mixed radix engine to perform a selected one of radix3, radix4, radix5, and radix6 computations.

15 . The method of claim 13 , wherein the operation of storing comprises storing the radix result of the selected radix calculation back into the memory bank using a vector feedback data path.

16 . The method of claim 13 , further comprising scaling the vector data from the memory bank to generate scaled vector data.

17 . The method of claim 7 , method of claim 13 , further comprising multiplying the scaled vector data by twiddle factors.

18 . The method of claim 17 , further comprising generating the twiddle factors.

19 . The method of claim 13 , further comprising generating addresses used to write data into the memory bank and read data from the memory bank.

20 . The method of claim 13 , further comprising configuring the vector data path pipeline to carry twelve data values per clock cycle.

Assignees

• Guo Yuanbin
• Kim Hong Jik
• Cavium Inc

Inventors

• Guo Yuanbin
• Kim Hong Jik

Classifications

• G06F17/142 Primary

  Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm · CPC title

• G06F17/16

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title

• H04W16/18

  Network planning tools · CPC title

• G06F17/141 Primary

  Discrete Fourier transforms · CPC title