Forum: Digitale Signalverarbeitung / DSP / Machine Learning Was genau macht man beim Radix-2 Verfahren


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Dieter A. (diycpuguy)


Bewertung
0 lesenswert
nicht lesenswert
Guten Tag, ich beschäftige mich seit längerer Zeit mit der Diskreten 
Fourier Transformation. Ich habe diese in Octave und Python umgesetzt, 
und jetzt möchte ich einen schritt weitergehen. Ich möchte die FFT, 
genauer den Coley-Tukey Algorithmus oder auch Radix-2 Verfahren genauer 
verstehen und auch mal programmieren.

Bei der Diskreten Fourier Transformation ist es ja so, das man sich eine 
Matrix mit verschiedenen Gewichtungen erstellt, und dann einfach das 
Audio mit der Matrix multipliziert und dann einfach Integriert. Dann hat 
man schon den Plot mit den Frequenzen.

Was ich bisher zur Fast Fourier Transformation verstanden habe:
-Das Audio muss Samples mit der Anzahl von einem Exponenten von 2 haben, 
damit man es dann bis zum Faktor zwei zerlegen kann.
-Man versucht sich anscheinend die Symetrie der Gewichtungen zu nutze zu 
machen
-Zuerst wird zwischen Geraden und Ungeraden Zahlen getrennt.

Was ich nicht verstehe ist was man jetzt machen muss, damit man am Ende 
die Frequenzen hat. Im Internet findet man überall solche Grafiken mit 
sich Überkreuzenden Pfeilen, ich verstehe die aber nicht.

Könnte mir das hier jemand erläutern?

Und noch ein Hinweis: Ich habe die Frage schon in einem anderen Forum 
gestellt, und mir wurde ohne Grund (also die wussten nicht mal wie weit 
ich überhaupt bin) geschrieben das ich auf einem höheren Mathematischen 
Niveau sein muss,und dann vertehe ich es. Mathematisch bin ich aber sehr 
wohl auf einem Niveau das ausreichend ist das zu verstehen. Ich habe 
auch die Diskrete Fourier Transformation verstanden. Ich frage nur weil 
mir im Internet überall nur die Formeln hinterhergeschmissen werden und 
nicht ausreichend genug erläutert werden.

: Bearbeitet durch User
von Bernd (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Dieter A. schrieb:
> Ich frage nur weil
> mir im Internet überall nur die Formeln hinterhergeschmissen werden und
> nicht ausreichend genug erläutert werden.
Das Internet ersetzt (noch) keine Bücher.

Ich habe festgestellt, das die englischen Wikipedia-Artikel oft 
ergiebiger sind, was solche Informationen angeht:
https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm#Idea

von Felix U. (ubfx)


Bewertung
0 lesenswert
nicht lesenswert
Dieter A. schrieb:
> Ich habe
> auch die Diskrete Fourier Transformation verstanden. Ich frage nur weil
> mir im Internet überall nur die Formeln hinterhergeschmissen werden und
> nicht ausreichend genug erläutert werden.

Wenn du die DFT verstanden hast, verstehe ich deine Frage nicht. Die 
Butterfly-Struktur geht direkt aus der DFT-Summe hervor wenn man sie 
entsprechend ihrer Phasenterme zerlegt hat.

von Egon D. (egon_d)


Bewertung
1 lesenswert
nicht lesenswert
Dieter A. schrieb:

> -Man versucht sich anscheinend die Symetrie der
>  Gewichtungen zu nutze zu machen

Ja.
Für das Verständnis wichtig ist die Tatsache, dass sich
bei der Sinus- wie bei der Kosinusfunktion stets die Werte
in der "ersten" Halbwelle (0..pi) nur im Vorzeichen von den
um Pi verschobenen Werten der "zweiten" Halbwelle (pi..2pi)
unterscheiden.

Das hat die Folge, dass man die Reihenfolge von Multiplikation
und Addition vertauschen darf: Man darf ERST beide Werte
addieren (okay.. eigentlich: subtrahieren) und DANN gemeinsam
mit dem Koeffizienten multiplizieren (oder eben auch nicht).


> -Zuerst wird zwischen Geraden und Ungeraden Zahlen getrennt.

Stopp.
Das ist die (übliche) Variante "decimation in time". Ich
persönlich finde diese Herleitung ABSOLUT unverständlich;
ich habe mich mit "decimation in frequency" (was immer das
heißt) befasst.

Bei letzterer wird jede Teilfolge immer in eine erste und
eine zweite Hälfte aufgeteilt, was aufgrund der Eigenschaft,
dass sich erste und zweite Hälfte der "Mischfrequenz" nur im
Vorzeichen unterscheiden, leicht verständlich ist.


> Was ich nicht verstehe ist was man jetzt machen muss,
> damit man am Ende die Frequenzen hat. Im Internet findet
> man überall solche Grafiken mit sich Überkreuzenden
> Pfeilen,

Richtig. :)


