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).

 

Mišići grkljana slepog miša brže proizvode zvuk nego što vi možete trepnuti

Ovde imam dve zanimljive stvari.

1)      Ovo Bat Man ne može.

2)      Svi znaju kako TO radi, ali se niko do sada nije pozabavio time i zaista video pravu mehaniku koja stoji iza ovog fenomena.

Dakle, super heroj (koji, usput budi rečeno, to nije, jer nema super moći nego se koristi vrlo skupim tehnološkim igračkama) ne može se podičiti onim što ovi mali sisari mogu.

Myotis daubentonii - Maleni slepi miš sa njabržim mišićima u celom Meksiku i šire. 😉 Izvor: Lasse Jakobsen & Coen Elemans

Idemo redom. Nisu mnogo lepi, uglavnom se kreću u periodu od sumraka do svitanja, ako se slučajno nađu na zemlji, lako mogu stradati od većih grabljivica i vrlo su smešni dok se kreću. Međutim, međ’ braćom sisarima, oni su jedini koji mogu da lete (i to odlično), a ispostavilo se da poseduju suludu brzinu kontrakcije mišića grkljana. Dok šišmiš leti u potrazi za plenom, oni ispuštaju zvuk ubrzanim ritmom. Postepeno, ta učestanost raste i može dostići 160-190 zvukova (kratkih zvučnih impulsa) u sekundi. Ovo je moguće zahvaljujući mišićima grkljana koji mogu kontrahovati i do 200 puta u sekundi, tvrde istraživači.

Tokom samog procesa lova, ovi sisari počinju ispitivanje terena sa manjim učestanostima ispuštanja zvuka, a što si bliži plenu to je frekvenca veća da bi na kraju ceo proces kulminirao terminalnim brujanjem (terminal buzz) . Koen Elemans i Džon Ratklif (Coen Elemans, John Ratcliffe) sa univerziteta u Danskoj (University of Southern Denmark) su se pozabavili genezom ovog brujanja u svojoj skorašnjoj studiji. Sem toga, hteli su utvrditi da li je brzina učestanosti brijanja funkcija brzine prijema povratnog signala, koji dolazi od plena, ili je to samo zato što imaju fizičko ograničenje grkljanskog aparata pri proizvodnji zvuka.

Slepi miš na osnovu vremena odbijanja zvuka koji sam proizvodi i njegove promene posle odbitka od mete, ima vrlo preciznu predstavu o poziciji mete (plena). Što se više približava svojoj meti, ovaj sisar ubrzava ritam zvukova i tako, samo na osnovu zvuka, on vrlo precizno prati svoju žrtvu, sve dok je ne uhvati.

Da bi otkrili zamišljeno, naučnici su u izolovanu sobu postavili 12 mikrofona i snimili su aktivnosti i kretanje 5 slobodno letećih šišmiša (vrsta: Myotis daubentonii). Možete ih naći bilo gde na severnoj hemisferi od Britanije, pa sve do Japana, ako krenete na istok.

„Leteći miševi“ su lovili larve moljca koje su visile svuda po prostoriji. Brzina proizvodnje zvuka je bila toliko velika da si istraživači odmah shvatili da se za njihovu proizvodnju ne mogu koristiti obični mišići za pokretanje kostura (kod čoveka bi to bio,na primer, biceps).

Zatim, zakačili su mišiće sa grkljana slepog miša na motor, i stimulisali ih na kontrahovanje. Istraživači su posmatrali da su mišići bili u stanju da kontrahuju do frekvenci od 180 HZ, a u jednom slučaju i do 200 Hz.

Sem toga, primećeno je da se povratni eho jednog signala (zvuka) završavao (dolazio do same životinje nazad) pre nego što je novi zvuk pušten. Zbog toga se ne može desiti da se ovaj leteći sisar zbuni  prilikom prijema sopstvenih signala. Pokazalo se da ove životinje mogu proizvesti, teoretski, zvučne signale (brujanja) i sa većim frekvencijama nego 200Hz – mogu dostići učestanost i do 400 Hz, pere nego što interferenca (preklapanje i mašanje zvučnih signala) postane problem. Postavlja se pitanje, pa zašto to i ne praktikuju? Razlog: ovi super brzi mišići su jedini toliko brzi. Tehnički rečeno,  šišmiš bi morao da unapredi još neke delove svog navigacionog aparata, da bi imao koristi od frekvencija koje prevazilaze utvrđeno granicu od 200 Hz.

Ova slika pokazuje vazušne sposobnosti slepog miša tokom lova. Izvor: Lasse Jakobsen & Coen Elemans

Andriju Mid (Andrew Mead), diplomac na biološkom fakultetu u Pensilvanijskoj školi umetnosti i nauke (University of Pennsylvania’s School of Arts and Science) kaže da se rad mišića može porediti sa radom motora kod automobila: „Motor može biti naštimovan da radi efikasnije ili da bude moćniji, ali to zavisi od toga šta želite uraditi sa njim.“

Konkretno, kod šišmiša, oni namerno gube na snazi da bi dobili vrlo brze oscilacije. „Na isti način, kao kada bi ste vi namestili mehanički motor da ima veliki broj obrtaja u minuti.“

