System and Method for Computing Oscillating Functions
First Claim
1. A circuit for calculating a quadrature output having X and Y values from a quadrature input having X and Y values which define a point on a sinusoidal waveform, comprising:
- a first scaling element configured to receive the input Y value and scale the input Y value by a scaling factor;
a first adder configured to receive and add the input X value and the scaled Y value thereby producing the output X value;
a second scaling element configured to receive the output X value and scale the output X value by the scaling factor; and
a second adder configured to receive and add the input Y value and the scaled output X value thereby producing the output Y value;
wherein the output X value and output Y value define a next point on the sinusoidal waveform.
1 Assignment
0 Petitions
Accused Products
Abstract
An improved system and method for quickly calculating Fourier transforms without multiplication is disclosed. A combinatorial unit circuit that contains only adders and scaling elements is used to calculate each sine wave value that is summed to create the Fourier transform. A real-time Fourier transform (RTFT) can be implemented using only a number of such combinatorial units, making it possible to complete a hardware DFT transform in a single clock cycle regardless of the number of samples of the input signal, thus bringing a significant improvement in speed and simplicity over the prior art. By using a chain of such combinatorial units and a sufficiently fast adder/multiplexor, a RTFT may be performed on an input signal in each frequency band and the outputs added to generate a transformed output signal in real-time for transmission of a signal. The input signal is recovered from the transmitted signal by the same process.
0 Citations
19 Claims
-
1. A circuit for calculating a quadrature output having X and Y values from a quadrature input having X and Y values which define a point on a sinusoidal waveform, comprising:
-
a first scaling element configured to receive the input Y value and scale the input Y value by a scaling factor; a first adder configured to receive and add the input X value and the scaled Y value thereby producing the output X value; a second scaling element configured to receive the output X value and scale the output X value by the scaling factor; and a second adder configured to receive and add the input Y value and the scaled output X value thereby producing the output Y value; wherein the output X value and output Y value define a next point on the sinusoidal waveform. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A circuit for performing a Fourier transform on samples of a signal, comprising:
-
a chain of N combinatorial units, where N is a number of samples of a sine wave to be included in the Fourier transform, each combinatorial unit comprising; a first scaling element configured to receive an input Y value and scaling the Y value by a scaling factor; a first adder configured to receive and add an input X value and the scaled Y value thereby producing an output X value; a second scaling element configured to receive the output X value and scale the X value by the scaling factor; and a second adder configured to receive and add the input Y value and the scaled output X value thereby producing an output Y value; a first combinatorial unit in the chain receiving an input signal, and each subsequent combinatorial unit receiving as its input the output X and Y values of an immediately preceding combinatorial unit in the chain; a stateful adder configured to add selected combinations of outputs from the combinatorial units thereby determining a current transform element and add the current transform element to a prior transform sum to determine a current transform sum; and an output element configured to store the current transform sum and output the current transform sum after the series of quadrature inputs is complete. - View Dependent Claims (8, 9, 10, 11, 12, 13)
-
-
14. A method for performing a Fourier transform on a signal, comprising:
-
receiving by a circuit a series of quadrature inputs representing an input signal, each quadrature input having X and Y values; for each quadrature input, creating by the circuit a plurality of samples of a sine wave to be included in the Fourier transform by repeatedly; scaling by the circuit an input Y value by a scaling factor; adding by the circuit an input X value and the scaled Y value thereby producing an output X value; scaling by the circuit the output X value by the scaling factor; and adding by the circuit the input Y value and the scaled output X value thereby producing an output Y value; for each quadrature input, adding by the circuit selected combinations of sine wave samples thereby determining a current transform element; and adding by the circuit all of the current transform elements from each quadrature input. - View Dependent Claims (15, 16)
-
-
17. A method for calculating a quadrature output having X and Y values from a quadrature input having X and Y values which define a point on a sinusoidal waveform, comprising:
-
scaling by the circuit the input Y value by a scaling factor; adding by the circuit the input X value and the scaled Y value thereby producing an output X value; scaling by the circuit the output X value by the scaling factor; and adding by the circuit the input Y value and the scaled output X value thereby producing an output Y value; wherein the output X value and output Y value define a next point on the sinusoidal waveform. - View Dependent Claims (18)
-
-
19. A circuit for performing a discrete Fourier transform on four samples of a signal, comprising:
-
first and second arithmetic units each configured to receive a different two of the samples as complex quadrature inputs having X and Y values, and each comprising first and second complex adders, the first complex adder adding the input X and Y values of the two samples, and the second complex adder adding the X and Y value of one sample to the inverse of the X and Y values of the other sample, thereby resulting in two quadrature outputs having X and Y components; first, second, third and fourth combinatorial units, each combinatorial unit comprising; a first scaling element configured to receive an input Y value and scaling the Y value by a scaling factor; a first adder configured to receive and add an input X value and the scaled Y value thereby producing an output X value; a second scaling element configured to receive the output X value and scale the X value by the scaling factor; and a second adder configured to receive and add the input Y value and the scaled output X value thereby producing an output Y value; the first and third combinatorial units configured to receive a first quadrature output of the first arithmetic unit, and the second and fourth combinatorial unit configured to receive a second quadrature of the first FFT unit; first, second, third and fourth adders; the first adder configured to add the first output of the second arithmetic unit to the output of the first combinatorial unit; the second adder configured to add the second output of the second arithmetic unit to the output of the second combinatorial unit; the third adder configured to add the first output of the second arithmetic unit to the output of the third combinatorial unit; and the fourth adder configured to add the Y output of the second arithmetic unit to the output of the fourth combinatorial unit.
-
Specification