Tehničko veleučilište u Zagrebu · Zagreb

Smanjenje veličine binarnih dijagrama odlučivanja korištenjem graničnih rezultata iz VLSI dizajna

ostalo

ostalo

Smanjenje veličine binarnih dijagrama odlučivanja korištenjem graničnih rezultata iz VLSI dizajna

Vrsta prilog u časopisu
Tip ostalo
Godina 2014
Časopis Zbornik radova Elektrotehničkog odjela
Nadređena publikacija Zbornik radova Elektrotehničkog odjela
Volumen 1
Stranice str. 63-74
ISSN 1849-5621
Status objavljeno

Sažetak

Binarni dijagrami odlučivanja (skr. BDD) predstavljaju važnu strukturu podataka za zapisivanje logičkih funkcija u računalima. Njihova primjenjivost u različitim tehničkim problemima posebno dolazi do izražaja zbog efikasnosti algoritama koji su implementirani na njima. Efikasnost zapisa i algoritama vezana je uz problem izbora redoslijeda varijabli u Shannonovom razvoju logičke funkcije. U ovom članku predstavit ćemo teorijsku osnovu problema i pristupe rješavanju koji su proizašli iz sklopova i uređaja za integraciju (skr. VLSI). Neovisno o tome što su neki algoritmi razvijeni na osnovi poznatih graničnih rezultata iz dizajna VLSI sklopova oni su iskoristivi u drugim granama, primjerice u analizi stabla kvara. Algoritmi predstavljeni u ovom radu spadaju u kategoriju egzaktnih algoritama i služe za određivanje redoslijeda u Shannonovom razvoju koji dovodi do minimalne veličine BDD zapisa logičke funkcije.

Ključne riječi

BDD ; VLSI ; Stablo kvara ; Shannonov razvoj ; poredak variabli