Minimization of ordered pseudo Kronecker decision diagrams
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)
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
IdentifiersURN: urn:nbn:se:ltu:diva-39844DOI: 10.1109/ICCD.2000.878329Local ID: ebd866d0-6d0a-11db-83c6-000ea68e967bISBN: 0-7695-0801-4OAI: oai:DiVA.org:ltu-39844DiVA: diva2:1013363
International Conference on Computer Design : 17/09/2000 - 20/09/2000
Godkänd; 2002; 20061105 (ysko)2016-10-032016-10-03Bibliographically approved