ostalo
Smanjenje veličine binarnih dijagrama odlučivanja korištenjem graničnih rezultata iz VLSI dizajna
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