A Quaternary Decision Diagram Machine: Optimization of Its Code

Tsutomu SASAO  Hiroki NAKAHARA  Munehiro MATSUURA  Yoshifumi KAWAMURA  Jon T. BUTLER  

IEICE TRANSACTIONS on Information and Systems   Vol.E93-D   No.8   pp.2026-2035
Publication Date: 2010/08/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E93.D.2026
Print ISSN: 0916-8532
Type of Manuscript: INVITED PAPER (Special Section on Multiple-Valued Logic and VLSI Computing)
quarternary decision diagram,  branching program machine,  

Full Text: PDF>>
Buy this Article

This paper first reviews the trends of VLSI design, focusing on the power dissipation and programmability. Then, we show the advantage of Quarternary Decision Diagrams (QDDs) in representing and evaluating logic functions. That is, we show how QDDs are used to implement QDD machines, which yield high-speed implementations. We compare QDD machines with binary decision diagram (BDD) machines, and show a speed improvement of 1.28-2.02 times when QDDs are chosen. We consider 1-and 2-address BDD machines, and 3- and 4-address QDD machines, and we show a method to minimize the number of instructions.