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
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
@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
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.
