Minimum resource fast fourier transform

摘要

A minimum resource FFT design may calculate the FFT for an input data series using minimal logic resources to implement the FFT. In one implementation, the FFT design may include a butterfly component for performing one or more complex addition and multiplication operations and outputting a plurality of results; a first memory coupled to the butterfly component, the first memory including a number of memory banks equal in number to the number of the plurality of the results; a second memory coupled to the butterfly component, the second memory including a number of memory banks equal in number to a number of the plurality of the results; and a control component to control reading and writing from the first and second memories and the butterfly component using a ping-pong access technique that reads and writes intermediate values to the first and second memories to implement the FFT.

主权项

1. A method comprising:
during a stage of a Fast Fourier Transform (FFT) operation:
determining data that includes:
a value of a counter during the stage of the FFT operation,a stage value associated with the stage of the FFT operation, anda quantity of input values of a plurality of inputs values,
the data being determined by a device;performing, based on the stage value and the quantity of input values, one or more shift operations and one or more addition operations on the value of the counter, during the stage of the FFT operation, to determine an address,
the one or more shift operations and the one or more addition operations being performed by the device;determining, based on the stage value, to read the plurality of input values from a first plurality of memory banks and to write a plurality of output values to a second plurality of memory banks,
the second plurality of memory banks being different from the first plurality of memory banks, anddetermining to read the plurality of input values from the first plurality of memory banks and to write the plurality of output values to the second plurality of memory banks being performed by the device;reading, based on the address, the plurality of input values from a first plurality of memory banks,
the plurality of input values being read by the device;performing, using the plurality of input values, a calculation of the FFT operation to determine the plurality of output values,
the calculation being performed by the device; andwriting, based on the address, the plurality of output values to the second plurality of memory banks,
the plurality of output values being written by the device, andthe quantity of input values being the same as a quantity of output values of the plurality of output values.