Sveučilište u zagrebu fakultet elektrotehnike I ra
Download 0.83 Mb. Pdf ko'rish
|
- Bu sahifa navigatsiya:
- Slika 9. Spektar niza impulsa – preuzeto iz [4]
- Slika 10. Spektar jednog impulsa- preuzeto iz [4]
- 2.3.5 Digitalna ra čunala i Fourierova transformacija
- Slika 11. Spektar neperiodi čnog kontinuiranog signala – preuzeto iz [4]
- Slika 12. Spektar neperiodi čnog diskretnog signala – preuzeo iz [4]
- Slika 13. Diskretan spektar – preuzeto iz [4]
- 2.3.6 Op ćenito o uzorkovanju
- Slika 15. Niz Diracovih impulsa – comb(t)
- Slika 16. Novonastali signal
- Slika 17. Princip rada Radix- 2 FFT – preuzeto iz [5]
- Slika 18. Grafi čka interpretacije algoritma – preuzeto iz [5]
- Slika 14. Butterfly kompleksno množenje
- Slika 19. Ukupan dijagram toka Radix- 2 algoritma nad 8 uzoraka – preuzeto iz [5]
- Tablica 1. Redoslijed uzoraka na ulazu u FFT
|
16 2.3.4 Kontinuirana Fourierova transformacija Do sada je pokazano kako se može izračunati spektar periodičnih signala koristeći Fourierov red. Nažalost, Fourierov red nam ne može puno pomoći u izračunu spektra neperiodičnih signala. Većina realnih signala je upravo neperiodična. Primjer je zvuk, slika, video itd. Jednom pametnom prilagodbom Fourierovog reda dolazi se do izraza koji računa spektar neperiodičnih signala. Upravo je to glavna bit Fourierove transformacije. Promotrimo sada kako izgleda spektar periodičnog niza pravokutnih impulsa izračunat koristeći Fourierov red.
Kao što je već spomenuto u prošlom poglavlju spektar je diskretan. Spektralne komponente razmaknute su za recipročnu vrijednost temeljnog perioda signala.
17 Ako bismo povećavali period pravokutnog signala, spektralne komponente postajale bi sve gušće i gušće. U krajnjem slučaju, dok period teži u beskonačnost spektar postaje kontinuiran. Pogledajmo kako se to odražava na formulu za Fourierov red. ) )
) cos(
( 2 ) ( 1 0 0 0 ∑ ∞ = + + =
n n t n b t n a a t f ω ω Koeficijent 0
nestaje jer je srednja vrijednost impulsa promatrana kroz beskonačnost nule. Sumator koji zbraja spektralne komponente se zamjenjuje integralom jer spektar više nije diskretan, već kontinuiran. Dakle, diskretne frekvencije 0 ω n sada prelaze u kontinuiranu frekvenciju ω .
ω ω ω d t b t a t f n n ∫ ∞ = + = 0 )) sin( ) cos(
( ) ( Ukoliko gornji izlaz zapišemo u kompleksnom obliku (slično kao u poglavlju 2.3.3) dobivamo ω ω ω d e X t f t j ∫ ∞ ∞ − = ) ( ) (
Koeficijent ) ( ω X predstavlja kontinuiranu jačinu harmonika kompleksne eksponencijale. Drugim riječima, predstavlja spektar signala.
∫ ∞ ∞ − − = ω ω ) ( ) (
Ukratko rezimirano, spektar periodičnih signala je diskretan i može se izračunati koristeći Fourierov red. S druge strane, spektar neperiodičnih signala je kontinuiran i računa se uporabom Fourierove transformacije.
18 2.3.5 Digitalna računala i Fourierova transformacija Fourierova transformacija je matematička transformacija signala iz vremenskog područja u frekvencijsko i obratno. Digitalna računala, tj. procesori su diskretni ure aji. Oni nisu sposobni raditi s beskonačnom količinom podataka koje bi unijela jedna kontinuirana funkcija u memoriju računala. Iz tog je razloga potrebno osigurati metodu izračuna spektra nad diskretnim uzorcima signala koje računalo bez problema obra uje. Drugim riječima, cilj je formulu za Fourierovu transformaciju prilagoditi digitalnom računalu. Da bi računalo bilo u mogućnosti izvoditi Fourierovu transformaciju potrebno je • osigurati ulazni signal konačne duljine i konačne širine spektra (tj. konačne maksimalne frekvencije) • signal mora biti otipkan konačnim brojem uzoraka • dobiveni spektar mora imati konačan broj frekvencijskih komponenti
Slika 11. Spektar neperiodičnog kontinuiranog signala – preuzeto iz [4] Sli
Slika 11 prikazuje spektar neperiodičnog kontinuiranog signala. Spektar je tako er neperiodičan i kontinuiran. Otipkajmo sada signal nekom fiksnom frekvencijom otipkavanja
.
19 Slika 12. Spektar neperiodičnog diskretnog signala – preuzeo iz [4] Slika 12 prikazuje kontinuirani spektar. Razlog tomu leži u množenju kontinuiranog signala x(t) s nizom Diracovih impulsa što rezultira konvolucijom u frekvencijskoj domeni izme u ta dva spektra (Diracovog niza i spektra signala). Proces otipkavanja detaljnije je razra en u sljedećem poglavlju. Možemo vidjeti da konvolucija zrcali spektar oko pola frekvencije otipkavanja, tj. spektar se ponavlja s periodom dužine frekvencije otipkavanja. Sljedeći korak je diskretizacija spektra pošto računalo ne može raditi s kontinuiranim spektrom.
Slika 13. Diskretan spektar – preuzeto iz [4] Slika 13 prikazuje uzorkovan spektar. Pogledamo li kako sada izgleda otipkani signal, primjećujemo da je on periodičan. Množenje spektra s Diracovim delta impulsima rezultira konvolucijom u vremenskoj domeni koja čini signal periodičnim. Važna osobina DFT algoritma je ta što očekuje da je ulazni signal periodičan. Vise u ovom problemu u poglavlju 4.5
20 Diskretiziranjem signala i spektra, postigli smo da su oba postala periodična i kao takvi predstavljaju beskonačan skup podataka. Digitalnom računalu želimo ustupiti samo N uzoraka signala koji tvore jedan period. To se postiže jednostavnim množenjem s jediničnim prozorom koji pokriva N uzoraka (izvan perioda prozor ima vrijednost nula). Sada kada imamo diskretan spektar 0 ϖ
i konačan broj uzoraka signala nT , možemo prilagoditi formule opisane u poglavlju 2.3.4 na sljedeći način. ∑ ∑
= − − = = = 1 0 ) 2 ( 1 0 ) 2 ( ) ( ) ( ) ( 1 ) ( N n kn N j N k kn N j e n x k X e k X N n x π π Druga formula naziva se Diskretna Fourierova transformacija (DFT) i omogućava računalu izračun spektra signala od N otipkanih uzoraka. Prva formula predstavlja inverznu transformaciju spektra u signal.
Uzorkovanje signala (otipkavanje) je postupak kojim iz vremenski kontinuiranog signala izvlačimo niz uzoraka (eng. samples). Promotrimo signal x(t) prikazan na slici 14.
Da bismo izvukli uzorke, signal x(t) množimo sa funkcijom comb(t).
21 ∑ ∞ −∞ = − = m s mT t t comb ) ( ) ( δ Funkcija comb(t) se sastoji od niza diskretno postavljenih (po vremenu) Diracovih delta impulsa i prikazana je na slici 15.
Konstanta
predstavlja razmak izme u dva Diracova impulsa. Recipročna vrijednost od
, 1/
s T je vrlo bitan parametar, jer će nakon množenja jednoznačno odrediti frekvenciju uzorkovanja signala s F . Množimo comb(t) sa x(t) s mT t m s u t x mT t t x t x t comb t x = ∞ −∞ = = − = • = ∑ | ) ( ) ( ) ( ) ( ) ( ) ( δ
Kao što vidimo, novonastali signal ) (t x u odgovara početnom signalu isključivo u točkama uzorkovanja, dok je u ostalim točkama nula.
Slika 16. Novonastali signal Crvena linija je početni signal. Vrijednosti u točkama s mT odgovaraju visini Diracovih impulsa (zapravo odgovaraju površini impulsa, no radi lakšeg shvaćanja impulsi su skalirani po visini).
22 Signal ) (t x u je i dalje kontinuiran (ima vrijednost nula izme u točaka uzorkovanja) i potrebno ga je diskretizirati na način da se samo pokupe dobiveni uzorci u točkama uzorkovanja. ] [
2 [ ], 1 [ ], 0 [ | ) ( ] [ n x x x x t x n x s mT t u u = = =
Da bi dobiveni signal postao digitalan, potrebno ga je još i kvantizirati po amplitudi. Postavlja se pitanje: Kada je moguće otipkani signal jednoznačno rekonstruirati? Odgovor na ovo pitanje daje Shannonov teorem o uzorkovanju, koji kaže da frekvencija uzorkovanja mora biti barem dvostruko veća od harmonika najveće frekvencije u signalu. Frekvencija najbržeg harmonika ponekad se naziva Shannonova frekvencija, za koju mora vrijediti spomenuto pravilo. s shann T f 1 ≤ Sve gore opisane postupke, u praksi radi analogno digitalni pretvornik (ADC) opisan u poglavlju 4.2.1
23 Brza Fourierova transformacija (FFT) 3.1 Uvod Promotrimo na trenutak DFT izraz kako bismo utvrdili složenost algoritma. Za N-point DFT potrebno je napraviti 2
kompleksnih množenja, tj. složenost iznosi približno ) (
N O . To je očito iz formule, jer za svaku izlaznu diskretnu frekvenciju, kojih ima N, moramo obaviti N kompleksnih množenja uzoraka ulaznog signala. Točna složenost je nešto veća, jer se zanemaruje potrebna količina zbrajanja. Kao primjer uzmimo da je N=512. Algoritam zahtijeva minimalno 262144 kompleksnih množenja ! Iako bi današnji (god. 2008) procesori s tim vjerojatno bez problema izašli na kraj, to bi značajno umanjilo važnost Fourierovog otkrića. Cilj je provoditi analizu spektra na vrlo štedljivim i samim time sporijim procesorima, kakvi se ugra uju u ugradbena računala (npr. mali prijenosni analizatori spektra). Iz tog su razloga matematičari i inženjeri razvili brojne metode ubrzanja algoritma, bez kojih ovaj završni rad ne bi bilo moguće napraviti na korištenom mikrokontroleru. Svi algoritmi koji na neki način omogućuju digitalnom računalu brži izračun DFT-a zovu se FFT ili Fast Fourier Transform algoritmi. Jedan od njih je Radix-2 algoritam i opisan je u nastavku, jer se upravo on koristi u ovom završnom radu.
24 3.2 Radix-2 algoritam Radix-2 algoritam spada u najjednostavnije FFT algoritme. Osnovni princip rada je da dijeli jednakost za diskretnu Fourierovu transformaciju (DFT) na dva dijela. Ta se novonastala dva dijela tako er dijele, sve dok ne ostane N signala svaki dužine jednog uzorka. Ovaj je princip grafički prikazan na sljedećoj slici.
Ovakav se algoritam naziva i algoritam s decimacijom u vremenu, jer preslaguje vremenske uzorke signala koji se obra uje. Raspišimo sada DFT izraz po tom načelu. )] 1
),..., 3 ( ), 1 ( [ )] 2 ( ),...,
2 ( ), ( [ ) ) 1 2 ( ( ) ) 2 ( ( ) ) 1 2 ( ( ) ) 2 ( ( ) ( ) ( 2 1 2 0 2 2 2 1 2 0 2 2 1 2 0 1 2 0 ) 1 2 ( 2 ) 2 ( 2 1 0 2 − + − = + + = + + = = ∑ ∑ ∑ ∑ ∑ − = − − − = − − = − = + − − − = − N x x x DFT W N x x x x DFT e n x e e n x e n x e n x e n x k X k N N N n nk N j k N j N n nk N j N n N N k n N j k n N j N n nk N j π π π π π π
Gornja jednakost pokazuje da se izlazna spektralna komponenta može izračunati kao suma dva manja DFT-a dužine N/2. Pri tome su uzorci podijeljeni u grupe s parnim i neparnim indeksima.
25 Neparni dio DFT-a množi se s faktorom k N W koji se u literaturi često naziva twiddle faktor.
S G(k) su označeni frekvencijski izlazi iz prvog parnog DFT-a, dok su sa H(k) oni neparnog. Zbog periodičnosti frekvencijskih uzoraka s N/2, kombinirajući izlaze dva manja DFT-a, moguće je izračunati dva frekvencijska uzorka (izlaza) N-point DFT-a uz korištenje različitih twiddle faktora.
Kombiniranje uzoraka manjih DFT-a u veći, prikazano je na slici 14. Dobilo je ime butterfly zbog oblika protoka podataka koji podsjeća na leptira. Butterfly se sastoji od sljedeće dvije jednadžbe.
26 ) ( ) ( ) 2 ( ) ( ) ( ) ( 2 1 2 1
x W k x N k X k x W k x k X k N k N − = + + = Kada se nad skupom od N ulaznih podataka primjeni algoritam do kraja (dok se podaci ne sortiraju u grupice od dva uzorka) i tijek izračuna spektra prikaže gore opisanim butterfly jednadžbama, dobije se dijagram toka prikazan na slici 15. Slika 19. Ukupan dijagram toka Radix- 2 algoritma nad 8 uzoraka – preuzeto iz [5] Napomena: slika demonstrira izračun spektra za 8 uzoraka, a ne 16, kao na slici 13, isključivo zbog preglednosti. Princip je isti. Iz njega se vidi da se algoritam izvršava po nivoima (eng. stage). Ukupan broj nivoa iznosi
2 log . U svakom nivou obavi se točno N/2 butterfly izračuna. Jedan butterfly izračun uključuje jedno kompleksno množenje i dva zbrajanja (osvrnite se na jednadžbe na prethodnoj stranici, twiddle faktor se samo jednom množi s x2(k)). Prema tome ukupna složenost FFT Radix-2 DIT algoritma iznosi N N 2 log 2
Direktan izračun spektra pomoću DFT algoritma za N=512 uzoraka zahtijevao bi 262144 kompleksnih množenja (poglavlje 3.1). Koristeći FFT algoritam, taj se broj
27 svodi na samo 2560 množenja. Što je veći broj uzoraka, to FFT više pokazuje svoju brzinsku prednost nad direktnim izračunom DFT algoritmom. Pogled na sliku 15 otkriva da se ulazni uzorci moraju na neki način preurediti, kako bi se dobili izlazi u pravilnom redoslijedu. Vrlo je lako uočiti da se svaki uzorak nalazi točno na obrnutom (eng. reversed) indeksu. Zamjena indeksa uzoraka prikazana je u tablici 1. Tablica 1. Redoslijed uzoraka na ulazu u FFT Indeks dekad. Indeks (baza 2) Obrnuti index Obrnuti (baza 10) 0 000 000 0 1 001 100
4 2 010 010 2 3 011 110
6 4 100 001 1 5 101 101
5 6 110 011 3 7 111 111
7 Uzorak signala koji se u trenutku uzorkovanja nalazio na indeksu 1 (001 ) 2
) prelazi u indeks (100 ) 2
), tj. 4 itd. Samo preslagivanje uzoraka na ovaj način zahtijeva odre eno procesorsko vrijeme. Prije njegove implementacije potrebno se zapitati: Je li ono stvarno potrebno? Npr. ukoliko aplikacija služi za detektiranje maksimalne frekvencije u signalu, preslagivanje na ulazu u FFT nije potrebno. Softver može nakon izračuna spektra pretražiti rezultate i okrenuti samo onaj indeks na kojemu se nalazi maksimalna vrijednost amplitude. S obzirom na to da je cilj ovog završnog rada izrada analizatora spektra u kojem su sve frekvencijske komponente bitne, okretanje indeksa svih ulaznih uzoraka izvršit će se prije propuštanja uzoraka kroz FFT algoritam. |
