PROCESSOR ARCHITECTURES FOR FAST COMPUTATION OF MULTI-DIMENSIONAL UNITARY TRANSFORMS.

This work presents the development of new algorithms and special purpose sequential processor architectures for the computation of a class of one-, two- and multi-dimensional unitary transforms. In particular, a technique is presented to factorize the transformation matrices of a class of multi-dimensional unitary transforms, having separable kernels, into products of sparse matrices. These sparse matrices consist of Kronecker products of factors of the one-dimensional transformation matrix. Such factorizations result in fast algorithms for the computation of a variety of multi-dimensional unitary transforms including Fourier, Walsh-Hadamard and generalized Walsh transforms. It is shown that the u-dimensional Fourier and generalized Walsh transforms can be implemented with a u-dimensional radix-r butterfly operation requiring considerably fewer complex multiplications than the conventional implementation using a one-dimensional radix-r butterfly operation. Residue number principles and techniques are applied to develop novel special purpose sequential processor architectures for the computation of one-dimensional discrete Fourier and Walsh-Hadamard transforms and convolutions in real-time. The residue number system (RNS) based implementations yield a significant improvement in processing speed over the conventional realizations using the binary number system. As an illustration of the factorization techniques developed in this work, novel sequential architectures of RNS-based fast Fourier, Walsh-Hadamard and generalized Walsh transform processors for real-time processing of two-dimensional signals are presented. These sequential processor architectures are capable of processing large bandwidth (\u3e 5 M.Hz) input sequences. The application of the proposed FFT processors for the real-time computation of two-dimensional convolutions is also investigated. A special memory structure to support two-dimensional convolution operations is presented and it is shown that the two-dimensional FFT processor architecture proposed in this work requires less hardware than the conventional implementations. The FFT algorithms and processor architectures are verified by computer simulation.Dept. of Electrical and Computer Engineering. Paper copy at Leddy Library: Theses & Major Papers - Basement, West Bldg. / Call Number: Thesis1981 .N246. Source: Dissertation Abstracts International, Volume: 42-08, Section: B, page: 3366. Thesis (Ph.D.)--University of Windsor (Canada), 1981