Technology mapping via transformations of function graphs

TitleTechnology mapping via transformations of function graphs
Publication TypeConference Paper
Year of Publication1992
AuthorsChang, S-C, Marek-Sadowska, M
Conference NameComputer Design: VLSI in Computers and Processors, 1992. ICCD '92. Proceedings., IEEE 1992 International Conference on
Date Publishedoct
KeywordsBoolean equations, Boolean functions, combinational circuit, combinatorial circuits, logic design, minimum number of blocks, reduced ordered binary decision diagram, Roth-Karp decomposition, subject function, table lookup, target TLU table lookup architecture, technology mapping, transformations of function graphs
AbstractThe authors address the problem of how to realize a given combinational circuit described by means of Boolean equations using the minimum number of blocks of the target TLU table lookup architecture. Their Boolean decomposition scheme works directly on a reduced ordered binary decision diagram (ROBDD) of a subject function, using two techniques. The first, referred to as cutting, is an efficient implementation of Roth-Karp decomposition. The second technique is referred to as a substitution. The idea is to replace subgraphs of ROBDD by new variables. The substitution process is accompanied by certain reductions of the resulting ROBDD graph, which further decreases its size