PIPELINED FFT WITH LOCALIZED TWIDDLE

1 . A radar system, comprising:

an analog to digital converter (ADC);

a digital processing unit coupled to the ADC, the digital processing unit comprising:

a plurality of Fast Fourier Transform (FFT) elements; and

a plurality of memory storage devices coupled to the plurality of FFT elements,

wherein the plurality of FFT elements and the plurality of memory storage devices are configured in a pipeline; and

a twiddle factor table comprising a plurality of twiddle factors, wherein each twiddle factor of the plurality of twiddle factors corresponds to an FFT element in the plurality of FFT elements.

2 . The radar system of claim 1 , further comprising:

a control unit coupled to the digital processing unit and configured to control each of the plurality of FFT elements a predetermined number of times.

3 . The radar system of claim 1 , further comprising:

an address remapping unit configured to digit reverse input indices.

4 . The radar system of claim 1 , wherein at least a portion of the plurality of FFT elements are base 4 elements.

5 . The radar system of claim 1 , wherein the pipeline comprises four stages, each stage comprising four FFT elements, wherein each FFT element is cycled four times to generate an output.

6 . The radar system of claim 1 , wherein at least one twiddle factor of the twiddle factor table is a multiplier in FFT processing.

7 . The radar system of claim 1 , wherein the plurality of FFT elements process data iteratively.

8 . The radar system of claim 1 , wherein the plurality of memory storage devices includes a set of registers.

9 . The radar system of claim 1 , wherein an input to the pipeline is provided in increments.

10 . The radar system of claim 9 , wherein a final stage of the pipeline accesses multiple increments.

11 . A digital processing system, comprising:

a plurality of stages of processing elements configured in a sequence, wherein a number of stages is a function of a number of inputs and the plurality of stages form a processing pipeline;

a plurality of memory storage devices coupled to each stage of the plurality of stages, the memory storage devices adapted to store interim results;

a final stage of processing elements configured to combine outputs from the sequence of stages; and

a controller adapted to iteratively process data through the processing elements.

12 . The digital processing system of claim 11 , further comprising:

a lookup table coupled to the controller, the lookup table storing a plurality of operational coefficients comprising twiddle factors.

13 . The digital processing system of claim 12 , wherein the lookup table stores the twiddle factors corresponding to each stage of the plurality of stages.

14 . The digital processing system of claim 13 , further comprising:

an address remapping module coupled to the plurality of stages.

15 . The digital processing system of claim 14 , wherein each stage of the plurality of stages includes radix-4 FFT elements.

16 . A digital processing method, comprising:

determining a number of stages for digital processing as a function of a number of inputs in an input sample;

determining a number of cycles for each stage of the stages;

receiving the number of inputs;

processing the input samples in each successive stage according to the number of cycles for each stage, wherein the number of cycles is a function of a sample size; and

generating results from the processing.

17 . The method of claim 16 , wherein the digital processing method is a Fast Fourier Transform (FFT) processing.

18 . The method of claim 17 , further comprising:

prior to determining the number of cycles for each stage, calculating an operational coefficient for each of the stages, wherein the operational coefficient comprises a twiddle factor.

19 . The method of claim 18 , wherein the twiddle factor is a trigonometric constant.

20 . The method of claim 16 , further comprising:

remapping addresses of input data.