Uporaba urejenih odločitvenih grafov pri računalniški obdelavi logičnih funkcij

diplomsko delo

Robert Meolic (Avtor), Zmago Brezočnik (Mentor)

Povzetek

Odločitveni grafi so uspešna podatkovna struktura za predstavitev logičnih funkcij. V diplomskem delu so podane potrebne matematične osnove za njihovo razumevanje in računalniški algoritmi za njihovo učinkovito realizacijo. Podrobno so opisani urejeni binarni odločitveni grafi (OBDD), urejeni funkcijski odločitveni grafi (OFDD) in urejeni binarni odločitveni grafi s potlačenimi ničlami (0-sup-BDD). Dodan je pregledni opis prostih binarnih odločitvenih grafov (FBDD), razširjenih binarnih odločitvenih grafov (XBDD), urejenih Kroneckerjevih funkcijskih odločitvenih grafov (OKFDD) in diferenčnih binarnih odločitvenih grafov (\delta BDD). Za ROBDD, ROFDD in 0-sup-BDD so podani razčlenitveno pravilo, pravilo minimizacije in algoritmi za logične operacije, ki so tudi izpeljani. Algoritmi so bili realizirani v programskem jeziku C. Prikazani so rezultati testov, v katerih se primerja učinkovitost različnih vrst odločitvenih grafov pri preverjanju enakosti logičnih funkcij, pri predstavitvi množic kombinacij in pri predstavitvi slik.

Ključne besede

Boolova algebra;logične funkcije;binarni odločitveni grafi;funkcijski odločitveni grafi;podatkovne strukture;

Podatki

Jezik:	Slovenski jezik
Leto izida:	1995
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
Založnik:	[R. Meolic]
UDK:	681.3.01:519.1
COBISS:	1821974
Št. ogledov:	1763
Št. prenosov:	105
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Using ordered decision diagrams for computer-aided manipulation of Boolean functions.
Sekundarni povzetek:	Decision Diagrams are successful data structure for representation of Boolean functions. Mathematical background needed for their understanding and computer algorithms for their efficient implementation are given in this diploma work. Ordered Binary Decision Diagrams (OBDDs), Ordered Functional Decision Diagrams (OFDDs) and Zero-Suppresed Binary Decision Diagrams (0-sup-BDDs) are described in details. Also, a short overview of Free Binary Decision Diagrams (FBDDs), Extended Binary Decision Diagrams (XBDDs), Ordered Kronecker Functional Decision Diagrams (OKFDDs) and Differential Binary Decision Diagrams (\delta BDDs) is included. For ROBDD, ROFDD, and 0-sup-BDD the decomposition rule and reduction rule are shown and algorithms for logical operations are derived. Algorithms were realized in programming language C. Efficiency of various types of decision diagrams is compared. Results of tests in the domains of Boolean function equality testing, representing combination sets, and representing images are given.
Sekundarne ključne besede:	Boolean algebra;Boolean functions;Binary Decision Diagrams;Functional Decision Diagrams;data structures;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Diplomsko delo
Strani:	98 str.
ID:	10852738