First Advisor

Marek Perkowski

Term of Graduation

Fall 1995

Date of Publication

11-8-1995

Document Type

Thesis

Degree Name

Master of Science (M.S.) in Electrical and Computer Engineering

Department

Electrical Engineering

Language

English

Subjects

Fourier transformations -- Computer programs, Signal processing -- Digital techniques -- Software, Array processors -- Design and construction

DOI

10.15760/etd.6752

Physical Description

1 online resource (2, xi, 178 pages)

Abstract

With the advance of the VLSI technology, the FFT algorithm has been pushed further in solving the multidimensional array signal processing in real time. Many DSP chip users have tried to find ways to improve addressing huge data in multidimension systems with minimum cost and maximum performance. However, there is no efficient method to address data for 1-D to M-D FFTs.

A methodology has been defined to conquer the addressing problem of M-D FFT. It is well known that the twiddle factor matrix of Discrete Fourier Transform (DFT) can be recursively factored into basic butterfly stage matrices. The matrix can be factored into three matrices practically specifying the input data, twiddle factor, and output data sequence of the Fast Fourier Transform (FFT). The equivalent relationship of these matrices will be introduced. The equivalent relationship for a variety of the FFT algorithms can be obtained by equivalent transformations. Furthermore, the multidimensional (M-D) FFT can be represented by the same vector-matrix form as the one-dimensional (1-D) FFT. In addition, the addressing sequences of the 1-D FFT is a subset of the M-D FFT. Therefore, the signal flow graph of the 1-D FFT can be used to describe that of the M-D FFT and all M-D indexing can be implemented by 1-D indexing. Finally, this unified indexing approach was implemented into the WinDSP software simulator. Examples of M-D FFTs implemented with the unified indexing method are simulated on the WinDSP and the computation performance were analyzed. From the benchmark analysis, the 2-D FFT applications implemented with unified methodology use less instructions and the execution time is almost two times faster than the traditional method.

WinDSP is a software simulator that simulates the functional characteristics of Sharp LH9124/LH9320 DSP chip set. It intended to manage the complete development of DSP applications, from conceptualization and experimentation, to verification of unified indexing for 1-D to M-D FFT. It is also intended for system development, where hardware can be implemented for the design.

Rights

In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/ This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).

Comments

If you are the rightful copyright holder of this dissertation or thesis and wish to have it removed from the Open Access Collection, please submit a request to pdxscholar@pdx.edu and include clear identification of the work, preferably with URL.

Persistent Identifier

https://archives.pdx.edu/ds/psu/28415

Download

Share

COinS