Ist der Frequenzbereich ein realer Ort?
(lcamtuf.substack.com)- Die diskrete Fourier-Transformation (DFT) ist ein zentrales Werkzeug in Kommunikation und Signalverarbeitung, aber der Frequenzbereich ist nicht die einzige Möglichkeit, Realität zu interpretieren
- In Strukturen wie der DCT, bei denen Frequenz-Bins ermittelt werden, indem Eingabestichproben mit Werten von Basisfunktionen multipliziert werden, lässt sich allein durch einen Wechsel der Basis ein Frequenzbereich mit anderen Regeln erzeugen
- Die Walsh-Matrix liefert eine Rechteckwellen-Basis, die nur
+1und-1verwendet; wenn Sequency und Orthogonalität stimmen, kann man zwischen Zeitbereich und Frequenzdarstellung hin- und herwechseln - Die Hadamard-Matrix ist eine umsortierte Form der Walsh-Matrix; sie wird mit dem Kronecker-Produkt oder Bit-Operationen erzeugt und für die WHT durch erneutes Sortieren der Zeilen nach Sequency genutzt
- Dieselbe Eingabe verteilt sich in der DCT über mehrere harmonische Komponenten, während sie in der Walsh-Hadamard-Transformation in Rechteckwellen-Komponenten zerlegt wird – ein Hinweis darauf, dass die DFT kein Monopol auf die „Wahrheit“ hat
Den Fourier-Frequenzbereich neu betrachten
- Der Frequenzbereich ist ein mathematischer Raum, in dem komplexe Signale als Amplituden und Phasen von Sinuswellen dargestellt werden
- Durch diese Darstellung lassen sich Signalverarbeitungsaufgaben, die im Zeit- oder Raumbereich schwer direkt zu behandeln sind, deutlich einfacher ausführen
- Die DFT spielt in Kommunikation und Signalverarbeitung eine zentrale Rolle, aber ob die Zerlegung einer Rechteckwelle in eine Summe ungeradzahliger sinusförmiger Harmonischer die einzige „reale“ Interpretation ist, ist eine andere Frage
- Sinuswellen kommen in der Natur häufig vor, weshalb Werkzeuge der Fourier-Familie für viele Aufgaben gut passen; man kann jedoch auch andere wohldefinierte Frequenzbereiche mit anderen Regeln konstruieren
Die DCT als Basisfunktion verstehen
- Die diskrete Kosinustransformation (DCT) kann als vereinfachte, nur mit reellen Zahlen arbeitende Version der DFT betrachtet werden
- Bei DCT-II wird die Größe eines bestimmten Frequenz-Bins
F_kbestimmt, indem Eingabewertes_nmit den Werten einer bestimmten Kosinusformel multipliziert und dann aufsummiert werden - Der entscheidende Punkt ist die Basisfunktion, die eine Kosinuswelle mit der Frequenz erzeugt, die zur aktuellen DCT-Bin-Nummer gehört
- Verallgemeinert liefert
B(k, n)abhängig vonkundneinen Multiplikator, der mit den Eingabestichproben multipliziert und aufsummiert wird - Aus Software-Sicht lässt sich
B(k, n)als Lookup-Array verstehen, mathematisch als Matrix - In der DCT-Basismatrix für
N=16entspricht die erste Zeilek=0der DC-Komponente bei 0 Hz; sie ist ein Kosinus, dessen Werte alle+1.00sind - Die folgenden Zeilen haben Kosinusformen, die immer schneller wechseln – etwa eine halbe Periode, eine volle Periode, anderthalb Perioden usw.
Rechteckwellen-Basis und Walsh-Matrix
- Eine Basisfunktion, die Signale nicht in Sinusfrequenzen, sondern in Rechteckwellen zerlegt, lässt sich mit der Walsh-Matrix aufbauen
- Die Walsh-Matrix besteht aus Rechteckwellen, die sich mit unterschiedlichen Geschwindigkeiten ändern, und alle Multiplikatoren sind
+1oder-1 - Dadurch vereinfacht sich die Berechnung auf das Vorzeicheninvertieren eines Teils der Eingabedaten und anschließendes Aufsummieren
- Auch eine simpel wirkende Matrix muss jedoch zwei Bedingungen erfüllen
- Jede Zeile muss eine Sequency-Reihenfolge haben, bei der es gegenüber der vorherigen Zeile genau einen Vorzeichenwechsel mehr gibt
- Damit man zwischen Zeitbereichsdaten und Frequenzdarstellung sauber hin- und herwechseln kann, muss Orthogonalität erhalten bleiben
- Um eine Walsh-Matrix direkt zu konstruieren, beginnt man mit einem
N×N-Array, wobeiNeine Zweierpotenz sein muss- In die linke erste Spalte werden in allen Zeilen
+1eingetragen - Eine neue Spalte wird als gespiegelte Kopie bestehender Werte erzeugt, und der neu hinzugefügte Bereich wird in mehrere horizontale Abschnitte unterteilt, in denen das Vorzeichen teilweise invertiert wird
- Bei jeder Wiederholung wird die Spalte kopiert, die Anzahl der Zeilenabschnitte erhöht und das Vorzeichen abwechselnd invertiert
- In die linke erste Spalte werden in allen Zeilen
Aus der Hadamard-Matrix ein Walsh-Array machen
- In Literatur und Open-Source-Code wird ein Walsh-Array oft nicht direkt konstruiert, sondern aus einer Hadamard-Matrix abgeleitet
- Die Hadamard-Matrix ist eine Version des Walsh-Arrays mit anderer Zeilenreihenfolge
- Zum Beispiel wandert bei
N=16in Walsh die Zeile Nr. 15 in Hadamard auf Nr. 1, und Walsh-Zeile Nr. 1 liegt dort auf Nr. 8
- Zum Beispiel wandert bei
- Historisch wurde die Hadamard-Konstruktion früher beschrieben und Walsh später darauf aufgebaut, was eine Erklärung für diese Konvention ist
- Praktisch ist die Erzeugung der Hadamard-Matrix besser dokumentiert, und es gibt auch einfache und effiziente Varianten mit Bit-Manipulation
- Die lehrbuchartige Konstruktion beginnt mit einem
1×1-Array und kopiert die vorherige MatrixH_{n-1}in vier Kacheln- Oben links, oben rechts und unten links werden unverändert kopiert
- Unten rechts werden alle Vorzeichen invertiert
- Für diese Erweiterung wird die Schreibweise des Kronecker-Produkts
⊗verwendet, tatsächlich handelt es sich aber um Kopieren und Vorzeichenumkehr
- Nach
nKonstruktionsschritten hat die Hadamard-Matrix immer die Größe2^n × 2^n - Der Hadamard-Wert einer bestimmten Zelle lässt sich ermitteln, indem
x & yberechnet und dann geprüft wird, ob die Zahl der gesetzten Bits im Ergebnis gerade oder ungerade ist- Ist die Zahl gesetzter Bits ungerade, ergibt sich
-1, bei gerader Zahl+1 - In C wird das als
__builtin_popcount(x & y) % 2implementiert
- Ist die Zahl gesetzter Bits ungerade, ergibt sich
Implementierung der Walsh-Hadamard-Transformation
- Um die Hadamard-Matrix in die intuitivere Walsh-Reihenfolge zu bringen, müssen die Zeilen nach Sequency sortiert werden
- Die einfachste Methode besteht darin, in jeder Zeile die Anzahl der Vorzeichenwechsel zu zählen
- Es sind auch andere Bit-Manipulationsverfahren möglich
- Die Walsh-Zeilennummer wird mit sich selbst XOR-verknüpft, nachdem sie um 1 Bit nach rechts verschoben wurde, um einen Gray-Code zu erzeugen
- Anschließend wird die Reihenfolge der letzten
nBits umgedreht, um die Zuordnung zur Hadamard-Zeile zu berechnen
- Ersetzt man mit diesem Walsh-Array in einer DCT-Implementierung die Basis, erhält man eine „discrete square transform“ und deren Inverses
- Technisch ist diese Transformation die Walsh–Hadamard-Transformation (WHT)
- Wenn die Beispiel-Eingabe
1 1 1 1 5 5 5 5mit der DCT verarbeitet wird, verteilen sich harmonische Komponenten auf mehrere Frequenz-BinsDCT : +24.00 -10.25 -0.00 +3.60 +0.00 -2.41 -0.00 +2.04
- Wird dieselbe Eingabe mit der Rechteckwellen-Transformation verarbeitet, erscheinen nichtnullige Komponenten nur in
F_0undF_1SQFT : +24.00 -16.00 +0.00 +0.00 +0.00 +0.00 +0.00 +0.00
- Die inverse Transformation
isqft()stellt die ursprüngliche Eingabe wieder herISQFT : +1.00 +1.00 +1.00 +1.00 +5.00 +5.00 +5.00 +5.00
Vergleich von Spektrogrammen und praktische Einordnung
- Anhand eines 11-Sekunden-Audioclips aus „DARE“ von Gorillaz werden ein DCT-Spektrogramm und ein Walsh-Hadamard-Spektrogramm verglichen
- Die Walsh-Hadamard-Transformation ist auch auf leistungsschwachen Computern recheneffizient und eignet sich für bestimmte Datentypen, weshalb sie in einigen Nischenanwendungen eingesetzt wird
- Die Schlussfolgerung ist nicht, dass man WHT häufiger verwenden sollte, sondern dass die diskrete Fourier-Transformation kein Monopol auf die Wahrheit hat
- Die Spektrogramme wurden aus einer 44,1-kHz-Mono-Audiodatei mit DCT und WHT berechnet
- Das Eingabe-Sample-Window beträgt
512 - Der Transform-Stepover beträgt
1 - Die Größe des Ausgabearrays liegt bei etwa
512 × 485k - Auf die normalisierte Betragsfunktion der Pixelintensität wird ein Gamma von etwa
0.4angewendet - Das Bild wird mit Lanczos-Resampling skaliert und mit einer linearen Schwarz–Himmelblau–Weiß-Colormap gerendert
- Das Eingabe-Sample-Window beträgt
- Als Beispiel für Experimente mit Walsh-Hadamard in der Bildkompression wird außerdem
http://rotormind.com/blog/2019/hadamard-days-night/genannt
1 Kommentare
Hacker-News-Kommentare
Mathematisch ist die Fourier-Transformation nur eine Methode, ein Zeitsignal in einer bestimmten orthogonalen Vektorbasis darzustellen.
Den Verschiebungsvektor auf der Erdoberfläche kann man ebenfalls in einer Nord-/Ost-Basis ausdrücken oder auch entlang einer beliebigen Straßenrichtung und der dazu senkrechten Richtung.
Zeitabhängige Signale oder „schöne“ Funktionen liegen in einem unendlichdimensionalen Vektorraum und sind daher schwer anschaulich vorstellbar, aber die zugrunde liegende Mathematik funktioniert ähnlich.
Bei der Fourier-Transformation sind die Basisvektoren harmonische Funktionen, und der Frequenzbereich ist eine Art „Karte“, die ein Signal als Kombination unendlich vieler harmonischer Funktionen zeigt.
Karten auf der Basis anderer Basen wie der Walsh–Hadamard-Transformation sind genauso real, und auch die Darstellung im Zeitbereich ist nur deshalb besonders, weil sie uns vertraut ist – sie ist nur eine von vielen möglichen Karten.
Es gibt viele Anwendungen, etwa in der Bildverarbeitung, beim Lösen von Differentialgleichungen und bei schneller Multiplikation.
Mathematisch sind solche Transformationen verlustfrei, das heißt, die transformierte Funktion enthält exakt dieselben Informationen wie die ursprüngliche Funktion, und allein aus der Transformation kann man zum Original zurückkehren.
Im Ingenieurwesen transformiert man allerdings oft gerade deshalb, um unerwünschte Informationen wie bestimmte Frequenzanteile zu verwerfen, wodurch dieser Punkt häufig aus dem Blick gerät.
Letztlich ist es nur eine von mehreren Perspektiven auf dieselbe Funktion.
Gerade in mehrdimensionalen Räumen funktioniert die gewöhnliche mehrdimensionale Fourier-Transformation nur dann richtig, wenn dieser Raum eine flache Metrik hat.
Wenn man bedenkt, dass das Universum selbst gekrümmt ist, wirkt das wie ein Warnsignal.
Kürzlich gab es interessante Arbeiten, die Fourier-Reihen auf bestimmte hyperbolische Gitter verallgemeinern, und dabei kann der Fourier-Raum eine höhere Dimension als der Ortsraum haben.
Außerdem hängt die Dimension dieses „Fourier-Raums“ davon ab, wie das Gitter diskretisiert wird, sodass ein bestimmtes 2D-Gitter einen 4D-frequenzähnlichen Raum haben kann, während ein anderes 2D-Gitter einen 8D-ähnlichen Raum besitzt.
https://arxiv.org/abs/2108.09314 oder https://www.pnas.org/doi/full/10.1073/pnas.2116869119
Das Modell war völlig falsch, aber praktisch gesehen benutzte man damit Fourier-Reihen als Approximator für Funktionen.
Auch wenn man eine Basis wie Polynome verwendet, baut man eine Funktion letztlich aus Frequenzanteilen auf.
Die Fourier-Basis ist insofern besonders, als jedes ihrer Elemente einer bestimmten Frequenz entspricht.
Allerdings ist jede Basis eher für einen bestimmten Zweck entworfen, und ein Basiswechsel kann das Spektrum auf eine komplizierte Weise umordnen, sodass man dann eher andere Eigenschaften wie Glattheit analysiert.
Die meisten Funktionen, die uns interessieren, haben zwar ein charakteristisches Spektrum, aber die Fourier-Basis beantwortet nicht jede Frage.
Wenn sie wie Norden und Nordosten nur teilweise senkrechte Komponenten haben, kann man [n, e] doch trotzdem in anderen Koordinaten ausdrücken.
Die genauen Koeffizienten mögen wegen Hitze falsch sein, aber der Kernpunkt ist, dass es möglich ist.
Das erinnert mich an ein Gespräch vor dem Whiteboard in meiner Masterzeit in einer Arbeitsgruppe für dynamische Systeme.
„Links wird Energie in das System eingespeist, und rechts hier wird sie dissipiert.“
„Aber das System ist rotationsinvariant, es gibt also weder links noch rechts.“
„Ich meinte im Frequenzraum.“
„Ach so, ich dachte, du meinst den realen Raum.“
„Bist du doof? Wer denkt denn im realen Raum?“
Das ist doch eine abstrakte Darstellung und steht nicht in direkter Beziehung zu links, rechts, oben oder unten in den Raumdimensionen.
Die Fourier-Basis ist insofern einzigartig, als komplexe Exponential-Basisfunktionen Eigenvektoren linearer zeitinvarianter (LTI-)Systeme sind.
Andere Transformationen haben diese Eigenschaft nicht.
Viele reale Systeme wie Schaltungen, Kommunikationskanäle und Antennen sind LTI, und dank dieser Eigenschaft stören sich auf unterschiedlichen Frequenzen übertragene Signale nicht gegenseitig.
Deshalb wird die Fourier-Transformation viel breiter eingesetzt als andere Transformationen.
Auch in der Quantenphysik gibt es die Verbindung, dass Orts- und Impulswellenfunktionen ein Fourier-Paar bilden; solche Eigenschaften haben andere Transformationen nicht.
Aus elektrotechnischer Sicht nimmt man für die Analyse viele Systeme als linear oder nur sehr schwach nichtlinear an, und Signale sind meist ebenfalls periodisch, sodass die Fourier-Transformation naheliegt.
Faltung wird zu Multiplikation, und die zeitliche Ableitung eines komplexen Exponentialterms entspricht einer Multiplikation mit j*omega.
Multiplikation ist einfach viel angenehmer als Faltung und zeitliche Differentiation.
Wenn man akzeptiert, dass man „die Fourier-Darstellung verwendet, weil sie in einer häufigen speziellen Situation praktisch ist“, dann ist es auch nicht überraschend, für andere Probleme andere mathematische Transformationen zu verwenden.
Ich fand es immer seltsam, dass viele Vorlesungen die allgemeinere zweiseitige Laplace-Transformation nie richtig behandeln, sondern direkt von der zweiseitigen Fourier-Transformation zur einseitigen Laplace-Transformation springen.
https://en.wikipedia.org/wiki/Two-sided_Laplace_transform
Wenn man fragt, ob es ein „real existierender Ort“ ist, fällt mir ein früheres optisches Experiment ein
Wenn man ein Bild durch ein paar Linsen schickt, entsteht eine Ebene der Frequenzen, die dann durch weitere Linsen wieder auf einen Schirm projiziert wird
Wenn man einen Teil dieser Frequenzebene blockiert, verändert sich das Bild
Es war extrem heikel zu handhaben, und ich empfinde große Dankbarkeit gegenüber Dr. Bruce Sinclair aus St Andrew’s
Die Arbeit im physikalischen Labor lässt einen sehen, wie Dinge funktionieren, aber wenn man einige Monate nach dem Experiment die Theorie wieder anschaut, fühlt man sich ziemlich verloren
Daher scheint es zu kommen, dass die Apertur die Auflösung begrenzt und bei Spiegelteleskopen Beugungsspitzen entstehen
Schlieren funktioniert ebenfalls so
Eine weitere interessante Verallgemeinerung der DFT ist die Lomb-Scargle-Transformation
Sie erfordert im Zeitbereich keine festen Messintervalle
Sie wird oft verwendet, um die Frequenz periodischer Signale zu finden, wenn die Messabstände nicht konstant sind, etwa in der Astrophysik
https://iopscience.iop.org/article/10.3847/1538-4365/aab766 ist eine allgemeine Einführung, und https://docs.astropy.org/en/stable/timeseries/lombscargle.ht... erklärt gut, wie man es in der Python-Bibliothek astropy verwendet
Auto-Scaling kann zwar dabei helfen, ausfallbedingte Leistungseinbrüche zu vermeiden, sagt einem aber nicht, wie hoch das Jahresbudget sein sollte und warum
Allerdings lassen sich Prometheus-Daten kaum als wirkliches Abtastintervall ansehen
Selbst wenn jede Maschine in einem Cluster in festen Abständen meldet, sind sie nicht miteinander synchronisiert
Aus einer anderen Perspektive kann man die Cochlea als eine „reale“ Implementierung einer Fourier-Transformation betrachten
https://www.britannica.com/science/sound-physics/The-ear-as-...
Sie transformiert zwar in den Frequenzbereich, führt aber keine Fourier-Transformation aus und approximiert sie auch nicht
Die Zeit→Frequenzbereich-Transformation, die die Cochlea „implementiert“, ist eher einer Wavelet-Transformation ähnlich
Die Cochlea als Fourier-Transformation zu deuten, ist ein ähnlicher Fehler wie zu denken, dass die Zapfen im Auge nur auf rotes, grünes und blaues Licht reagieren
Tatsächlich reagiert jede Zelle unterschiedlich über einen bestimmten Frequenzbereich hinweg
Zapfen haben ihre Maxima in niedrigen, mittleren und hohen Frequenzbereichen und fallen zu beiden Seiten ab, während die Haarzellen der Cochlea eher wavelet-artige Antwortkurven mit einem zweiten Peak bei Harmonischen der Spitzenfrequenz haben
Ich bin kein Experte, nur ein begeisterter Amateur, und hoffe, dass jemand mit mehr Wissen mich korrigiert
An der Universität hatten wir ein Problem damit, dass sich unsere Stammzelllinie zu Knochen differenzierte, und es stellte sich heraus, dass die Steifigkeit der Umgebung ein Signal war, das Stammzellen wahrnehmen können
Die harte Kulturschale sagte den Zellen gewissermaßen, dass sie zu Knochenzellen werden sollten
Im Artikel hieß es: „Ich kenne keinen eleganteren Algorithmus, um die Zeilen einer Hadamard-Matrix nach Sequency zu sortieren, als die Zahl der Nulldurchgänge zu zählen“, aber ich habe beim Betrachten der Matrix ein Muster vermutet, und es stellte sich heraus, dass die Methode bereits bekannt war
Laut https://en.wikipedia.org/wiki/Walsh_matrix erhält man die Sequency-Sortierung einer Walsh-Matrix, indem man auf eine Hadamard-Matrix zuerst die Bit-Reversal-Permutation und danach die Gray-Code-Permutation anwendet
Der Artikel stellt eine sehr allgemeine und philosophische Frage, sagt dann aber später, dass der Frequenzbereich nicht besonders speziell sei, weil man andere orthogonale Basen und Transformationen finden könne
Trotzdem halte ich den Frequenzbereich und die Fourier-Transformation für spezieller als viele andere Transformationen
Weil man sie in der Natur direkt beobachten kann
Eine Linse führt zum Beispiel die zweidimensionale Fourier-Transformation eines auf parallelem Licht getragenen Eingangsbildes aus, und man kann das auf einem Schirm sehen
Außerdem kann man die Ausgabe eines Gitters oder Prismas auf ein CCD projizieren, um die Wellenlänge oder Frequenz des Lichts zu messen; auch das ist eine direkte Messung des Frequenzbereichs
Ähnliche Messungen sind auch bei HF-Wellen möglich
Sinuswellen sind insofern besonders, als sie natürliche Lösungen der Helmholtz-Wellengleichung sind
Rechteckwellen haben zudem andere Probleme wie unendliche Energie
Dieser Artikel mag für Mathematiker oder Informatiker Sinn ergeben, verfehlt aber die grundlegende Physik von Klang und Wellen
Das physikalische Ergebnis ist wahrscheinlich eine Folge dieser Eigenschaft
Letztlich besteht eine der zentralen Lehren der modernen Mathematik darin, dass es nützlich ist, Dinge aus mehreren Perspektiven zu betrachten
Extrem viele physikalische Objekte sind harmonische Oszillatoren, und das hat in der Physik eine ziemlich fundamentale Grundlage
Mir fallen auch viele andere Bereiche ein, in denen Fourier-Analyse sinnvoll ist, aber Sinuswellen sind physikalisch „realer“, und die Aussage, dass man alles mit irgendeiner Basis darstellen kann, ist eher die „gültigere“
Das Wort „real“ scheint das Gefühl zu vermitteln, dass hinter dem Phänomen ein tatsächlicher Oszillator steht
Rechteckwellen sind wegen der Unstetigkeiten sowohl im Signal als auch in seiner Ableitung weniger physikalisch, und die Natur mag Unstetigkeiten wirklich nicht
Das Gibbs-Phänomen ergibt sich zum Beispiel ganz natürlich aus der inversen Fourier-Transformation einer Frequenzantwort, die alle Frequenzen oberhalb einer bestimmten Grenzfrequenz auf 0 setzt
Ich frage mich, wie der Frequenzbereich einer Rechteckwelle das Gibbs-Phänomen erklären würde
Vermutlich würden Harmonische der Grundfrequenz der Rechteckwelle auftauchen, so als wäre das System nichtlinear
Während des Physik- und Mathematikstudiums im Grundstudium kam ich zu dem Schluss, dass es äquivalent ist, die Werte einer Funktion f(x) für unendlich viele x zu kennen oder die Frequenzkomponenten von f für unendlich viele Frequenzen zu kennen
Philosophisch sind beide Darstellungen gleichermaßen „real“
Manche Probleme lassen sich in der einen Darstellung einfach leichter lösen als in der anderen
Der Wechsel vom Zeitbereich in den Frequenzbereich ist wie ein Koordinatensystemwechsel
Ein Signal mit einem einzelnen schmalen Peak im Zeitbereich lässt sich durch ein einziges Delta an der Peak-Position sehr klein und spärlich darstellen, aber im Frequenzbereich ergibt sich keine so komprimierte Darstellung
Umgekehrt ist ein Sinussignal im Zeitbereich dort nicht compact, im Frequenzbereich genügen jedoch ein paar Deltas
Zeit und Frequenz sind zwei Arten, dieselbe Sache darzustellen; in manchen Fällen ist der eine Bereich einfacher, in anderen der andere
Man kann beweisen, dass etwas, das im Zeitbereich beschränkt ist, im Frequenzbereich unbeschränkt wird, und umgekehrt gilt das ebenso
Deshalb breitet sich etwas, das in einem Bereich compact ist, im anderen Bereich immer aus
In der Quantenmechanik sind Ort und Impuls wie Zeit und Frequenz oben konjugierte Variablen, sodass bei beschränktem Ort der Impuls unbeschränkt ist und umgekehrt
Das ist die Kernidee des Heisenbergschen Unschärfeprinzips