Patent ID: 8166426
Filing Date: 2012-04-24
Classification: G06F

Abstract:
1. A method for reducing a depth of binary decision diagram, comprising: identifying, with a processing device, one or more less probable positive paths within the binary decision diagram, wherein the one or more 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 eliminating, using the processing device the identified one or more less probable positive paths within the binary decision diagram; wherein identifying the one or more less probable positive paths within the binary decision diagram further comprises: assigning ƒ to the binary decision diagram; assigner K to a depth threshold of the binary decision diagram; constructing a second binary decision diagram g by logically ORing together positive paths in ƒ that have a length above K; and wherein eliminating the identified one or more less probable positive paths in ƒ comprises obtaining an approximated function ƒ′, by conjuncting ƒ and the negation of g, such that ƒ′≡ƒ^