Method of and apparatus for implementing fast orthogonal transforms of variable size

An integrated chip comprising 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, 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;
• 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 configure the architecture for processing data in time and space depending on the format of the data, provide coefficients to the computational unit, and control the sizes of memory and multiplexing architecture in the storage unit, 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 of different radixes and fast Walsh orthogonal transforms, 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.

A method of performing any one of a plurality of fast orthogonal transforms of vectors in multiple stages in accordance with any one of plurality of transform formats including fast Fourier transforms of different radixes and fast Walsh orthogonal transforms, including FFTs, 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, 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 method comprising:

• choosing a fast transform format and carrying out the following steps in accordance with that format;
• configuring and arranging a computational unit in order to process data in time and space depending on the format of the data so as to include only one or more butterfly units as a function of the format;
• a block so as to include one or more multipliers coupled to the output of the computational unit, configuring and arranging the one or more butterfly units and one or more multipliers so as to perform all of the butterfly computations for at least one stage of the transform;
• storing the intermediate results of the butterfly computations and predetermined coefficients in a storage unit for use by the computational unit for performing each butterfly computation, the storage unit including memory and multiplexing architecture;
• time multiplexing all of the butterfly computations of the transform using the computation unit for the one stage so that only one computation unit is required for the stage;
• and
• providing coefficients to the computational unit, and controlling the sizes of memory and multiplexing architecture in the, wherein the sizes of the memories 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.

A method of performing a fast orthogonal transform of vectors in multiple stages in accordance with any one of a plurality of fast transform formats, including fast Fourier transforms of different radixes and fast Walsh orthogonal transforms, including FFTs, 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, 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 method comprising:

• choosing a fast transform format and carrying out the following steps in accordance with that format;
• utilizing a reconfigurable group of butterfly units and a reconfigurable set of multipliers configured and arranged so as to process data in time and space as a function of the format of the data so that at least one computational unit can be configured and arranged to include at least only one butterfly unit and a multiplier coupled to the output of the butterfly unit so that the computational unit can perform all of the butterfly computations for at least one stage of the transform, and reconfigurable memory coupled to the computational unit so as to store the intermediate results of the butterfly computations and predetermined coefficients for use in performing each butterfly computation;
• wherein coefficients and sizes of memories, for each stage are modified as a function of the value of N, and the sizes of the memories are a function of the stage of the transform.

A system of performing a fast orthogonal transform of vectors in multiple stages in accordance with any one of a plurality of fast transform formats, including fast Fourier transforms of different radixes and fast Walsh orthogonal transforms, including FFTs, 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, 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 method comprising:

• choosing a fast transform format and carrying out the following steps in accordance with that format;
• a reconfigurable group of butterfly units and a reconfigurable set of multipliers configured and arranged so as to process data in time and space as a function of the format of the data so that at least one computational unit can be configured and arranged to include at least only one butterfly unit and a multiplier coupled to the output of the butterfly unit so that the computational unit can perform all of the butterfly computations for at least one stage of the transform, and reconfigurable memory coupled to the computational unit so as to store the intermediate results of the butterfly computations and predetermined coefficients for use in performing each butterfly computation;
• wherein coefficients and sizes of memories, for each stage are modified as a function of the value of N, and the sizes of the memories are a function of the stage of the transform.