Portal de Periódicos da CAPES

The fast generalized discrete Fourier transforms: A unified approach to the discrete sinusoidal transforms computation

1999; Elsevier BV; Volume: 79; Issue: 2 Linguagem: Inglês

10.1016/s0165-1684(99)00088-2

1872-7557

Vladimír Britaňák, K.R. Rao,

Advanced Scientific Research Methods

Special forms of the generalized discrete Fourier transform (GDFT) matrices are investigated and their sparse matrix factorizations are presented to complete Wang's set of real sparse matrix factorizations for the family of discrete sinusoidal transforms. Different versions of the GDFT, different versions of the generalized discrete Hartley transform (GDHT) or equivalently of the discrete W transform (DWT), various versions of the discrete cosine transform (DCT) and discrete sine transform (DST) are members of the discrete sinusoidal transform family. There are intrinsic relationships among corresponding versions of the GDFT, GDHT (DWT), DCT and DST for real data sequences. A real sparse matrix factorization of GDFT matrices leads to simple fast algorithms for their computation, where only real arithmetic is involved. The resulting generalized signal flow graphs for the computation of different versions of the GDFT represent simple and compact unified approach to the fast discrete sinusoidal transforms computation. It is also shown that all algorithms are based on the universal DCT-II/DST-II (DCT-III/DST-III) computational structure which is used as the basic processing component. Spezielle Formen der generalisierten diskreten Fourier-Transformations (GDFT) Matrizen werden untersucht und deren dünnbesetzten Matrix-Faktorisierungen werden gezeigt, um die Wang'sche Menge der reelen schwachbesetzten Matrizen-Faktorisierungen für die Familie der diskreten sinusförmigen Transformationen zu vervollständigen. Unterschiedliche Formen der GDFT, der generalisierten diskreten Hartley Tranformation (GDHT) oder der diskreten W-Tranformation, sowie viele Formen der diskreten Kosinus-(DCT) und Sinus-Transformation (DST) sind Mitglieder der Familie der diskreten sinusartigen Transformationen. Für reele Datenfolgen gibt es innere Zusammenhänge zwischen entsprechenden Formen der GDFT, GDHT (DWT), DCT und DST. Eine reele dünnbesetzten Matrix-Faktorisierung der GDFT-Matrizen führt zu einfachen schnellen Berechnungs-Algorithmen, wobei nur reele Arithmetik verwendet wird. Der resultierende generalisierte Signalfluss für die Berechnung verschiedener Formen der GDFT repräsentiert einem einfachen und kompakten einheitlichen Ansatz für die Berechnung von schnellen diskreten sinusartigen Transformationen. Es wird weiter gezeigt, dass alle diese Algorithmen auf der universellen DCT-II/DST-II (DCT-III/DST-III) Berechnungsstruktur basieren, die als grundlegende Berechnungseinheit genutzt wird. Des formes spéciales des matrices de la transformation de Fourier discrète généralisée (TFDG) sont étudiées et leurs factorisations en matrices creuses sont présentées, pour compléter l'ensemble des factorisations en matrices creuses réelles de Wang, pour la famille des transformations sinusoı̈dales discrètes. Différentes versions de la TFDG, différentes versions de la transformation de Hartlet discrète généralisée (THDG), ou de façon équivalente de la transformation W discrète (TWD), différentes versions de la transformation en cosinus discrets (TCD) et en sinus discrets (TSD) sont des membres de la famille des transformations sinusoı̈dales discrètes. Il y a des relations intrinsèques entre les versions correspondantes des TFDG, THDG (TWD), TCD et TSD pour des séquences de données réelles. Une factorisation par matrice creuse réelle des matrices de la TFDG conduit à des algorithmes simples et rapides pour leur calcul, ne mettant en œuvre que de l'arithmétique réelle. Les graphes de flux de signaux généralisés qui en résultent, pour le calcul de différentes versions de la TFDG, représentent une approche unifiée simple et compacte pour le calcul rapide des transformations sinusoı̈dales discrètes. Nous montrons aussi que tous ces algorithmes reposent sur la structure de calcul universelle TCD-II/TSD-II (TCD-III/TSD-III), qui est utilisée comme le composant de traitement de base.