Over the past few years, the demand for high speed Digital Signal Processing (DSP) has increased dramatically. New applications in real-time multimedia communications, video processing, satellite broadcasting, and radar signal processing demand major performance improvements at several levels:​ algorithmic, architectural, and implementation. Although a basis of comparison of the various DSP algorithms is the number of multiplications and additions they require, for VLSI implementations other factors such as area of interconnect, I/O bandwidth, complexity of control, power dissipation, design modularity, and layout regularity are also important.

This thesis proposes efficient and cost-effective techniques for mapping highly parallel DSP and video computations onto VLSI architectures. The main focus of this research is on developing new recursive formulations for a class of multidimensional DSP applications that allow the generation of larger parallel computations by combining the results of smaller size computations of the same dimension. This is useful for both hardware and software solutions, in which a very efficient smaller size core has been developed, and a larger computation is required. The proposed design methodology can be used to derive regular and modular architectures for DSP. Regularity and modularity are essential factors for facilitating design automation and implementation of parallel organizations in maturing application-specific integrated circuits (ASICs) and emerging programmable logic environments. The proposed methodology targets multi-dimensional convolution and multi-dimensional transforms.

A key result of this thesis is the proposal of a number of novel algorithms that can implement a large multi-dimensional transform (or convolution) from a single parallel stage of smaller-size multi-dimensional transforms (or convolutions).

Our approach is based on extensive parallelization of several classes of DSP computations and mapping these computations onto parallel hardware. Our methodology employs tensor product (Kronecker product) formulations and permutation matrices as the main tools for expressing DSP algorithms in a parallel form. The effort in modularizing the resulting architectures involves both the computational sections as well as the interconnection sections. Mapping tools then manipulate such formulations into suitable recursive expressions which can be mapped efficiently onto modular parallel architectures.