A Novel Approach to Fast Discrete Fourier Transform

In this: publication
By this: publisher
In this Subject: Computer Science
By this author: Liu J.G. ;&nbsp; Li H.F. ;&nbsp; Chan F.H.Y. ;&nbsp; Lam F.K.

Authors: Liu J.G.¹; Li H.F.²; Chan F.H.Y.³; Lam F.K.³

Source: Journal of Parallel and Distributed Computing, Volume 54, Number 1, October 1998 , pp. 48-58(11)

Buy & download fulltext article:

Price: $52.63 plus tax (Refund Policy)

Abstract:

Discrete Fourier transform (DFT) is an important tool in digital signal processing. In the present paper, we propose a novel approach to performing DFT. We transform DFT into a form expressed in discrete moments via a modular mapping and truncating Taylor series expansion. From this, we extend the use of our systolic array for fast computation of moments without any multiplications to one that computes DFT with only a few multiplications and without any evaluations of exponential functions. The multiplication number used in our method is O(N log₂ N/ log₂ log₂ N) superior to O(N log₂ N) in FFT. The execution time of the systolic array is only O(N log₂ N/ log₂ log₂ N) for 1-D DFT and O(N^k) for k-D DFT (k ges 2). The systolic implementation is a demonstration of the locality of dataflow in the algorithms and hence it implies an easy and potential hardware/VLSI realization. The approach is also applicable to DFT inverses. Copyright 1998 Academic Press.

Language: English

Document Type: Research article

Affiliations: 1: Institute for Pattern Recognition and Artificial Intelligence, Huazhong University of Science & Technology, State Education Commission Laboratory for Image Processing & Intelligent Control, People epsi s Republic of China s Republic of China "> 2: Department of Computer Science, University of Concordia, Montreal, Quebec, Canada 3: Department of Electrical and Electronic Engineering, The University of Hong Kong, Hong Kong