In this paper, we propose a novel compact BDD structure, called Non-crossing ordered BDD (NCOBDD), that can be mapped directly to a regular circuit structure. Compared with other BDD-based regular structures, NCOBDDmapped circuits reduce the costs of area, power and latency, while preserving the regularity of the structure. We also present an algorithm that uses a top-down level-by-level sweep and a back-tracing mechanism to construct the minimum sized NCOBDD. Experimental results show that for asymmetric benchmark circuits, the average reduction on area, power and latency are 57.8%, 49.9% and 68.7%, respectively, compared with Yet Another Decision Diagram (YADD) [14].

Date of this Version

January 2003