Forum: Digitale Signalverarbeitung / DSP 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)


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


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


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


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


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


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


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

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.