The USC Andrew and Erna Viterbi School of Engineering USC Signal and Image Processing Institute USC Ming Hsieh Department of Electrical Engineering University of Southern California

Technical Report USC-SIPI-135

“Kronecker and Array Algebra for Parallel Image Processing”

by Daniel G. Antzoulatos

December 1988

This dissertation presents a mathematical framework for implementing highly concurrent tasks on three-dimensional multilayered massively parallel synchronous computing structures. The framework is an extension and unification of ideas and concepts found in signal processing, parallel processing and large scale computing. It takes advantage of the duality between Kronecker and array algebras. The former is matrix algebra augmented with Kronecker products and shuffle permutations. Array algebra--a derivative of sensor analysis--is extended for more flexibility. Useful identities and theorems for both algebras are presented/derived. Multilayered architectures are given new classifications. Closely examined are those architectures that consist of cascaded pairs of a global interplane communication structure and a regular array of processing elements--isoplanar homosyndetic architectures. Of particular interest are global interconnections of the shuffle permutation class. The primary example of such an architecture is an envisioned 2-D Omega processor--a 2-D processing extension of the Omega network.

Canonical forms of 2-D shuffle/processing stages are derived. The computational tasks addressed are those which can be cast in the context of matrix algebra. Mappings of linear transformations are demonstrated including 2-D Hadamard transformations, matrix rotations and transposition. Potential optical implementation technologies are discussed and the applicability of Kronecker algebra in the implementation of shuffles using strategically located thin lenses is demonstrated.

To download the report in PDF format click here: USC-SIPI-135.pdf (5.1Mb)