Elm-Chans FFT-Routinen verstehen?

[AVRli .. (avrli)]

Hallo,

ich habe ein Verständnisproblem mit dem Beispiel zu den FFT-Routinen von 
Elm-Chans.

http://elm-chan.org/works/akilcd/report_e.html

In dem ZIP gibt es die Datei "fftest.c" welche ich hier mal unten als 
Code einfüge.

Die ADC Werte befinden sind auf der halbe Betriebsspannung.
Eine Wechselspannung von -2,5V - 0V - +2,5V
wird als 0 - 512 - 1024 eingelesen.


Jetzt taucht in dem Beispiel immer wieder der Wert 32768 auf, was 
passiert da? Ich nehme an das es sehr wichtig ist für die korrekte 
Weiterverarbeitung, doch ich verstehe nicht ganz was da genau passiert 
und warum.

Grüße AVRli...

/*------------------------------------------------*/
/* FFTEST : A test program for FFT module         */

#include <avr/io.h>
#include <avr/pgmspace.h>
#include "suart.h"    /* Defs for using Software UART module (Debugging via AVRSP-COM) */
#include "ffft.h"    /* Defs for using Fixed-point FFT module */

#define  SYSCLK    16000000



/*------------------------------------------------*/
/* Global variables                               */

char pool[16];  /* Console input buffer */

int16_t capture[FFT_N];      /* Wave captureing buffer */
complex_t bfly_buff[FFT_N];    /* FFT buffer */
uint16_t spektrum[FFT_N/2];    /* Spectrum output buffer */



/*------------------------------------------------*/
/* Capture waveform                               */

void capture_wave (int16_t *buffer, uint16_t count)
{
  ADMUX = _BV(REFS0)|_BV(ADLAR)|_BV(MUX2)|_BV(MUX1)|_BV(MUX0);  // channel

  do {
    ADCSRA = _BV(ADEN)|_BV(ADSC)|_BV(ADFR)|_BV(ADIF)|_BV(ADPS2)|_BV(ADPS1);
    while(bit_is_clear(ADCSRA, ADIF));
    *buffer++ = ADC - 32768;
  } while(--count);

  ADCSRA = 0;
}


/* This is an alternative function of capture_wave() and can omit captureing buffer.

void capture_wave_inplace (complex_t *buffer, uint16_t count)
{
  const prog_int16_t *window = tbl_window;
  int16_t v;

  ADMUX = _BV(REFS0)|_BV(ADLAR)|_BV(MUX2)|_BV(MUX1)|_BV(MUX0);  // channel

  do {
    ADCSRA = _BV(ADEN)|_BV(ADSC)|_BV(ADFR)|_BV(ADIF)|_BV(ADPS2)|_BV(ADPS1);
    while(bit_is_clear(ADCSRA, ADIF));
    v = fmuls_f(ADC - 32768, pgm_read_word_near(window));
    buffer->r = v;
    buffer->i = v;
    buffer++; window++;
  } while(--count);

  ADCSRA = 0;
}
*/

/*------------------------------------------------*/
/* Online Monitor via an ISP cable                */

int main (void)
{
  char *cp;
  uint16_t m, n, s;
  uint16_t t1,t2,t3;


  DDRE = 0b00000010;  /* PE1:<conout>, PE0:<conin> in N81 38.4kbps */
  TCCR1B = 3;  /* clk/64 */

  xmitstr(PSTR("\r\nFFT sample program\r\n"));

  for(;;) {
    xmitstr(PSTR("\r\n>"));      /* Prompt */
    rcvrstr(pool, sizeof(pool));  /* Console input */
    cp = pool;

    switch (*cp++) {  /* Pick a header char (command) */
      case '\0' :    /* Blank line */
        break;

      case 'w' :    /* w: show waveform */
        capture_wave(capture, FFT_N);
        for (n = 0; n < FFT_N; n++) {
          s = capture[n];
          xmitf(PSTR("\r\n%4u:%6d "), n, s);
          s = (s + 32768) / 1024;
          for (m = 0; m < s; m++) xmit(' ');
          xmit('*');
        }
        break;

      case 's' :    /* s: show spectrum */
        capture_wave(capture, FFT_N);
        TCNT1 = 0;  /* performance counter */
        fft_input(capture, bfly_buff);
        t1 = TCNT1; TCNT1 = 0;
        fft_execute(bfly_buff);
        t2 = TCNT1; TCNT1 = 0;
        fft_output(bfly_buff, spektrum);
        t3 = TCNT1;
        for (n = 0; n < FFT_N / 2; n++) {
          s = spektrum[n];
          xmitf(PSTR("\r\n%4u:%5u "), n, s);
          s /= 512;
          for (m = 0; m < s; m++) xmit('*');
        }
        xmitf(PSTR("\r\ninput=%u, execute=%u, output=%u (x64clk)"), t1,t2,t3);
        break;

      default :    /* Unknown command */
        xmitstr(PSTR("\n???"));
    }
  }
}

