Alapadatok
Év, oldalszám:2004, 50 oldal
Nyelv:magyar
Letöltések száma:134
Feltöltve:2010. április 23.
Méret:953 KB
Intézmény:
-
Megjegyzés:
Csatolmány:-
Letöltés PDF-ben:Kérlek jelentkezz be!
Értékelések
Nincs még értékelés. Legyél Te az első!Mit olvastak a többiek, ha ezzel végeztek?
Tartalmi kivonat
1 DSP processzorok: 2 3 HP zajgenerátor: 4 Shift regiszter + XOR kapu: 2n állapot Autókorrelációs függvény: l. pénzdobálás: (sin x/x)2 burkoló! 5 Fehérzajhoz a konstans érték kell - megoldás a digitális szűrő Összegezési súlyok sin x/x szerint (ez akár analóg is lehet!!!) Lépcsőfüggvény az órajelnél rövidebb idő alatt: további simı́tás 6 Szűrő tı́pusok Alul/felül/sáváteresztő/sávzáró Aluláteresztő: 1 H(ω) = 1 + F (ω/ω0) • ingadozás az átviteli sávban rossz • ingadozás a vágási részen elfogadható pl. -3 dB adhatja meg a vágási pontot (mint az RC esetén) • vágás mértéke: dB/dekád • vágási szint (pl. -40 dB) • Fázis linearitás csak az átviteli sávban fontos • Fázismenetben a kicsi nemlinearitás még elfogadható lehet Tervezés: bonyolult, n elemre tervezőprogramokkal optimalizálják a fázis és
frekvenciamenetet. 7 Példák: • Bessel: F (ω/ω0) Bessel-fv. maximálisan sima fázismenet lassú felfutás • Butterworth: F (ω/ω0) = ((ω/ω0)2n teljesen sima az átviteli sávban legsimább” átvitel ” • Csebisev: F (ω/ω0) Csebisev-fv. gyors lefutás, de ingadozás is van rossz fázismenet 8 Frekvenciamenet: 1 = kritikusan csillapı́tott; 2 = Bessel; 3 = Butterworth; 4 = Csebisev szűrő 9 Ugrásfüggvény-átvitel: 1 = kritikusan csillapı́tott; 2 = Bessel; 3 = Butterworth; 4/5 = Csebisev szűrő 10 11 12 Képek nagyı́tása, interpoláció Eredeti kép és DFT spektrum: 13 Nagyı́tott kép és DFT spektruma: 14 Legközelebbi szomszéd, átlagolás: Nagyı́tott kép és a simitó magfüggvény: 15 Interpolált kép és DFT spektruma: 16 Lineáris interpoláció : Nagyı́tott kép és a simitó magfüggvény: 17 Interpolált kép és DFT spektruma:
18 Ideális aluláteresztő: Nagyı́tott kép és az ideális aluláteresztő szűrő: 19 Interpolált kép és DFT spektruma: 20 Butterworth szűrés: Nagyı́tott kép és a Butterworth szűrő: 21 Interpolált kép és DFT spektruma: 22 Összehasonlı́tás: Legközelebbi szomszéd és lineáris interpoláció: 23 Ideális aluláteresztő és Butterworth 24 25 DFT - diszkrét Fourier transzformáció Sávlimitált jel - N minta, periódikus! Fourier transzformált: V (kΩ) = N −1 X −iΩknT v(nT )e n=0 itt Ω = 2π NT Mennyi információ, hány különböző jel? N mérési eredmény 26 Ha k = rN + k0 és r =egész 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ódussal ismétlődik! N (valós) adat N/2 független (komplex!) spektrumvonal! 27 A diszkrét Fourier
transzformáció mátrixművelet: (ω = exp(i2π/N )): 0 1 0 V0 1 1 B1 B V1 C ω B B C B V2 C = B 1 ω −2 B . C B @ . A @ VN −1 1 ω −(N −1) 1 ω −2 ω −4 . . . . ω −2(N −1) 10 1 B ω −(N −1) C C B −2(N −1) C B ω CB A@ . ω −(N −1) 2 v0 v1 v2 . 1 C C C C A vN −1 N = 4-re nincs szorzás! 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 érték nem nulla (pl. Dirac delta) minden tag ugyanakkora! Oda-vissza transzformáció: 1 N Vk = faktor! N −1 X n=0 ω −nk vn 28 vn Itt ω = ei2π/N , Fázis problémák: = N −1 N −1 N −1 1 X nk X −lk 1 X nk ω 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áció Fourier transzformáció N 2 szorzás (ugyanannyi, mint a konvolúció) 1965: Cooley és Tukey N log2
N algoritmus 1978: Winograd algoritmus szorzás/pont összeadás/pont 8000 4O 6 4000 6O 91 DFT (1000 × 1000) CT-FFT (1024 × 1024) Winograd (1008 × 1008) CT algoritmus: részekre bontás: N pont DFT N 2 szorzás N/2 pont DFT 2(N/2)2 szorzás külön-külön: eredeti v adatok: g páros és h páratlan adatokra bonthatók, ekkor G és H kombinációja ω k -val szorzódik: ¡ 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én 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öbbszörösen ismételhető N/2 ≤ k ≤ N − 1 0 ≤ k ≤ N/2 − 1 35 Az FFT
algoritmus részei N = 8 esetén Kiinduló adatok és az első lépés 36 Lepkeműveletet 37 A 3 fázis 38 Teljes FFT 39 Teljes transzformáció: (N/2) log2 N lepkeművelet N log2 N : pl. N = 1024 esetén csak 1% szorzás marad! Adatok keverednek az FFT-ben: bit-reverzálás Sok algoritmus (Numerical Recipes, speciális progamok) További sebességnövelés: pl. csak valós 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ásai Univerzális eljárás: konvolúció-dekonvolúció: Gyorsı́tás: • gyorsabb számı́tógép • aritmetikai processzor alkalmazása; • lehetőleg mindent számı́tsunk ki előre (ún. look-up table) • csökkentett fix számábrázolást; • hatékony algoritmusok • DSP (digital signal processor) chipek
használata, szorzás és összeadás egy lépésben 42 43 Cirkuláris konvolúció! 44 Problémák a kvázi-periodikusság miatt: Diszkrét értékek, szivárgás, ha egy jel nem PONTOSAN egy adott spektrumvonalra esik! 45 Megoldás: ablakfüggvény alkalmazása: négyszög 1 Bartlett (háromszög) 1 − 2|n|/(N − 1) Hamming 0.54 + 046 cos( N2πn −1 ) Hanning 0.5 + 05 cos( N2πn −1 ) Blackman 4πn 0.42 + 05 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éb eljárások, módszerek Strassen algoritmus: műveletszám csökkentése: 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áris konvolució: pl. 8 × 8-as cikruláris konvolucióra 64 helyett 17 szorzás: ţ 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ámok hatványai, nem csak 2n hatványok. Pl (Θ = 2π/5): 49 0 1 0 1 0 B0 1 0 0 V0 0 0 0 B 0 B V1 C B1 1 1 C 1 0 −1 C B B B C B B V2 C = B 1 1 −1 1 C B 0. 1 0 B C B CB . @ 1 1 −1 −1 −1 0 A B . @ V3 A @ V4 1 1 1 −1 0 1 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ás! Más felbontás: Walsh, Haar, wavelet alapok! B2 = 0.5(cos Θ−cos 2Θ), B5 = j(sin Θ+sin 2Θ). B5 50
frekvenciamenetet. 7 Példák: • Bessel: F (ω/ω0) Bessel-fv. maximálisan sima fázismenet lassú felfutás • Butterworth: F (ω/ω0) = ((ω/ω0)2n teljesen sima az átviteli sávban legsimább” átvitel ” • Csebisev: F (ω/ω0) Csebisev-fv. gyors lefutás, de ingadozás is van rossz fázismenet 8 Frekvenciamenet: 1 = kritikusan csillapı́tott; 2 = Bessel; 3 = Butterworth; 4 = Csebisev szűrő 9 Ugrásfüggvény-átvitel: 1 = kritikusan csillapı́tott; 2 = Bessel; 3 = Butterworth; 4/5 = Csebisev szűrő 10 11 12 Képek nagyı́tása, interpoláció Eredeti kép és DFT spektrum: 13 Nagyı́tott kép és DFT spektruma: 14 Legközelebbi szomszéd, átlagolás: Nagyı́tott kép és a simitó magfüggvény: 15 Interpolált kép és DFT spektruma: 16 Lineáris interpoláció : Nagyı́tott kép és a simitó magfüggvény: 17 Interpolált kép és DFT spektruma:
18 Ideális aluláteresztő: Nagyı́tott kép és az ideális aluláteresztő szűrő: 19 Interpolált kép és DFT spektruma: 20 Butterworth szűrés: Nagyı́tott kép és a Butterworth szűrő: 21 Interpolált kép és DFT spektruma: 22 Összehasonlı́tás: Legközelebbi szomszéd és lineáris interpoláció: 23 Ideális aluláteresztő és Butterworth 24 25 DFT - diszkrét Fourier transzformáció Sávlimitált jel - N minta, periódikus! Fourier transzformált: V (kΩ) = N −1 X −iΩknT v(nT )e n=0 itt Ω = 2π NT Mennyi információ, hány különböző jel? N mérési eredmény 26 Ha k = rN + k0 és r =egész 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ódussal ismétlődik! N (valós) adat N/2 független (komplex!) spektrumvonal! 27 A diszkrét Fourier
transzformáció mátrixművelet: (ω = exp(i2π/N )): 0 1 0 V0 1 1 B1 B V1 C ω B B C B V2 C = B 1 ω −2 B . C B @ . A @ VN −1 1 ω −(N −1) 1 ω −2 ω −4 . . . . ω −2(N −1) 10 1 B ω −(N −1) C C B −2(N −1) C B ω CB A@ . ω −(N −1) 2 v0 v1 v2 . 1 C C C C A vN −1 N = 4-re nincs szorzás! 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 érték nem nulla (pl. Dirac delta) minden tag ugyanakkora! Oda-vissza transzformáció: 1 N Vk = faktor! N −1 X n=0 ω −nk vn 28 vn Itt ω = ei2π/N , Fázis problémák: = N −1 N −1 N −1 1 X nk X −lk 1 X nk ω 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áció Fourier transzformáció N 2 szorzás (ugyanannyi, mint a konvolúció) 1965: Cooley és Tukey N log2
N algoritmus 1978: Winograd algoritmus szorzás/pont összeadás/pont 8000 4O 6 4000 6O 91 DFT (1000 × 1000) CT-FFT (1024 × 1024) Winograd (1008 × 1008) CT algoritmus: részekre bontás: N pont DFT N 2 szorzás N/2 pont DFT 2(N/2)2 szorzás külön-külön: eredeti v adatok: g páros és h páratlan adatokra bonthatók, ekkor G és H kombinációja ω k -val szorzódik: ¡ 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én 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öbbszörösen ismételhető N/2 ≤ k ≤ N − 1 0 ≤ k ≤ N/2 − 1 35 Az FFT
algoritmus részei N = 8 esetén Kiinduló adatok és az első lépés 36 Lepkeműveletet 37 A 3 fázis 38 Teljes FFT 39 Teljes transzformáció: (N/2) log2 N lepkeművelet N log2 N : pl. N = 1024 esetén csak 1% szorzás marad! Adatok keverednek az FFT-ben: bit-reverzálás Sok algoritmus (Numerical Recipes, speciális progamok) További sebességnövelés: pl. csak valós 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ásai Univerzális eljárás: konvolúció-dekonvolúció: Gyorsı́tás: • gyorsabb számı́tógép • aritmetikai processzor alkalmazása; • lehetőleg mindent számı́tsunk ki előre (ún. look-up table) • csökkentett fix számábrázolást; • hatékony algoritmusok • DSP (digital signal processor) chipek
használata, szorzás és összeadás egy lépésben 42 43 Cirkuláris konvolúció! 44 Problémák a kvázi-periodikusság miatt: Diszkrét értékek, szivárgás, ha egy jel nem PONTOSAN egy adott spektrumvonalra esik! 45 Megoldás: ablakfüggvény alkalmazása: négyszög 1 Bartlett (háromszög) 1 − 2|n|/(N − 1) Hamming 0.54 + 046 cos( N2πn −1 ) Hanning 0.5 + 05 cos( N2πn −1 ) Blackman 4πn 0.42 + 05 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éb eljárások, módszerek Strassen algoritmus: műveletszám csökkentése: 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áris konvolució: pl. 8 × 8-as cikruláris konvolucióra 64 helyett 17 szorzás: ţ 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ámok hatványai, nem csak 2n hatványok. Pl (Θ = 2π/5): 49 0 1 0 1 0 B0 1 0 0 V0 0 0 0 B 0 B V1 C B1 1 1 C 1 0 −1 C B B B C B B V2 C = B 1 1 −1 1 C B 0. 1 0 B C B CB . @ 1 1 −1 −1 −1 0 A B . @ V3 A @ V4 1 1 1 −1 0 1 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ás! Más felbontás: Walsh, Haar, wavelet alapok! B2 = 0.5(cos Θ−cos 2Θ), B5 = j(sin Θ+sin 2Θ). B5 50
