Was ist ein Faltungsrechner?

Rainair
Aktiver Hörer
Beiträge: 148
Registriert: 29.06.2014, 12:22
Wohnort: 82024 Taufkirchen b. München

Was ist ein Faltungsrechner?

Beitrag von Rainair »

Hallo allerseits,

...immer wieder stosse ich in diesem Forum auf "Faltungsrechner".
Kann mir jemand von euch erklären, -was- -wie- -womit- gefaltet wird ?

Für sachdienliche Hinweise und Erklärungen wär ich sehr dankbar.

LG, Rainair
Bild
axxxxx

Beitrag von axxxxx »

Guggst Du hier:

http://www.aktives-hoeren.de/viewtopic.php?f=40&t=1270

Damit werden die FLAC/WAV files online mit den Acourate Filtern gefaltet.

Gruß,
Kai
axxxxx

Beitrag von axxxxx »

Danke, Kai!
Gerne, Rainair.
frankl
Aktiver Hörer
Beiträge: 486
Registriert: 20.01.2013, 01:43
Wohnort: Aachen

Beitrag von frankl »

Rainair hat geschrieben: ...immer wieder stosse ich in diesem Forum auf "Faltungsrechner".
Kann mir jemand von euch erklären, -was- -wie- -womit- gefaltet wird ?

Für sachdienliche Hinweise und Erklärungen wär ich sehr dankbar.
Hallo Rainair,

ich versuche es mal:
  • * Was?

    Ein digitales Musiksignal, das ist im Computer pro Kanal eine Folge von Zahlen
    x[0], x[1], x[2], x[3], ................................., x[m]
    (typischerweise 44100 bis 192000 davon pro Sekunde und pro Kanal).

    * Womit?

    Mit einem "Filter", das ist auch eine Folge von Zahlen
    f[0], f[1], f[2], ..., f[n]
    (die Anzahl n+1 dieser Zahlen liegt typischerweise zwischen 2 und 500000)

    * Wie?

    Das "Falten" ist eine mathematische Operation, die aus dem Musiksignal und dem Filter ein Ausgangssignal, also eine neue Folge von Zahlen
    y[0], y[1], y[2], y[3], ................................., y[m]
    berechnet. Die Faltungsoperation ist ganz einfach, um die i-te Zahl y zu berechnen benötigt man die i-te Zahl im Musiksignal und die n davor liegenden und berechnet
    y = f[0]*x + f[1]*x[i-1] + f[2]*x[i-2] + ... + f[n]*x[i-n]


Vielleicht hast Du jetzt noch weitere Fragen, zum Beispiel:

  • * Warum?

    Bei geschickter Wahl der f[0], ..., f[n] erhält man interessante Effekte. Zum Beispiel kann man Frequenzweichen so realisieren, es werden also zum Beispiel hohe oder niedrige Frequenzen entfernt. Oder man verändert Frequenzgang und Phase des Eingangssignal so, das Probleme des Lautsprechers oder des Wiedergaberaums beim Abspielen der Musik ausgeglichen werden (solche Filter werden von einigen Forenmitgliedern zum Beispiel mit drc oder Acourate berechnet).

    * Was ist ein "Faltungsrechner"?

    Ein Computer, der die beschriebene Faltung berechnet. Einige hier machen das während des Abspielens der Musik, und andere machen das zum "Vorfalten" ihrer Musik (das heißt, sie speichern auch y[0], y[1], ..... auf ihrer Festplatte und spielen beim Musikhören dieses Signal, statt des ursprünglichen x[0], x[1], ...).

    * "Falten" sieht doch ganz einfach aus, macht das nicht jeder Computer mit links?

    Na ja, wenn in dem Filter n=500000 ist, muss für jedes y in der Ausgabe (also mindestens 44100 Mal pro Sekunde und Kanal, wenn das Ergebnis gleich angehört werden soll) 500000 mal multiplizert und addiert werden. Das schafft kein Computer (zumindest keiner, den Du bezahlen möchtest). Es gibt aber einen mathematischen Trick, die "diskrete Fouriertransformation", mit dem man in der gleichen Zeit, in der mit der Formel oben ein y berechnet wird, fast 500000 der y ausrechnen kann. Ich benutze dafür zum Beispiel das Programm brutefir, es gibt auch andere.
    Ein "Faltungsrechner" muss also unter Umständen schon eine ansehnliche Rechenleistung bringen.


Für weitere Infos suche im Internet nach FIR-Filter.

Viele Grüße,

Frank
Bild
qwe
Aktiver Neuling
Beiträge: 233
Registriert: 25.06.2013, 12:31

Beitrag von qwe »

aston456 hat geschrieben:Danke, Kai!
Gerne, Rainair.
Undank ist der Welten Lohn!

