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 .

Podle toho co si pamatuju máš pravdu. FT převádí signál z časové oblasti do frekvenční. FFT je "rychlou" implementací FT; zřejmě musí být splněny určitý podmínky.

Jinak obecně při vzorkování se musí dodržet vzorkovací (Shannon-Kotelnikuv) teorém; vzorkovací frekvence musí být dvojnásobkem (teoreticky) maximální frekvence obsažené v signálu (prakticky tak čtyřnásobkem).

Pavel

V tomto pripade bych to omezil dvojnasobkem maximalni frekvence, kterou ten spektralni analyzator bude moct zobrazit. A rozlisovaci schopnost lidskeho ucha konci nekde u 16kHz (to jsou ti netopyri).

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.

popis zpracovani signalu od str. 9, DFT od str. 15 BP.pdf
algoritmus Cooley-Turkey - od str. 49 https://dip.felk.cvut.cz/browse/pdfcache/zdarsj1_2 007bach.pdf

Tohle si prectu , abych nevypadnul ze cviku. Mozna se matika stane opet mym konickem (na vejsce me od ni dokonale odradili).

jinak tady jsou programove rutiny - http://webcache.googleusercontent.com/search?q=cac he:7QMRaFR6LjsJ:en.literateprograms.org/Cooley-Tuk ey_FFT_algorithm_(C)+FFT+p%C5%99%C3%ADklad+cooley& cd=5&hl=cs&ct=cln k&gl=cz

Se přiznám, že jsem předevčírem nahlédl do skript z elektřiny a magnetizmu z FJFI a opět mě přepadla touha to pokořit. Já se normálně začnu zase věnovat matice a až ji budu ovládat tím správným způsobem, třeba to CVUT jednou dodělám.

Matematika z FJFI... tomu rikam masochismus jako studovat vypocetni techniku na teto fakulte. I kdyz znam par studujicich lidi z FELu CVUT, kteri tu studovali fyziku. Jeden se specializuje na jadernou fuzi a do Reze u Prahy behem studii jezdil casteji nez domu... (o CERNU a vyjezdech na ruzne konference se ani nezminuji) Jsou to proste paradoxy.

Prakvapive me prijde, ze matiku tam uci (pro me) lepe, nez na FELu. Tak nejak prehledneji.

Asi je to tim, ze matika je na FJFI alfou a omegou vseho a provazi studium az do konce. Kdyz neumis matiku jako z matfyzu, nedostudujes. Navic se tam dalo jednat s vyucujicimi, taze znam pripady, kdy se namisto pouze 1x opakovani predmetu dalo opakovat tolikrat, dokud to vyučujici ci student sam nevzdal...

Na FEL se bere povinne ze zacatku... Navic na FEL byla za starych planu povinne matika 6x, nyni je 4x (pokud se nemylim). Navic nema az takovou prioritu.

Otazku kvality vyucujicich necham stranou.

Mozna se matika stane opet mym konickem

Je to věda o lži, to se hodí.

Tak díky všem, snažil jsem se to pochopit, ale je to na mě ještě moc, uvidím za 2-3 roky, třeba se zadaří .

To su zlozite veci tykajuce sa rozkladu periodickeho signalu, zabudni na to ze to pochopis sposobom ze 2 jablka + 2 jablka = 4 jablka :) Teoria sa hra so zlozitymi diferencialnymi rovnicami a nekonecnymi radami a ja neviem co vsetko (ja osobne som tie dokazy do detailu tiez nechapal a verim ze to okrem uja Fouriera nechape nikto :D, a veria tomu co ujo Fourier povedal ze to tak sa da urobit a ze to plati, a nelamu si s tym viac hlavu :D)

Zober nejaky algoritmus a pouzi. Algoritmov je mnoho roznych, vyber si taky ktory ti najviac vyhovuje co sa tyka moznosti toho uC. Osobne si nie som isty ci ti to bude uC stihat, povedal by som ze nebude, takze sa snaz hladat algoritmus s minimom vypoctovych operacii a s minimom potrebnej RAM (asi http://en.wikipedia.org/wiki/Split-radix_FFT_algor ithm, neviem zhlavy)

V principe FFT je par problemov z dovodu ze ta analyza akokeby zobere tvoj "vysek" signalu a urobi z neho periodicky signal - t.j. polozi ten vysek za sebou nekonecne vela krat, a to sa analyzuje. Z toho vyplyva ze vlnova dlzka minimalnej zdetekovanej frekvencie sa rovna dlzke vzorky, t.j. ked budes analyzovat len 41 vzoriek pri 41kHz vzorkovacej frekvecnii tak nemozes tam v tom detekovat frekvencie nizsie ako 1kHz. Ked chces detekovat aj frekvencie napr. 20Hz tak musis zobrat aspon 2050 vzoriek.
Druha vec je tusim ze ziskas silu nejakych klucovych (harmonickych) frekvencii, ktore ale nemusia byt nutne to co bolo na vstupe nepriklad ak mas cistu sinusovku 1kHz a tvoja transformacia analyzuje 100, 200, 400, 800, 1600, 3400, atd Hz, tak zistis ze tvoja 1kHz neni 1kHz ale zmes 800 a 1600 Hz alebo tak nejak, uz neviem zhlavy (pisem zhlavy takze to ber s rezervou, FFT som nevidel uz asi 10 rokov a nechce sa mi to znova studovat vsetko).

Citaj wikipediu apod. Idealne ak si najdes rovno nejaky zdrojak spektralneho analyzera, aby si tam v tom videl jaku to presne bere dlzkou vzorky a jake s tym tam potom robi finty aby odrbal problemy popisane vyssie, resp. jak ten cely analyzer je urobeny.

Kukni si napr. tu
http://www.relisoft.com/Science/Physics/sound.html
citaj a klikaj na next, next, je to tam pekne vysvetlene uplne od zakladov (ten web som si cital kedysi davno ked som robil analyzer s FFT). Strana 6 je nakoniec samotne FFT a je tam aj nejaky jednoduchy priklad z ktoreho by ti malo byt jasne jak vytvara zo vzoriek tie komplexne cisla a co s nimi robi. Uplne na konci je aj link na stiahnutie zdrojakov frequencneho analyzera. Ten som nikdy nepouzil takze neviem co to je zac :)

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.