FFT device and method for performing a Fast Fourier Transform

Patent metadata

Field	Value
Publication number	US-10282387-B2
Application number	US-201315034622-A
Country	US
Kind code	B2
Filing date	Nov 6, 2013
Priority date	Nov 6, 2013
Publication date	May 7, 2019
Grant date	May 7, 2019

Abstract

An FFT device for performing a Fast Fourier Transform (FFT) of an operand vector of length N is described. The FFT device comprises a control unit, a coefficient unit, and a transformation unit. The control unit controls a sequence of transformation rounds, the transformation rounds including two or more FFT rounds and further including or not including a window round. The control unit also maintains configuration data indicating for each of said transformation rounds whether the respective transformation round is an FFT round, a window-FFT round, or a window round. The coefficient unit provides transformation data. The transformation unit is arranged to receive the transformation data and to perform the respective linear transformation on the basis of the transformation data. A method for performing a Fast Fourier Transform is described as well.

First claim

The invention claimed is:

1. An FFT device for performing a Fast Fourier Transform (FFT) of an operand vector of length N, comprising:
control circuitry arranged to control a sequence of transformation rounds, the transformation rounds responsive to a command, including two or more FFT rounds and further including or not including a window round, and arranged to maintain configuration data indicating for any transformation round whether the respective transformation round is an FFT round, a window-FFT round, or said window round; and
coefficient circuitry connected to the control circuitry, the coefficient circuitry for providing transformation data;
transformation circuitry connected to the coefficient circuitry, the transformation circuitry arranged to receive, for each of said transformation rounds, transformation data from the coefficient circuitry, the transformation data depending on whether the respective transformation round is an FFT round, a window-FFT round, or said window round as indicated by the configuration data, and responsive to a respective flag to perform the respective linear transformation on the basis of the transformation data;
an input operand Random Access Memory (RAM) connected to the control circuitry;
input buffer and reorder circuitry connected to the input operand RAM, to the control circuitry, and to the transformation circuitry;
an output buffer connected to the transformation circuitry and to the control circuitry; and
an output operand RAM connected to the output buffer and to the control circuitry.

2. The FFT device of claim 1 , wherein the coefficient circuitry comprises or is integrated in Random Access Memory (RAM) circuitry.

3. The FFT device of claim 1 , wherein the transformation data for an FFT round comprises a set of twiddle coefficients, the transformation data for a window-FFT round comprises a set of modified twiddle coefficients, and the transformation data for a window round comprises a set of window coefficients.

4. The FFT device of claim 1 , wherein the coefficient circuitry comprises quadrature extension circuitry for providing a complete set of twiddle coefficients on the basis of a reduced set of twiddle coefficients of a first octant of a unit circle by exploiting symmetry properties of the twiddle coefficients.

5. The FFT device of claim 4 , wherein the quadrature extension circuitry is arranged to be bypassed in any round that is a window round or a window-FFT round.

6. The FFT device of claim 1 , wherein the transformation circuitry comprises first radix circuitry for performing a radix-P operation and second radix circuitry for performing a radix-P operation, wherein the first and second radix circuitries are arranged to operate in parallel.

7. A method for performing a Fast Fourier Transform (FFT) of an operand vector of length N, comprising:
providing an input operand from an input operand Random Access Memory (RAM) via input buffer and reorder circuitry to transformation circuitry, the input operand RAM and the input buffer connected to control circuitry;
responsive to a command, carrying out, in the transformation circuitry, a sequence of transformation rounds, each transformation round resulting in a linear transformation of the operand vector, the transformation rounds including two or more FFT rounds and further including or not including a window round;
providing configuration data and respective flag, indicating for each of said transformation rounds whether the respective transformation round is a FFT round, a window-FFT round, or said window round;
wherein each of said transformation rounds comprises:
reading transformation data from coefficient circuitry, the transformation data depending on whether the respective transformation round is a FFT round, a window-FFT round or said window round as indicated by the configuration data, and
carrying out the respective linear transformation on the basis of the transformation data; and
providing an output of the respective linear transformation from the transformation circuitry via an output buffer to an output operand RAM, the output buffer and the output operand RAM connected to the control circuitry.

8. The method of claim 7 , wherein the coefficient circuitry comprises or is integrated in Random Access Memory (RAM) circuitry.

9. The method of claim 7 , wherein the transformation data for an FFT round comprises a set of twiddle coefficients, the transformation data for a window-FFT round comprises a set of modified twiddle coefficients, and the transformation data for a window round comprises a set of window coefficients.

10. The method of claim 7 , wherein the coefficient circuitry comprises quadrature extension circuitry for providing a complete set of twiddle coefficients on the basis of a reduced set of twiddle coefficients by exploiting symmetry properties of the twiddle coefficients.

11. The method of claim 10 , wherein the quadrature extension circuitry is arranged to be bypassed in any round that is a window round or a window-FFT round.

12. The method of claim 7 , wherein the transformation circuitry comprises first radix circuitry for performing a radix-P operation and second radix circuitry for performing a radix-P operation, wherein the first and second radix circuitries are arranged to operate in parallel.

Assignees

• Brett Maik
• Gill Navdeep Singh
• Tomar Rohit
• Nxp Usa Inc

Inventors

• Brett Maik
• Gill Navdeep Singh
• Tomar Rohit

Classifications

• G06F17/142 Primary

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