SIGNÁLY A SOUSTAVY
                                      V MATEMATICKÉ BIOLOGII

                                   prof. Ing. Jiří Holčík, CSc.



                                        holcik@iba.muni.cz

                                                V.
                                         DISKRÉTNÍ SIGNÁL
                                         FREKVENČNÍ OBLAST

                             Rozklad Diskrétního periodického signálU

þ spojitý signál – opakování

   Fourierova řada (v komplexním tvaru)

                                          FOURIEROVA ŘADA
                                       PRO DISKRÉTNÍ SIGNÁLY

þ  nechť x(kT) je periodický signál s periodou NT; pak x(kT) lze rozložit pomocí komplexní
exponenciální Fourierovy řady





   kde

                                          FOURIEROVA ŘADA
                                               DŮKAZ

þ  změňme index sumace ve vztahu pro výpočet koeficientu c[n]

                                          FOURIEROVA ŘADA
                                               DŮKAZ

                                          FOURIEROVA ŘADA
                                              PŘÍKLAD

x(kT) = A.cos(2pk/N) je periodická funkce s periodou N

                                          FOURIEROVA ŘADA
                                              PŘÍKLAD

                         FOURIEROVA TRANSFORMACE S DISKRÉTNÍM ČASEM - DTFT

þ nechť x(kT) je časově omezený signál s diskrétním časem s x(kT)=0 pro všechna celá k>N[1] a
k<-N[1], kde N[1] je celočíselná konstanta.

þ dále, nechť pro kladné sudé celé číslo N>2N[1] označíme             periodický signál s periodou
NT, který je x(kT) pro k = -N/2, -(N/2)+1, …, -1, 0, 1, …, (N/2)-1.

[þ    ]z definice            máme[]

                                          FOURIEROVA ŘADA
                                              PŘÍKLAD

þ protože             je periodická funkce s periodou NT, má Fourierovu řadu

                                          FOURIEROVA ŘADA
                                              PŘÍKLAD

þ Z definice              vyplývá, že lze poslední uvedenou rovnici přepsat do tvaru











kde ω je pro N→¥ spojitá (nediskrétní) veličina.

                              DISKRÉTNÍ FOURIEROVA TRANSFORMACE - DFT

þ  aby bylo možné počítat s frekvenčním spektrem na počítači, je třeba spektrální funkci
diskretizovat;

þ  předpokládejme, že diskrétní signál x(nT)=0 pro

   n < 0 a n ≥ N-1, pak DFT je definována vztahem

                                   ZPĚTNÁ DISKRÉTNÍ FT – DFT^-1

                                         INVERZIBILITA DFT

                                                DFT
                                             ω[1] = 2Ω
                                              = 4p/NT

                                                DFT
                                        ω[1] = 2,5Ω = 5p/NT

                               RYCHLÁ FOURIEROVA TRANSFORMACE - FFT

þ  hodnoty funkcí cos a sin se používají z tabulek pro čtvrtinu periody;

þ  zrychlení výpočetního algoritmu se dosáhne využitím dříve vypočítaných mezivýsledků, resp.
vynecháním zbytečných výpočtů – např. násobení nulou;

                               RYCHLÁ FOURIEROVA TRANSFORMACE - FFT

FFT – (Cooley, Tukey – 1965, ale před nimi již i mnozí další od 1903)

è rozklad v časové oblasti;

è rozklad ve frekvenční oblasti

jednotka pracnosti P – jedno komplexní násobení a sečítání

pracnost výpočtu jednoho vzorku spektra – N.P

pracnost celé transformace – N.N.P = N^2.P

                                                FFT
                                     ROZKLAD V ČASOVÉ OBLASTI

þ  vstupní posloupnost o sudém počtu vzorku rozdělíme na dvě dílčí posloupnosti

   {g[i]} = {x[2i]} - sudé prvky původní posloupnosti,

   {h[i]} = {x[2i+1]} - liché prvky původní posloupnosti,

                                                                                     i=0,1,…, N/2-1

   předpokládáme, že každá z posloupností (původní i obě dílčí), mají svou DFT

                                                FFT
                                     ROZKLAD V ČASOVÉ OBLASTI

                                                FFT
                                     ROZKLAD V ČASOVÉ OBLASTI

                                                FFT
                                     ROZKLAD V ČASOVÉ OBLASTI

þ výsledná pracnost bude součtem pracností výpočtu spekter obou posloupností

                                          2.(N/2)^2.P+N.P

   tzn. uspoření pracnosti téměř na polovinu;

þ je-li N/2 opět sudé, může se v dělení pokračovat – celkově je výhodné, je-li N = 2^m

                                                FFT
                                     ROZKLAD V ČASOVÉ OBLASTI

                                                FFT
                                     ROZKLAD V ČASOVÉ OBLASTI

þ každý uzel v grafu představuje jedno komplexní násobení a součet

þ N uzlů ve vrstvě; celkem m vrstev m=log[2]N

þ celková pracnost:

                                        P.N.m = P.N.log[2]N

   to představuje při N=8 úsporu 60%, při N=1024 již téměř 99% a při N=131072=2^17 dokonce 99,99%

                                                FFT
                                     ROZKLAD V ČASOVÉ OBLASTI

þ výstup je uspořádán přirozeně; vstup je v bitově inverzním pořadí;

þ opakující se struktury „motýlků“ obsahujících 4 uzly a 4 hrany