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


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


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


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


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


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


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


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


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


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

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.