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. FREKVENČNÍ TRASFORMACE
 — DISKRÉTNÍ SIGNÁLY –

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(kT) je periodický signál s periodou NT; pak x(kT) 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(kT) = 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(kT) je časově omezený signál s diskrétním časem s x(kT)=0 pro všechna celá k>N1 a k<-N1,
kde N1 je celočíselná konstanta.
FOURIEROVA TRANSFORMACE S DISKRÉTNÍM ČASEM - DTFT

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(kT) 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

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(nT)=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/NT
fft_princip1

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

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