Preskoči na sadržaj
Moj profil

ostalo · 2014

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

dr. sc. Reni Banov, v. pred., mr. sc. Davor Šterc, v. pred.

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