Lokale Maxima einer FFT finden (FPGA geeignet)

[Burkhard (Gast)]

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.

[Egon D. (Gast)]

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).

[Hp M. (nachtmix)]

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

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

[Weltbester FPGA-Pongo (Gast)]

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.

[Burkhard (Gast)]

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.

[Mark W. (kram)]

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.

[Rechenfreak (Gast)]

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.

[Jürgen S. (engineer)]

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.

[Jürgen S. (engineer)]

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.