[Sascha W. (sascha-w)]

Hallo,

ohne den Code jetzt genau durchgeschaut zu haben gehe ich mal von 
folgendem aus:
Der Code benutzt 16-Bit Integer -> damit verwendet man 32768 um den 
Nullpunkt in die "Mitte" der 16-Bit zu verschieben und so die 
Berechnugen unsigned durchführen zu können.

Sascha

[Thomas E. (picalic)]

AVRli .. schrieb:
> Jetzt taucht in dem Beispiel immer wieder der Wert 32768 auf, was
> passiert da?

das ist in Bezug auf eine 16-Bit unsigned Integer Zahl das, was bei 
Deinem 10-Bit AD-Wandler Wert die 512 ist, nämlich genau die Mitte.

[AVRli .. (avrli)]

Danke für die Erklärung aber ganz so klar ist es mir noch nicht.
Mir fehlt die Vorstellung was bei dem rechnen mit den Typen unsigned und 
signed eigentlich passiert.

Die FFT Berechnung erfolgt in ASM und das sicher als unsigned, ich 
wundere mich das der Buffer als signed deklariert ist.

Der Buffer im Beispiel in dem die ADC Werte gespeichert werden ist vom 
Typ

int16_t (-32768 bis 32768).

Abgelegt wird der Wert darin im Beispiel mit...

*buffer++ = ADC - 32768

U ADC Pin  ADC    Buffer Wert
-2,5V    0    - 32768
0V    512    - 32256
+2,5V    1023    - 31745

betrachtet man die Buffer Werte sind die immer negativ obwohl 1023 am 
ADC doch einen positiven Wert erzeugen sollte...?

[Thomas E. (picalic)]

AVRli .. schrieb:
> Danke für die Erklärung aber ganz so klar ist es mir noch nicht.
> Mir fehlt die Vorstellung was bei dem rechnen mit den Typen unsigned und
> signed eigentlich passiert.

Der Unterschied liegt in der Interpretation der Zahlen:
0xFFFF wird bei int16_t als -1 interpretiert, bei uint_16t bedeutet 
0xFFFF aber 65535. (int16_t)0x8000 ist -32768, (uint16_t)0x8000 ist 
32768.
Und 0x7FFF ist in beiden Fällen 32767.

Ich vermute mal, daß die FFT-Routinen von einem linksbündigen AD-Wert 
ausgehen, d.h. Du müsstest Deine AD-Samples erstmal (durch *64 bzw. 6x 
Linksschieben) auf 16 Bit Zahlenbereich hochskalieren.

[Georg G. (df2au)]

AVRli .. schrieb:
> ADMUX = _BV(REFS0)|_BV(ADLAR)|_BV(MUX2)|_BV(MUX1)|_BV(MUX0);  //
> channel

ADLAR ist "left adjust". Und damit geht der AD Wandler von -32768 bis + 
32767. Ist es wirklich so schwer, ein Datenblatt zu lesen?

[M. K. (sylaina)]

Georg G. schrieb:
> AVRli .. schrieb:
>> ADMUX = _BV(REFS0)|_BV(ADLAR)|_BV(MUX2)|_BV(MUX1)|_BV(MUX0);  //
>> channel
>
> ADLAR ist "left adjust". Und damit geht der AD Wandler von -32768 bis +
> 32767. Ist es wirklich so schwer, ein Datenblatt zu lesen?