Mišići grkljana, kod slepog miša, 20 puta brže kontrahuju nego najbrži mišići oka kod čoveka, i oko 100 puta brže nego tipičan mišić kostura, tvrde istraživači.

Ranije se mislio da ovako lucidno brze mišiće imaju samo neke vrsta zmija (zvečarke – za proizvodnju zvuka) i neke vrste riba. Elemans ih je našao i kod nekih ptica pevačica, a sada ih je pronašao i kod sisara. Sve je jasnije da su ovi specijalni mišići mnogo češći u životinjskom svetu nego što se to, pre, mislilo.

Rad o ovom fenomenu je objavljen u časopisu Science.

Lični zaključak: Ako imate neki uređaj koji radi u nekom opsegu vrednosti, njegovo optimalno korišćenje je uvek u sredini tog opsega, nikada na krajevima. Pri datim srednjim vrednostima sistem se „oseća“ dobro, dugo može raditi i minimalna je šansa da se desi neki kvar ili povreda. Opet, u životinjskom svetu ima primera prilagođenosti gde se namerno forsira ekstremna situacija da bi se postigao željeni rezultat. Neverovatna gepardova brzina je tipičan primer za to.

I am just saying…

Elektronski paparazo – sistem koji će fotografisati elektrone tokom akta interakcije sa drugim česticama

U radu publikovanom u jednom od skorašnjih izdanja Nature of Photonics,  internacionalni tim (što je za svaku pohvalu) istraživača je objavio da su napravili značajan iskorak napred u proučavanju fizike elektrona. Sa ovim radom, deluje, da je naučna javnost za korak bliža vrlo zanimljivoj mogućnosti da se naprave efektivni video snimci pojedinačnih elektrona. Nivo mogućnosti koje se naziru je jednak onom kada jednom sa običnog vida ili sočiva pređete na optički mikroskop. Neki bi, jednostavno, rekli: progledao sam…

Šematski prikaz novog dizajna lasera koji će emitovati ultra kratke pulseve svetlosti. Svetlosni talasi različitih frekvencija (crveni i zeleni) su kombinuju u novi talas (žuti), koji prolazi kroz gas (plave tačkice). Svetlost pobuđuje atome gasa, koji, onda ispuštaju višak energije kao svetlost koja poseduje još veću frekvenciju.

Ako se ispostavi da je pristup dobar, to će praktično značiti da će naučnici biti u stanju da istražuju elektrone i njihove interakcije sa, do sada, neverovatnim nivoom detalja. To znači, sa aspekta hemije, da će jedan hemičar moći da posmatra reakciju pojedinačnih molekula. Slično važi za sve grane nauke i tehnologije koje se baziraju na saznanjima koja im pruža hemija.

Grupa istraživača je dosta velika i, samo, 8 njih je sa univerziteta MIT, iz elektronske istraživačke laboratorije ili Research Laboratory of Electronics (RLE). Tehnika koja bi omogućila ovako detaljan pogled u svet elektrona i molekula se bazira na korišćenju lasera. Osnovni koncept podrazumeva da se može proizvesti laserski snop koji bi trajao 1 atosekundu (attosecond), što predstavlja 1 milijarditi deo milijarditog dela sekunde, ili ako vam je teže da zamislite, evo i drugog zapisa: 10-18s. Tu već dolazimo do malog problema: najkraće izmereno vreme je „samo“ 100 atosekundi. Vratimo se laserima i da vidimo zašto je atosekunda toliko važna. Na primer, elektron u vodoniku (H2) obavi jednu revoluciju oko jezgra (jedna krug) za nekih 151 atosekundi. Da bi smo ga uhvatili kako „opšti“ nije nam dovoljan vremenski interval od 100 atosekundi, mora biti barem jedan red veličina manji, ako ne i dva. I taman toliko je atosekunda manja, za dva reda veličina. Kroz brojeve bi to bilo:

Za 151 atosekundu elektron obrne ceo krug ili 360°.

To znači da je potrebno za pola kruga oko 75 atosekundi.

Elektronu je, onda, potrebno 360 : 151 = 2.384 atosekundi da prebriše ugao od jednog stepena.

Dakle, puls od  jedne atosekunde je više nego dobrodošao.

„Ako možete stvoriti puls koji ima kraće trajanje, onda možete da ispitate dinamiku koja se odvija na toj skali“, kaže Franz Kartner (Franz Kaertner), profesor sa odeljenja za elektronski inženjering i kompjuterske nauke, koji je, inače, vodio celo istraživanje. „Ovo nas povezuje sa radom Harolda Edgertona (Harold Edgerton)“, u kome je on bio sposoban da napravi, sa optičkom fotografijom, snimke čije je trajanje bilo mereno u mikro i nano sekundama.“

Da, atosekundni pulsevi lasera su bili mogući i ranije, ali nisu imali dovoljnu jačinu, koja je potrebna za tzv vremensku spektroskopiju, tehnika koja se, tipično, koristi za merenje dinamike elektrona. Novi pristup stvaranju ovih laserskih pulseva, ne samo da će omogućiti veću snagu, nego i jednostavniju aparaturu, što je čini još praktičnijom nego ranije. Deluje kao kombinacija u kojoj svi dobijaju…

