Circuit for computing a fast fourier transform

Abstract

The present invention is generally directed to a processing circuit for computing a fast Fourier transform (FFT). The present invention reflects the recognition that excessive reads to and writes from memory consume excessive amounts of power. Accordingly, the circuit of the present is specifically designed to minimize the number of reads and writes to memory. In addition, the circuit is designed so that processing parallelism may be achieved in order to reduce the total number of clock cycles required to compute a FFT. In accordance with one aspect of the invention, the processing circuit includes a data memory for storing data values, and a separate coefficient memory for storing coefficient (or twiddle) values. The circuit further includes a multiplier configured to multiply values received from the coefficient memory and another value retrieved from some other location. The circuit further includes a first adder configured to add a value output from the multiplier with a value retrieved from another location. The circuit further includes a second adder configured to add a value retrieved from the data memory with a value retrieved from another location. Finally, the circuit includes write-back data path disposed between the second adder and the data memory. The write-back data path is configured to write data output from the second adder to the data memory, to a location where a data value was previously retrieved.

Dependencies are inferred from the claim text.