Nein, das ist nicht so schwer aber das sieht nicht jeder gleich dass a. 
der AD-Wandler auf "left Adjust" steht und b. die 32768 genau damit zu 
tun haben.

[AVRli .. (avrli)]

Thomas E. schrieb:
> Der Unterschied liegt in der Interpretation der Zahlen:

Danke, das Umdenken in die verschiedenen Bereiche fällt mir noch sehr 
schwer.


Georg G. schrieb:
> ADLAR ist "left adjust". Und damit geht der AD Wandler von -32768 bis +
> 32767.

Da kommt für mich was absolut neues in's Spiel: "left adjust"


Michael K. schrieb:
> ...aber das sieht nicht jeder gleich dass
> a. der AD-Wandler auf "left Adjust" steht und
> b. die 32768 genau damit zu tun haben.

Ganz richtig und ich muß nun erstmal verstehen warum man diesen Weg 
gegangen ist. Es kommt zwar ein Ergebnis aus der FFT heraus aber das ist 
sehr unruhig und es sieht eher zufällig aus als das es die einzelnen 
Spektren entspricht.

Dazu kommt das man nicht erfährt ob im Beispiel nur positive Spannungen 
am ADC Eingang anliegen oder dort auch +/- anliegen darf.

Gruß AVRli...

[M. K. (sylaina)]

AVRli .. schrieb:
> Dazu kommt das man nicht erfährt ob im Beispiel nur positive Spannungen
> am ADC Eingang anliegen oder dort auch +/- anliegen darf.

Das ist wiederum im Datenblatt beschrieben: Negative Spannungen dürfen 
am ADC-Eingang schlicht nicht anliegen. Ab ca. -0.7V "pfuscht" dir dann 
eh die Schutzdiode dazwischen und ab 0V und kleiner ist für den ADC eh 
alles 0, macht also keinen Unterschied.

AVRli .. schrieb:
> Ganz richtig und ich muß nun erstmal verstehen warum man diesen Weg
> gegangen ist.

Ich denke mal, das liegt daran dass man dann den Kram auch schnell auf 8 
bit umstricken kann. Zumindest die Sample-Daten hat man so quasi schon 
als 8 bit vorliegen (nur ADCH auslesen). Ich könnte mir vorstellen, dass 
man den Code erst für 8 bit entwickelt hat und es dann auf 16 bit 
aufgebohrt hat.

AVRli .. schrieb:
> Es kommt zwar ein Ergebnis aus der FFT heraus aber das ist
> sehr unruhig und es sieht eher zufällig aus als das es die einzelnen
> Spektren entspricht.

Könnte auch an deinem Aufbau liegen. Die Routinen benutze ich selbst 
auch (mache derzeit damit eine FFT auf 50 kHz Signale) und die sind 
definitiv stabil. Am Aufbau muss natürlich alles perfekt sein. Vom 
Messeingang bis zur Referenzquelle des ADCs.

[AVRli .. (avrli)]

Hallo,

ich bin das ganze nochmal durchgegangen und es hat in jedem Fall mit dem 
"left adjust" zu tun!

Nun läuft es wesentlich besser, wenn nicht sogar richtig! ;-)

Mit dem "left adjust" stehe ich aber noch voll auf dem Abstellgleis.
Ich habe mir mal einen Poti an einen weiteren Eingang gelötet um zu 
sehen was da passiert.

U      Right Adjust Left Adjust
0V     0x0000       0x0000
2,5V   0x0200       0x8000
5V     0x03FF       0xFFC0

"Right Adjust" kann ich nachvollziehen, bei "Left Adjust" kann ich 
lediglich erkennen das die halbe Spannung wirklich genau die "ominösen" 
0x8000 (32768) als Wert erzeugen. Dabei hat sich sicher einer was 
gedacht, nur was?

Gruß AVRli...

[Jonas B. (jibi)]

