1
DSP processzorok:
2
3
HP zajgener´ator:
4
Shift regiszter + XOR kapu: 2n ´allapot Aut´okorrel´aci´os f¨ uggv´eny: l. p´enzdob´al´as: (sin x/x)2 burkol´o!
5
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 • 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.
7
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
8
Frekvenciamenet:
1 = kritikusan csillap´ıtott; 2 = Bessel; 3 = Butterworth; 4 = Csebisev sz˝ ur˝ o
9
Ugr´asf¨ uggv´eny-´atvitel:
1 = kritikusan csillap´ıtott; 2 = Bessel; 3 = Butterworth; 4/5 = Csebisev sz˝ ur˝o
10
11
12
K´ epek nagy´ıt´ asa, interpol´ aci´ o
Eredeti k´ep ´es DFT spektrum:
13
Nagy´ıtott k´ep ´es DFT spektruma:
14
Legk¨ozelebbi szomsz´ed, ´atlagol´as: Nagy´ıtott k´ep ´es a simit´o magf¨ uggv´eny:
15
Interpol´alt k´ep ´es DFT spektruma:
16
Line´aris interpol´aci´o : Nagy´ıtott k´ep ´es a simit´o magf¨ uggv´eny:
17
Interpol´alt k´ep ´es DFT spektruma:
18
Ide´alis alul´atereszt˝o: Nagy´ıtott k´ep ´es az ide´alis alul´atereszt˝o sz˝ ur˝o:
19
Interpol´alt k´ep ´es DFT spektruma:
20
Butterworth sz˝ ur´es: Nagy´ıtott k´ep ´es a Butterworth sz˝ ur˝o:
21
Interpol´alt k´ep ´es DFT spektruma:
22
¨ Osszehasonl´ ıt´as: Legk¨ozelebbi szomsz´ed ´es line´aris interpol´aci´o:
23
Ide´alis alul´atereszt˝o ´es Butterworth
24
25
DFT - diszkr´ et Fourier transzform´ aci´ o
S´avlimit´alt jel - N minta, peri´odikus!
Fourier transzform´alt:
V (kΩ) =
N −1 X
−iΩknT
v(nT )e
n=0
itt Ω =
2π NT
Mennyi inform´aci´o, h´any k¨ ul¨onb¨oz˝o jel? N m´er´esi eredm´eny
26
Ha k = rN + k0 ´es r =eg´esz
V (kΩ) =
N −1 X
−iΩ(rN +k0 )nT
v(nT )e
n=0
=
N −1 X n=0
−iΩk0 nT
v(nT )e
“ ” −iΩT N r e ≡1
A spektrum N peri´odussal ism´etl˝odik!
N (val´os) adat → N/2 f¨ uggetlen (komplex!) spektrumvonal!
27
A diszkr´et Fourier transzform´aci´o m´atrixm˝ uvelet: (ω = exp(i2π/N )):
0 1 1 1 V0 B1 B V1 C ω B C B B V2 C = B 1 ω −2 B B . C @ @ .. A 1 ω −(N −1) VN −1 0
1 ω −2 ω −4 ...
... ... ...
ω −2(N −1)
10
1
B ω −(N −1) C C B −2(N −1) C B ω CB A@ 2
. . . ω −(N −1)
v0 v1 v2 ...
1 C C C C A
vN −1
N = 4-re nincs szorz´as! 0
1 1 1 1 1 B 1 −i −1 i C B C @ 1 −1 1 −1 A 1 i −1 −i
Ha csak egy ´ert´ek nem nulla (pl. Dirac delta) → minden tag ugyanakkora! Oda-vissza transzform´aci´o: →
1 N
Vk =
faktor!
N −1 X n=0
ω
−nk
vn
28
vn
Itt ω = ei2π/N ,
F´azis probl´em´ak:
=
N −1 N −1 N −1 1 X nk 1 X nk X −lk ω Vk = ω ω vl N k=0 N k=0 l=0
=
N −1 N −1 1 X X k(n−l) vn vl ω = 0 N l=0 k=0
(1 − ω (n−l)N )/(1 − ω n−l ) = 0
(n = l) (n 6= l)
29
30
31
32
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 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) (n = 0, 1, . . . , N − 1)
⇒
g(n) = v(2n) n = 0, 1, . . . N h(n) = v(2n + 1) 0, 1, . . . N/2 −
33
Vk =
N −1 X
N/2−1
vnω
−nk
=
n=0
X
N/2−1
gn ω
−2nk
n=0
+
X
hn ω
(2n+1)k
k = 0, 1, . . . N
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
34
k > N/2 − 1 eset´en ez k − N/2: −k
Vk
=
Gk−N/2 + ωN Hk−N/2
Vk+N/2
=
Gk + ωN
−k+N/2
Hk
Ha N = 2k → t¨obbsz¨ or¨osen ism´etelhet˝o
N/2 ≤ k ≤ N − 1 0 ≤ k ≤ N/2 − 1
35
Az FFT algoritmus r´ eszei N = 8 eset´ en
Kiindul´o adatok ´es az els˝o l´ep´es
36
Lepkem˝ uveletet
37
A 3 f´azis
38
Teljes FFT
39
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) Tov´abbi sebess´egn¨ovel´es: pl. csak val´os adatokkal:
v1(n)
⇐⇒ V1(k)
v2(n)
⇐⇒ V2(k)
V (k)
=
V1(k)
=
∗
V1(k) + iV2(k) V (k) = V1(k) − jV2(k) ˜ 1ˆ ∗ V (N − k) + V (k) 2
40
V2(k)
=
˜ 1ˆ ∗ V (N − k) − V (k) 2
41
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 • DSP (digital signal processor) chipek haszn´alata, szorz´as ´es ¨osszead´as egy l´ep´esben
42
43
Cirkul´aris konvol´ uci´o!
44
Probl´em´ak a kv´azi-periodikuss´ag miatt:
Diszkr´et ´ert´ekek, sziv´arg´as, ha egy jel nem PONTOSAN egy adott spektrumvonalra esik!
45
Megold´as: ablakf¨ uggv´eny alkalmaz´asa:
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.42 + 0.5 cos( N2πn −1 ) + 0.08 cos( N −1 )
4π /N
22 %
8π /N
4%
8π /N
1%
8π /N
2.6 %
12π /N
0.1 %
46
47
48
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 f
«
„ =
c −d d c
«„
a b
«
„ =
1 0 1 0 1 1
«
0
10 c−d 0 0 1 0 @ 0 c + d 0A@0 1 0 0 d 0 −
Winograd algoritmus: primsz´amok hatv´anyai, nem csak 2n hatv´anyok. Pl. (Θ = 2π/5):
49
0
1
1
0
0
B0 V0 1 0 0 0 0 0 B 0 C B V1 C B1 1 1 1 0 −1 C B B B B C C B 0. B V2 C = B 1 1 −1 1 1 0 CB . B C B @ 1 1 −1 −1 −1 0 A B . @ V3 A @ 1 1 1 −1 0 1 V4 0
1 B0 B B0 ×B B0 B @0 0 B0 = 1,
0 0 B2
...
B3 B4
1 0 1 1 1 1 1 v0 1 1 1 1 C C B v1 C B C 1 −1 −1 1 C C B v2 C B C 1 −1 1 −1 C C @ v3 A 1 0 0 −1 A v4 0 −1 1 0
B1 = 0.5(cos Θ+cos 2Θ)−1,
B3 = j sin Θ,
0 B1 0
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Θ).
B5
50
