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, Kamenice 3, 4. patro, dv.č.424

logo-IBA logo-MU
© Institut biostatistiky a analýz
V. DISKRÉTNÍ SIGNÁLY
 — Č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
(signálu, 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 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ého signálu, 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 navzorkovaný signál 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
SAMPLING
Vzorkovací frekvence:
fs > 2B = fN,
kde B je maximální kmitočet ve vzorkovaném signálu
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
Reálné vzorkování
þjiné 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
Aliasing – překrývání spekter

levy-panel-IBA-se-zavojem logo-IBA-transparent logo-MU
© Institut biostatistiky a analýz
þZÁKLADNÍ TYPY MATEMATICKÝCH MODELŮ SIGNÁLŮ 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É SIGNÁLY
þ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 periodický signál, 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
þ
þ
þ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 PERIODICKÝCH POSLOUPNOSTÍ NA DÍLČÍ HARMONICKÉ SLOŽKY

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 NT, 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í signál 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
FFT-result

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