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. 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 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é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 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Ů 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