Title :
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
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;
Conference_Titel :
Circuits and Systems, 1996., IEEE 39th Midwest symposium on
Conference_Location :
Ames, IA
Print_ISBN :
0-7803-3636-4
DOI :
10.1109/MWSCAS.1996.588019
