New multiplicative 2-dimensional FFT algorithms.
Item
-
Title
-
New multiplicative 2-dimensional FFT algorithms.
-
Identifier
-
AAI9207129
-
identifier
-
9207129
-
Creator
-
Tian, Hongjiang.
-
Contributor
-
Adviser: Richard Tolimieri
-
Date
-
1991
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Engineering, Electronics and Electrical
-
Abstract
-
The purpose of this dissertation is to present the modern technique on the design, analysis and implementation of the discrete Fourier transform and convolution algorithms which is of central importance to the field of digital signal processing and many application fields. This dissertation develops a new family of 2-dimensional Fourier transform algorithms based on the multiplicative property of the indexing set {dollar}{lcub}\cal Z{rcub}/P\times {lcub}\cal Z{rcub}/P{dollar}. The field structure is determined by the irreducible polynomials over {dollar}{lcub}\cal Z{rcub}/P{dollar}. While the degree of the polynomial determines the dimensionality of the Fourier transform, irreducibility determines the prime numbers P. Thus the theory presented here can be used to generate a set of multiplicative multidimensional Fourier transform algorithms which can be implemented using tensor product technique.;The difference in data flow of our algorithm comes from treating {dollar}{lcub}\cal Z{rcub}/P\times{lcub}\cal Z{rcub}/P{dollar} as a simple object. As a result, there is no intermediate data transfer stage. By using the block-diagonalization method, the calculation of the Fourier transform is expressed as a set of small convolutions located diagonally. All blocks are skew-circulant matrices or circulant matrices which are independent of each other. The number and size of blocks are controlled again by the multiplicative group structure. These flexibility and independency are more valuable in the vectorization and parallelization with different machine architectures.;In addition to finding its advantage in the supercomputer architectures, this new multiplicative algorithm with field and ring structures has naturally defined an algebraic structure for both prime and composite numbers on X-ray data of a crystal with crystallographic symmetry groups. By incorporating the crystallographic symmetries to our algorithm, we gain computational advantage by removing all redundant data and arithmetic. The efficiency of our algorithm is apparent since the data is compressed and the computation operation is divided by the degree of symmetry against the original non-symmetry case.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
