Aspects of parallel topologies applied to digital transforms of discrete signals

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.

Name dc:type.qualificationname

other

Level dc:type.qualificationlevel

rmaster

Grantor dc:publisher.institution

Victoria University of Technology

Year dc:date.issued

1994

Author dc:creator

• White, Roderick J

• 0102 Applied Mathematics
• 0802 Computation Theory and Mathematics
• School of Engineering and Science

Language dc:language

en