Change search
ReferencesLink to record
Permanent link

Direct link
Minimization of ordered pseudo Kronecker decision diagrams
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Embedded Internet Systems Lab.
Albert-Ludwigs-University, Freiburg.
Albert-Ludwigs-University, Freiburg.
2000 (English)In: Proceedings, 2000 International Conference on Computer Design: 17 - 20 September 2000, Austin, Texas, Los Alamitos, Calif: IEEE Communications Society, 2000, 504-510 p.Conference paper (Refereed)
Abstract [en]

The introduction of Decision Diagrams (DDs) has brought new means towards solving many of the problems involved in digital circuit design. Compactness of the representation is one key issue. Ordered Pseudo Kronecker Decision Diagrams (OPKDDs) together with the use of complemented edges is known to offer the most general ordered read-once DD representation at the bit-level, hence OPKDDs hold all minimal sized bit-level ordered DDs for a given function. This representation allows us to trade-off diagram canonicity against compactness. Ternary-OPKDDs (TOPKDDs) implicitly holds all OPKDDs for a given variable order. We state the canonicity criteria for TOPKDDs having complemented edges and develop an efficient sifting based method for their minimization. Furthermore, a heuristic minimization algorithm for OPKDDs is devised, utilizing the redundancies of Ternary-OPKDDs (TOPKDDs). Experiments on a set of MCNC benchmarks confirm the potential compactness of OPKDDs and demonstrate the efficiency of the proposed heuristics.

Place, publisher, year, edition, pages
Los Alamitos, Calif: IEEE Communications Society, 2000. 504-510 p.
Research subject
Embedded System
URN: urn:nbn:se:ltu:diva-39844DOI: 10.1109/ICCD.2000.878329Local ID: ebd866d0-6d0a-11db-83c6-000ea68e967bISBN: 0-7695-0801-4OAI: diva2:1013363
International Conference on Computer Design : 17/09/2000 - 20/09/2000
Godkänd; 2002; 20061105 (ysko)Available from: 2016-10-03 Created: 2016-10-03Bibliographically approved

Open Access in DiVA

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

Other links

Publisher's full text

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
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

Altmetric score

ReferencesLink to record
Permanent link

Direct link