Brza Furijeova transformacija je postala još brža

U svetu informatike (kao nauke) nema važnijeg algoritma od Furijeove transformacije, a stručnjaci sa MIT-a su našli načina da ga ubrzaju.

Furijeova transformacija je jedan od fundamentalnih koncepata u informatičkoj nauci. Ona predstavlja metod za prikazivanje ne regularnih signala – kao što je dinamička promena napona u žici koja povezuje  MP3 uređaj sa zvučnikom – kao kombinacija čistih učestanosti (frekvencija). Njena primena je univerzalna u obradi signala, a može se iskoristiti prilikom kompresije slike ili digitalnog audio zapisa. Sem toga, može pomoći u rešavanju diferencijalnih jednačina ili u praćenju dinamike tržišta i berze.

Tajna leži, u stvari, u algoritmu koji nazivamo brza Furijeova transformacija, razrađena šezdesetih godina 20. veka, koja omogućava brži račun Fourijeove transformacije, tako reći, u letu. Od kada je algoritam razvijen i ušao u primenu, pa sve do sadašnjeg trenutka, ljudi su se pitali da li je moguće osmisliti neki novi algoritam koji bi bio još brži.

Tokom januara meseca na simpozijumu Diskretnih algoritama (Symposium on Discrete Algorithms [SODA]), grupa istraživača sa MIT univerziteta je predstavila novi algoritam koji, u velikom broju praktičnih primena, poboljšava brzu Furijeovu transformaciju. Pod određenim uslovima, poboljšanje može biti značajno – desetostruko ubrzanje. Novi algoritam je posebno koristan prilikom kompresije digitalne slike. To bi omogućilo uređajima kao što je smartphone da bežičnim putem emituju video materijal, a da im taj proces ne iscrpi skoro svu energiju iz baterija ili da ne potroše mesečni Internet protok za mnogo kraće vreme.

Poput postojećeg starog algoritma, i novi radi sa digitalnim signalima. Digitalni signal je, niz brojeva – diskretan uzorak analognih signala, kao što je zvuk muzičkog instrumenta. Oba algoritma postojeći digitalni signal sa određenim brojem signala izražavaju (prikazuju) kao težinsku sumu (weighted sum) istog broja frekvencija.

Pojam težinski uz reč „suma“ proizilazi iz činjenice da neka vrednost, u ovom slučaju frekvencija ima veći udeo u konačnom rezultatu (veću „težinu“). Zaista, mnoge frekvencije imaju zanemarljivi udeo u konačnom rezultatu, pa ih slobodno možemo otpisati. Ovo je razlog zašto je Furijeova transformacija korisna prilikom kompresije digitalnih podataka. Blok od 8×8 piksela (piksel – 1 tačka na monitoru) se može posmatrati kao signal od 64 podataka ili kao suma od 64 različite frekvencije. Međutim, kao što istraživači pokazuju u svom skorašnjem radu, empirijska istraživanja pokazuju da, u proseku, možemo zanemariti 57 od tih 64 frekvencije. Sa druge strane, gubitak kvaliteta slike je minimalan.

Teško deljenje

Signali koje Furijeova transformacija formira na osnovu relativnog malo broja „teških“ frekvencija se nazivaju „sparse“ (oskudan). Novi algoritam „prepoznaje“ težinu najtežih frekvencija u signalu; što je signal oskudniji, to je veće ubrzanje koje algoritam daje. U krajnjem slučaju, ako je signal dovoljno oskudan, algoritam ga može interpretirati po principu slučajnog izobara, umesto da ga čita potpuno.

„U prirodi, većina normalnih signala su ’oskudni’.“ tvrdi Dina Katabi (Dina Katabi),  jedan od članova istraživačkog tima koji je razvio novi algoritam. „Razmotrimo, na primer, snimanje neke muzičke partiture kamerne muzike. Krajnji, kombinovani zvuk se sastoji od zvukova koje proizvode nekoliko instrumenata i to jednu notu u trenutku. Sa druge strane, snimanje svih mogućih instrumenata koji proizvode sve moguće zvukove u isto vreme ne bi bilo oskudno – ali to ne bi bio signal do koga je nekome stalo!“

