Forum: Digitale Signalverarbeitung / DSP / Machine Learning Lokale Maxima einer FFT finden (FPGA geeignet)


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 Burkhard (Gast)


Lesenswert?

Um aus einer Spektraldarstellung eines kontinuierlich einlaufenden 
Signals sogenannte Moden (Hintergrund der Idee: 
https://arxiv.org/abs/1912.00414 ) zu extrahieren, suche ich einen 
Algorithmus analog zu Matlabs findpeak-Funktion, mit dem eine 
(begrenzte) Anzahl von lokalen Maxima als "Kontrollpunkte" (mit 
Bin-Index) identifiziert werden können.

Konkreter: Es liegt das Ergebnis einer komplexen FFT (N=256 oder N=512) 
vor, für die bis zu 8 lokale Maxima gefunden werden sollen. Nur Werte 
über einem bestimmten Schwellwert sollen berücksichtigt werden und nur 
solche mit einem Mindestabstand zum nächsten zu berücksichtigenden Peak. 
Eine neue FFT liegt spätestens alle 500us vor oder kommt mit jedem 
Sample als "Sliding DFT".

Naiver Ansatz: Absolutwerte zunächst nach Größe sortieren, danach die 
mit zu geringem Abstand rausschmeissen und zuletzt die bis zu 8 größten 
herausfischen (Schwellwert berücksichtigen) - haufenweise 
Schleifenoperationen, kein Pipelining. Für eine effiziente (und vor 
allem FPGA geeignete) Implementierung fehlt mir noch die zündende Idee.

von Egon D. (egon_d)


Lesenswert?

Burkhard schrieb:

> Naiver Ansatz: Absolutwerte zunächst nach Größe sortieren,
> danach die mit zu geringem Abstand rausschmeissen und
> zuletzt die bis zu 8 größten herausfischen (Schwellwert
> berücksichtigen) -

Klingt doch gut.


> haufenweise Schleifenoperationen, kein Pipelining.

Heap verwenden (--> Heapsort).

von Hp M. (nachtmix)


Lesenswert?

Burkhard schrieb:
> Naiver Ansatz: Absolutwerte zunächst nach Größe sortieren

Nein, erst alle wegwerfen, die unterhalb der Schwelle liegen.

von Weltbester FPGA-Pongo (Gast)


Lesenswert?

Das schon die dritte naive Frage heute: Im FPGA geht nichts anders, als 
in anderen digitalen Systemen auch. Eine Sortierroutine ist wohl mit das 
Einfachste, was man tun kann zumal einiges parallel laufen kann. 
Maximasuchen mit 8 Kanälen machen bei uns die Studenten im ersten 
Praktikum.

von Burkhard (Gast)


Lesenswert?

Weltbester FPGA-Pongo schrieb im Beitrag #6248992:
> Im FPGA geht nichts anders, als in anderen digitalen Systemen auch.
Nur die vorhandenen Resourcen sehen anders aus.

>Eine Sortierroutine ist wohl mit das
> Einfachste, was man tun kann zumal einiges parallel laufen kann.
> Maximasuchen mit 8 Kanälen machen bei uns die Studenten im ersten
> Praktikum.
Für mich ist das Hobby - und manchmal bin ich deshalb dankbar, wenn mir 
jemand - wie Egon oben mit dem Stichwort "Heapsort" - auf die Sprünge 
hilft.

Inzwischen habe ich 
https://github.com/randysuen/heap_sorting/blob/master/doc/Dual%20port%20memory%20based%20heapsort%20implementation%20for%20FPGA.pdf 
auf github gefunden. Wobei ich nicht nur 8 Kanäle habe, sondern 
length(FFT) - angedacht sind 256.

von Mark W. (kram) Benutzerseite


Lesenswert?

Du kannst auch folgendermassen vorgehen:

Mittels Komparator aufeinander folgende Samples vergleichen, um die 
Peaks zu finden.
Jedes Mal wenn ein Peak erkannt wurde, den in einen Speicher schreiben. 
Dabei pruefen ob er groesser ist als die schon vorhandenen. Wenn ja, 
dann den Kleinsten ueberschreiben. So dass am Schluss die X groessten 
drin stehen.

von Rechenfreak (Gast)


Lesenswert?

Mark W. schrieb:
> Mittels Komparator aufeinander folgende Samples vergleichen, um die
> Peaks zu finden.

Um dann WAS??? zu tun? Nur die Peaks an sich repräsentieren noch nicht 
das Ergebnis, es sein denn die FFT ist sehr feinmaschig. Da muss 
weitergerechnet werden. Ich finde es zweckmäßiger, benachbarte peaks zu 
nehmen, das Ergebnis zu berechnen und diese in die Queue zu stecken.

von Jürgen S. (engineer) Benutzerseite


Lesenswert?

Mark W. schrieb:
> Jedes Mal wenn ein Peak erkannt wurde, den in einen Speicher schreiben.
> Dabei pruefen ob er groesser ist als die schon vorhandenen.

Das lässt sich auch alles im Vorbeigehen machen, wenn die Werte 
einlaufen. Einfach 8 Abfrager parallel die sortieren und sich jeweils 
den grössten merken und den kleineren nach hinten weitergeben. Die 
Abfrager haben an ihrem einen Eingang jeweils den Ausgang eines 
Vorgängers. Damit hängen nach FFT-Länge+8 Schritten alle 8 Werte soriert 
in den 8 Abfragern. brute force sozusagen.

von Jürgen S. (engineer) Benutzerseite


Lesenswert?

Raum-Moden an sich lassen sich aber auch etwas geschickter suchen. Das 
Problem der FFT ist nämlich das der zeitlichen Ausdehnung und damit 
einem variblen Zeitverlauf des Klanges über die Zeit, der die FFT 
verschmiert. Besonders bei den Bässen kommt das zum Tragen.

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]
  • [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.