Naši veliki umovi: Bane Vasić

Ophrvani iskrivljenim vrednostima u državi, zapljusnuti raznim turbo-rijaliti senzacijalizmima, mi prosto zaboravljamo na svetle primere naših naučnika koji žive i rade kod nas i u svetu. Da ih se ne bismo sećali na godišnjicama smrti, a i da probamo da povratimo makar centimetar poljuljanog morala, upoznaćemo vas sa veoma važnim i intrigantnim domaćim naučnicima

Profesor Bane Vasić, koji je doktorirao na niškom Elektronskom fakultetu, nedavno je došao u žižu javnosti kada je otkrio novi algoritam za korekciju grešaka. Ekskluzivno za „Svet kompjutera” on otkriva detalje o svom radu.

SK: Možete li nam otkriti osnove tog novog sistema za korekciju grešaka? Na čemu se on zasniva? Gde sve može da se primeni?

Prof. Vasić: Pre svega da kažem da je ovaj algoritam za ispravljanje grešaka rezultat saradnje sa kolegom iz Francuske, profesorom Deklerkom (Declercq). U razvoju algoritma učestvovali su i Šiva Plandžeri (Shiva Planjery) i Šaši Kiran Čilapagari (Shashi Kiran Chilappagari) iz moje laboratorije.

U računarima i telekomunikacionim sistemima se na različitim nivoima i dalje koriste klasični sistemi za ispravljanje grešaka zasnovani na algebarskim strukturama. Tipičan primer su Rid-Solomonovi (RS), Hamingovi i BCH kôdovi. Poslednjih desetak godina napravljen je prodor, skoro revolucija, u ovoj oblasti, koja je rezultovala novom klasom kodova nazvanih Low-Density Parity Check (LDPC). Za razliku od dekodovanja RS i BCH kodova, koje se zasniva na komplikovanim operacijama u konačnim poljima, LDPC kodovi imaju elegantan algoritam za dekodovanje po imenu Belief Propagation (BP). BP operiše na grafovskoj reprezentaciji koda tako što prenosi verovatnoće kroz graf.

BP algoritam potiče iz teorije veštačke inteligencije i koristi se za automatsko zaključivanje. Algoritam se zasniva na Bajesovoj teoriji zaključivanja i optimalan je kad se uzroci i posledice u logičkom zaključivanju mogu povezati grafom koji nema petlje (drugim rečima, posledica ne može posredno da bude uzrok sama sebi). Grafovi koji opisuju kôdove po svojoj prirodi imaju petlje i zbog toga BP nije optimalan algoritam za njihovo dekodovanje.

Međutim, BP radi vrlo, vrlo dobro čak i ako postoje petlje, pa je usvojen u mnogim standardima (DVB-S2 standard za satelitsku televiziju, 10 Gb Ethernet, IEEE 802.16e (WiMAX), IEEE 802.11n (WiFi) itd.). Prosto rečeno, BP je najbolji praktičan algoritam koji je poznat. Tačnije, bio je dok nismo objavili naše rezultate.

SK: Proteklih meseci objavljivano je da ste razvili novi sistem za korekciju grešaka. Po čemu je on različit ili bolji od dosadašnjih? Koliko dugo ste ga razvijali?

Prof. Vasić: Za razliku od algoritama za dekodovanje, npr. RS kodova, za koje tačno znamo koliko grešaka mogu da isprave, za BP je taj broj još nepoznat. U zavisnosti od toga gde su, BP može da ispravi veoma veliki broj grešaka, ali može da zataji ako su greške na nekim „nezgodnim” mestima. Razumevanje ove pojave (nazvane error-floor) jedan je od najvažnijih nerešenih problema u modernoj teoriji kodova.

Moja laboratorija radi na ovom problemu skoro deset godina i algoritam koji smo razvili zasniva se na onome što znamo o grafovima čije prisustvo izaziva da algoritam za dekodovanje zataji. Naš dekoder je različit od BP zato što kroz graf ne prenosi verovatnoće nego binarne poruke. Verovatnoće su realni brojevi i u principu je za njihovu reprezentaciju potrebno beskonačno decimalnih mesta. U praksi, međutim, reprezentacija sa 6 bita ne kvari drastično dekoder. Naš dekoder prenosi samo 3 bita, što znači da je, grubo rečeno, 100 odsto prostiji od BP. A uz to radi bolje nego BP.

SK: Vi ste bili profesor na Elektronskom fakultetu u Nišu duži niz godina. Šta vas je u stvari odvelo u SAD? Dalji planovi?

Prof. Vasić: Da, bio je to lep period u Nišu, što i urednik ovog cenjenog časopisa može da posvedoči. I dalje sam u kontaktu sa kolegama u Nišu i svakog leta održim neko predavanje ili kratki kurs. U stvari, radio sam tek godinu dana kao docent kad sam otišao u SAD.

Otišao sam sa namerom da ostanem samo godinu dana. Onda sam dobio posao u Bell Labsu, laboratorijama koje su predstavljale centar sveta za istraživanja u mojoj oblasti, a takvu ponudu bilo je neozbiljno ne prihvatiti. Tamo sam napravio jedan jednostavan i elegantan detektor i dekoder koji se i danas primenjuju u hard diskovima u računarima. Taj pronalazak je otvorio različita vrata, naročito na fakultetima. Na fakultetu u Tusonu sam već deset godina. Univerzitet Arizone ima jake programe u mnogo disciplina i moji projekti se prožimaju s tim programima. Trenutno je najveći projekat na kom radim DARPA projekat od 3,6 miliona dolara, u kojem razvijamo radar, telekomunikacioni prijemnik i uređaj za spektroskopiju koji koriste novu computational sensing teoriju. Za informaciju čitaocima, DARPA je skraćenica za Defense Advanced Research Projects Agency, a to je agencija koja je finansirala nastanak Interneta. Drugi zanimljiv projekat finansiran je od strane National Science Foundation (NSF) i odnosi se na primenu metoda iz teorije kôdova na informacije u genetici, tačnije u analizi mreža za regulaciju gena. Projekat na temu Flash memorija sa IBM Research Labom iz Ciriha treba da počne ove godine, kao i projekat za razvoj novih LDPC kodova za Seagate Research i detektora za bit patterned medije za konzorcijum IDEMA (International Disk Drive Equipment and Materials Association).

SK: Da li ste pregovarali sa nekim firmama o daljoj budućnosti tog algoritma za korekciju grešaka?

Prof. Vasić: Proces je još u toku. STMicroelectronics je licencirao tehnologiju i učestvovao u finansiranju patenta. Postoje dva scenarija za dalji tok primene ovih dekodera. STMicroelectronics može naše dekodere da ugradi u svoje proizvode, a da mi pronalazači dobijamo procenat od prodaje, ili da ja osnujem kompaniju koja će da napravi čipove koje će STMicroelectronics da kupi. Kolega profesor Deklerk je za drugu opciju, ali još nismo odlučili šta ćemo. Mene više interesuju bazična istraživanja i nerešeni problemi nego biznis, tako da je prva varijanta verovatnija.

Dušan STOJIČEVIĆ