Imajući ovo u vidu, kao neku vrstu definicije prirode signala oko nas, nastao je novi algoritam. Autori su profesori Katabi i Piotr Indyk, oboje sa MIT odseka koji se bavi kompjuterskom naukom i veštačkom inteligencijom. Uz njih, na istraživanju su radili i Erik Prajs (Eric Price) i Haitham Hasanej (Haitham Hassanieh), njihovi studenti. Novi algoritam se bazira na dva ključne ideje. Prva stvar je postojeći signal podeliti na uže propusne signale, i to tako da ti odsečci sadrže samo frekvencije sa velikom težinom.

Prilikom obrade signala, osnovni alat za izdvajanje frekvencije je filter. Međutim, filtri često imaju nejasne ili mutne granice. To znači da će određeni opseg frekvencija proći kroz filter, više manje ne promenjen, a frekvencije odmah van opsega filtera će biti prigušene. Što je veća razlika između opsega filtra i neke frekvencije, to će ona biti više prigušena. U krajnjem slučaju, neke frekvencije daleko od opsega neće uopšte proći i biće otklonjene zahvaljujući filtru.

Opisani princip rada filtra može dovesti do situacije gde će se neka od frekvencija sa velikom težinom naći na ivici opsega filtra i samim tim u situaciji da bude prigušena i zanemarena. Zbog toga, istraživači su morali naći efikasan način da kombinuju filtre sa različitim opsezima koji se preklapaju, sve sa ciljem da ni jedna teška frekvencija u ciljanom opsegu ne završi prigušena, ali da granice između isečaka i dalje ostanu dovoljno oštre.

Kada jednom izoluju neki segment spektra, istraživači su i dalje u poziciji da moraju odrediti koje su frekvencije najteže u datom delu. To su postigli učestalim seckanjem posmatranog dela spektra na manje delove i zadržavajući samo one gde je veći deo signala bio skoncentrisan. Za sada, prema radu koji je još neobjavljen,  istraživači opisuju znatno efikasniju tehniku, koja se oslanja na strategiju obrade signala koju koriste 4G telefonske mreže. Frekvencije se mogu posmatrati kao sitna talasanja, ali se zato mogu razmatrati kao oscilacije; obradom istog dela opsega ali u različitim trenucima vremena, istraživači mogu ustanoviti koja je frekvencija dominantna u određenom ciklusu oscilacije.

Istraživanje i rezultat koji sam upravo opisao nije prvo u ovoj oblasti. Dva istraživača sa univerziteta u Mičigenu (SAD), Ana Gilbert (Anna Gilbert) i Martin Štraus (Martin Štraus) su već ranije predložili algoritam koji bi ubrzao svemoguću brzu Furijeovu transformaciju. Međutim, njihov algoritam doprineo ubrzanju u znatno manjem broju slučajeva nego ovaj novi algoritam sa MIT-a. Možda je čak i bolji ali manju vrednost u primenjivanju, manja mu je težina. 😉

Poenta cele priče je – ako želite ubrzanje u domenu obrade podataka, imate dva moguća pristupa:

a) Napraviti još bolji i brži kompjuter koji će moći da se nosi sa još većom količinom podataka nego njegov prethodnik, a da pri tome ne gubite ni jedan jedini podatak

ili

 b) Da optimizujete procese do te mere gde će algoritmi nalaziti pravu i suštinsku informaciju, a sve ostalo proglasiti šumom i nepotrebnim.

Ovaj drugi pristup je definitvno brži, ali morate uvek imati na umu da se prilikom njegove primene može desiti neželjeni, vitalni gubitak informacije. Novi algoritam je tu i verovatno će naći svoju primenu, a koliko će nam pomoći u razvoju nauke i kompjutera, to će tek vreme pokazati.

 ***

U akustici, fizičke barijere, napravljene od čvrstih tela imaju tendenciju da odbijaju zvuk više frekvencije, a da propuštaju zvuk niže frekvencije. Kada se izvor zvuka ili muzike nalazi u susednoj sobi, slušalac će mnogo lakše čuti niže tonove od viših, pod uslovom da je između njega i izvora samo zid (bez ikakvih otvora).

 

Leave a Reply

Your email address will not be published. Required fields are marked *