logo-IBA logo-MU
© Institut biostatistiky a analýz
•INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ
logo-MU
SIGNÁLY A LINEÁRNÍ SYSTÉMY
prof. Ing. Jiří Holčík, CSc.
holcik@iba.muni.cz, UKB A29, dv.č.112

logo-IBA logo-MU
© Institut biostatistiky a analýz
VIII. FREKVENČNÍ TRANSFORMACE
 — ČASOVÉ ŘADY –

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þVZORKOVÁNÍ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
DEFINICE
þVzorkování je postup výběru jednotlivých pozorování, na jehož základě získáváme informaci o
vlastnostech sledované skutečnosti či jevu. Každé pozorování může obecně zahrnovat více vlastností
(věk, diagnóza onemocnění, velikost napětí, …), které mohou být použity k identifikaci daného jevu
či jeho části. þVzorkováním rozumíme postup výběru určité podmnožiny (vzorku) dané množiny
(veličiny, populace, dat, materiálu) tak, aby vlastnosti vybraného vzorku (dostatečně) přesně
reprezentovaly vlastnosti celé množiny (signálu, populace, dat, materiálu). þVzorkování je postup
selekce jednotlivých pozorování s cílem získat určitou znalost o dané populaci, zejména pro účely
statistické inference.
þ
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
PŘÍKLADY
þvolba frekvence a místa odběru pro hodnocení úrovně znečištění vodních toků; þvolba parametrů
digitalizace obrazu pro jeho přenos či archivaci; þvolba tématu a množiny respondentů při průzkumu
veřejného mínění; þvýběr výrobků při výstupní kontrole kvality výroby; þvýběr pacientů pro odhad
vývoje daného onemocnění.

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
DEFINICE
þVzorkováním dané veličiny (signálu) rozumíme činnost, při které z průběhu určité veličiny, která
je definovaná na spojitém definičním oboru, vybíráme hodnoty pouze v určitých časových okamžicích,
resp. pro určité hodnoty prostorových souřadnic.
þ
þHodnoty časových či prostorových souřadnic mohou být rozmístěny v definičním prostoru obecně
nerovnoměrně, z hlediska práce s daty je ale výhodnější, pokud jsou souřadnice vzorků rozmístěny
rovnoměrně (a v tom případě lze i teoreticky dovodit pravidlo pro maximální vzdálenost mezi každými
dvěma vzorky).
þ
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
DISKRÉTNÍ SIGNÁL - VZORKOVÁNÍ
vzorkovani
•s(nT)

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
IDEÁLNÍ VZORKOVÁNÍ
skenování0001.jpg
þAby bylo možné zjednodušit analýzu vlivu vzorkování na vlastnosti vzorkované veličiny, je
navzorkovaná verze původní spojité veličiny s(t) vyjadřována ve tvaru s(t).sδ(t), kde sδ(t) je
periodický sled jednotkových impulsů definovaný jako
þ
þ
þZ toho pro navzorkovanou veličinu platí
þ
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
VZORKOVACÍ TEORÉM
•s(t) → s(T1), s(T2), s(T3), …, s(Tn), …
•s(t) → s(T), s(2T), s(3T), …, s(nT), …

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
VZORKOVACÍ TEORÉM
•Reálné vzorkování
þintuitivní (?) zdůvodnění minimální vzorkovací frekvence
þ
•

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
VZORKOVACÍ TEORÉM
SAMPLING
•Vzorkovací frekvence:
•fs > 2B = fN,
•kde B je maximální kmitočet ve vzorkované veličině
•fN –
•Nyquistův, (Shannonův, Kotelnikovův) kmitočet
•TN = 1/fN = 1/2B
•Nyquistův interval (perioda), vzorkovací interval (perioda)

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
VZORKOVACÍ TEORÉM
•Reálné vzorkování
samplingfb
•fsr = (4÷5).fN

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
VZORKOVACÍ TEORÉM
•Aliasing – překrývání spekter
•překrývání spekter - aliasing

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
HARMONICKÁ POSLOUPNOST
þkdyž T = NTvz a tedy f = 1/NTvz nebo
þ
þ
þ
þ
þKomplexní exponenciála samozřejmě rovněž reprezentuje periodickou veličinu, protože platí
þ
þ
þkdy exp(2pj) = cos(2p) + j.sin(2p) = 1 + j0 = 1
•
•
•

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
harmD2
HARMONICKÁ FUNKCE A VZORKOVÁNÍ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
REKONSTRUKCE SPOJITÉ FUNKCE
Z NAVZORKOVANÉ POSLOUPNOSTI
þPředpokládejme, že původní spojitá funkce xa(t) měla frekvenč-ně omezené spektrum Xa(f), tj. platí
pro ni
þ
þ
þ
þkde je X(f) frekvenční spektrum dané posloupnosti. Protože víme, že spektrum navzorkované
posloupnosti je periodické s periodou danou vzorkovací frekvencí, zajímá nás pouze její jedna
(první) perioda, pro kterou v rozsahu frekvencí |f|£ fvz/2 platí
þ
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
REKONSTRUKCE SPOJITÉ FUNKCE
Z NAVZORKOVANÉ POSLOUPNOSTI
þPotom pro původní funkci xa(t) je
þ
þ
þ
þ
þ
þ
þ
þ
þ
þtj. původní funkce je dána nekonečným součtem vzorkovacích funkcí, které procházejí každou
hodnotou xa(t) z nekonečného počtu vzorků navzorkované posloupnosti.
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
REKONSTRUKCE SPOJITÉ FUNKCE
Z NAVZORKOVANÉ POSLOUPNOSTI

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þROZKLAD DISKRÉTNÍCH POSLOUPNOSTÍ NA DÍLČÍ HARMONICKÉ SLOŽKY

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
HARMONICKÁ ANALÝZA DISKRÉTNÍCH POSLOUPNOSTÍ
þ
þdiskrétní Fourierova řada
þFourierova transformace s diskrétním časem
þdiskrétní Fourierova transformace
þrychlá Fourierova transformace

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
ROZKLAD DISKRÉTNÍHO PERIODICKÉHO SIGNÁLU
þspojitý signál – opakování
þ Fourierova řada (v komplexním tvaru)
•kde cn jsou komplexní Fourierovy koeficienty
•Ω – úhlový kmitočet základní harmonické složky (základní harmonická);

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
FOURIEROVA ŘADA
PRO DISKRÉTNÍ SIGNÁLY
þnechť x(kTvz) je periodický signál s periodou NTvz; pak x(kTvz) lze rozložit pomocí komplexní
exponenciální Fourierovy řady
þ
þ
þ kde

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
FOURIEROVA ŘADA
DŮKAZ
þzměňme index sumace ve vztahu pro výpočet koeficientu cn

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
FOURIEROVA ŘADA
DŮKAZ
•(součet N členů geometrické posloupnosti                       )
s_n = a_1 \frac{ 1 - q^n }{ 1 - q }

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þx(kTvz) = A.cos(2pk/N) je periodická funkce s periodou N
FOURIEROVA ŘADA
PŘÍKLAD

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
FOURIEROVA ŘADA
PŘÍKLAD

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þnechť x(kTvz) je časově omezený signál s diskrétním časem s x(kTvz)=0 pro všechna celá k>N1 a
k<-N1, kde N1 je celočíselná konstanta.
FOURIEROVA TRANSFORMACE S DISKRÉTNÍM ČASEM - DTFT
•vz
•vz

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þdále, nechť pro kladné sudé celé číslo N>2N1 označíme             periodický signál s periodou NT,
který je x(kTvz) pro k = -N/2, -(N/2)+1, …, -1, 0, 1, …, (N/2)-1.
þz definice           máme
FOURIEROVA TRANSFORMACE S DISKRÉTNÍM ČASEM - DTFT
•vz
•vz
•vz
•vz

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þprotože             je periodická funkce s periodou NTvz, má Fourierovu řadu
FOURIEROVA TRANSFORMACE S DISKRÉTNÍM ČASEM - DTFT

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þZ definice              vyplývá, že lze poslední uvedenou rovnici přepsat do tvaru
þ
þ
þ
þ
þ
þkde ω je pro N→¥ spojitá (nediskrétní) veličina.
FOURIEROVA TRANSFORMACE S DISKRÉTNÍM ČASEM - DTFT

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
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í veličina x(nTvz)=0 pro n < 0 a n ≥ N-1, pak DFT je
definována vztahem

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
ZPĚTNÁ DISKRÉTNÍ FT – DFT-1

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
INVERZIBILITA DFT

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
DFT
ω1 = 2Ω
= 4p/NTVZ
•
DFTr.bmp

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
DFT
ω1 = 2,5Ω = 5p/NTVZ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þ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

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þ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 = N2.P
RYCHLÁ FOURIEROVA TRANSFORMACE - FFT

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þvstupní posloupnost o sudém počtu vzorku rozdělíme na dvě dílčí posloupnosti
þ {gi} = {x2i} - sudé prvky původní posloupnosti,
þ {hi} = {x2i+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

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
FFT
ROZKLAD V ČASOVÉ OBLASTI

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
FFT-2
FFT
ROZKLAD V ČASOVÉ OBLASTI

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þ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 = 2m
FFT
ROZKLAD V ČASOVÉ OBLASTI

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
FFT
ROZKLAD V ČASOVÉ OBLASTI

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
FFT
ROZKLAD V ČASOVÉ OBLASTI

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þkaždý uzel v grafu představuje jedno komplexní násobení a součet
þN uzlů ve vrstvě; celkem m vrstev m=log2N
þcelková pracnost:
þP.N.m = P.N.log2N
þ to představuje při N=8 úsporu 60%, při N=1024 již téměř 99% a při N=131072=217 dokonce 99,99%
FFT
ROZKLAD V ČASOVÉ OBLASTI

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þ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
FFT
ROZKLAD V ČASOVÉ OBLASTI