> ich verstehe die aber nicht.
>
> Könnte mir das hier jemand erläutern?

Das ist leider Stoff für ein ganzes Buch.

Meine Ratschläge im Telegrammstil:

1. Mache Dir gründlich klar, was die Additionstheoreme der
   Winkelfunktionen (sin, cos) besagen. Beachte die
   verschiedenen Varianten (sin*sin, cos*cos, sin*cos, ...)

2. Mache Dir den Zusammenhang zwischen "Mischung" (im HF-
   technischen Sinne) und der Multiplikation klar.

3. Befasse Dich AUSFÜHRLICH mit dem Prinzip des I/Q-Mischers.

4. Man kann jetzt die FFT als Abfolge von einzelnen Durchgängen
   auffassen; bei jedem Durchgang werden einerseits nur Werte
   durch Addition zusammengefasst und andererseits Werte durch
   Multiplikation gemischt.

Das reine Addieren von Punkten lässt sich auch als Mischung mit
der Frequenz "0.0" auffassen (Gleichspannung).

Es passiert also folgendes: Im ersten Durchgang werden die
Messpunkte im Zeitbereich mit Gleichspannung und mit der
Frequenz "1.0" gemischt. Es entstehen zwei Teilfolgen, die
jeweils die Hälfte des Speichers einnehmen. (Das klappt ohne
Informationsverlust, weil sich erste und zweite Halbwelle
der Mischfrequenz nur im Vorzeichen unterscheiden.)

Im zweiten Schritt wird mit den Frequenzen "0.0" und "2.0"
gemischt -- ABER es wird jedes mit jedem kombiniert. Es
entstehen VIER Teilfolgen, die jeweils ein Viertel des
Speichers einnehmen:
- Im ersten Viertel wurde "0.0" mit "0.0" gemischt; das gibt
  "0.0" -- also den neuen Gleichanteil.
- Im zweiten Viertel wurde "0.0" mit "2.0" gemischt, das
  gibt die Zwischenergebnisse für die Frequenz "2.0".
- Im dritten Viertel wurde "1.0" mit "0.0" gemischt, das gibt
  "1.0". Das sind die Zwischenergebnisse für die Frequenz "1.0".
- Im vierten Viertel wurde "1.0" mit "2.0" gemischt, das gibt
  "3.0". Das sind die Zwischenergebnisse für die Frequenz "3.0".

Man kann erkennen, dass in jedem Durchgang einerseits die alten
Zwischenergebnisse einfach weitergereicht werden (Mischung mit
"Gleichspannung"), andererseits werden auch alle alten Zwischen-
ergebnisse mit der neuen nächsten Zweierpotenz gemischt. Die
Mischfrequenzen sind also:

0000000011111111    Mischfrequenz 1
0000222211113333    Mischfrequenz 2
0044226611553377    Mischfrequenz 4
084C2A6E195D3B7F    Mischfrequenz 8

Der Algorithmus ist beendet, wenn je Frequenz nur ein (komplexer)
Wert übrig ist.


> Und noch ein Hinweis: Ich habe die Frage schon in einem anderen
> Forum gestellt, und mir wurde ohne Grund (also die wussten nicht
> mal wie weit ich überhaupt bin) geschrieben das ich auf einem
> höheren Mathematischen Niveau sein muss, und dann vertehe ich es.

Diese Diskussion ist nicht zielführend.

Für mich ist nicht der Beweis entscheidend, DASS es funktioniert --
ich möchte ein intuitives Verständnis dafür bekommen, WARUM es
funktioniert.

von Egon D. (egon_d)


Bewertung
0 lesenswert
nicht lesenswert
Felix U. schrieb:

> Dieter A. schrieb:
>> Ich habe
>> auch die Diskrete Fourier Transformation verstanden. Ich
>> frage nur weil mir im Internet überall nur die Formeln
>> hinterhergeschmissen werden und nicht ausreichend genug
>> erläutert werden.
>
> Wenn du die DFT verstanden hast, verstehe ich deine Frage
> nicht.

Dich erwartet der Schock Deines Lebens.


> Die Butterfly-Struktur geht direkt aus der DFT-Summe hervor
> wenn man sie entsprechend ihrer Phasenterme zerlegt hat.

Das mag sein -- aber was als bekannte und offensichtliche
Grundtatsache vorausgesetzt werden kann, variiert von Mensch
zu Mensch.

von W.S. (Gast)