Mnogostrukost

Da bi se dobio izuzetno kratki puls svetlosti, neophodno je kombinovati svetlosne talase različitih frekvencija. Talas se može prikazati kao izvijena linija koja u pravilnim razmacima dostiže stalno istu tačku, gde je frekvencija, u stvari, „rastojanje“ između tih dvaju izbočina. Kada kombinujemo dva talasa, on se pojačava tamo gde se ove „izbočine poklapaju“, ali ako nema tog poklapanja dolazi do suprotnog efekta – međusobno se poništavaju. Sa pravom kombinatorikom moguće je napraviti novi talas sa radikalno drugačijom oblikom.

Crni talas je rezultat sabiranja plavog poketnog talasa i žućkastog neporetnog talsa

Drugi naučnici su pokušali da naprave kratke pulseve svetlosti kombinujući laserske zrake, ali su koristili za svaki zrak po jedan laser. Takav pristup u mnogome otežava proces sinhronizacije zrakova, u pokušaju da se njihove amplitude poklope na željeni način. Istraživači iz RLE odseka i njihove kolege sa univerziteta u Sidneju, politehničkog univerziteta u Milanu i hamburškog univerziteta su, umesto toga, provukli jedan laserski zrak kroz kristal koji ga deli na zrake sa različitim frekvencijama. Pošto su zraci iz istog izvora, oni ostaju i dalje savršeno sinhronizovani.

Sve kraće i kraće

Opisana tehnika, daje vrlo kratke laserske pulseve svetla, ali i dalje nisu na nivou atosekunde. Sledeći korak je propustiti dobijene pulseve kroz gas.  Kada čestice laserskog snopa – fotoni – udare u atome gasa, oni bivaju apsorbovani (uobičajena interakcija atoma i fotona), ali se odmah posle apsorpcije desi i proces ponovnog emitovanja novog fotona. Ovi poslednji, ponovo emitovani, fotoni mogu imati frekvencije koje mogu biti mnogo puta veće od onog fotona koji je udario u atom. Veće frekvencije znače još kraće pulseve svetlosti.

Međutim, RLE istraživači još nisu sproveli poslednji korak. Za sada, oni provlače laserski zrak kroz dva pojačavača da bi mu povećali energiju, ali i dalje ima potrebe za dodatnom energijom da bi izazvao dovoljno visoko frekventne fotone iz interakcije sa gasom. Dodavanje još jednog pojačavača bi trebalo da reši energetski problem, ali to, trenutno, uspostavlja dodatne tehničke i inženjerske probleme koji se moraju rešiti.

Jan Valmsli (Ian Walmsley), profesor fizike sa Oksfordskog univerziteta i vođa univerzitetske grupe koja se bavim kvantnom optikom (Ultrafast Quantum Optics Group), kaže da je modularnost pristupa ove grupe istraživača najveća prednost. „Pametan dizajn koji primenjuju Franz i njegove kolege koristi mogućnost da sve komponente rade u sinhronom režimu.“, tvrdi Valmsli. „Ovaj novi pristup, mislim da je vrlo važan jer, u principu, omogućava generisanje mnogo većih energija u tim kratkim pulsevima.“

Valsmli, doduše, sumnja da taj poslednji gasni korak u proizvodnji dovoljno kratkih pulseva svetlosti „neće biti jednostavan.“ Ali, odmah dodaje: „Postoje aspekti ovog pristupa problemu koji obećavaju. Može se pokazati kao izazov za sebe postići sve kraće i kraće impulse, ali mislim, da je moguće izvesti.“

Ok, i čemu sve to?

Recimo, na primer, da ne znamo mnogo o molekulima, atomima i elektronima. Krenimo samo od toga da se elektroni vrte oko jezgra. Zamislimo sada da je to isto kada bismo uzeli neki satelit i postavili ga da se okreće oko planete Zemlje. Ono što je problem naučnicima, još uvek, je činjenica da oni ne mogu da vide elektron kako se tačno kreće, jer je mnogo brz. Ako se vratimo na primer sa Zemljom to bi, sa bilo koje distance, izgledalo kao da naša planeta ima prsten poput onih koji se nalaze oko Saturna, jer se taj virtuelni satelit užasno brzo kreće.

Sada, sa novim metodama, elektron više nije tako brz, tačnije, on se i dalje kreće istom brzinom, ali naša kamera je sada „brža“ od njega. Prva dobra stvar – elektron će još biti opipljiviji, kao materijalni objekat. Drugo, njegova putanja će biti, teoretski, oslikana direktno, korak po korak.

Doduše, ostaje pitanje, šta se dešava sa definicijom elektronskih orbitala koja se mogla dosta često čuti i tokom školovanja:

„Orbitale su najverovatnije putanje na kojima se nalaze elektroni…“

Ako priča o laserima znači da će u prethodnoj rečenici reč najverovatnije biti zamenjena sa sigurno, to je za naučni svet, najverovatnije 🙂, veliki korak u istraživanju sveta elementarnih čestica.