4096-Punkte FFT mit besonders wenig Speicher.

Speichergeizkragen Gast #5455361
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!
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
Possetitjel Gast #5455404
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Speichergeizkragen Gast #5455421
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...
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Possetitjel Gast #5455426
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Speichergeizkragen Gast #5455462
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Martin S. #5479123
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
}
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren