Invention Grant
- Patent Title: Method and system for building binary decision diagrams efficiently in a structural network representation of a digital circuit
- Patent Title (中): 在数字电路的结构网络表示中有效构建二进制决策图的方法和系统
-
Application No.: US10926587Application Date: 2004-08-26
-
Publication No.: US07340473B2Publication Date: 2008-03-04
- Inventor: Viresh Paruthi , Christian Jacobi , Geert Janssen , Jiazhao Xu , Kai Oliver Weber
- Applicant: Viresh Paruthi , Christian Jacobi , Geert Janssen , Jiazhao Xu , Kai Oliver Weber
- Applicant Address: US NY Armonk
- Assignee: International Business Machines Corporation
- Current Assignee: International Business Machines Corporation
- Current Assignee Address: US NY Armonk
- Agency: Dillon & Yudell LLP
- Agent Casimer K. Salys
- Main IPC: G06F17/50
- IPC: G06F17/50

Abstract:
A method, system and computer program product for building decision diagrams efficiently in a structural network representation of a digital circuit using a dynamic resource constrained and interleaved depth-first-search and modified breadth-first-search schedule is disclosed. The method includes setting a first size limit for a first set of one or more m-ary decision representations describing a logic function and setting a second size limit for a second set of one or more m-ary decision representations describing a logic function. The first set of m-ary decision representations of the logic function is then built with one of the set of a depth-first technique or a breadth-first technique until the first size limit is reached, and a second set of m-ary decision representations of the logic function is built with the other technique until the second size limit is reached. In response to determining that a union of first set and the second set of m-ary decision representations do not describe the logic function, the first and second size limits are increased, and the steps of building the first and second set are repeated. In response to determining that the union of the first set of m-ary decision representations and the second set of m-ary decision representations describe the logic function, the union is reported.
Public/Granted literature
Information query