OT: Potřeboval bych pochopit Fourierovu transformaci, ale potřebuju nakopnout

metod je vice, zkus se podivat na toto, snad to lepe pochopis...

http://elektronika.kvalitne.cz/ATMEL/necoteorie/tr ansformation/AVRFFT/AVRFFT.html

Tak je mi to zase o trochu jasnější .

Takže u Cooley-Tukey algoritmu je jako první krok třeba udělat bitovou inverzi vstupního pole a poté to "motýlkové" zpřeházení viz obrázek?

Když budu mít tedy 64 (256) vzorků, tak bude třeba tohle provést 6 resp. 8 zpřeházení (vždy N, kde 2^N = počet vzorků)?
A potom se tam píše, že je třeba provést vlastní FFT. A tam už mi to není jasné, pokoušel jsem si přepsat ten algoritmus do mat. výrazů, ale bez úspěchu. Konkrétně se mi jedná o tenhle kód:

#define N 8

typedef struct{
    double re;
    double im;
}TCplx;

double tsincos[N]={0.000, 1.000, 0.7071, 0.7071, 1.000, 0.000, 0.7071,-0.7071};
TCplx FFTwarr[N];

void FFTditR2(void)
{
    double dsin,dcos;
    double *Fnk;
    TCplx C;
    TCplx *A,*B;
    int s,k;
    int n=1;
    int angf=N;
        
    while(n<N)
    {
        A=&FFTwarr[0];
        B=&FFTwarr[n];     
        Fnk=&tsincos;
        
        for(k=0;k<n;k++)
        {
            dsin=*Fnk++;
            dcos=*Fnk++;
            
            for(s=0;s<angf;s++)
            {
                C.re=A->re*dcos - A->im*dsin;
                C.im=A->re*dsin + A->im*dcos;
                B->re=A->re - C.re;
                B->im=A->im - C.im;
                A->re+=C.re;
                A->im+=C.im;
                A+=2*n;
                B+=2*n;              
            }
            A-=(N-1);
            B-=(N-1);             
            Fnk+=(angf-2);
        }        
        n<<=1;
        angf>>=1;
    }
}

Tak je mi to zase o trochu jasnější

Hele já se Tě jenom trošku zeptám... K čemu je dobrá ta Furiérova transformace ( jestli to jde nějak vysvětlit ).

Chci si postavit spektrální analyzátor - watch
A nechci tam cpát 10-30 analogových filtrů, PIC stejnak nemá ani tolik analogových vstupů. Takhle mi to spočítá, jaké všechny frekvence vzorek hudby obsahuje a dá se s tím krásně pracovat. Taky to využiju do dig. osciloskopu a spekt. analyzátoru s PICama.

Jinak význam té fourierovy transformace spočívá v tom, že ty máš nějakej signál:

Třeba po 100 mikrosekundách si zapíšeš hodnoty - třeba 0,7V;1,2V,1,1V,0,2V atd. To proženeš fourierem a vyhodí ti to komplexní čísla - ve výsledku pak dostaneš informace o tom, jaké tam jsou frekvence (třeba 200Hz, 1100Hz, 2200Hz) a jejich amplituda ("síla") a z toho vytvoříš takovýto podobný graf:

Toto konkrétně vypadá na spektrum obdélníkového signálu.

Když jsem někde napsal blbost, tak mě opravte, taky v tom nejsem zběhlej .

U toho youtube odkazu ma odkaz na postup - je tem i nekompilovaný kód na Atmega8 http://diy.elektroda.eu/analizator-widma-akustyczn ego/. Třeba tam něco najdeš, je to polsky - a já tam nic jako FFt nenašel.

Este k tvojmu konkretnemu dotazu o tom komplexnom poli, na tom tvojom webe:

After the real array has been passed to a complex array with the complex part equal to 0, you compute the FFT.

T.j. do komplexneho pola nadrbes tvoje vzorky do realnej casti, imaginarna cast naplnis nulami. Ak to tam spravne chapem to co tam pise.

Potom na to pustis tie vsetky algoritmy a vypadne ti z toho vysledok ako pole komplexnych cisel.

Ak to pole obsahovalo tolko komplexnych cisel kolko je tvoja samplovacia frekvencia (t.j. naplnil si to 1 sekundovym usekom) tak kazdy prvok (komplexne cislo) pola zodpoveda jednej zanalyzovanej frekvencii s krokom 1Hz (ak tam nacpes pocet vzoriek rovny polovici vzorkovacej frekvencie t.j. 0,5s usek tak mas vysledky s krokom 2Hz, atd)

The absolute value of a complex number is the square root of the square of the real plus the square of the complex.

T.j. vyslednu silu signalu (pre nejaku frekvenciu) z prislusneho komplexneho cisla vyratas ako velkost vektora komplexneho cisla, t.j. z pytagorovej vety, druha odmocnina z (realna cast ^ 2 + imaginarna cast ^ 2).
Ak to spravne chapem. Pisem FFT som to 10rokov nevidel tak to ber s rezervou :)

P.S. skus si ale najst efektivnejsi algoritmus, skus pohladat Split-radix, ptz toto co si nasiel asi neni najefektivnejsi (ten danielson lanczos je z 1942 ci kolko, split-radix je z 1984). Ale neviem zhlavy ktory je najefektivnejsi. Na wikipedii pisu ze split-radix.

Díky a sorry, že jsem se k tomu dostal až teď. Našel jsem Split Radix:
http://www.mit.edu/~emin/source_code/fft/index.htm l
To se mi zdálo ze všech kodů zatím nejstravitelnější (dá se to "pochopit" stylem 2 hrušky + 2 hrušky = 4 hrušky ) Nepotřebuju nic superpřesného, stačí mi bohatě těch 8 frekvencí, je to do zesilovače jen pro parádu, aby se tam něco hejbalo ). Hodil jsem to do mého zdrojáku, vložil tam nějaká data (funkci sinus, kroky po 0.3):

0
0.29
0.56
0.78
0.93
0.99
0.97
0.86
0.67
0.42
0.14
-0.15
-0.44
-0.68
-0.87

A vyplivlo mi to:

4,47
-2,87
6,25e-1
6,39e-1
3,6e-1
2,93e-2
-2,65e-1
-4,76e-11
-5,5e-1
-5,65e-1
-7,2e-1
9,25e-21
4,7e-11
5,48e-121
4,8e-11
2,87e-11

Už tohle je úspěch, že to "něco" spočítalo a vypadá to, že by to mohlo být dobře (jedna hlavní frekvence a potom malinké další, které tam vznikly tím, že mezi jednotlivými vzorky je nějaká doba a kdybych si nakreslil graf, tak tam budou ostré hrany = spousta malých sinusovek). Tys mi popsal způsob získání dat o frekvenci a amplitudě u Danielsona-Lanzcose, tady je to úplně to samé? Všechno nejlíp chápu z příkladů, mohl bys mi prosím napsat, jak by to vypadalo při vzorkovací frekvenci 100Hz? Vstupní pole jsem udělal jako sinus v krocích po 0.3, 2 pi je cca. 6.3, tedy 21 samplů na jednu plnou sinusovku, 0.21s jedna sinusovka = cca. 4,76Hz a amplituda 1.

Uf, tak jsem na konci. Nepotřeboval jsem fourierovu transformaci, stačil mi Goertzelův algoritmus:
Goertzel_algorithm

Díky všem za pomoc.

Alespon sis rozsiril obzory.