Ono to je v celku jednoduche. V podstate sa jedna o allgoritmicku metodu. Tak ako je dolezite pri vzorkovani dodzrat podmienku aby ty nevznikal aliasingovy singal. Tak aj FFT musis dodrzat podmienku, teda pocet vzoriek sa musi dat vyjadrit exponencialnou fuknciou 2^m. Cize 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768 atd. Nie nic medzi tym!
Motylik: najdolezitejsia vec u FFT je pochopenie motylika (butterfly) a pracu s ním.
Riadis sa tymito pravidlami:
[*]
Bitova reverzacia vsimi si poradie bitov navzorkovaneho signalu (vstup) a poradie bitov spektra (vystup). Su bitovo reverzovane. V tomto priklade podla obrazka mame 8 vzoriek. Cislo 8 dokazeme zapisat v exponencialnom tvare 2^3 (16 zase 2^4 ...). Teda riesime 3 miestnu bitovu reverzaciu. Bitova reverzacia je ze cislo citas odzadu. Priklad si zvolime napriklad x(3). Cislo 3 v dvojkovej sustave je 011b (musis dodzat pocet miest v tomto pripade sme zistili ze sa jedna o 3 miestnu). Po bitovej reverzacii to mas 110b a to je X(6). Nic zlozite
[*]
Pocet krokov (stages) a velkost uzla: Velkost uzla v stage 1 je vzdy 2. V kazdom dalsom nasledujucom uzli je uzol dvojnasobne vacsie (stg1: 2, stg2: 4, stg3: 8, stg4: 16, stg5: 32 atd). A pocet krokov je len tolko po kedy velkost uzla nebude taky velky ako pocet bitov FFT. V tomto pripade mame len 3 kroky (stg1:2, stg2: 4 a stg3:
.
[*]
Sipky: Tunak je to tiez jednoduche prva polovica bitov uzla do druhej polovice. A druha polovica do prvej polovice.
[*]
Znak -1: vzdy v druhej polovici uzla mas -1.
[*]
W: tu ho nedokazem zapisat takze Wx(y) kde x mas horny index a y mas dolny index. Piseme ho tiez len v druhej polovici na zaciatok. Kde x ty urcuje poradie bitu polovicky uzla (0, 1, 2 ,3 ...) a y je velkost uzla.
Easy ako facka. Riadis sa tymto postupom a zostavis si lubovolny motylik FFT
Teraz ideme si ideme vysvetlit samotny prepocet.
[*]
Elementarny motylik:
[*]
Vypocet W: Wx(y), kde x je horny index a y je dolny index.
Wx(y)=cos(2*PI*x/y)-j*sin(2*PI*x/y)
Vysledok: vysledkom FFT mas imaginarne cislo, podla ktorej si vies vypocitaj pre kazdu spektralnu ciaru maxiamalnu hodnotu a fazovy posun.
Snad som trocha pomohol. Ak chces vediet o tomto trocha hlbsie mal by si vediet aj to co je
kvantovy sum, aliasing, presakovanie spektra atd. odporucam knihu, ktora mi bola kedysi odporucana.
http://www.pulib.sk/web/kniznica/epc/dokument/12293
Kde ju kupit netusim, ja som ju kupil od jedneho z tejto stranky.