Hallo zusammen, ich habe eine Frage zur schnellen Faltung und wusste nicht wo im Forum ich diese stellen soll. Es geht um den Einsatz der schnellen Faltung in der Industrie. Da FIR-Filer ja auch mit der schnelle Faltung realisiert werden können und das ab der 40. Ordnung effektiver sein soll (Digitale Signalverarbeitung, Kammeyer), würde mich interessieren ob es wirklich Anwendungsfälle gibt in welcher die schnelle Faltung eingesetzt wird. Vielen Dank u. beste Grüße Stephan
:
Verschoben durch Admin
Was genau verstehst Du unter "schneller Faltung"? Ich mutmaße mal, dass Du folgendes meinst: Anstatt die Faltungssumme zu berechnen transformiert man in den Frequenzbereich (FFT), multipliziert die Signale miteinander und transformiert zurück. Das findet in jedem Handy Anwendung.
Danke erstmal für die Antworten. Die Links von Winfried kenne ich bereits. Mir geht es in der Tat darum, konkrete Anwendungsbeispiele für die "schnelle Faltung" zu finden. (So wie Daniel das beschrieben hat) Also in welchem Gerät/Anwendung anstatt einen FIR Filter mit einer Ordnung >= 40 die schnelle Faltung implementiert wird @Daniel Für welche Anwendung im Handy wird das denn genutzt?
Mal rechnen: Willst Du m Abtastwerte mit einem FIR n-te Ordnung behandeln brauchst Du n*m Multiplikationen. Mittels FFT: Die FIR Koeffizienten sind schon transformiert, wegen der zyklischen Fortsetzung wird mit Nullen gestopft, es sind 2n Faktoren vorhanden. Deine Abtastwerte kommen geblockt daher, es gibt m/(2n) Blöcke. Jetzt gehts los. - die m/(2*n) Blöcke hin/rück-transformieren: 2*m/(2n)*n*log2(n)*4 reelle Multiplikationen - mit den Koeffizienten multiplizieren: m/(2n)*2n*4 reele Mult. Also insgesamt macht das Sinn wenn gilt 4*(log2(n)+1)<n also für n>22. Faktor 2 neben Kammeyer, 3dB, close enough ;-)) Hätte ich nicht geglaubt. dass das bei so kleinen Filterordnungen schon lohnt. Habe noch nicht gesehen, dass selbst sehr lange FIRs mit FFTs gerechnet werden. Oft wird ja vom Zeitsignal sowieso die FFT gemacht, kann man sich also die Rücktransformation sparen. wieder was gelernt Cheers Detlef
Jop, danke! Was ich mittlerweile mal ansatzweise probiert habe ist folgendes... Da ich mehr oder weniger in der FPGA-Ecke zuhause bin, habe ich mal mit dem Coregenerator einen FIR Filter 40. Ordnung und eine FFT generieren lassen. Der Ressourcenverbrauch des FIR-Filters ist immens geringer wie der der FFT (und die bräuchte ich ja 3 mal). Von daher stellt sich mir weiterhin die Frage, gibt es Firmen die FIR Filter mittels der schnellen Faltung realisieren? Beste Grüße stephan
@Detlef_a, Deine Meinung zu folgendem Vorschlag interessiert mich: Könnte man den Rechenaufwand nicht nochmals reduzieren, indem man die FFT durch die FHT (Fast Hadamard) ersetzt? Statt der Multiplikationen wären dann nur noch Additionen bzw. Subtraktionen erforderlich. Die FIR-Koeffizienten müsste man natürlich auch FH-transformieren. mare_crisium
>>Von daher stellt sich mir weiterhin die Frage, gibt es Firmen die FIR >>Filter mittels der schnellen Faltung realisieren? Mir sind einige Chips intim bekannt, die lange FIRs benutzen, z.B. für echocanceller mit einigen hundert taps. Die machen das alle brute force ohne FFT. @Harald Für die Hadamard Transformation gilt vermutlich nicht der Faltungssatz, auf dem der hack beruht. Nen kurzer Matlab Test hat zumindest nicht geklappt. math rulez! Cheers Detlef clear x=[zeros(1,8) 1:8 zeros(1,8)]; n=length(x); fil=[zeros(1,8) 1:8 zeros(1,8)]; %fil=[1:n/2 n/2:-1:1]; y=filter(fil,1,x); M=hadamard(n); hfil=fil*M; hx=x*M; hry=(hx.*hfil); ry=hry*M';
Detlef, der Faltungssatz gilt doch für alle Transformationen, die auf orthogonalen Funktionensystemen aufbauen, oder? Die Hadamardfunktionen sind orthogonal. Die Rücktransformation ist (bis auf einen Normierungsfaktor) ebenfalls die Hadamardtransformation f(x)~H(H(f(x))). Ich sehe nichts, was der Gültigkeit des Faltungssatzes für diese Funktionen widerspräche... Was meinst Du? math rulez! Und wie! mare_crisium
Schöner Artikel: http://archive.chipcenter.com/dsp/DSP000517F1.html
1 | One key difference between FHTs and FFTs is that the magnitude of an FFT is |
2 | invariant to phase shifts in the signal. This fact isn't true of the FHT |
3 | because a circular shift in one row of the Hadamard matrix doesn't leave it |
4 | orthogonal to the other rows. In fact, the shifted row might be closer (in |
5 | Hamming distance) to other rows than to the original. Thus data alignment is |
6 | critically important to FHT applications. For this reason, the FHT is less |
7 | useful than the FFT in most spectral-analysis applications. |
Ich hab' so das Gefühl dass es mit der FHT nicht so einfach ist. Habe mich aber noch nie mit der HT beschäftigt. Just my two cents.
@pumpkin, ja, der Artikel ist wirklich gut. Die Aussagen, die Du zitierst, sind alle richtig. Deshalb hat ein Hadamard-"Spektrum" auch keine anschauliche Bedeutung - im Gegensatz zum Fourierspektrum. Bei Stephans Fragestellung kommt's aber gar nicht auf Anschaulichkeit an, sondern nur darauf, eine Funktion ohne Informatiosnverlust und mit möglichst wenig Rechenaufwand in einen anderen Funktionenraum und wieder zurück zu transformieren (mit zwischengeschalteter Multiplikation). Auf dem Gebiet ist die FHT ziemlich unschlagbar. @Detlef, in Deinem Matlab-Beispiel finde ich die Rücktransformation nicht... übersehe ich da was? math rulez! Toujours. mare_crisium
>> in Deinem Matlab-Beispiel finde ich die Rücktransformation nicht...
die letzte Zeile ry=hry*M'; ?!
Cheers
Detlef
Detlef, aha, jetzt verstehe ich die Schreibweise. Komisch, dass es nicht funzt. Theoretisch müsste es! Ciao, mare_crisium.
Harald M. schrieb: > @pumpkin, > > ja, der Artikel ist wirklich gut. > > Die Aussagen, die Du zitierst, sind alle richtig. Deshalb hat ein > Hadamard-"Spektrum" auch keine anschauliche Bedeutung - im Gegensatz zum > Fourierspektrum. Bei Stephans Fragestellung kommt's aber gar nicht auf > Anschaulichkeit an, sondern nur darauf, eine Funktion ohne > Informatiosnverlust und mit möglichst wenig Rechenaufwand in einen > anderen Funktionenraum und wieder zurück zu transformieren (mit > zwischengeschalteter Multiplikation). Auf dem Gebiet ist die FHT > ziemlich unschlagbar. Auch was du sagst ist richtig. :^) Meine Vorstellung von der Sache ist: Wenn das Eingangssignal verschoben wird, dann bekommt man ein komplett anderes Filterergebnis:
1 | One key difference between FHTs and FFTs is that the magnitude of an |
2 | FFT is invariant to phase shifts in the signal. This fact isn't true |
3 | of the FHT [...] |
Das finde ich bedenklich. Vllt irre ich mich. Ich sag ja nicht, dass es gar nicht geht, ich sage nur, dass es nicht so einfach ist. ;^) Cheersekowski!
Zur Ursprungsfrage "Faltung im Zeitbereich oder Multiplikation im Frequenzbereich": Der große Vorteil bei der Faltung im Zeitbereich ist, dass die Operationen sequentiell und lokal sind. Man kann - gerade im FPGA - eine wunderbare Pipeline aufbauen. Bei der FFT braucht man a) das komplette Signal im Speicher b) random-access Zugriff auf die einzelnen Samples Auf der einen Seite könnte schneller SRAM (FPGA, cache im DSP) schnell zu klein werden, auf der anderen Seite sind DDR-Speicher nicht geeignet, da immer Paar-/Blockweise transferiert wird.
Kollegen, zur Thematik habe ich hier noch was geäußert: Beitrag "Hadamard Transformation" Wenns denn nützt. Cheers Detlef
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.