Das Suchergebnis hat sich seit Ihrer Suchanfrage verändert. Eventuell werden Dokumente in anderer Reihenfolge angezeigt.
  • Treffer 82 von 517
Zurück zur Trefferliste

Improving the Power of Ordered Binary Decision Diagrams by Integrating Parity Nodes

Verbesserung der Berechnungskraft von geordneten Binaeren Entscheidungsdiagrammen durch Integration von Parity-Knoten

  • Hardware bugs can be extremely expensive, financially. Because microprocessors and integrated circuits have become omnipresent in our daily live and also because of their continously growing complexity, research is driven towards methods and tools that are supposed to provide higher reliability of hardware designs and their implementations. Over the last decade Ordered Binary Decision Diagrams (OBDDs) have been well proven to serve as a data structure for the representation of combinatorial or sequential circuits. Their conciseness and their efficient algorithmic properties are responsible for their huge success in formal verification. But, due to Shannon's counting argument, OBDDs can not always guarantee the concise representation of a given design. In this thesis, Parity Ordered Binary Decision Diagrams are presented, which are a true extension of OBDDs. In addition to the regular branching nodes of an OBDD, functional nodes representing a parity operation are integrated into the data structure, thus resulting in Parity-OBDDs. Parity-OBDDs are more powerful than OBDDs are, but, they are no longer a canonical representation. Besides theoretical aspects of Parity-OBDDs, algorithms for their efficient manipulation are the main focus of this thesis. Furthermore, an analysis on the factors that influence the Parity-OBDD representation size gives way for the development of heuristic algorithms for their minimization. The results of these analyses as well as the efficiency of the data structure are also supported by experiments. Finally, the algorithmic concept of Parity-OBDDs is extended to Mod-p-Decision Diagrams (Mod-p-DDs) for the representation of functions that are defined over an arbitrary finite domain.
  • n.a.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Metadaten
Verfasserangaben:Harald Sack
URN:urn:nbn:de:hbz:385-2148
DOI:https://doi.org/10.25353/ubtr-xxxx-1832-56bd/
Betreuer:Christoph Meinel, Prof. Dr. sc.
Dokumentart:Dissertation
Sprache:Englisch
Datum der Fertigstellung:15.06.2004
Veröffentlichende Institution:Universität Trier
Titel verleihende Institution:Universität Trier, Fachbereich 4
Datum der Abschlussprüfung:11.01.2002
Datum der Freischaltung:15.06.2004
Freies Schlagwort / Tag:Formal Verification; Integrated Circuits; OBDDs; Ordered Binary Decision Diagrams; XOR Parity
GND-Schlagwort:Algorithmus; Datenstruktur; Erweiterung; OBDD
Institute:Fachbereich 4 / Informatik
DDC-Klassifikation:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik

$Rev: 13581 $