Multipoint pipeline processor for computing the discrete fourier transform

DETAILED DESCRIPTION In accordance with the broad principles of the present invention, a pipeline processor for performing a discrete Fourier transformation (DFT) on an input array of N signal values to derive an output array of at most N signal values representative of the frequency transformation of the input array comprises an input processing section, an intermediate processing section and an output processing section.
The input processing section includes a first plurality of cascadedly coupled computational elements operative to perform only additions and subtractions substantially in butterfly-type arrangements, and is governed to operate on the input array of N signal values with the computational elements in a pipeline computational fashion and to propagate the resulting interelement computed signal values therethrough in a first predetermined signal flow pattern to render a first intermediate array of signal values.
The intermediate processing section multiplies each signal value of the first intermediate array with at least one respectively corresponding predetermined transformation value to generate a second intermediate array of signal values.
The output processing section includes a second plurality of cascadedly coupled computational elements operative to perform only additions and subtraction substantially in butterfly-type arrangements, and is governed to operate on said second intermediate array of signal values with the computational elements in a pipeline computational fashion and to propagate the resulting interelement computed signal values therethrough in a second predetermined signal flow pattern to render the output array of at most N signal values.
More specifically, the pipeline processor comprises a radix-2 configuration having top and bottom propagation rails.
The signal values of the input array are, preferably, input sequentially at the top and bottom rails of the input processing section in a predetermined first order of coupled pairs.
Similarly, the first intermediate array is preferably rendered sequentially from the top and bottom rails of the input processing section in a second predetermined order of coupled pairs