Ich hingegen danke Dir, lieber Kai, für Deine treue Hilfeleistung, auch wenn ich nicht der Fragende war.

Vielleicht ist es ja auch möglich, neben dem Jahrbuch mal eine Art Glossar für Aktives Hören in das Forum einzubinden?

Hmm... Gruß,
QWE
Bild
cinematic
Aktiver Neuling
Beiträge: 708
Registriert: 28.04.2013, 12:42

Beitrag von cinematic »

...x[0], x[1], x[2], x[3], ................................., x[m]
f[0], f[1], f[2], ..., f[n]
y[0], y[1], y[2], y[3], ................................., y[m]
y = f[0]*x + f[1]*x[i-1] + f[2]*x[i-2] + ... + f[n]*x[i-n]
[/list]
Vy[0], y[1], ..... x[0], x[1], ...).....

endlich habe ich das auch mal verstanden. :wink: :mrgreen:

Gruß
tom
Bild
nihil.sine.causa
Aktiver Hörer
Beiträge: 1506
Registriert: 28.07.2011, 12:31
Wohnort: Bonn

Beitrag von nihil.sine.causa »

Hallo Frank,

danke für Deine Darstellung, dieses Thema einmal etwas formaler zu beschreiben!
frankl hat geschrieben: * Wie?

Das "Falten" ist eine mathematische Operation, die aus dem Musiksignal und dem Filter ein Ausgangssignal, also eine neue Folge von Zahlen
y[0], y[1], y[2], y[3], ................................., y[m]
berechnet. Die Faltungsoperation ist ganz einfach, um die i-te Zahl y zu berechnen benötigt man die i-te Zahl im Musiksignal und die n davor liegenden und berechnet
y = f[0]*x + f[1]*x[i-1] + f[2]*x[i-2] + ... + f[n]*x[i-n]
frankl hat geschrieben: * "Falten" sieht doch ganz einfach aus, macht das nicht jeder Computer mit links?

Na ja, wenn in dem Filter n=500000 ist, muss für jedes y in der Ausgabe (also mindestens 44100 Mal pro Sekunde und Kanal, wenn das Ergebnis gleich angehört werden soll) 500000 mal multiplizert und addiert werden. Das schafft kein Computer (zumindest keiner, den Du bezahlen möchtest). Es gibt aber einen mathematischen Trick, die "diskrete Fouriertransformation", mit dem man in der gleichen Zeit, in der mit der Formel oben ein y berechnet wird, fast 500000 der y ausrechnen kann. Ich benutze dafür zum Beispiel das Programm brutefir, es gibt auch andere.
Ein "Faltungsrechner" muss also unter Umständen schon eine ansehnliche Rechenleistung bringen.

Für Online-Convolving (also Falten zur Laufzeit des Digital-Players) gibt es massive Rechenbeschränkungen und daher gute Grunde, ein Näherungsverfahren einzusetzen. Wie aber sieht es aus, wenn wir Offline-Convolving (als Falten, dessen Ergebnis in eine modifzierte Audiodatei weggeschrieben wird) machen? Hierbei könnten wir uns doch eigentlich Zeit lassen und die diskrete Faltungsrechnung exakt vornehmen. Hierzu nun zwei Fragen:

  • Kennt jemand von Euch ein - etwa unter Windows - verfügbares Programm, in dem der exakte Algorithmus implementiert und für Offline-Convolving verfügbar ist?
  • Welche Fehler macht man im Vergleich zum exakten Verfahren, wenn man die üblichen Näherungsverfahren anwendet und wie würden sich solche Fehler ggf. anhören?


Viele Grüße
Harald
Bild
Rainair
Aktiver Hörer
Beiträge: 148
Registriert: 29.06.2014, 12:22
Wohnort: 82024 Taufkirchen b. München

Beitrag von Rainair »

hallo frankl,

...vielen Dank für deine tolle und fundierte Erklärung ! Genau das hatte ich gesucht. Spitze !!!

LG, Rainair
Bild
uli.brueggemann
Aktiver Hersteller
Beiträge: 4658
Registriert: 23.03.2009, 15:58
Wohnort: 33649
Kontaktdaten:

Beitrag von uli.brueggemann »

nihil.sine.causa hat geschrieben:Für Online-Convolving (also Falten zur Laufzeit des Digital-Players) gibt es massive Rechenbeschränkungen und daher gute Grunde, ein Näherungsverfahren einzusetzen. Wie aber sieht es aus, wenn wir Offline-Convolving (als Falten, dessen Ergebnis in eine modifzierte Audiodatei weggeschrieben wird) machen?
...
[*]Welche Fehler macht man im Vergleich zum exakten Verfahren, wenn man die üblichen Näherungsverfahren anwendet und wie würden sich solche Fehler ggf. anhören? [/list]
Harald,

