mikrocontroller.net

Forum: Digitale Signalverarbeitung / DSP Schnelle Faltung


Autor: Stephan N. (notste)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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
Autor: Winfried J. (Firma: Nisch-Aufzüge) (winne)
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: Daniel R. (daniel_r)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
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.

Autor: Winfried J. (Firma: Nisch-Aufzüge) (winne)
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: Stephan N. (notste)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Stephan N. (notste)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Harald M. (mare_crisium)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>>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';

Autor: Harald M. (mare_crisium)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: T. H. (pumpkin) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Schöner Artikel:

  http://archive.chipcenter.com/dsp/DSP000517F1.html

One key difference between FHTs and FFTs is that the magnitude of an FFT is 
invariant to phase shifts in the signal. This fact isn't true of the FHT 
because a circular shift in one row of the Hadamard matrix doesn't leave it 
orthogonal to the other rows. In fact, the shifted row might be closer (in 
Hamming distance) to other rows than to the original. Thus data alignment is 
critically important to FHT applications. For this reason, the FHT is less 
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.

Autor: Harald M. (mare_crisium)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>> in Deinem Matlab-Beispiel finde ich die Rücktransformation nicht...

die letzte Zeile ry=hry*M'; ?!

Cheers
Detlef

Autor: Harald M. (mare_crisium)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Detlef,

aha, jetzt verstehe ich die Schreibweise. Komisch, dass es nicht funzt. 
Theoretisch müsste es!

Ciao,

mare_crisium.

Autor: T. H. (pumpkin) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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:

One key difference between FHTs and FFTs is that the magnitude of an
FFT is invariant to phase shifts in the signal. This fact isn't true 
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!

Autor: Ras Funk (rasfunk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kollegen, zur Thematik habe ich hier noch was geäußert:

Beitrag "Hadamard Transformation"

Wenns denn nützt.

Cheers
Detlef

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.