Bit                 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
10 Bit Left adjust: ^^^^^^^^^^^^^^^^^^^^^^^^^
10 Bit Right adjust:            ^^^^^^^^^^^^^^^^^^^^^^^^^

Bei left adjust, steht dein Wert in den Bits 15-6, bei Right adjust eben 
bei 11-0. Beim Auslesen muss man das eben beachten ;)

Gruß J

[M. K. (sylaina)]

AVRli .. schrieb:
> Mit dem "left adjust" stehe ich aber noch voll auf dem Abstellgleis.

Das benutzt man eigentlich nur wenn man beim ADC nur mit 8 bit arbeiten 
will. Man liest dann nur das ADCH-Register aus. (siehe z.B. AVR125)
Wie schon gesagt, ich denke der Code war ursprünglich nur als 8 bit 
geplant und wurde dann später auf 16 bit aufgebohrt. Vielleicht wollte 
man auch das Zweierkomplement ausnutzen, ich mein da mal was gelesen zu 
haben, dass da ein gesetztes ADLAR auch einen Vorteil haben kann. Weiß 
aber leider nicht mehr wo ich das gelesen habe.

However, die Routinen von Elm-Chan funktionieren auch mit ADLAR == 0. 
Den Assemblerzeilen ist das wurscht woher die Daten kommen.

[AVRli .. (avrli)]

Jonas B. schrieb:
> Bei left adjust, steht dein Wert in den Bits 15-6, bei Right adjust eben
> bei 11-0. Beim Auslesen muss man das eben beachten ;)

Das kann ich mir nun gut vorstellen, danke!


Michael K. schrieb:
> However, die Routinen von Elm-Chan funktionieren auch mit ADLAR == 0.
> Den Assemblerzeilen ist das wurscht woher die Daten kommen.

Bei mir ist es viel schärfer wenn ADLAR gesetzt ist und man die 0x8000 
Konvertierung macht. Ist es nicht gesetzt dann habe ich ordentliche 
"Dreckeffekte".

Gruß AVRli...

[M. K. (sylaina)]

AVRli .. schrieb:
> Bei mir ist es viel schärfer wenn ADLAR gesetzt ist und man die 0x8000
> Konvertierung macht. Ist es nicht gesetzt dann habe ich ordentliche
> "Dreckeffekte".

Hm, dann hast du ggf. ein Problem. Elm-Chans FFT-Routinen machen 16 bit 
FFT und woher die Daten kommen stört das nicht. Schau dir mal die 
Assemblerzeilen genau an.
Ich denke eher: mit dem Left-Adjust werden die "kleineren Schwingungen" 
mehr gedämpft, sprich mit dem Right-Adjust siehst du mehr von dem was 
wirklich da ist.

Baue dir einfach mal zwei Eingangsfolgen. Die erste Folge seien 
Zufallszahlen von 0 bis 1023. Die zweite Folge sei lediglich die erste 
Folge mit einem LeftShift von 2 bit. Die FFT sollte hier, normiert auf 
die jeweils maximale Amplitude, exakt das selbe Spektrum ergeben. 
Zumindest ist das bei meiner FFT mit meinem Testaufbau der Fall. Da ist 
es egal ob ich ADLAR == 0 oder ADLAR == 1 habe, das Ergebnis der FFT ist 
immer das Selbe. Meine FFT (N=128) ist dabei auf VRef (LT1021-5) 
"normiert", Bilder dazu im Anhang. Lief auf einem Atmega32, Sinus war 
auf ca. 2 Vpp eingestellt, Offsetspannung bei ca. 3 VDC. Einen 
Unterschied sehe ich nicht…OK, das Display bzw. meine Zeichenfläche 
skaliert das auch auf ~6 bit runter ("nur" 50 Pixel ist der Graph hoch). 
Sollte mir mal ne serielle Schnittstelle dran bauen und mir das Spektrum 
zum PC übertragen lassen.

[Ingo Less (Gast)]

Du tastest einen 20kHz Sinus mit 9,6kHz ab???

[Michael (Gast)]