siehe hierzu das im übrigen hervorragende Buch (dazu kostenlos) auf http://www.dspguide.com.
http://www.dspguide.com/ch12/4.htm hat geschrieben:The FFT has another advantage besides raw speed. The FFT is calculated more precisely because the fewer number of calculations results in less round-off error. This can be demonstrated by taking the FFT of an arbitrary signal, and then running the frequency spectrum through an Inverse FFT. This reconstructs the original time domain signal, except for the addition of round-off noise from the calculations. A single number characterizing this noise can be obtained by calculating the standard deviation of the difference between the two signals. For comparison, this same procedure can be repeated using a DFT calculated by correlation, and a corresponding Inverse DFT. How does the round-off noise of the FFT compare to the DFT by correlation?
Im Klartext: eine Zu-Fuss-Rechung mit vielen Multiplikationen und Additionen führt aufgrund der Beschränkung der Zahlenformate zumindest ab einer gewissen Faltungsgröße zu mehr Ungenauigkeiten im Vergleich zur FFT-Convolution. Was sich im Prinzip als Rauschen bemerkbar macht.

Grüsse
Uli
Bild
nihil.sine.causa
Aktiver Hörer
Beiträge: 1506
Registriert: 28.07.2011, 12:31
Wohnort: Bonn

Beitrag von nihil.sine.causa »

Hallo Uli,
uli.brueggemann hat geschrieben: Im Klartext: eine Zu-Fuss-Rechung mit vielen Multiplikationen und Additionen führt aufgrund der Beschränkung der Zahlenformate zumindest ab einer gewissen Faltungsgröße zu mehr Ungenauigkeiten im Vergleich zur FFT-Convolution. Was sich im Prinzip als Rauschen bemerkbar macht.
das verstehe ich so nicht. Die Operation, wie sie Frank notiert hat:
frankl hat geschrieben:Die Faltungsoperation ist ganz einfach, um die i-te Zahl y zu berechnen benötigt man die i-te Zahl im Musiksignal und die n davor liegenden und berechnet
y = f[0]*x + f[1]*x[i-1] + f[2]*x[i-2] + ... + f[n]*x[i-n]

fasse ich erst einmal als exakt gerechnete (rationale) Zahl y auf. Von Näherungsverfahren wollte ich ja gerade absehen. Die FFT muss dem gegenüber zu einem Fehler führen, oder wo liegt der Denkfehler?

Beste Grüße
Harald
Bild
uli.brueggemann
Aktiver Hersteller
Beiträge: 4658
Registriert: 23.03.2009, 15:58
Wohnort: 33649
Kontaktdaten:

Beitrag von uli.brueggemann »

Es wird mit Zahlen endlicher Genaugkeit gerechnet, also z.B. 32 oder 64 bit Gleitkomma.
Bei den zig-tausend Einzelrechnungen gibt es entsprechend minimalste Rechenfehler, die sich aber dann doch im Ergebnis niederschlagen.

Wenn Du z.B. zwei Zahlen mit 10 Nachkommastellen multiplizierst, hat das Ergebnis 20 Nachkommastellen. Und wenn das Zahlenformat aber nur 10 Nachkommastellen hat, dann wird hinten abgeschnitten.

Per FFT-Faltung wird die Anzahl der Berechnungen deutlich kleiner. Dadurch kann eben das Ergebnis trotz Transformation und Rücktransformation überraschenderweise genauer sein.

Grüsse
Uli
Bild
nihil.sine.causa
Aktiver Hörer
Beiträge: 1506
Registriert: 28.07.2011, 12:31
Wohnort: Bonn

Beitrag von nihil.sine.causa »

Hallo Uli,
uli.brueggemann hat geschrieben:Es wird mit Zahlen endlicher Genaugkeit gerechnet, also z.B. 32 oder 64 bit Gleitkomma.
Bei den zig-tausend Einzelrechnungen gibt es entsprechend minimalste Rechenfehler, die sich aber dann doch im Ergebnis niederschlagen.
Das ist aber doch nicht zwingend. Mit einem Computeralgebra-Programm könnten wir doch auch exakt rechnen. Nochmal: y ist eine rationale Zahl. Rechengenauigkeit wie bei numerischen Approximationen spielt da keine Rolle.

Gruß Harald
Bild
uli.brueggemann
Aktiver Hersteller
Beiträge: 4658
Registriert: 23.03.2009, 15:58
Wohnort: 33649
Kontaktdaten:

Beitrag von uli.brueggemann »

Harald,

