Apparatus and method for preventing I/O bandwidth limitations in fast fourier transform processors
AssigneesSharp Microelectronics Technology, Inc., Sharp Kabushiki Kaisha
InventorsRohit Bhatia, Masaru Furuta
Life of this patent
Estimating the term…
Abstract
A Quasi Radix-16 Butterfly comprises an radix-4 butterfly processor and on-board memory with external memory addressing changes from a conventional radix-4 butterfly processor. On-chip cache memory is included to store data outputs of the radix-4 butterfly processor for application as data inputs to the radix-4 butterfly processor in a second series of butterfly operations to implement high-speed processing that is maximally execution-bound.
Claims12
In a digital signal processor in which the I/O data bandwidth, memory capacity and execution unit throughput are each limited and mutually dependent, and the input/output ("I/O") data bandwidth and the execution unit throughput are comparable, a processor for performing fast Fourier transforms comprising:
- an input memory having inputs and outputs for storing data;
- an output memory having inputs and outputs for storing data;
- an internal cache memory having inputs and outputs for storing data;
- a coefficient memory having inputs and outputs for storing data;
- and
- an execution unit having inputs and outputs for performing logical and arithmetic operations on real and imaginary numbers, the outputs of said execution unit coupled to the inputs of the output memory and the internal cache memory, the inputs of said execution unit coupled to the outputs of the input memory, the outputs of the coefficient memory and the outputs of the internal cache memory;
- wherein the internal cache memory is of a size sufficient to hold the output of the execution unit and which corresponds to the bus widths of the input memory and the output memory, such that the execution unit is continuously active and not limited by the bus widths of the input memory or the output memory.
In a digital signal processor in which the input/output "(I/O") data bandwidth, memory capacity and execution unit throughput are each limited and mutually dependent, and the I/O bandwidth and execution unit throughput are comparable, a method for performing a sequence of fast Fourier transforms, or FFT's, in a processor having an execution unit, an input memory, an output memory, a coefficient memory and an internal cache memory which is of a size sufficient to hold the output of the execution unit and which corresponds to the bus widths of the input memory and the output memory, said method comprising the steps of:
- storing data in the input memory and the coefficient memory for a first FFT and a second FFT;
- reading data from the output memory and the coefficient memory for the first FFT;
- performing a first set of calculations for the first FFT on the data from the input memory and the coefficient memory with the execution unit;
- storing the result of the first set of calculations for the first FFT in the internal cache memory;
- reading data from the input memory and the coefficient memory for the second FFT;
- performing a first set of calculations for the second FFT on the data from the input memory and the coefficient memory with the execution unit;
- storing the result of the first set of calculations for the second FFT in the internal cache memory while simultaneously reading the result of the first set of calculations for the first FFT from the internal cache memory;
- performing a second set of calculations for the first FFT on the data from the internal cache memory, the input memory and the coefficient memory with the execution unit;
- storing the result of the second set of calculations for the first FFT in the output memory while simultaneously reading the result of the first set of calculations for the second FFT from the internal cache memory;
- performing a second set of calculations for the second FFT on the data from the internal cache memory, the input memory and the coefficient memory with the execution unit;
- and
- storing the result of the second set of calculations for the second FFT in the output memory,
- wherein the correspondence of the bus widths of the internal cache memory, the input memory and the output memory is such that the execution unit is continuously active and not limited by the bus widths of the input memory of the output memory.
Dependencies are inferred from the claim text.