Approximation of a clock gating function via BDD path elimination
US8166426B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Aug 14, 2008 |
| Grant date | Apr 24, 2012 |
| Priority date | — |
| Expiry date | Feb 14, 2031 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F30/30
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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 ƒ′≡ƒ^ g.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.