Student Računarskog fakulteta Uroš Živković je u sredu, 12. aprila 2023. godine odbranio diplomski rad na temu Dekodovanje blok kodova pomoću trelisa pred komisijom koju su činili mentor dr Desimir Vučić i član dr Selena Vukotić.
U uvodu svog rada Uroš je istakao sledeće:
Obično se Viterbijev algoritam koristi kao optimalna strategija dekodovanja konvolucionih kodova koristeći njihovu unutrašnju memoriju. Jack Wolf je još 1978. godine, predložio način kako da se linearni blok kodovi predstave u obliku trelisa (engleski „trellis“ – rešetka) i na taj način omogući korišćenje Viterbijevog algoritma za dekodovanje linearnih blok kodova. Viterbijev algoritam za dekodovanje linearnih blok kodova može biti računarski manje zahtevan u poređenju sa klasičnim algebarskim metodama. Viterbijevo dekodovanje linearnih blok kodova predstavlja atraktivno rešenje u nekim primenama gde blok kodovi imaju prednost nad konvolucionim kodovima, ali su klasične metode dekodovanja bile nepraktične zbog potrebnog vremena za dekodovanje.
…
Predstavljanje i dekodovanje blok kodova pomoću trelisa ima teorijski i praktični značaj. Trelis se može posmatrati kao relativno kompaktan kombinatorni (za razliku od algebarskog) opis datog blok koda.
U ovom radu je pokazano kako se linearni blok kodovi mogu predstaviti pomoću trelisa, što omogućuje da se efikasni Viterbijev algoriam dekodovanja primeni i na ove kodove. Izrazita prednost Viterbijevog algoritma u odnosu na klasične blok dekodere je postojanje efikasnih algoritama mekog odlučivanja koji koriste informacije o merenju kanala.
Opisana tehnika predstavljanja i dekodovanja blok kodova pomoću trelisa je ilustrovana primerima.
Očigledna prednost Viterbijevog dekodera u odnosu na algebarske je mogućnost smanjene složenosti računanja. Da bi se ova prednost iskoristila kod (n,k) linearnih blok kodova potrebno je pažljivo odabirati parametre n i k. Pored mogućnosti smanjenja složenosti dekodovanja linearnih blok kodova primenom Viterbijevog algoritma, primena blok kodova sa dekodovanjem pomoću trelisa može u nekim aplikacija, uključujući sisteme koji koriste strategije interlivinga/de-interlivinga, imati prednost u odnosu na klasična rešenja sa konvolucionim kodovima. – zaključio je Uroš.
Fotografije sa odbrane dostupne su u galeriji.