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
V. Č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
þZÁKLADNÍ TYPY MATEMATICKÝCH MODELŮ VELIČIN DISKRÉTNÍCH V ČASE

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
PERIODICKÉ POSLOUPNOSTI
þDiskrétní posloupnost x(nTvz) je periodická s periodou NTvz, právě když platí
þx[(n+k.N)Tvz] = x(nTvz),  pro n, k = 0, ±1, ±2, … ,
þ
þve zkráceném tvaru argumentu
þx[n+k.N] = x(n),  pro n, k = 0, ±1, ±2, … .
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
E) PERIODICKÉ A NEPERIODICKÉ VELIČINY
þPozor!
þDiskrétní signál získaný rovnoměrným vzorkováním  periodického spojitého signálu nemusí být
periodický.
þSoučet dvou spojitých periodických signálů nemusí být periodický signál.
þSoučet dvou diskrétních periodických signálů je vždy periodický signál.
èPohov!
nPro diskrétní signál definujeme periodický signál s periodou N obdobně
a

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
PERIODICKÉ POSLOUPNOSTI

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
HARMONICKÁ FUNKCE A VZORKOVÁNÍ
harmD1

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
JEDNORÁZOVÉ POSLOUPNOSTI
þdiskrétní jednotkový impulz (Kronekerovo delta)
þdiskrétní jednotkový skok

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
JEDNORÁZOVÉ POSLOUPNOSTI
þPodobně jako pro spojitou nezávisle proměnou platí i pro diskrétní, že
þ
þ
þresp.
þ
þ
þA také
þ
þ
þa
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þZÁKLADNÍ OPERACE S MATEMATICKÝMI MODELY SIGNÁLŮ DISKRÉTNÍCH V ČASE

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
JE TO TŘEBA?

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
DISKRÉTNÍ KONVOLUCE
þspojité funkce
þ
þ
þdiskrétní posloupnosti

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
DISKRÉTNÍ KONVOLUCE
SCHÉMA VÝPOČETNÍHO ALGORITMU

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
DISKRÉTNÍ KONVOLUCE
þpro kauzální posloupnosti, tj. takové pro které platí x(n) = 0 pro n < 0 se konvoluční vztah mění
na
þ
þ
þ
þV reálných podmínkách při zpracování reálných dat samozřejmě nejsou posloupnosti x1(n) a x2(n)
nekonečné, nýbrž mají konečnou délku. Předpokládejme obecně N1 vzorků v případě posloupnosti x1(n)
a N2 vzorků v případě posloupnosti x2(n). Dále položme x1(n) = 0 pro n Ï á0, N1-1ñ a analogicky
x2(n) = 0 pro n Ï á0, N2-1ñ.

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
DISKRÉTNÍ KONVOLUCE
SCHÉMA VÝPOČETNÍHO ALGORITMU

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
DISKRÉTNÍ KRUHOVÁ KONVOLUCE
SCHÉMA VÝPOČETNÍHO ALGORITMU

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
DISKRÉTNÍ KONVOLUCE
PŘÍKLAD
þVypočtěte konvoluci posloupností x1 = {x10, x11, … x13} a x2 = {x20, x21, x22}.
þ
þŘešení:
þPro výpočet se také občas uvádí následující výpočetní schéma:
þ{x10, x11, … x13} * {x20, x21, x22} =
þ= (x10. x20)(x10. x21)(x10. x22)
þ        (x11. x20)(x11. x21)(x11. x22)
þ           (x12. x20)(x12. x21)(x12. x22)
þ    (x13. x20)(x13. x21)(x13. x22)
þ
þ součet dílčích součinů v jednotlivých sloupcích
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
DISKRÉTNÍ KONVOLUCE
PŘÍKLAD
þVypočtěte konvoluci posloupností x1(n) = {1, 2, -2, -1} a x2(n) = {1, -1, 1} .
þ
þŘešení:
þPro výpočet se také občas uvádí následující výpočetní schéma:
þ{1, 2, -2, -1} * {1, -1, 1} =
þ= 1 -1 1
þ 2 -2 2
þ -2 2 -2
þ -1 1 -1
þ 1 1 -3 3 -1 -1
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
DISKRÉTNÍ KORELACE
þpro spojitý případ obecně platí
þ
þza předpokladu stacionarity a ergodicity pro funkce s definičním oborem tÎ(-¥, ¥)
þ
þ
þa abychom se vyhnuli limitním komplikacím i v podstatě nulovým hodnotám takto určené korelační
funkce využívá se pouze integrální části vztahu

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
DISKRÉTNÍ KORELACE
þna konečném intervalu
þ
þ
þ
þpro diskrétní posloupnost

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
DISKRÉTNÍ KORELACE

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
DISKRÉTNÍ KORELACE
þodhad s konstantní vahou
þ
þkaždá hodnota korelační sumy se považuje za hodnotu autokorelační funkce se stejnou vahou, která
se rovná převrácené hodnotě celkového počtu vzorků vstupních posloupností x1(n) a x2(n), N je délka
posloupnosti. Střední hodnota tohoto odhadu je (bez důkazu)
þ
þ
þkde Rx1x2(m) je skutečná hodnota korelační funkce. To znamená, že střední hodnota odhadu se
nerovná správné hodnotě, ale blíží se jí, když N®¥ a |m| << N. Platí tedy, že
þ
þ
þodhad je asymptoticky nevychýlený.

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
DISKRÉTNÍ KORELACE
þodhad s konstantní vahou
þ
þ
þOdhad rozptylu pro posloupnosti reálných čísel je přibližně
þ
þ
þProtože odhad rozptylu konverguje pro N ® ¥ k nule, je odhad korelační funkce konzistentním
odhadem Rx1x2(m). Z praktického hlediska to všechno znamená, že se snižujícím se počtem součinů
v korelační sumě se relativně zvyšuje váha, kterou je hodnota součtu násobena a tedy i v případě
periodických posloupností není průběh jejich korelační funkce periodický, nýbrž se její kmity
tlumí.
þ
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
DISKRÉTNÍ KORELACE
þodhad s proměnnou vahou
þ
þ
þstřední hodnota tohoto odhadu je
þ
þ
þcož znamená, že je rovna, pro libovolné N a m, skutečné hodnotě korelační funkce. Rozptyl tohoto
odhadu
þ
þ

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
KRUHOVÁ DISKRÉTNÍ KORELACE

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
DISKRÉTNÍ KORELACE
PŘÍKLAD ZE ŽIVOTA

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

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