File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A Novel Approach to Fast Discrete Fourier Transform

TitleA Novel Approach to Fast Discrete Fourier Transform
Authors
Issue Date1998
PublisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jpdc
Citation
Journal of Parallel and Distributed Computing, 1998, v. 54, p. 48-58 How to Cite?
AbstractDiscrete 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 isO(Nlog2N/ log2log2N) superior toO(Nlog2N) in FFT. The execution time of the systolic array is onlyO(Nlog2N/ log2log2N) for 1-D DFT andO(Nk) fork-D DFT (k≥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. © 1998 Academic Press.
Persistent Identifierhttp://hdl.handle.net/10722/225191
ISSN
2015 Impact Factor: 1.32
2015 SCImago Journal Rankings: 0.851

 

DC FieldValueLanguage
dc.contributor.authorLiu, JQ-
dc.contributor.authorLi, HF-
dc.contributor.authorChan, FHY-
dc.contributor.authorLam, FK-
dc.date.accessioned2016-04-28T01:51:07Z-
dc.date.available2016-04-28T01:51:07Z-
dc.date.issued1998-
dc.identifier.citationJournal of Parallel and Distributed Computing, 1998, v. 54, p. 48-58-
dc.identifier.issn0743-7315-
dc.identifier.urihttp://hdl.handle.net/10722/225191-
dc.description.abstractDiscrete 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 isO(Nlog2N/ log2log2N) superior toO(Nlog2N) in FFT. The execution time of the systolic array is onlyO(Nlog2N/ log2log2N) for 1-D DFT andO(Nk) fork-D DFT (k≥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. © 1998 Academic Press.-
dc.languageeng-
dc.publisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jpdc-
dc.relation.ispartofJournal of Parallel and Distributed Computing-
dc.titleA Novel Approach to Fast Discrete Fourier Transform-
dc.typeArticle-
dc.identifier.emailChan, FHY: fhychan@hkueee.hku.hk-
dc.identifier.emailLam, FK: fklam@hkueee.hku.hk-
dc.identifier.doi10.1006/jpdc.1998.1472-
dc.identifier.scopuseid_2-s2.0-0038902298-
dc.identifier.hkuros45195-
dc.identifier.volume54-
dc.identifier.spage48-
dc.identifier.epage58-
dc.publisher.placeUnited States-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats