A Unified Treatment of Discrete Fast Unitary Transforms

A set of recursive rules which generate unitary transforms with a fast algorithm (FUT) are presented. For each rule, simple relations give the number of elementary operations required by the fast algorithm. The common Fourier, Walsh-Hadamard (W-H), Haar, and Slant transforms are expressed with these rules. The framework developed allows the introduction of generalized transforms which include all common transforms in a large class of “identical computation transforms”. A systematic and unified view is provided for unitary transforms which have appeared in the literature. This approach leads to a number of new transforms of potential interest. Generalization to complex and multidimensional unitary transforms is considered and some structural relations between transforms are established.