Matrix factorization derivation and analysis of computational complexity of a new radix-2 DFT algorithm

Author

Sundararajan, D. ; Ahmad, M.O.

Author_Institution

Dept. of Electr. & Comput. Eng., Concordia Univ., Montreal, Que., Canada

Volume

2

fYear

1996

Firstpage

763

Abstract

Recently, a new family of discrete Fourier transform algorithms has been reported in which the structural complexity is significantly reduced without affecting the arithmetic complexity. In the present paper, a radix-a algorithm of this family is derived using the matrix factorization approach. This approach is known to be useful in mapping algorithms to architectures. An analysis of the computational complexity of this algorithm is carried out. A run-time comparison of the proposed algorithm is made with the Cooley-Tukey radix-2 algorithm

Keywords

computational complexity; discrete Fourier transforms; mathematics computing; matrix algebra; arithmetic complexity; computational complexity; discrete Fourier transform algorithms; matrix factorization; radix-2 DFT algorithm; run-time comparison; structural complexity reduction; Algorithm design and analysis; Computational complexity; Computer architecture; Digital arithmetic; Discrete Fourier transforms; Equations; Matrices; Runtime; Signal processing algorithms; Software performance;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 1996., IEEE 39th Midwest symposium on

Conference_Location

Ames, IA

Print_ISBN

0-7803-3636-4

Type

conf

DOI

10.1109/MWSCAS.1996.588019

Filename

588019