Nein, ich taste einen 20 kHz Sinus mit ca. 115 kHz ab. Habe einen 12 MHz 
Quarz am Atmega und lasse den ADC mit 1.5 MHz laufen. Da hier für die 
Anzeige grad mal 6 bit erforderlich sind brauch ich auf die 200 kHz 
keine Rücksicht nehmen da die ja nur für full Resulution erforderlich 
sind. Der Aufbau ist für Signale bis 50 kHz gedacht.

[jibi (Gast)]

>Atmega und lasse den ADC mit 1.5 MHz laufen.

Bist du sicher das das geht? Ich meine die schaffen das doch gar nicht?
Eine Wandlung braucht (glaub ich) 13 cyclen, macht bei 12MHz / 13 = 
0,9Mhz.

Dann gab es noch einen weiteren fallstrick, der das nochmal durch 2 
teilt. Effektiv kommst du auf ca. 500kHz bei 8 Bit.
Alles aus dem Kopf.

Gruß J

[M. K. (sylaina)]

jibi schrieb:
> Bist du sicher das das geht? Ich meine die schaffen das doch gar nicht?
> Eine Wandlung braucht (glaub ich) 13 cyclen, macht bei 12MHz / 13 =
> 0,9Mhz.

Autsch. Ja, das geht. Erstmal: Atmegafrequenz teilen durch den Vorteiler 
für den ADC, der ist bei mir auf 8 eingestellt, also 12 MHz/8 macht 1.5 
MHz. Im Freerunningmode braucht der ADC 13 ADC-Zyklen bis die Wandlung 
fertig ist, also 1.5 MHz/13 Zyklen macht ca. 115 kHz.

jibi schrieb:
> Dann gab es noch einen weiteren fallstrick, der das nochmal durch 2
> teilt. Effektiv kommst du auf ca. 500kHz bei 8 Bit.

Also für meine Anzeige wäre das völlig OK. Und 500 kHz > 115 kHz

jibi schrieb:
> Alles aus dem Kopf.

Dann schau doch mal ins Datenblatt. ;)

Ich habs zumindest bei meinem Atmega32/Schaltung gemessen und bei mir 
wackelt nicht mal das letzte der zehn Bits. Das Datenblatt schreibt bei 
1 MHz ADC-Takt dass man 3 LSB typischer Weise hat. Ist bei mir ein wenig 
besser. Ich denke aber auch, dass das von der Ref-Quelle abhängt. Gehe 
ich auf die interne oder noch schlimmer auf Vcc dann zappelt es 
ordentlich aber 8 bit sind dann immer noch drin.

[Nils S. (kruemeltee)]

Michael K. schrieb:
> Ich habs zumindest bei meinem Atmega32/Schaltung gemessen und bei mir
> wackelt nicht mal das letzte der zehn Bits. Das Datenblatt schreibt bei
> 1 MHz ADC-Takt dass man 3 LSB typischer Weise hat

Kurze Zwischenfrage,

bei 1MHz sind demnach also die Bits 2^0, 2^1 und 2^2 nicht mehr 
brauchbar?

[M. K. (sylaina)]

Nils S. schrieb:
> Kurze Zwischenfrage,
>
> bei 1MHz sind demnach also die Bits 2^0, 2^1 und 2^2 nicht mehr
> brauchbar?

Fast, das heißt wohl dass der Count-Wert um ±3 schwanken darf. Im 
Datenblatt ist nämlich auch eine Angabe wo es z.B. 16 LSB heißt bzgl. 
der Full Resolution (ADC-Takt im Bereich 50-200 kHz, Gain auf 10, 
Differential Mode) und bei deiner Annahme würde es knapp werden beim 10 
bit ADC-Wert ;)

[Ingo L. (corrtexx)]

Ich hätte da auch ne Frage:
Wie wurde das Hamming Fenster und die cos_sin Tabelle erstellt?


Leider kenne ich mich mit FFT mal so garnicht aus :(...

[M. K. (sylaina)]

Ingo L. schrieb:
> Wie wurde das Hamming Fenster und die cos_sin Tabelle erstellt?

Entweder mit Matlab und Co ausgerechnet oder mit Excel und Co. Ich denke 
das fragst du am Besten den Autor.