2003 IEEE International Conference on Computer Design (ICCD'03)
Boolean Decomposition Based on Cyclic Chains
San Jose, California
October 13-October 15
ISBN: 0-7695-2025-1
Elena Dubrova, Royal Institute of Technology, IMIT/KTH, Stockholm, Sweden
Maxim Teslenko, Royal Institute of Technology, IMIT/KTH, Stockholm, Sweden
Johan Karlsson, Royal Institute of Technology, IMIT/KTH, Stockholm, Sweden
This paper presents a new algorithm for decomposition of type f = g ? h + r. The algorithm searches for Boolean products g ? h of a special type, called cyclic chains. The number of cubes in a cyclic chain is no greater than the number of cubes in the part of the on-set of f covered by this chain. The number of literals is always smaller. Cyclic chains are extracted recursively until no more can be found. The presented algorithm is of particular interest in applications which require circuit representations of a limited depth. Experimental results on benchmark circuits demonstrate the efficiency of our approach.
Citation:
Elena Dubrova, Maxim Teslenko, Johan Karlsson, "Boolean Decomposition Based on Cyclic Chains," iccd, pp.504, 2003 IEEE International Conference on Computer Design (ICCD'03), 2003