| Popis: |
Im letzten Kapitel haben wir gesehen, das es attraktiv sein kann, mittels einer NTT eine schnelle Faltung zu berechnen. Der bei der NTT berechnete N-Tupel im Bildbereich entspricht aber nicht der Approximation der Fourier- Transformation, die man bei der Verwendung der DFT mit α = e −2πj/N erhalt. Wurde man z.B. einen einzelnen „Pol“ α k = 2 k der NTT mittels Gortzel-Algorithmus (Abb. 8.4, S. 145) realisieren, so entsteht im allgemeinen nicht ein Filter mit einem einzelnen Durchlasbereich. Murakami et al. [140, 141] haben jedoch gezeigt, das man mit sehr wenigen arithmetischen Operationen aus einer NTT der Lange N = 8 die DFT-Koeffizienten bestimmen kann. Diese Idee soil Ausgangspunkt unserer Betrachtungen sein: Wir wollen untersuchen, ob es moglich ist, zunachst die „preiswerte“ NTT oder andere rechteckformige Transformation zu berechnen und dann mittels weniger arithmetischer Operationen daraus die DFT-Werte zu bestimmen. Diese Idee ist in Abb. 11.1 veranschaulicht. Wir transformieren zunachst die Eingangsfolge x[n] mittels einer Transformation G in den Bildbereich und erhalten die Zwischenwerte Y[k], Nun verwenden wir eine zweite Abbildung T, um schlieslich die DFT-Werte X[k] zu berechnen. In Matrixschreibweise ergibt sich $$ Y = G x $$ (11.1) $$ X = T Y = T G x $$ (11.2) |
