Algorithms and methods for multidimensional digital signal processing.
Item
-
Title
-
Algorithms and methods for multidimensional digital signal processing.
-
Identifier
-
AAI9130365
-
identifier
-
9130365
-
Creator
-
Rofheart, Martin.
-
Contributor
-
Adviser: Richard Tolimieri
-
Date
-
1991
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Engineering, Electronics and Electrical
-
Abstract
-
One of the major issues of parallel processing is the design of algorithms that minimize interprocessor communications. This research addresses this issue with respect to the parallel computation of the multidimensional discrete Fourier transform.;A tensor product formulation for multidimensional Cooley-Tukey type fast Fourier transform algorithms is developed. The formulation depends on the expression of data flow by the coset decomposition of the underlying index set. This representation allows fast algorithms to be designed by algebraic manipulations of the tensor product formulation.;A new reduced transform algorithm for the computation of the multidimensional discrete Fourier transform is developed. The algorithm computes a d-dimensional discrete Fourier transform by a set of independent k-dimensional discrete Fourier transforms ({dollar}k < d{dollar}); it is a reduction algorithm in the sense that it has lowered the dimension of the Fourier transforms that are computed. The k-dimensional discrete Fourier transforms are performed on data derived from the input using only additions, and produce k-dimensional hyperplanes of the output array.;The major contribution of this research is an intrinsically parallel algorithm for the computation of the d-dimensional DFT. The main features of the algorithm are that it requires no interprocessor communications, and that it maps to the degree of parallelism of the target multiprocessor flexibly.;The mapping of the algorithm onto architectures with broadcast and report capabilities is given. Expressions are obtained for estimating the speed on these machines as a function of the size of the d-dimensional DFT, the bandwidth C of the communications channel, the time A for an addition, the time T(FFT) for a single processing element to perform a k-dimensional DFT ({dollar}k < d{dollar}), and the degree of parallelism of the machine. For single I/O channel machines that are capable of exploiting the full degree of parallelism of the algorithm, execution times as low as the time required to compute a single k-dimensional DFT plus the I/O time for data upload and download are attainable.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