Bewertung
1 lesenswert
nicht lesenswert
Felix U. schrieb:
> Wenn du die DFT verstanden hast, verstehe ich deine Frage nicht. Die
> Butterfly-Struktur geht direkt aus der DFT-Summe hervor wenn man sie
> entsprechend ihrer Phasenterme zerlegt hat.

Und ich verstehe dein Unverständnis nicht. Also der TO hat es kapiert, 
wie man die Elemente des Eingangsfeldes umordnet (Indexinversion) oder 
sich selbst rekursiv aufruft, so daß man in jeder Stufe jeweils ein Odd 
und ein Even Feld hat, bis man ans Ende gelangt. Nun fragt er, wie zum 
Kuckuck es dann weitergeht und wie er aus all dem das Feld mit den 
finalen Frequenzanteilen tatsächlich erhält.

Diese Frage ist doch verständlich!

Also erzähle ihm, was er denn in irgend einer existierenden 
Programmiersprache tun muß. All die grandiosen Pseudo-Codes sind ihm 
nämlich auch bloß genauso unverständlich wie die rein mathematische 
Darstellung.

Ich sehe das als ein allgemeines Übel an: Die Mathematiker, die damit 
tagtäglich umgehen, meinen, es sei ja alles derart trivial, daß man es 
gar nicht erklären muß. Kalauer: "den Löwen zu fangen, wenn er sich 
zuletzt im Einheitsfeld[x,y] befindet und dort nicht mal ne Pfote rühren 
kann, überlasse ich den Studenten als Übungsaufgabe für daheim".

Vielleicht würde es helfen, wenn man sie zwänge, all das auch mal auf 
Botokudisch oder Sanskrit zu formulieren, aber OHNE jegliche 
Sonderzeichen. Kurzum: Wer einem Programmierer erklären will, wie man 
eine FFT schreibt, der hat dazu eine Programmiersprache zu wählen - 
sonst bleibt er unverstanden.

Ich möchte mal den Mathematiker sehen, der es versteht, wenn ich ihm den 
CORDIC in PIC-Assembler erkläre, ohne Kommentare und ohne ihm dazu 
irgend ein mathematisches Pendant zu den Assemblerzeilen zu geben.

W.S.

von Egon D. (egon_d)


Bewertung
1 lesenswert
nicht lesenswert
W.S. schrieb:

> Die Mathematiker, die damit tagtäglich umgehen,
> meinen, es sei ja alles derart trivial, daß man
> es gar nicht erklären muß.

Nein. Mathematiker betreiben Mathematik, d.h. sie
BEWEISEN mathematische Aussagen.

Nichtmathematiker wenden die Mathematik an, d.h. sie
RECHNEN.

Das ist ein ähnlicher Unterschied wie der zwischen
Jurist und Kaufmann -- oder der zwischen Gemüsezüchter
und Koch.

von Alexander S. (alesi)


Bewertung
0 lesenswert
nicht lesenswert
Dieter A. schrieb:
> Im Internet findet man überall solche Grafiken mit
> sich Überkreuzenden Pfeilen, ich verstehe die aber nicht.

W.S. schrieb:
> Also der TO hat es kapiert,
> wie man die Elemente des Eingangsfeldes umordnet (Indexinversion) oder
> sich selbst rekursiv aufruft, so daß man in jeder Stufe jeweils ein Odd
> und ein Even Feld hat, bis man ans Ende gelangt.

W.S. schrieb:
> Wer einem Programmierer erklären will, wie man
> eine FFT schreibt, der hat dazu eine Programmiersprache zu wählen

Hallo,

die FFT kann man elegant durch einen rekursiven Algorithmus beschreiben 
und mit einer funktionalen Programmiersprache implementieren (geht 
natürlich auch in einer imperativen Sprache wie C). Hier ein Beispiel in 
Scheme:
The Scheme Programming Language, Section 12.9. Fast Fourier Transform
https://scheme.com/tspl4/examples.html#./examples:h9

von Dieter A. (diycpuguy)


Bewertung
0 lesenswert
nicht lesenswert
> Diese Frage ist doch verständlich!

Richtig.

> Also erzähle ihm, was er denn in irgend einer existierenden
> Programmiersprache tun muß. All die grandiosen Pseudo-Codes sind ihm
> nämlich auch bloß genauso unverständlich wie die rein mathematische
> Darstellung.

Richtig, ich bin weder Mathematiker noch Programmierer. Meine Denkweise 
ist irgendwas dazwischen.

> Ich sehe das als ein allgemeines Übel an: Die Mathematiker, die damit
> tagtäglich umgehen, meinen, es sei ja alles derart trivial, daß man es
> gar nicht erklären muß.

Das ist zu 100% Richtig. Dann hätte ich diese Frage niemals gestellt.

