Back to results
US 6,477,554 B1Granted
Circuit and method for computing a fast fourier transform
AssigneeGlobespanVirata, Inc.
InventorsYair Aizenberg, Daniel Amrany, Yue-Peng Zheng
Life of this patent
Estimating the term…
Abstract
A process circuit is disclosed for computing a fast Fourier transform (FFT). In one embodiment, the processing circuit includes a memory device, a multiplier, a detector, a state machine, and a circuit for performing the 2's compliment of a coefficient. The memory storage device stores data values and coefficient (or twiddle) values. The detector integrates a date pointer with the state machine. The detector is designed to identify the symmetry lines (by memory address). The state machine, when notified by the detector that a line of symmetry has been encountered, appropriately adjusts either the coefficients, the imaginary sign, or the real sign for input to a multiplier.
Claims23
A circuit for calculating a Fast Fourier Transform (FFT) of a plurality of data values comprising:
- a memory device for storing data values and coefficient values;
- a first circuit configured to multiply data values and coefficient values retrieved from the memory device to provide a first result;
- a second circuit configured to receive and add another value to said first result to provide a second result, wherein the second result is stored in the memory device;
- a detector having an input from the memory device for monitoring the processing of data values;
- a state machine in communication with the detector, wherein the input from the detector is used to increment the state machine and wherein the state machine is configured to control the processing of coefficient values through the first circuit;
- and
- means for performing the 2's complement of the coefficient values in communication with the state machine.
4 more elements
A circuit for calculating a Fast Fourier Transform (FFT) of a plurality of data values comprising:
- a memory device for storing data values and coefficient values;
- a multiplier disposed to receive data values and coefficient values from the memory device, the multiplier being configured to multiply values retrieved from the memory device and provide the result at a multiplier output;
- an adder disposed to receive data from the multiplier output, the adder being configured to add the value retrieved from the multiplier output and another value;
- an arithmetic logic unit (ALU) disposed to receive data values from the memory device, the ALU being configured to add a value retrieved from the memory device with another value;
- a write-back data path disposed between the ALU and the memory device configured to write data output from the ALU to the memory device;
- a first multiplexer having a plurality of inputs and an output that is in communication with the adder, wherein the one of the first multiplexer inputs is disposed in communication with an output of the adder;
- a second multiplexer having a plurality of inputs and an output that is in communication with the adder, wherein the one of the second multiplexer inputs is disposed in communication with an output of the ALU;
- a third multiplexer having a plurality of inputs and an output that is in communication with the multiplier, wherein the inputs of the third multiplexer are disposed in communication with the memory device for processing coefficient values;
- a detector having an input from the memory device for monitoring the processing of data values;
- a state machine disposed between the detector and the third multiplexer, wherein the input from the detector is used to increment the state machine and wherein the state machine is configured to control the processing of coefficient values through the third multiplexer;
- and
- means for performing the 2's complement of the coefficient values output by the third multiplexer configured to be controlled by the state machine for input to the multiplier.
9 more elements
A circuit for calculating a fast Fourier transform (FFT) of a plurality of data values comprising:
- a data memory for storing data values;
- a coefficient memory for storing coefficient values;
- a multiplier disposed to receive data values and coefficient values from the data memory and the coefficient memory, the multiplier being configured to multiply values retrieved from the data memory and the coefficient memory and provide the result at a multiplier output;
- an adder disposed to receive data from the multiplier output, the adder being configured to add the value retrieved from the multiplier output and another value;
- an arithmetic logic unit (ALU) disposed to receive data from the data memory, the ALU being configured to add a value retrieved from the data memory with another value;
- a write-back data path disposed between the ALU and the data memory configured to write data output from the ALU to the data memory;
- a first multiplexer having a plurality of inputs and an output that is in communication with the adder, wherein the one of the first multiplexer inputs is disposed in communication with an output of the adder;
- a second multiplexer having a plurality of inputs and an output that is in communication with the adder, wherein the one of the second multiplexer inputs is disposed in communication with the coefficient memory for processing coefficient values;
- a detector having an input from the data memory for monitoring the processing of data values;
- a state machine disposed between the detector and the third multiplexer, wherein the input from the detector is used to increment the state machine and wherein the state machine is configured to control the processing of coefficient values through the third multiplexer;
- and
- means for performing the 2's complement of the coefficient values output by the third multiplexer configured to be controlled by the state machine for input to the multiplier.
9 more elements
Dependencies are inferred from the claim text.