Forum: Digitale Signalverarbeitung / DSP / Machine Learning 4096-Punkte FFT mit besonders wenig Speicher.


von Speichergeizkragen (Gast)


Lesenswert?

Hallo ihr Spezialisten.
Ich bin leider am Gebiet der digitalen Signalverarbeitung ziemlich aus 
der Übung. Daher kann es sein dass ich hier einigen mit einer "zu 
einfachen" Frage auf die Nerven gehe. Ich habe aber (schwöre bei meiner 
Ehre) anderndhalb Stunden in Google gesucht ohne eine definitive Antwort 
zu finden.
Sollte daher jemand durch meine "Dummheit" angestachelt sein mich 
niederzumachen bitte ich trotzdem zunächst den Benutzern mit 
Bereitschaft zur Hilfeleistung den Vortritt zu lassen.
Also ich habe folgende Anforderung: Mein Mikrocontroller hat noch etwa 
20kB RAM übrig mit denen muss ich eine 4096-Punkte (real) FFT (kann 
nicht kleiner sein!) durchführen. Die Quelldatenbreite sind 16bit.
Es wäre ok, wenn die Quelldaten verloren gehen, ein in-place-Algorithmus 
wäre also ok. Rechengeschwindigkeit ist zunächst nachrangig.
Leider konnte ich den genauen Speicherbedarf der verschiedenen 
Implementationen nicht so leicht finden. Zu CMSIS-DSP hab ich in einem 
Forum was gefunden:
https://ez.analog.com/thread/97376-cmsis-dsp-fft-functionality-increases-size-of-the-project-drastically
braucht doch recht viel Platz.
Kennt jemand eine Bibliothek mit wenig Speicherverbrauch, idealerweise 
eine wo man schon im vorhinein ausrechnen kann ob sich das ausgeht.
Danke im Voraus!

von Possetitjel (Gast)


Lesenswert?

Speichergeizkragen schrieb:

> Leider konnte ich den genauen Speicherbedarf der
> verschiedenen Implementationen nicht so leicht finden.

Naja, zu einer normalen Radix-2-FFT ist vom Platzbedarf
für das Programm her nicht viel dazu; das sind nur drei
geschachtelte Schleifen. Bitreversing und Umrechnung auf
Betrag/Phase geht nochmal extra, ist aber auch nicht viel.

Ein Problem könnten die Koeffizienten (Funktionswerte
der Winkelfunktionen; "komplexe Einheitswurzeln") werden;
entweder braucht man eine Fließkommabibliothek für die
Winkelfunktionen, oder man verwendet CORDIC, oder aber
man speichert die Werte tabelliert ab.
Im besten Falle muss man nur ein Viertel der Koeffizienten
speichern; das sind für eine 4096-Punkte-FFT also 1024
Werte.

von Speichergeizkragen (Gast)


Lesenswert?

Hallo  Possetitjel .
Leider fühle ich mich nicht fähig eine FFT-Funktion selber zu schreiben, 
zumindest nicht in vertretbarer Zeit.
Entsprechend werde ich eher nicht in den Koeffiziententabellen der 
Bibliotheken optimieren können...

von Possetitjel (Gast)


Lesenswert?

Speichergeizkragen schrieb:

> Leider fühle ich mich nicht fähig eine FFT-Funktion
> selber zu schreiben, zumindest nicht in vertretbarer
> Zeit.

Das hatte ich vermutet; das ging mir auch 25 Jahre lang so :)


> Entsprechend werde ich eher nicht in den Koeffiziententabellen
> der Bibliotheken optimieren können...

Naja, "selber schreiben" und "einen Blick in den Quelltext
wagen" sind ja zwei verschiedene Dinge.

Wenn die Winkelfunktionswerte bei Bedarf immer wieder neu
berechnet werden, dann ist das zwar nicht mehr wirklich "fast",
aber man braucht überhaupt keine Koeffiziententabelle -- also
fällt dafür auch kein Platzbedarf an.
Allerdings ist in diesem Falle eine Fließkommabibliothek
notwendig, die die Winkelfunktionen kennt. Das wirst Du ja
wissen, was Dir in Deiner Sprache zur Verfügung steht.

von Speichergeizkragen (Gast)


Lesenswert?

puh...
Du meinst das ist schaffbar in vertretbaren Aufwand in einer Woche sagen 
wir mit 6h Schlaf und netto 45Minuten Körperhygiene/tag?
Mir wärs recht wenns eine für den Speicherverbrauch optimierte Library 
geben würde, ist etwas verträglicher, auch für meine Umwelt.

von Jim M. (turboj)


Lesenswert?

Speichergeizkragen schrieb:
> braucht doch recht viel Platz.

Dann nimm halt den nächstgrößeren µC aus der Familie. Moderne Cortex-M 
gibts mit reichlich Flash und RAM.

Wenn man nicht grade >>10k Stück verkauft, wäre das preiswerter als eine 
Woche Entwicklungszeit.

von Bernd B. (microwave-designer)


Lesenswert?

Possetitjel schrieb:
> Im besten Falle muss man nur ein Viertel der Koeffizienten
> speichern; das sind für eine 4096-Punkte-FFT also 1024
> Werte.

... man braucht nur einen Achtel-Kreis. Überlege einmal warum.

Gruß

Bernd

von Martin S. (strubi)


Lesenswert?

Moin,

die Frage ist nicht dumm, geht nämlich schon in Details die man 
typischerweise im Studium nicht lernt.
Offene Libraries dazu sind mir ausser der fftw und div. 
DSP-Implementierungen nicht bekannt, ich fürchte, du musst dich in die 
Materie etwas reingraben. An Tricksereien diesbezüglich fällt mir 
folgendes ein:

- Sliding DFT
- Partielle FFT
- Realdaten-Packing (Eingangs-Analogdaten ohne Imaginäranteil)
- Auf Radix 4 gehen (Preisfrage: Warum geht hier Radix 8 nicht..)

Sollten einige Papers (englisch) zu finden sein.

Realdaten-Packen geht mit Standard-Libs a la:
1
/*----------------------------------------------
2
 * FFT fuer Realdaten; packt diese in ein  
3
 * komplexes Array          
4
 * n: Anzahl Werte            i
5
 */
6
7
void fftreal(FFT_FLOAT *r, FFT_COMPLEX *c, int n) 
8
{
9
  int i;
10
11
  for (i = 0; i < (n >> 1); i++)
12
  {
13
    c[i]->re = *(r++);
14
    c[i]->im = *(r++);
15
  }
16
17
  fftrow(c);
18
  fftunscramble(c);
19
  fftrealtran(c, n); 
20
}

: Bearbeitet durch User
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.