Студент Рачунарског факултета Урош Живковић је у среду, 12. априла 2023. године одбранио дипломски рад на тему Декодовање блок кодова помоћу трелиса пред комисијом коју су чинили ментор др Десимир Вучић и члан др Селена Вукотић.
У уводу свог рада Урош је истакао следеће:
Обично се Витербијев алгоритам користи као оптимална стратегија декодовања конволуционих кодова користећи њихову унутрашњу меморију. Jack Wolf је још 1978. године, предложио начин како да се линеарни блок кодови представе у облику трелиса (енглески „trellis“ – решетка) и на тај начин омогући коришћење Витербијевог алгоритма за декодовање линеарних блок кодова. Витербијев алгоритам за декодовање линеарних блок кодова може бити рачунарски мање захтеван у поређењу са класичним алгебарским методама. Витербијево декодовање линеарних блок кодова представља атрактивно решење у неким применама где блок кодови имају предност над конволуционим кодовима, али су класичне методе декодовања биле непрактичне због потребног времена за декодовање.
…
Представљање и декодовање блок кодова помоћу трелиса има теоријски и практични значај. Трелис се може посматрати као релативно компактан комбинаторни (за разлику од алгебарског) опис датог блок кода.
У овом раду је показано како се линеарни блок кодови могу представити помоћу трелиса, што омогућује да се ефикасни Витербијев алгориам декодовања примени и на ове кодове. Изразита предност Витербијевог алгоритма у односу на класичне блок декодере је постојање ефикасних алгоритама меког одлучивања који користе информације о мерењу канала.
Описана техника представљања и декодовања блок кодова помоћу трелиса је илустрована примерима.
Очигледна предност Витербијевог декодера у односу на алгебарске је могућност смањене сложености рачунања. Да би се ова предност искористила код (n,k) линеарних блок кодова потребно је пажљиво одабирати параметре n и k. Поред могућности смањења сложености декодовања линеарних блок кодова применом Витербијевог алгоритма, примена блок кодова са декодовањем помоћу трелиса може у неким апликација, укључујући системе који користе стратегије интерливинга/де-интерливинга, имати предност у односу на класична решења са конволуционим кодовима. – закључио је Урош.
Фотографије са одбране доступне су у галерији.