BDD Representation for Incompletely Specified Multiple-Output Logic Functions and Its Applications to the Design of LUT Cascades

Munehiro MATSUURA  Tsutomu SASAO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E90-A   No.12   pp.2762-2769
Publication Date: 2007/12/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e90-a.12.2762
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Category: Logic Synthesis and Verification
incompletely specified function,  characteristic function,  binary decision diagram,  functional decomposition,  LUT cascade,  

Full Text: PDF(253.3KB)>>
Buy this Article

A multiple-output function can be represented by a binary decision diagram for characteristic function (BDD_for_CF). This paper presents a method to represent multiple-output incompletely specified functions using BDD_for_CFs. An algorithm to reduce the widths of BDD_for_CFs is presented. This method is useful for decomposition of incompletely specified multiple-output functions. Experimental results for radix converters, adders, a multiplier, and lists of English words show that this method is useful for the synthesis of LUT cascades. An implementation of English words list by LUT cascades and an auxiliary memory is also shown.