mikrocontroller.net

Forum: Digitale Signalverarbeitung / DSP Optimierungswettbewerb FFT u. IFFT


Autor: thomas (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Folgende Aufgabe wird gestellt:
Eine 256 Punkt(Eingabelänge 256 Samples im Realteil,Imagteil wird
ausgenullt!!!) FFT mit einer größe von Typ short(16 Bit mit Vorzeichen)
soll so effektiv wie möglich auf einem Atmega32 (16 Mhz Taktung)
implementiert werden. Ich möchte einfach mal wissen, wo hier der max.
Rekord liegt. Ich habe  35 ms für die normale FFT und 52 ms
für die IFFT gebraucht. Wenn das einer von Euch überbieten kann, so
schreibt
bitte einen Beitrag ,wie er es gemacht hat.

Mit einem PIC   (8 Bit Busbreite mit 36 Mhz taktung) hat jemand in
140 ms die IFFT geschaft. Andere 16 Bit Controller brauchen im schnitt
bei 16 Mhz 60 ms für die IFFT.

Ich behaupte einfach mal ,das ich mit den Werten 35 und 52 schon Recht
gut liege. Ein kollege hat mir einen Ansatz genannt, wie ich meinen
Algorithmus nocheinmal um 13 ms verbessern könnte. Ob das klappt
,erfahrt Ihr selbstverständlich auch hier.

Ich freue mich über Eure Vorschläge.
Auf Anfrage gebe ich Euch auch meinen FFT Algorithmus optimiert für
die ATMega8 -128 Reihe.

Autor: OldBug (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Was richtig klasse wäre, wenn Du/ihr das im Wiki austragen würde(s)t...

Autor: Gerhard Gunzelmann (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Thomas

ich arbeite zwar mit nem Pic, mich würde aber trotzdem Dein Algorithmus
interessieren. Ich arbeite an einem mobilen Messsystem, das online eine
FFT machen soll. Soll also möglichst effektiv sein. Ich habe zwar ne
C-Bibliiotek für FFT, die läuft aber nur auf nem PIC30, aber nicht auf
dem PIC18.

Ich würde mich freuen, wenn Du Deinen mir Deinen Code mailen könntest.

->  gunzelg@arcor.de


Danke im Vorraus

Gerhard

Autor: juergen klauck (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
hi!!
ist IFFT die ruecktransformation???
spiele ein bischen mit nem mega128 rum und wuerde mich ueber den
algorithmus sehr freun!!!

Autor: ape (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
hüstel
hätte da auch interesse dran :)

Autor: tobias hofer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
hallo thomas

du schreist:

>Eine 256 Punkt(Eingabelänge 256 Samples im Realteil,Imagteil wird
>ausgenullt!!!)

was macht das in der praxis für einen sinn wenn der imaginärteil gleich
null ist? und wäre nicht das berechnen der sinus und cosinus werte ein
teil der erheblich zeit brauchen würde?

gruss
tobias

Autor: Sebastian (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das kann doch problemlos sein, wenn du rein reelle Daten hast. Eine
zweidimensionale FFT auf einem reellen Bilddatensatz ist z.B. ein
Beispiel. Bei der IFFT darfst du den Im-Teil natürlich nicht
vernachlässigen, das stimmt.

Autor: thomas (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
du schreist:

>Eine 256 Punkt(Eingabelänge 256 Samples im Realteil,Imagteil wird
>ausgenullt!!!)

was macht das in der praxis für einen sinn wenn der imaginärteil
gleich
null ist?

Wenn man z.B. einen Audiostream hat und diesen in sein Spektrum
zerlegen will ,dann muß man den Imaginärteil sogar ausnullen ,da es in
der Zeitlichen Wellenformdarstellung nur Zeit und Ampiltude gibt.



 und wäre nicht das berechnen der sinus und cosinus werte ein
teil der erheblich zeit brauchen würde?
Nein, den Sinus und Cosinus kann man bequem mit Konstantentabellen
machen g

gruss
tobias

Autor: Benedikt (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Könntest du mal deinen Code posten ?

Autor: Hagen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Du solltest dich mal nach den modularen Integer FFT's erhundigen. Diese
FFT's arbeiten mit Primzahlen in modularen Ringen und ermöglichen es
somit vollständig auf Fliekommazahlen zu verzichten. Desweiteren sind
diese Abarten der FFT's die effizientesten die man auf Binärrechnern
umsetzen kann. Durch die Anwendung von Integern und Modulararithmetik
habe diese im Gegensatz zu Fließkommaberechnungen ein Fehler von Null,
sie sind also exakte FFTs.

Es gibt nun verschiedene solche FFTs, zB. Nussbaumer oder die Modulare
Fermat FFT von Schönhage und Strassen. Bei all diesen FFTs müssen
modulare Divisionen durchgeführt werden, also im Grunde langsamme
Disvisionen. Aber beide vorhergenannte FFT's arbeiten mit Modularen
Ringen die auf Primzahlen von spezieller Form aufsetzen. Zb. Fermat
Zahlen wie 2^(2^m)+1 oder 2^(2^m)-1. Eine Modulare Division mit solchen
Zahlen involvieren nur Bit-Shifts und Ausgleichsaddtionen bzw.
Subtraktionen. Somit wurde die langsamme Disvision, vergleichbar mit
den vielen Multiplikation bei Fließkomma FFTs, durch enorm schnelle
Operationen ersetzt. Allgemein kann man sagen das modulare Integer FFTs
ca. 5-10 mal schneller sind als die FFTs in komplexen Zahlen basierend
auf Fließkomma/Festkomma Operationen.

Gruß Hagen

Autor: thomas (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
//Hier meine für den Atmel optimierte FFT-Version
// Target : M32
// Crystal: 16.000Mhz

#include <iom32v.h>
#include <macros.h>

#define M       8
#define N       (1<<M)




#define N_WAVE          1024    /* dimension of Sinewave[] */
#define LOG2_N_WAVE     10      /* log2(N_WAVE) */
#define N_LOUD          100     /* dimension of Loudampl[] */
#ifndef fixed
#define fixed short
#endif
#if N_WAVE != 1024
        ERROR: N_WAVE != 1024
#endif
const fixed Sinewave[1024] = {
      0,    201,    402,    603,    804,   1005,   1206,   1406,
   1607,   1808,   2009,   2209,   2410,   2610,   2811,   3011,
   3211,   3411,   3611,   3811,   4011,   4210,   4409,   4608,
   4807,   5006,   5205,   5403,   5601,   5799,   5997,   6195,
   6392,   6589,   6786,   6982,   7179,   7375,   7571,   7766,
   7961,   8156,   8351,   8545,   8739,   8932,   9126,   9319,
   9511,   9703,   9895,  10087,  10278,  10469,  10659,  10849,
  11038,  11227,  11416,  11604,  11792,  11980,  12166,  12353,
  12539,  12724,  12909,  13094,  13278,  13462,  13645,  13827,
  14009,  14191,  14372,  14552,  14732,  14911,  15090,  15268,
  15446,  15623,  15799,  15975,  16150,  16325,  16499,  16672,
  16845,  17017,  17189,  17360,  17530,  17699,  17868,  18036,
  18204,  18371,  18537,  18702,  18867,  19031,  19194,  19357,
  19519,  19680,  19840,  20000,  20159,  20317,  20474,  20631,
  20787,  20942,  21096,  21249,  21402,  21554,  21705,  21855,
  22004,  22153,  22301,  22448,  22594,  22739,  22883,  23027,
  23169,  23311,  23452,  23592,  23731,  23869,  24006,  24143,
  24278,  24413,  24546,  24679,  24811,  24942,  25072,  25201,
  25329,  25456,  25582,  25707,  25831,  25954,  26077,  26198,
  26318,  26437,  26556,  26673,  26789,  26905,  27019,  27132,
  27244,  27355,  27466,  27575,  27683,  27790,  27896,  28001,
  28105,  28208,  28309,  28410,  28510,  28608,  28706,  28802,
  28897,  28992,  29085,  29177,  29268,  29358,  29446,  29534,
  29621,  29706,  29790,  29873,  29955,  30036,  30116,  30195,
  30272,  30349,  30424,  30498,  30571,  30643,  30713,  30783,
  30851,  30918,  30984,  31049,
  31113,  31175,  31236,  31297,
  31356,  31413,  31470,  31525,  31580,  31633,  31684,  31735,
  31785,  31833,  31880,  31926,  31970,  32014,  32056,  32097,
  32137,  32176,  32213,  32249,  32284,  32318,  32350,  32382,
  32412,  32441,  32468,  32495,  32520,  32544,  32567,  32588,
  32609,  32628,  32646,  32662,  32678,  32692,  32705,  32717,
  32727,  32736,  32744,  32751,  32757,  32761,  32764,  32766,
  32767,  32766,  32764,  32761,  32757,  32751,  32744,  32736,
  32727,  32717,  32705,  32692,  32678,  32662,  32646,  32628,
  32609,  32588,  32567,  32544,  32520,  32495,  32468,  32441,
  32412,  32382,  32350,  32318,  32284,  32249,  32213,  32176,
  32137,  32097,  32056,  32014,  31970,  31926,  31880,  31833,
  31785,  31735,  31684,  31633,  31580,  31525,  31470,  31413,
  31356,  31297,  31236,  31175,  31113,  31049,  30984,  30918,
  30851,  30783,  30713,  30643,  30571,  30498,  30424,  30349,
  30272,  30195,  30116,  30036,  29955,  29873,  29790,  29706,
  29621,  29534,  29446,  29358,  29268,  29177,  29085,  28992,
  28897,  28802,  28706,  28608,  28510,  28410,  28309,  28208,
  28105,  28001,  27896,  27790,  27683,  27575,  27466,  27355,
  27244,  27132,  27019,  26905,  26789,  26673,  26556,  26437,
  26318,  26198,  26077,  25954,  25831,  25707,  25582,  25456,
  25329,  25201,  25072,  24942,  24811,  24679,  24546,  24413,
  24278,  24143,  24006,  23869,  23731,  23592,  23452,  23311,
  23169,  23027,  22883,  22739,  22594,  22448,  22301,  22153,
  22004,  21855,  21705,  21554,  21402,  21249,  21096,  20942,
  20787,  20631,  20474,  20317,  20159,  20000,  19840,  19680,
  19519,  19357,  19194,  19031,  18867,  18702,  18537,  18371,
  18204,  18036,  17868,  17699,  17530,  17360,  17189,  17017,
  16845,  16672,  16499,  16325,  16150,  15975,  15799,  15623,
  15446,  15268,  15090,  14911,  14732,  14552,  14372,  14191,
  14009,  13827,  13645,  13462,  13278,  13094,  12909,  12724,
  12539,  12353,  12166,  11980,  11792,  11604,  11416,  11227,
  11038,  10849,  10659,  10469,  10278,  10087,   9895,   9703,
   9511,   9319,   9126,   8932,   8739,   8545,   8351,   8156,
   7961,   7766,   7571,   7375,   7179,   6982,   6786,   6589,
   6392,   6195,   5997,   5799,   5601,   5403,   5205,   5006,
   4807,   4608,   4409,   4210,   4011,   3811,   3611,   3411,
   3211,   3011,   2811,   2610,   2410,   2209,   2009,   1808,
   1607,   1406,   1206,   1005,    804,    603,    402,    201,
      0,   -201,   -402,   -603,   -804,  -1005,  -1206,  -1406,
  -1607,  -1808,  -2009,  -2209,  -2410,  -2610,  -2811,  -3011,
  -3211,  -3411,  -3611,  -3811,  -4011,  -4210,  -4409,  -4608,
  -4807,  -5006,  -5205,  -5403,  -5601,  -5799,  -5997,  -6195,
  -6392,  -6589,  -6786,  -6982,  -7179,  -7375,  -7571,  -7766,
  -7961,  -8156,  -8351,  -8545,  -8739,  -8932,  -9126,  -9319,
  -9511,  -9703,  -9895, -10087, -10278, -10469, -10659, -10849,
 -11038, -11227, -11416, -11604, -11792, -11980, -12166, -12353,
 -12539, -12724, -12909, -13094, -13278, -13462, -13645, -13827,
 -14009, -14191, -14372, -14552, -14732, -14911, -15090, -15268,
 -15446, -15623, -15799, -15975, -16150, -16325, -16499, -16672,
 -16845, -17017, -17189, -17360, -17530, -17699, -17868, -18036,
 -18204, -18371, -18537, -18702, -18867, -19031, -19194, -19357,
 -19519, -19680, -19840, -20000, -20159, -20317, -20474, -20631,
 -20787, -20942, -21096, -21249, -21402, -21554, -21705, -21855,
 -22004, -22153, -22301, -22448, -22594, -22739, -22883, -23027,
 -23169, -23311, -23452, -23592, -23731, -23869, -24006, -24143,
 -24278, -24413, -24546, -24679, -24811, -24942, -25072, -25201,
 -25329, -25456, -25582, -25707, -25831, -25954, -26077, -26198,
 -26318, -26437, -26556, -26673, -26789, -26905, -27019, -27132,
 -27244, -27355, -27466, -27575, -27683, -27790, -27896, -28001,
 -28105, -28208, -28309, -28410, -28510, -28608, -28706, -28802,
 -28897, -28992, -29085, -29177, -29268, -29358, -29446, -29534,
 -29621, -29706, -29790, -29873, -29955, -30036, -30116, -30195,
 -30272, -30349, -30424, -30498, -30571, -30643, -30713, -30783,
 -30851, -30918, -30984, -31049, -31113, -31175, -31236, -31297,
 -31356, -31413, -31470, -31525, -31580, -31633, -31684, -31735,
 -31785, -31833, -31880, -31926, -31970, -32014, -32056, -32097,
 -32137, -32176, -32213, -32249, -32284, -32318, -32350, -32382,
 -32412, -32441, -32468, -32495, -32520, -32544, -32567, -32588,
 -32609, -32628, -32646, -32662, -32678, -32692, -32705, -32717,
 -32727, -32736, -32744, -32751, -32757, -32761, -32764, -32766,
 -32767, -32766, -32764, -32761, -32757, -32751, -32744, -32736,
 -32727, -32717, -32705, -32692, -32678, -32662, -32646, -32628,
 -32609, -32588, -32567, -32544, -32520, -32495, -32468, -32441,
 -32412, -32382, -32350, -32318, -32284, -32249, -32213, -32176,
 -32137, -32097, -32056, -32014, -31970, -31926, -31880, -31833,
 -31785, -31735, -31684, -31633, -31580, -31525, -31470, -31413,
 -31356, -31297, -31236, -31175, -31113, -31049, -30984, -30918,
 -30851, -30783, -30713, -30643, -30571, -30498, -30424, -30349,
 -30272, -30195, -30116, -30036, -29955, -29873, -29790, -29706,
 -29621, -29534, -29446, -29358, -29268, -29177, -29085, -28992,
 -28897, -28802, -28706, -28608, -28510, -28410, -28309, -28208,
 -28105, -28001, -27896, -27790, -27683, -27575, -27466, -27355,
 -27244, -27132, -27019, -26905, -26789, -26673, -26556, -26437,
 -26318, -26198, -26077, -25954, -25831, -25707, -25582, -25456,
 -25329, -25201, -25072, -24942, -24811, -24679, -24546, -24413,
 -24278, -24143, -24006, -23869, -23731, -23592, -23452, -23311,
 -23169, -23027, -22883, -22739, -22594, -22448, -22301, -22153,
 -22004, -21855, -21705, -21554, -21402, -21249, -21096, -20942,
 -20787, -20631, -20474, -20317, -20159, -20000, -19840, -19680,
 -19519, -19357, -19194, -19031, -18867, -18702, -18537, -18371,
 -18204, -18036, -17868, -17699, -17530, -17360, -17189, -17017,
 -16845, -16672, -16499, -16325, -16150, -15975, -15799, -15623,
 -15446, -15268, -15090, -14911, -14732, -14552, -14372, -14191,
 -14009, -13827, -13645, -13462, -13278, -13094, -12909, -12724,
 -12539, -12353, -12166, -11980, -11792, -11604, -11416, -11227,
 -11038, -10849, -10659, -10469, -10278, -10087,  -9895,  -9703,
  -9511,  -9319,  -9126,  -8932,  -8739,  -8545,  -8351,  -8156,
  -7961,  -7766,  -7571,  -7375,  -7179,  -6982,  -6786,  -6589,
  -6392,  -6195,  -5997,  -5799,  -5601,  -5403,  -5205,  -5006,
  -4807,  -4608,  -4409,  -4210,  -4011,  -3811,  -3611,  -3411,
  -3211,  -3011,  -2811,  -2610,  -2410,  -2209,  -2009,  -1808,
  -1607,  -1406,  -1206,  -1005,   -804,   -603,   -402,   -201,
};


 /* placed at end of this file for clarity */





/*
        fix_fft() - perform fast Fourier transform.

        if n>0 FFT is done, if n<0 inverse FFT is done
        fr[n],fi[n] are real,imaginary arrays, INPUT AND RESULT.
        size of data = 2**m
        set inverse to 0=dft, 1=idft
*/







fixed fix_fft(fixed fr[], fixed fi[], fixed m, char inverse)
{

short aus;

short v;
unsigned char *test;
unsigned char mr,nn,k,scale ;



   fixed i,j,l,istep, n;
     fixed t;

      fixed subi,subr,tr,ti;
        fixed wr,wi,qr,qi,shift;


                n = 1<<m;

        if(n > N_WAVE)
                return -1;

        mr = 0;
        nn = n - 1;
        scale = 0;

        /* decimation in time - re-order data */
        for(m=1; m<=nn; ++m) {
                l = n;
                do {
                        l >>= 1;
                } while(mr+l > nn);
                mr = (mr & (l-1)) + l;

                if(mr <= m) continue;
                tr = fr[m];
                fr[m] = fr[mr];
                fr[mr] = tr;
                ti = fi[m];
                fi[m] = fi[mr];
                fi[mr] = ti;
        }

        l = 1;
        k = LOG2_N_WAVE-1;
        while(l < n) {
                if(inverse) {
                        /* variable scaling, depending upon data */
                        shift = 0;
                        for(i=0; i<n; ++i) {
                                j = fr[i];
                                if(j < 0)
                                        j = -j;
                                m = fi[i];
                                if(m < 0)
                                        m = -m;
                               // if(j > 16383 || m > 16383) {




                               if(j > 16383 || m > 16383) {
                                        shift = 1;
                                        break;
                                }
                        }
                        if(shift)
                                ++scale;
                } else {
                        /* fixed scaling, for proper normalization -
                           there will be log2(n) passes, so this
                           results in an overall factor of 1/n,
                           distributed to maximize arithmetic accuracy.
*/
                        shift = 1;
                }
                /* it may not be obvious, but the shift will be
performed
                   on each data point exactly once, during this pass.
*/
                istep = l << 1;
                for(m=0; m<l; ++m) {
                        j = m << k;
                        /* 0 <= j < N_WAVE/2 */
                        wr =  Sinewave[j+N_WAVE/4];
                        wi = -Sinewave[j] ;
                        if(inverse)
                                wi = -wi;
                        if(shift) {
                                wr >>= 1;
                                wi >>= 1;
                        }
                        for(i=m; i<n; i+=istep) {
                                j = i + l;
 /*                                       tr = fix_mpy(wr,fr[j]) -
fix_mpy(wi,fi[j]);
                                        ti = fix_mpy(wr,fi[j]) +
fix_mpy(wi,fr[j]);
*/

 subi=fi[j]; subr= fr[j];

 //////// Beschleuniger Start
 v = wr*subr;
 test = (unsigned char *)&v +1;
    if (*test >= 128)
    {
     *test = 255;
     test--;
     *test= 255;
    }
     else

   {
      *test=0;
      test--;
      *test=0;
   }
   tr = v;

   v= wi*subi;

   test = (unsigned char *)&v +1;
    if (*test >= 128)
    {
     *test = 255;
     test--;
     *test= 255;
    }
     else

   {
      *test=0;
      test--;
      *test=0;
   }
   tr = tr - v;
   /////////////Zeile 1 Ende beginn Zeile 2 ////////////////

    v = (wr*subi);
 test = (unsigned char *)&v +1;
    if (*test >= 128)
    {
     *test = 255;
     test--;
     *test= 255;
    }
     else

   {
      *test=0;
      test--;
      *test=0;
   }
   tr = v;

   v= wi*subr;

   test = (unsigned char *)&v +1;
    if (*test >= 128)
    {
     *test = 255;
     test--;
     *test= 255;
    }
     else

   {
      *test=0;
      test--;
      *test=0;
   }
   tr = tr + v;

 ////////// Beschleuniger Ende

// tr = ((wr*subr)>>15) - ((wi*subi)>>15);
// ti = ((wr*subi)>>15) + ((wi*subr)>>15);
 //Mf(tr); Mf(ti);



                                qr = fr[i];
                                qi = fi[i];
                                if(shift) {
                                        qr >>= 1;
                                        qi >>= 1;
                                }
                                fr[j] = qr - tr;
                                fi[j] = qi - ti;
                                fr[i] = qr + tr;
                                fi[i] = qi + ti;
                        }
                }
                --k;
                l = istep;
        }

        return scale;
}

Autor: thomas (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die wesendliche Änderung besteht in dem Programmteil
"Beschleuniger". In der Ursprungsversion wurde der >>15
Befehl verwendet ,quasi ein Rechtsshift um 15 Stellen.
Da es auf einer Atmel MCU keinen effektiven Assemblerbefehl
dazu gibt, macht der C-Compiler nichts anderes ,als alle
15 shifts  mit einer Schleife durchzulaufen und diese beinhaltet auch
noch 17 Assenblerzeilen Code!!  Ich habe  einfach diesen
Shift 15 durch eine einfache Fallunterscheidung ersetzt.
Das braucht jetzt nur noch ca. 20 Assemblerzeilen ist aber mit
einem Durchlauf beendet. Ich beschäftige mich gerade mit den
Registeroptionen des Compilers und versuche nun das Effektiv mit
Assembleroptionen in den Code einzubinden.

//////// Beschleuniger Start

Autor: juergen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ok!!
wer seine email noch nicht mal richtig schreiben kann sollte vieleicht
was anderes machen
huestel
;-}

Autor: Mario (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@thomas

Schonmal was von Dateianhang gehört ?

Autor: Benedikt (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich habe ehrlich gesagt nich soviel Ahnung von FFT usw. suche allerdings
schon seit längerem nach einem schnellen FFT Code um einen Low Cost
Spektum Analyser mit einem kleinen Grafik LCD zu bauen. Daher kam
dieser optimierte Code gerade recht.

Für den ersten Test verwende ich einen berechneten Sinus und lade 1024
Werte in das fr Array. fi lade ich mit Nullen. Der Sinus hat einen
Wertebereich von +/-1000.
Nachdem fix_fft gelaufen ist, enthalten alle Werte im Array (0..255)
irgendwas im Bereich -2 bis 1, aber eigentlich müsste irgendwo eine
deutliche Spitze sein...

Einstellungen:
m=8;
inverse=0;

Habe ich was falsch gemacht, oder muss ich noch irgendwas beachten ?

Autor: thomas (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Jenachdem wie die Phase liegt, können die Zielwerte sowol im
Real als auch im Imagteil liegen. Du mußt, um die Lautstärke zu
ermitteln (abs(r[i]) +abs[i[i])) /2 rechnen. Außerdem kann eine solche
FFT nur exakt einen Sinuston finden, wenn er ein vielfaches
von der Niedrigsten Frequenz ist . Ansonsten fallen Werte zwichen
2 Frequenzen und man kann diese eine Frequenz nicht mehr exakt
bestimmen. Abhilfe dafür schafft z.b. Zero-Padding.
Aber bei einem einzigem Ton müßtest du trotzdem über 1-2
Frequnzen eine deutliche Spitze herausbekommen. Der Fehler leigt
vermutlich woanders. Du mußt natürlich als ArrayLänge 8 und nicht 256
angeben. Villeicht hat du in deiner Sinusfunktion einen fehler.
Um das zu testen nimm einfach mal Sinwave[0..n]. Oder wenn f Sinuston <
f Grundfrequenz ist, dann krigt man natürlich auch kein ergebnis.

Autor: thomas (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
oh mein Fehler ...............


{
      *test=0;
      test--;
      *test=0;
   }
   tr = tr + v; muß natürlich ti= tr + v heissen

 ////////// Beschleuniger Ende

// tr = ((wr*subr)>>15) - ((wi*subi)>>15);
// ti = ((wr*subi)>>15) + ((wi*subr)>>15);
 //Mf(tr); Mf(ti);

Autor: Steril (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Für den Blödian, der aber gern mitliest und es interessant findet(also
mich): was macht man mit einer FFT denn genau? oder generell? ;)

Autor: Benedikt (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Hab jetzt den Fehler behoben (und darüber auch noch den ti=tr-v)
Die Sinuskurve ist auf jedenfall richtig im Array:
fr[i]=1000*sin(i/2);
Das kann ich auch im Debugger nachprüfen.
Die Werte am Ende der FFT (mit zusammengefassten i und r Werten) liegen
dann bei 0-6...
Ich habe mal die Werte am Ende der FFT in den Anhang gepackt.

Autor: Benedikt (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Steril

Damit wird ein Signal in die darin enthaltenen einzelnen Frequenzen und
die entsprechende Stärke zerlegt. Speichert man nur die stärksten
Frequenzen, hat man einen mp3 Encoder.
Allerdings kann man mit FFT noch viel mehr machen wie z.B. Primzahlen
berechnen oder sehr, sehr große Zahlen multiplizieren (frag mich aber
bitte nicht wie...)
Eiegntlich ist FFT (Fast Fourier Transformation) nur eine Spezialform
von DFT (Discrete Fourier Transformation)

Autor: DerMax (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
sieht bei mir ähnlich aus
fi und fr jeweils länge 256
fi setze ich vorher komplett auf 0 fr enthält audio-samples (hab sowohl
musik als auch reinen sinus probiert)
m=8 und inverse=0
die ergebnisse liegen bei 0 bis 3

ich setze vor beginn der fft einen io-pin auf high und hintehrer wieder
auf low. laut oszilloskop dauert also die komplette fft mit 256 punkten
knappe 20ms, kommt mir etwas wenig vor (taktrate 18,432MHz)

Autor: Benedikt (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Gute Idee mit dem Pin....
Muss ich bei mir auch mal machen.
Ich habe das Programm allerdings nicht auf einem AVR sondern auf einem
16bit Controller M16C mit 24MHz laufen.

Autor: tobias hofer (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
hallo thomas

ich habe gerade ein bischen gegoogelt und folgende seite gefunden.

http://www.jjj.de/fft/fftpage.html

dort hat es ein txt file zum downloaden int fft.c, siehe anhang.
ich weiss jetzt halt auch nicht ob das deine homepage ist. wenn ja hut
ab, und gratulation zu der programmierung deiner fft. der code scheint
mit deinem ziemlich identisch zu sein.

nur wegen dem optimierungswettberb
gruss tobias

Autor: DerMax (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
jup die seite hab ich auch gefunden und mit der int_fft.c nen bissel
rumgespielt
es passiert mehr wie bei obigem code aber so ganz richtig ist das auch
noch nich

Autor: Benedikt (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich habe eine FFT Routine für QBASIC, aus einem simplen mp3 En/dekoder
Programm. Diese geht einwandfrei, nur in C gehts nichtmehr. In QBASIC
habe ich schon oft damit ein Oszilloskop mit Frequenzmessung
programmiert. Ebenso ein Empfänger für den Bereich 100-1MHz. Da konnte
ich mit einer einfachen Antenne, NE592 Videoopamp und einem TDA8703
über 100 MW Sender erkennen...

Autor: DerMax (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ich hab eine funktionierende FFT Funktion in C die auf dem AVR läuft nur
benutzt die leider fließkommaoperationen und ist entsprechend langsam
und invertieren kann sie auch nicht das brauch ich aber auch nicht

Autor: thomas (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
tobias hofer wrote.....
dort hat es ein txt file zum downloaden int fft.c, siehe anhang.
ich weiss jetzt halt auch nicht ob das deine homepage ist. wenn ja hut
ab, und gratulation zu der programmierung deiner fft. der code scheint
mit deinem ziemlich identisch zu sein.


die int_fft.c Ursprungsversion stammt nicht von mir , sondern ich habe
sie nur etwas abgeändert ,damit sie speziell auf Atmel Controllern
schneller läuft.

Autor: DerMax (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
so also hab jetzt den originalen sourcecode ohne die optimierungen
genommen und siehe da es funktioniert - wenn auch nich ganz so schnell
50ms bei 18,432MHz mit 256 Punkten.
außerdem hab ich die Sinus-Tabelle ins Flash getan das ist exakt
genauso schnell und sparrt 2kb RAM...

außerdem sollten die werte des eingangssignals den wertebereich des
datentyps halbwegs gut ausnutzen also +/- dürfte wohl etwas wenig sein

Autor: Benedikt (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bei mir gehts immer noch nicht...

Ich kann zwar eine Spitze erkennen, die sich auch verschiebt wenn ich
die Frequenz ändere, aber da sind noch mehr SPitzen, dort wo keine
hingehören....

Autor: Andreas Fertl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

jetzt grab ich den alten Thread wieder aus ;)

Ich verwende auch gerade diese FFT. Ich verstehe nicht was die m=8 bei
dem Funktionsaufruf der FFT bewirkt. Kann mir einer weiterhelfen?

Grüße Andreas

Autor: Andreas Fertl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
noch ne Frage :)

was für Werte erhält man denn wenn man ein Feld mit 256 Stellen nimmt
und diese von 0 - 255 füllt. sprich feld[20]=20,feld[21]=21 usw.

Oder besser gefragt, wie könnte man die FFT gut testen? Mit konstanten
Zahlen? Was erhalte ich hinter her?

Oh je so viel Fragen ;)

Grüße Andreas

Autor: Alex (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Weißt du überhaupt, was eine FFT ist?

http://www.dspguide.com/

Ich halte es für verkehrt, zu versuchen mit einer Sache
rumzuexperimentieren, wenn ich nicht einmal ihre Grundlagen verstanden
habe.

Autor: Andreas Fertl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Alex,

ich möchte ein Sprachsignal in den Frequenzbereich transformieren um
Untersuchungen in bestimmten Frequenzen vorzunehmen und möchte dafür
die FFT verwenden.

Als Input in diesem Fall wäre, da der A/D Wandler mir ja nur int Werte
liefert, wäre der Realteil (fr[] länge 256) die Daten vom A/D Wandler
und der Imaginärteil 0 (fi[] länge 256) und die FFT vorwärts mit 0.
Aber das m leuchtet mir nicht ein....

Naja ich les mal weiter...

Gruß Andreas

Autor: Andreas Fertl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hmm ok, die Länge der Felder....

weil ja auch nun mal 1<<8 = 255 ist.

Leuchtet ein :)

Gruß Andreas

Autor: Siggi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Benedikt

....Speichert man nur die stärksten Frequenzen, hat man einen mp3
Encoder. ....

 AUTSCH :-)

Autor: Andreas Siebel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Um die "Spitzen", die "nicht reinpassen" herauszubekommen, kann man
(wenn dir fft richtig funktioniert) noch ein sogenanntes "Windowing"
durchführen. Dabei wird einfach gesagt das Signal ein und ausgeblendet.
Damit werden die Signalsprünge am Anfang und Ende der Datenreihe
geglättet und somit diese hochfrequengen Anteile unterdrückt, die sonst
Aliasing Effekte erzeugen ("Spitzen, die nicht reinpassen").

Wen es interessiert googelt mal nach windowing fft, hanning window,
hamming window oder blackman window. Die Verschieden Arten wirken sich
auf Amplitudentreue oder Phasentreue aus.

Wäre auch interessant hier mal ne schnelle Lösung für nen MC zu haben
;)

Autor: D.N. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Andreas Siebel

jo das sieht man schön wenn man z.B einen Sinus abtastet und der nicht
100% innerhalb der Window Zeit (tw) liegt. Dann bekommt man noch ne
schöne si(x)-Funktion auf die Maximalwerte der eigentlichen Frequenz
des Sinussignals gelegt. Da wären wir schon wieder beim Thema
Faltung....

Autor: Alisa 1387 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Autor: Benedikt
> Datum: 04.08.2004 07:42

> Bei mir gehts immer noch nicht...

> Ich kann zwar eine Spitze erkennen, die sich auch verschiebt wenn
ich
> die Frequenz ändere, aber da sind noch mehr SPitzen, dort wo keine
> hingehören....

Wenn Du ne Sinuswelle reinjagst, die aufm ersten und letzten Sample
einen Nulldurchgang hat und es werden keine "fremden" Frequenzen
angezeigt, dann liegt's wahrscheinlich am Window.

Autor: romanua (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
"Es gibt nun verschiedene solche FFTs, zB. Nussbaumer oder die
Modulare
Fermat FFT von Schönhage und Strassen. Allgemein kann man sagen das
modulare Integer FFTs ca. 5-10 mal schneller sind als die FFTs in
komplexen Zahlen basierend auf Fließkomma/Festkomma Operationen."




Kann mir jemand mit einer Quelle helfen, wo diese Algorithmen
beschrieben sind?

vielen dank.

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]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [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.