Year

1990

Degree Name

Doctor of Philosophy

Department

Department of Electrical and Computer Engineering

Abstract

A structural approach to the construction of multidimensional vector radix fast Discrete Fourier Transforms (DFTs) and fast direct Discrete Cosine Transforms (DCTs) is presented in this thesis. The approach features the use of matrix representation (1-D) and two-dimensional (2-D) FFT and fast DCT algorithms along with the tensor product, and the use of logic diagram and rules for modifications.

In the first part of the thesis, the structural approach is applied to construct 2-D Decimation-In-Time (DIT), Decimation-In-Frequency (DIF) and mixed (DIT & DIF) vector radix FFT algorithms from corresponding 1-D FFT algorithms by the Cooley- Tukey method. The results are summarized in theorems as well as examples using logic diagrams. It has been shown that the logic diagram (or signal flow graph) as well as being a form of representation and interpretation of fast algorithm equations, is a engineering tool for the construction of fast algorithms. The concept of "vector signal processing" is adapted into the logic diagram representation which reveals the structural features of multidimensional vector radix FFTs and explains the relationships and differences between the row-column FFT, the vector radix FFT reported previously and the approach presented in this thesis. The introduction of the structural approach makes the formulation of a multidimensional vector radix FFT algorithm of high radix dimension easy to evaluate and implement by both software and hardware.

The hardware implementation of 2-D DFTs is discussed in the light of vector radix FFTs using the Frequency Domain Processor (FDP™) A41102, which has shown improvement in reducing the system complexity over the traditional row-column method.

With the help of the structural approach, the vector split-radix DIF FFT algorithm, mixed (DIT & DIF) vector radix FFT and Combined Factor (CF) vector radix FFT algorithms are presented whereby a comparison study is made in terms of arithmetic complexity. The approach is then generalized to vector radix FFTs of higher dimensions.

Two vector radix DCT algorithms are presented in the second part of the thesis. Although the one based on Lee's approach was reported by Haque using a direct matrix derivation method, it is derived independently by the author using the structural approach. The other vector radix DCT algorithm is based on Hou's method. The arithmetic complexities of these two algorithms are considered as well as various other known row-column DCT algorithms. The computation structures of 2-D vector radix direct fast DCT algorithms are discussed in comparison with those of 2-D vector radix FFT algorithms. A correction to the system description of Hou's DIT fast DCT algorithm is presented as an analysis result of the algorithm's computation structure.

The system design of the 2-D modified Makhoul algorithm using the FDP A41102 provides yet another solution to the real-time 2-D DCT image coding problem. The effects of finite-word-length computation of DCT using various direct fast algorithms studied by computer simulation for the purpose of transform coding of images. The results are also presented in the thesis.

Download

Share

COinS
 

Unless otherwise indicated, the views expressed in this thesis are those of the author and do not necessarily represent the views of the University of Wollongong.