Fast fourier transforms: A tutorial review and a state of the art
1990; Elsevier BV; Volume: 19; Issue: 4 Linguagem: Inglês
10.1016/0165-1684(90)90158-u
ISSN1872-7557
AutoresPierre Duhamel, Martin Vetterli,
Tópico(s)Blind Source Separation Techniques
ResumoThe publication of the Cooley-Tukey fast Fourier transform (FFT) algorithm in 1965 has opened a new area in digital signal processing by reducing the order of complexity of some crucial computational tasks like Fourier transform and convultion from N2 to N log2, where N is the problem size. The development of the major algorithms (Cooley-Tukey and split-radix FFT, prime factor algorithm and Winograd fast Fourier transform) is reviewed. Then, an attempt is made to indicate the state of the art on the subject, showin the standing of researh, open problems and implementations. Die Publikation von Cooley-Tukey's schnellem Fourier Transformations Algorithmus in 1965 brachte eine neue Area in der digitalen signaverarbeitung weil die Ordnung der Komplexität von gewissen zentralen Berechnungen, wie die Fourier Transformations und die digitale Faltung, von N2 zu Nlog2N reduziert wurden (wo N die Problemgrösse darstellt). Die Entwickflung der wichtigsten Algorithmen (Cooley-Tukey und Split-Radix FFT), Prime Factor Algorithmus und Winograd's schneller Fourier Transformation) ist nachvollzogen. Dann wird, den Stand des Feldes zu beschreiben, um zu zeigen wo die Forschung steht, was für Probleme noch offenstehen, wie zum Beispel in Implementierungen. La publication de l'algorithme de Cooley-Tukey pour la transformation de Fourier rapide a ouvert une nouvelle ère dans traitement numérique des signaux, en résiduisant l'ordre de comlexité de problèmes cruciaux, comme la transformation de Fourier ou la convulution de N2 à Nlog2N (où N est la taille du problème). Le dévelopment des algorithmes principaux (Cooley-Tukey, split-radix FFT, algorithmes des facteurs premiers, et transformée rapidem de Winograd) est déscrit. Ensuite, l'état de l'art est donné, et on parle problémes ouverts et des implantations.
Referência(s)