> Kalauer: "den Löwen zu fangen, wenn er sich
> zuletzt im Einheitsfeld[x,y] befindet und dort nicht mal ne Pfote rühren
> kann, überlasse ich den Studenten als Übungsaufgabe für daheim".

So fühle ich mich auf Wikipedia.

> Ich möchte mal den Mathematiker sehen, der es versteht, wenn ich ihm den
> CORDIC in PIC-Assembler erkläre, ohne Kommentare und ohne ihm dazu
> irgend ein mathematisches Pendant zu den Assemblerzeilen zu geben.

Ich auch. Einfach aus Rache.

Danke für die Antwort.

von Dieter A. (diycpuguy)


Bewertung
0 lesenswert
nicht lesenswert
...

> Meine Ratschläge im Telegrammstil:
...
> Das reine Addieren von Punkten lässt sich auch als Mischung mit
> der Frequenz "0.0" auffassen (Gleichspannung).
>
> Es passiert also folgendes: Im ersten Durchgang werden die
> Messpunkte im Zeitbereich mit Gleichspannung und mit der
> Frequenz "1.0" gemischt. Es entstehen zwei Teilfolgen, die
> jeweils die Hälfte des Speichers einnehmen. (Das klappt ohne
> Informationsverlust, weil sich erste und zweite Halbwelle
> der Mischfrequenz nur im Vorzeichen unterscheiden.)
...
> - Im ersten Viertel wurde "0.0" mit "0.0" gemischt; das gibt
>   "0.0" -- also den neuen Gleichanteil.
> - Im zweiten Viertel wurde "0.0" mit "2.0" gemischt, das
>   gibt die Zwischenergebnisse für die Frequenz "2.0".
> - Im dritten Viertel wurde "1.0" mit "0.0" gemischt, das gibt
>   "1.0". Das sind die Zwischenergebnisse für die Frequenz "1.0".
> - Im vierten Viertel wurde "1.0" mit "2.0" gemischt, das gibt
>   "3.0". Das sind die Zwischenergebnisse für die Frequenz "3.0".
>
> Man kann erkennen, dass in jedem Durchgang einerseits die alten
> Zwischenergebnisse einfach weitergereicht werden (Mischung mit
> "Gleichspannung"), andererseits werden auch alle alten Zwischen-
> ergebnisse mit der neuen nächsten Zweierpotenz gemischt. Die
> Mischfrequenzen sind also:
...
> Der Algorithmus ist beendet, wenn je Frequenz nur ein (komplexer)
> Wert übrig ist.

...

Danke für die Ausführliche Antwort. Es hat mich definitiv 
weitergebracht.

von W.S. (Gast)


Bewertung
1 lesenswert
nicht lesenswert
Alexander S. schrieb:
> die FFT kann man elegant durch einen rekursiven Algorithmus beschreiben
> und mit einer funktionalen Programmiersprache implementieren (geht
> natürlich auch in einer imperativen Sprache wie C). Hier ein Beispiel in
> Scheme:

Ja, man kann zeigen, daß... gilt. Hier geht es aber nicht um die 
beweisführung, daß ein Satz gilt oder daß etwas unter den gezeigten 
Randbedingungen konvergiert.

Das Thema FFT ist ein Thema der angewandten Mathematik. Das heißt im 
Klartext, daß die Zielrichtung eben die Anwendung ist (und nicht zu 
mathematischen Beweisen) und diese Anwendung schlußendlich in einen 
Haufen Maschinencode münden muß, der auf irgend einem Stück Silizium 
funktionieren soll.

Zwischen der Denke der Mathematiker und der tatsächlichen Anwendung 
klafft noch immer eine riesige Lücke. Manche Mathematiker meinen, sie 
hätten sich bereits ausreichend den schnöden Niederungen genähert, wenn 
sie ein Stück Quelle zeigen, das für Matlab etc. gedacht ist und dort 
lediglich eine der tausend eingebauten Funktionen aufruft. Andere 
versuchen, aus dieser Lücke ein Geschäft zu machen, indem sie versuchen, 
vorübersetzte Bibliotheken (ohne Quellcode) für sowas zu verkaufen.

Aber die Lücke zwischen mathematischer Darstellung und der Praxis (in 
Form von Quellen in benutzbaren Programmiersprachen) klafft noch immer. 
Und sowas wie eine Quelle in "Scheme" ist sowas von weltfremd...

Das wirklich einzige Werk, das wenigstens ansatzweise versucht, diese 
Lücke zu schließen, ist The Scientist and Engineer's Guide to
Digital Signal Processing ( http://www.dspguide.com/ ). Dort finden sich 
wenigstens einige Beispiele in BASIC formuliert. OK, hier ist nicht der 
platz über Basic zu diskutieren, aber besser dieses als garnichts.

W.S.

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.

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