Fft accelerator
AssigneeAnalog Devices, Inc.
InventorsNing Yang, David Miller, Boris Lerner, Guolin Pan, Steven L. Cox, Jiang Wu
Life of this patent
Estimating the term…
Abstract
An FFT operation is performed by dividing n time-domain input points into a plurality of groups of m points, performing a plurality of constant-geometry butterfly operations on each of the groups of m points, and finally performing at least one in-place butterfly operation on the group of n points.
Claims20
A method for computationally performing a Fast Fourier Transform (“FFT”) on n points, the method comprising:
- dividing the n points into a plurality of groups of m points, where m<n;
- performing a plurality of constant-geometry FFTs on each of the groups of m points, each constant-geometry FFT comprising:
- i. reading the m points from a computer memory into an input buffer;
- ii. computationally applying a butterfly operation to each of the m points;
- iii. writing results of the butterfly operation into an output buffer;
- and
- iv. storing transposed contents of the output buffer to the original location of the m points in the computer memory, thereby overwriting the original m points;
- and
- performing at least one in-place FFT on the results of the plurality of constant-geometry FFTs stored in the computer memory, thereby completing the FFT of the n points.
A system for performing a Fast Fourier Transform (“FFT”) on n points, the system comprising:
- an input buffer for receiving a subset of the n points, the subset comprising m points;
- a butterfly unit for performing a butterfly operation on the m points;
- an output buffer for receiving a result of the butterfly operation, the output buffer comprising an output port for transposing data points stored therein;
- and
- control logic for directing the butterfly unit to perform a plurality of constant-geometry butterfly operations followed by at least one in-place butterfly operation.
A method for computationally performing a Fast Fourier Transform (“FFT”) on n points, the method comprising:
- performing at least one stage of in-place FFTs on all n points;
- dividing the n points of the in-place FFT result into a plurality of groups of m points, where m<n;
- and
- performing a constant-geometry FFT on each of the groups of m points, the constant-geometry FFT comprising:
- i. reading the m points from a computer memory into an input buffer;
- ii. computationally applying a butterfly operation to the transposed contents of the input buffer which holds each of the m points;
- iii. writing results of the butterfly operation into an output buffer;
- and
- iv. storing contents of the output buffer to the original location of the m points in the computer memory, thereby overwriting the original m points, thereby completing the FFT of the n points.
Dependencies are inferred from the claim text.