White, Roderick J (1994) Aspects of parallel topologies applied to digital transforms of discrete signals. Research Master thesis, Victoria University of Technology.

Abstract

Discrete transformations are widely used in the fields of signal and image processing. Applications in the areas of data compression, template matching, signal filtering pattern recognition all utilise various discrete transforms. The calculation of transformations is a computationally intensive task which in most practical applications requires considerable computing resources. This characteristic has restricted the use of many transformations to applications with smaller datasets or where real-time performance is not essential. This restriction can be removed by the application of parallel processing techniques to the calculation of discrete transformations. The aim of this thesis is to determine efficient parallel algorithms and processor topologies for the implementation of the discrete Walsh, cosine, Haar and D4 Daubauchies transforms, and to compare the operation of the parallel algorithms running on T800 Transputers with the equivalent serial von Neumann type algorithm. This thesis also examines the transformations of a number of test functions in order to determine their ability to represent various common global and locally defined functions. It was found that the parallel algorithms developed during the course of this thesis for the discrete Walsh, cosine, Haar and D4 Daubauchies transforms could all be efficiently implemented on a hypercube processor topology. Development of a number of parallel algorithms also led to the discovery of a new parallel algorithm for the calculation of any transformation which can be expressed as a Kronecker or tensor product/sum. A hypercube based algorithm was devised which converts the Kronecker product to a Hadamard product on a hypercube structure. This provides a simple algorithm for parallel implementations. Examination of the four sets of transform coefficients for the test functions revealed that all the transforms examined were not suitable for representing functions with large numbers of discontinuity's such as the chirp function. Also, transforms with local basis functions such as the Haar and D4 Daubauchies transforms provided better representations of localised functions than transforms consisting of global basis function sets such as the discrete Walsh and cosine transformations.

Search Google Scholar

Repository staff login