A new FFT algorithm and its implementation on the DSP96002

Author

Rodriguez, Domingo

Author_Institution

Dept. of Electr. & Comput. Eng., Puerto Rico Univ., Mayaguez, Puerto Rico

fYear

1991

fDate

14-17 Apr 1991

Firstpage

2189

Abstract

A novel algorithm for computing the discrete Fourier transform (DFT) is presented. This fast Fourier transform (FFT) algorithm is obtained through decomposition of the Fourier matrix representing the DFT operator into a product of sparse matrices which are not all square matrices. The algorithm is based on additive properties of the input and output indexing sets of the Fourier transformation. Mathematical formulations of the algorithm are presented using tensor product algebra. Properties of this algebra are used to assist in the adaptation of the algorithm to the DSP96002 microprocessor architecture. This results in efficient implementations which take into account the inherent software and hardware features of the microprocessor

Keywords

digital arithmetic; digital signal processing chips; fast Fourier transforms; matrix algebra; tensors; DFT; DSP chips; DSP96002 microprocessor architecture; FFT algorithm; Fourier matrix; Fourier transformation; discrete Fourier transform; fast Fourier transform; software; tensor product algebra; Additives; Algebra; Computer architecture; Discrete Fourier transforms; Fast Fourier transforms; Indexing; Matrix decomposition; Microprocessors; Sparse matrices; Tensile stress;

fLanguage

English

Publisher

ieee

Conference_Titel

Acoustics, Speech, and Signal Processing, 1991. ICASSP-91., 1991 International Conference on

Conference_Location

Toronto, Ont.

ISSN

1520-6149

Print_ISBN

0-7803-0003-3

Type

conf

DOI

10.1109/ICASSP.1991.150848

Filename

150848