Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Applications of decision diagrams in digital circuit design
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Embedded Internet Systems Lab.
1999 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Design methodology of digital circuits is a rapidly changing field. In the last 20 years, the number of transistors on a single chip has increased from thousands to tens of millions. This sets new demands on the design tools involved, their ability to capture specifications on a high level, and finally synthesize them into hardware implementations. The introduction of Decision Diagrams (DDs) has brought new means towards solving many of the problems raised by the increasing complexity of todays designs. In this thesis, we study their use in VLSI CAD and develop a number of novel applications. Incomplete specifications are inherent to the functionality of almost all digital circuits. We present a design methodology providing a common basis between design validation and logic synthesis, namely the semantics of Kleenean Strong Ternary Logic. This is called upon as commonly used design methodologies, based e.g. on VHDL are shown to put design correctness in jeopardy. By an extension of DDs, we can efficiently represent and manipulate incompletely specified functions. The method presented, not only guarantees correctness of the final circuit, but also offers potential towards expressing and utilizing incompleteness in ways other methodologies are incapable of. The increasing density and speed of todays target technologies also changes the conditions for logic synthesis; e.g., traditional quality measures based on gate delays are becoming less accurate as delays caused by interconnections are raising their heads. To address this problem we propose methodologies allowing quality measures of the final circuit to be foreseen and considered throughout the whole synthesis process. In general this is a very hard task. We approach the problem by limiting our synthesis methodologies to those rendering regular layouts (Such as computational arrays and lattices). The regularity allows us to predict properties of the final circuit and at the same time, ensure design criteria to be met, e.g., path delays and routability of the final circuit. In this thesis, we develop new design methodologies and their algorithms. By our experimental results, they are shown to offer significant improvements to both state of the art two-level and multi-level based tools in the area of layout driven synthesis. Our minimization methods are based on Pseudo Kronecker Decision Diagrams (PKDDs) which are the most general type of ordered bitlevel diagrams for switching functions. In the thesis we elaborate on the properties of PKDDs and Ternary PKDDs (TPKDDs) and develop an efficient minimization method based on local variable exchange for TPKDDs. Furthermore, the problem of PKDD minimization is discussed and a number of different strategies are introduced and evaluated; the potential compactness of PKDDs is confirmed. The thesis spans from validation and verification of high-level specifications all the way down to layout driven synthesis, combining logic minimization, mapping and routing to the target architecture at hand. We conclude our work to offer new means towards solving many of the crucial problems occurring along the design process of modern digital circuits.

Place, publisher, year, edition, pages
Luleå: Luleå tekniska universitet, 1999. , 42 p.
Series
Doctoral thesis / Luleå University of Technology 1 jan 1997 → …, ISSN 1402-1544 ; 1999:45
National Category
Embedded Systems
Research subject
Embedded System
Identifiers
URN: urn:nbn:se:ltu:diva-16866Local ID: 0586fd50-7bc8-11db-8824-000ea68e967bOAI: oai:DiVA.org:ltu-16866DiVA: diva2:989853
Note
Godkänd; 1999; 20061117 (haneit)Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2017-11-24Bibliographically approved

Open Access in DiVA

fulltext(375 kB)16 downloads
File information
File name FULLTEXT01.pdfFile size 375 kBChecksum SHA-512
a7e74aff39ec954b97e9d552c9d40a7aa1026eff3ff7a05f2f9202fa767bba1b7f478dd5125a408ef259fe67eb5d966088041a418ed2c4225fdc5b2886ec7532
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Lindgren, Per
By organisation
Embedded Internet Systems Lab
Embedded Systems

Search outside of DiVA

GoogleGoogle Scholar
Total: 16 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 36 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf