Patent ID: 7870176

Claim:
A reconfigurable architecture for performing a fast orthogonal transform of vectors in multiple stages, the size of a vector being defined by N-points, wherein N can vary and the number of stages is a function of N, the architecture comprising: a computational unit configured and arranged so as to include only one or more butterfly units; a block including one or more multipliers coupled to the output of the computational unit, and an adder; configured and arranged so as to perform all of the butterfly computations for at least one stage of the transform; a storage unit configured and arranged so as to store the intermediate results of the butterfly computations and predetermined coefficients for use by the computational unit for performing each butterfly computation, the storage unit including memory and multiplexing architecture; a multiplexer unit configured and arranged so as to time multiplex all of the butterfly computations of the transform using said computation unit for the one stage so that only one computation unit is required for the stage; and a controller configured and arranged so as to provide coefficients to the computational unit, configure the architecture for processing data in time and space depending on the format of the data, and control the sizes of memory and multiplexing architecture in the, wherein the sizes of the memory are a function of the stage of the transform; wherein the multipliers' coefficients, the coefficients of the computational unit, the sizes of memories, and multiplexing architecture, for each stage are modified as a function of the value of N; and the architecture is reconfigurable so as to perform the fast orthogonal transform in accordance with any one of a plurality of transform formats including fast Fourier transforms (FFTs) of different radixes and fast Walsh orthogonal transforms, including, inverse FFT transforms (IFFT), any sub-products including Discrete Cosine/Sine Transforms including DCT and DST, Walsh-Hadamard transforms, and any sub-product including CDMA DSSS Spreading/De-spreading, and any algorithm including a combination of two or more of the foregoing transforms, and other functionality including filtering by using concatenation of FFT and IFFT transforms, Hilbert transforms, predictions, interpolations and correlations.