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

diplomsko delo

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

Abstract

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.

Keywords

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

Data

Language:	Slovenian
Year of publishing:	1995
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
Publisher:	[R. Meolic]
UDC:	681.3.01:519.1
COBISS:	1821974
Views:	1763
Downloads:	105
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Using ordered decision diagrams for computer-aided manipulation of Boolean functions.
Secondary abstract:	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.
Secondary keywords:	Boolean algebra;Boolean functions;Binary Decision Diagrams;Functional Decision Diagrams;data structures;
URN:	URN:SI:UM:
Type (COBISS):	Undergraduate thesis
Pages:	98 str.
ID:	10852738