Approximation of a clock gating function via bdd path elimination

Abstract

A method for reducing a depth of binary decision diagram includes identifying, with a processing device, one or more less probable positive paths within the binary decision diagram, the less probable positive paths within the binary decision diagram include a number of decision nodes from a starting variable to a positive, binary logic '1' terminal node within the binary decision diagram, and the identified less probable positive paths are eliminated. Identifying the less probable positive paths within the binary decision diagram includes: assigning ƒ to the binary decision diagram, assigning K to a depth threshold of the binary decision diagram, and constructing a second binary decision diagram g by logically ORing together positive paths in ƒ that have a length above K. Eliminating the identified less probable positive paths in ƒ comprises obtaining an approximated function ƒ', by conjuncting ƒ and the negation of g, such that ƒ′≡ƒ^.