1
DSP processzorok:
2
3
4
HP zajgener´ator:
5
Shift regiszter + XOR kapu: 2n ´allapot Aut´okorrel´aci´os f¨ uggv´eny: l. p´enzdob´al´as: (sin x/x)2 burkol´o! Feh´erzajhoz a konstans ´ert´ek kell - megold´as a digit´alis sz˝ ur˝o ¨ Osszegez´ esi s´ ulyok sin x/x szerint (ez ak´ar anal´og is lehet!!!) L´epcs˝of¨ uggv´eny az ´orajeln´el r¨ovidebb id˝o alatt: tov´abbi sim´ıt´as
6
Sz˝ ur˝ o t´ıpusok
Alul/fel¨ ul/s´av´atereszt˝o/s´avz´ar´o Alul´atereszt˝o: 1 H(ω) = 1 + F (ω/ω0) • ingadoz´as az ´atviteli s´avban rossz • ingadoz´as a v´ag´asi r´eszen elfogadhat´o pl. -3 dB adhatja meg a v´ag´asi pontot (mint az RC eset´en) • v´ag´as m´ert´eke: dB/dek´ad
7
• v´ag´asi szint (pl. -40 dB)
• F´azis linearit´as csak az ´atviteli s´avban fontos
• F´azismenetben a kicsi nemlinearit´as m´eg elfogadhat´o lehet
Tervez´es: bonyolult, n elemre tervez˝oprogramokkal optimaliz´alj´ak a f´azis ´es frekvenciamenetet.
8
P´eld´ak:
• Bessel: F (ω/ω0) Bessel-fv. maxim´alisan sima f´azismenet lass´ u felfut´as • Butterworth: F (ω/ω0) = ((ω/ω0)2n teljesen sima az ´atviteli s´avban legsim´abb” ´atvitel ” • Csebisev: F (ω/ω0) Csebisev-fv. gyors lefut´as, de ingadoz´as is van rossz f´azismenet
9
Frekvenciamenet:
1 = kritikusan csillap´ıtott; 2 = Bessel; 3 = Butterworth; 4 = Csebisev sz˝ ur˝o
10
Ugr´asf¨ uggv´eny-´atvitel:
11
1 = kritikusan csillap´ıtott; 2 = Bessel; 3 = Butterworth; 4/5 = Csebisev sz˝ ur˝o
12
13
14
K´ epek nagy´ıt´ asa, interpol´ aci´ o
Eredeti k´ep ´es DFT spektrum:
15
Nagy´ıtott k´ep ´es DFT spektruma:
16
Legk¨ozelebbi szomsz´ed, ´atlagol´as: Nagy´ıtott k´ep ´es a simit´o magf¨ uggv´eny:
17
Interpol´alt k´ep ´es DFT spektruma:
18
Line´aris interpol´aci´o : Nagy´ıtott k´ep ´es a simit´o magf¨ uggv´eny:
19
Interpol´alt k´ep ´es DFT spektruma:
20
Ide´alis alul´atereszt˝o: Nagy´ıtott k´ep ´es az ide´alis alul´atereszt˝o sz˝ ur˝o:
21
Interpol´alt k´ep ´es DFT spektruma:
22
Butterworth sz˝ ur´es: Nagy´ıtott k´ep ´es a Butterworth sz˝ ur˝o:
23
Interpol´alt k´ep ´es DFT spektruma:
24
¨ Osszehasonl´ ıt´as: Legk¨ozelebbi szomsz´ed ´es line´aris interpol´aci´o:
25
Ide´alis alul´atereszt˝o ´es Butterworth
26
27
DFT - diszkr´ et Fourier transzform´ aci´ o
S´avlimit´alt jel - N minta, peri´odikus!
28
Fourier transzform´alt: V (kΩ) =
N −1 X
v(nT )e−iΩknT
n=0
2π itt Ω = NT Mennyi inform´aci´o, h´any k¨ ul¨onb¨oz˝o jel? N m´er´esi eredm´eny
Ha k = rN + k0 ´es r =eg´esz
V (kΩ) =
N −1 X n=0
v(nT )e−iΩ(rN +k0)nT =
N −1 X n=0
v(nT )e−iΩk0nT ¡
−iΩT N r
e
≡1
¢
29
A spektrum N peri´odussal ism´etl˝ odik! N (val´ os) adat → N/2 f¨ uggetlen (komplex!) spektrumvonal!
30
A diszkr´et Fourier transzform´aci´o m´atrixm˝ uvelet: (ω = exp(i2π/N )):
V0 V1 V2 ..
1 1 1 ω = 1 ω −2 VN −1 1 ω −(N −1)
1 ω −2 ω −4 ..
... ... ...
ω −2(N −1)
...
N = 4-re nincs szorz´as!
1 1 1 −i 1 −1 1 i
1 −1 1 −1
1 i −1 −i
1
v0 v1 v2 ..
ω −(N −1) −2(N −1) ω 2 ω −(N −1) vN −1
31
Ha csak egy ´ert´ek nem nulla (pl. Dirac delta) → minden tag ugyanakkora! Oda-vissza transzform´aci´ o: →
1 N
faktor!
Vk =
N −1 X
ω −nk vn
n=0
vn =
N −1 N −1 N −1 1 X nk 1 X nk X −lk ω Vk = ω ω vl N N k=0
=
l=0
½ N −1 N −1 1 X X k(n−l) vn vl ω = 0 N l=0
Itt ω = ei2π/N ,
k=0
k=0
(1 − ω (n−l)N )/(1 − ω n−l) = 0
(n = l) (n 6= l)
32
F´azis probl´em´ak:
33
34
35
36
FFT - Fast Fourier transzform´ aci´ o
Fourier transzform´aci´o → N 2 szorz´as (ugyanannyi, mint a konvol´ uci´o) 1965: Cooley ´es Tukey → N log2 N algoritmus 1978: Winograd algoritmus szorz´as/pont
¨osszead´as/pont
8000 4O 6
4000 6O 91
DFT (1000 × 1000) CT-FFT (1024 × 1024) Winograd (1008 × 1008) CT algoritmus: r´eszekre bont´as: N pont DFT → N 2 szorz´as
37
N/2 pont DFT → 2(N/2)2 szorz´as k¨ ul¨on-k¨ ul¨on: eredeti v adatok: g p´aros ´es h p´aratlan adatokra bonthat´ok, ekkor G ´es H kombin´aci´oja ω k -val szorz´odik:
½ v(n) Vk =
(n = 0, 1, . . . , N − 1) N −1 X
⇒
g(n) = v(2n) n = 0, 1, . . . N/2 − 1 h(n) = v(2n + 1) 0, 1, . . . N/2 − 1
N/2−1
vn ω
−nk
=
n=0
X
N/2−1
gnω
−2nk
n=0
+
X
hnω (2n+1)k
k = 0, 1, . . . N − 1
n=0 2 ωN = ωN/2
N/2−1
Vk =
X
n=0
N/2−1 −nk gnωN/2
+
−k ωN
X
n=0
−nk k hnωN/2 = Gk + ωN Hk
k = 0, 1, . . . N/2 − 1
38
k > N/2 − 1 eset´en ez k − N/2:
Vk
−k = Gk−N/2 + ωN Hk−N/2 −k+N/2
Vk+N/2 = Gk + ωN
Hk
Ha N = 2k → t¨obbsz¨or¨osen ism´etelhet˝o
N/2 ≤ k ≤ N − 1 0 ≤ k ≤ N/2 − 1
39
Az FFT algoritmus r´ eszei N = 8 eset´ en Kiindul´o adatok ´es az els˝o l´ep´es
40
Lepkem˝ uveletet
41
A 3 f´azis
42
Teljes FFT
43
Teljes transzform´aci´o: (N/2) log2 N lepkem˝ uvelet N log2 N : pl. N = 1024 eset´en csak 1% szorz´as marad! Adatok keverednek az FFT-ben: bit-reverz´al´as
Sok algoritmus (Numerical Recipes, speci´alis progamok)
44
Tov´abbi sebess´egn¨ovel´es: pl. csak val´os adatokkal:
v1(n)
⇐⇒ V1(k)
v2(n)
⇐⇒ V2(k)
V (k) = V1(k) + iV2(k) V ∗(k) = V1(k) − jV2(k) 1 ∗ [V (N − k) + V (k)] V1(k) = 2 1 ∗ V2(k) = [V (N − k) − V (k)] 2
45
FFT alkalmaz´ asai
Univerz´alis elj´ar´as: konvol´ uci´o-dekonvol´ uci´o: Gyors´ıt´as:
• gyorsabb sz´am´ıt´og´ep • aritmetikai processzor alkalmaz´asa; • lehet˝oleg mindent sz´am´ıtsunk ki el˝ore (´ un. look-up table) • cs¨okkentett fix sz´am´abr´azol´ast; • hat´ekony algoritmusok
46
• DSP (digital signal processor) chipek haszn´alata, szorz´as ´es ¨osszead´as egy l´ep´esben
47
48
Cirkul´aris konvol´ uci´o!
49
50
Probl´em´ak a kv´azi-periodikuss´ag miatt:
51
Diszkr´et ´ert´ekek, sziv´arg´as, ha egy jel nem PONTOSAN egy adott spektrumvonalra esik!
Megold´as: ablakf¨ uggv´eny alkalmaz´asa:
52
n´egysz¨og 1 Bartlett (h´aromsz¨og) 1 − 2|n|/(N − 1) Hamming 0.54 + 0.46 cos( N2πn −1 ) Hanning 0.5 + 0.5 cos( N2πn −1 ) Blackman 4πn ) + 0.08 cos( 0.42 + 0.5 cos( N2πn −1 N −1 )
4π/N
22 %
8π/N
4%
8π/N
1%
8π/N
2.6 %
12π/N
0.1 %
53
54
55
Egy´ eb elj´ ar´ asok, m´ odszerek Strassen algoritmus: m˝ uveletsz´am cs¨okkent´ese:
e + jf = (a + jb)(c + jd)
Strassen :
=⇒
e = ac − bd,
e = (a − b)d + a(c − d),
f = ad + bc.
f = (a − b)d + b(c + d).
Cirkul´aris konvoluci´o: pl. 8 × 8-as cikrul´aris konvoluci´ ora 64 helyett 17 szorz´as: µ ¶ µ ¶µ ¶ µ e c −d a 1 = = f d c b 0
0 1
1 1
¶
1 c−d 0 0 0 c + d 00 0 0 0 d
µ ¶ 0 a 1 b −1
56
Winograd algoritmus: primsz´amok hatv´anyai, nem csak 2n hatv´anyok. Pl. (Θ = 2π/5): B0 0 0 ... V0 1 0 0 0 0 0 0 B1 0 V1 1 1 1 1 0 −1 0 0 B2 V2 = 1 1 −1 1 × 1 0 . . B 3 V3 1 1 −1 −1 −1 0 B4 V4 1 1 1 −1 0 1 B5 1 1 1 1 1 v0 0 1 1 1 1 0 1 −1 −1 1 v1 × 0 1 −1 1 −1 v2 v3 0 1 0 0 −1 v4 0 0 −1 1 0
57
B0 = 1,
B1 = 0.5(cos Θ + cos 2Θ) − 1,
B3 = j sin Θ,
B4 = j(− sin Θ + sin 2Θ),
Bonyolult programoz´as!
M´as felbont´as: Walsh, Haar, wavelet alapok!
B2 = 0.5(cos Θ − cos 2Θ),
B5 = j(sin Θ + sin 2Θ).
58