ja, das hast Du wohl recht. Da man Pi z.B. locker mit 1000 Nachkommastellen rechnen kann, kann man auch eine Faltung mit entsprechendem Aufwand, also erweiterter Rechengenauigkeit, rechnen.

Nehmen wir also an, dass Du mit einem Format mit 200 Nachkommastellen rechnest. Dann wäre wiederum die FFT bei demselben Format im Vorteil.

Acourate rechnet z.B. mit 64 bit float. Was so Rechengenauigkeiten von ca. -280 dB ermöglicht. Das sind ca. 140 dB Reserve bevor man das letzte Bit bei 24 Bit PCM erreicht.

Grüsse
Uli
Bild
Buschel
Aktiver Hörer
Beiträge: 989
Registriert: 12.12.2013, 20:12
Wohnort: Raum Karlsruhe

Beitrag von Buschel »

Hallo Harald,
nihil.sine.causa hat geschrieben:Kennt jemand von Euch ein - etwa unter Windows - verfügbares Programm, in dem der exakte Algorithmus implementiert und für Offline-Convolving verfügbar ist?
Welche Fehler macht man im Vergleich zum exakten Verfahren, wenn man die üblichen Näherungsverfahren anwendet und wie würden sich solche Fehler ggf. anhören?
nihil.sine.causa hat geschrieben:Das ist aber doch nicht zwingend. Mit einem Computeralgebra-Programm könnten wir doch auch exakt rechnen. Nochmal: y[ i] ist eine rationale Zahl. Rechengenauigkeit wie bei numerischen Approximationen spielt da keine Rolle.
Ich habe den Eindruck du setzt fft mit einer numerischen Näherung gleich. Das Ergebnis einer fft ist mathematisch identisch zu dem einer dft, sie benötigt nur weniger Rechenoperationen. Auf Basis einer dft wiederum kann eine Faltung vollkommen ersetzt werden -- mit demselben Ergebnis. Also keine Näherung, sondern mathematisch identisch. Sprich: eine Faltung lässt sich mathematisch vollständig durch eine fft-Lösung ersetzen. Eine einfache Visualisierung ist z.B. hier gut gelungen.

In der Praxis wiederum wird wie von Uli beschrieben mit jeder Multiplikation eine Ungenauigkeit hinzukommen. Je weniger Multiplikationen notwendig sind, desto genauer kann das Ergebnis sein, d.h. desto weniger Abweichung zum mathematischen Ideal.

Bei einer Faltung "zu Fuß" wächst die Anzahl der Multiplikationen für die Berechnung eines Ausgangswerts linear mit der Filterlänge N. Bei einer fft-basierten Lösung wächst sie nur mit log2(N).

Viele Grüße,
Andree
Bild
frankl
Aktiver Hörer
Beiträge: 486
Registriert: 20.01.2013, 01:43
Wohnort: Aachen

Beitrag von frankl »

Hallo Harald,

ich kann den bereits gegebenen Antworten auf Deine Frage nicht viel hinzufügen. Die FFT ist im Prinzip eine mathematisch exakte Methode, die Faltung durchzuführen (sie bringt nichts wenn ich nur ein y wie oben ausrechnen will, aber man kann eben viele aufeinanderfolgende y mit erheblich weniger Multiplikationen und Additionen ausrechnen). Fehler im Ergebnis entstehen nur durch Rundungsfehler, da alle Zwischenergebnisse beim Rechnen immer nur mit 32 oder 64 Bit Genauigkeit festgehalten werden. Und wie hier richtig angemerkt wurde, führt eine Rechnung mit erheblich weniger Zwischenschritten tendentiell zu genaueren Ergebnissen (die Wirklichkeit ist noch komplizierter). Die Faltung mit FFT ist also sicher kein Trade-off zwischen Geschwindigkeit und Genauigkeit, sondern beides wird verbessert.

Beim genauen Rechnen in einem Computeralgebrasystem bringt die FFT nichts, da man zwar weniger Operationen hat, aber die Einzeloperationen (mit sogenannten "Einheitswurzeln") erheblich aufwändiger werden.

Außerdem wäre ohne FFT bei langen Filtern die Rechenzeit ein Problem: Ich falte zum Beispiel 192 kHz Daten mit einem Filter mit Länge über 500000. Das belastet meine "Faltungsrechner"-CPU zu 70%, auch auf einem schnellen Pentium sind es noch ein paar Prozent. Ohne FFT würde sich die Rechenzeit wohl um einen Faktor von einigen 10000 oder so verlängern. Auch mit viel Geduld möchte darauf niemand warten. Ohne FFT wäre das "Falten", das viele von uns machen, gar nicht praktikabel.

Viele Grüße,
Frank
Bild
Antworten