Fast Fourier transform algorithms for special N's and the implementations on VAX.
Item
-
Title
-
Fast Fourier transform algorithms for special N's and the implementations on VAX.
-
Identifier
-
AAI8820878
-
identifier
-
8820878
-
Creator
-
Lu, Chao.
-
Contributor
-
Adviser: Richard Tolimieri
-
Date
-
1988
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Engineering, Electronics and Electrical
-
Abstract
-
A new class of FFT algorithms based upon multiplicative structure of indexing set have been designed for transform sizes 4p, 4pq, {dollar}p\sp2, p\sp{lcub}2{rcub}q,{dollar} where p and q are odd primes. These algorithms combine the arithmetic efficiency of the Winograd's multiplicative algorithms with simplicity of programming of the Cooley-Tukey algorithms, and offer significant advantage over the Winograd's algorithms in practical applications. Programs have been written for transform sizes N less than 128 on the Micro VAX II whose run-time is about 40% to 60% better and in some cases are even better than the radix-2 or radix-4 optimized Cooley-Tukey programs (DEC.LABSTAR DSP Package) of the next applicable size.;The fundamental algorithm is derived in the form of a factorization CA, where C is a block-diagonal matrix having skew-circulant blocks and tensor products of skew-circulant blocks, which can be computed by corresponding smaller FFT subroutines, and A is a pre-addition matrix.;For each case, a family of variants of the fundamental algorithm are also designed which present options as to whether additions or multiplications dominate arithmetic cost and which are further distinguished by data flow. These algorithmic parameters play an important role in deciding which algorithm is best suited for given computer architecture.;A very efficient Small DFT Library is given in section 11 for the purpose of small FFT subroutine calls. Many algorithms have been tried in VAX assembly code for each size N, the fastest one has been collected into the Library.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
