US5416719A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Computerized generation of truth tables for sequential and combinatorial cells
Assignee: Philips Semiconductors Inc
•
Filing: 1992-12-17
•
Granted: 1995-05-16
•
Expires: 2012-12-17
Abstract
Abstract A computerized method of generating a truth table of a cell in a library of circuit cells includes representing basic elements of the cells in a hardware description language, representing each cell as a set of equations in that language and parsing the equations each in accordance with a respective abstract data tree of which the `leaves` or extremities are signal values or constants. The parsing of each equation yields a respective partial truth table. The partial truth tables are merged to provide a complete truth table, which is preferably subjected to Boolean and/or expression optimization to reduce the number of entries in the truth table.
Inventors
- 👤 Olivier Pribetich
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 18:17
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
116 words
A method of automatically generating signals representing a complete truth table of a circuit from data defining said circuit by a set of equations consisting of signal entities and operational entities, comprising the steps of: performing in a data processor: (a) parsing each equation in accordance with an abstract data tree having a node for each operational entity and an extremity for each signal entity; (b) building, in accordance with the parsing of each equation and from elementary truth tables for each signal entity, a respective partial truth table for each equation; and (c) merging the said partial truth tables into said complete truth table for said circuit; and storing signals representing said complete truth table.
Claim 2
Independent Claim
116 words
A method of automatically generating signals representing a complete truth table of a circuit from data defining said circuit by a set of equations consisting of signal entities and operational entities, comprising the steps of: performing in a data processor: (a) parsing each equation in accordance with an abstract data tree having a node for each operational entity and an extremity for each signal entity; (b) building, in accordance with the parsing of each equation and from elementary truth tables for each signal entity, a respective partial truth table for each equation; and (c) merging the said partial truth tables into said complete truth table for said circuit; and storing signals representing said complete truth table.
Claim 3
Independent Claim
182 words
A method of automatically generating signals representing a truth table of a circuit from data stored in a cell library, said data defining said circuit in terms comprising constants, variables, operators and primitive functions, whereby the said circuit can be structurally described by a set of equations consisting of said terms, said method comprising the steps of: reading said data from the cell library to a data processor and performing in said data processor the following steps: (i) parsing each equation in accordance with a corresponding abstract data tree having nodes and extremities, assigning to each node a respective one of the operators and primitive functions and assigning to each extremity a respective one of the constants and variables; (ii) building, in an ascending order determined by the respective tree, truth tables for each node thereof from the truth tables of the descendants of said each node, whereby a respective partial truth table is built for each equation; and (iii) merging the said partial truth tables into a complete truth table for said circuit; and storing signals representing said complete truth table.
Claim 4
Independent Claim
182 words
A method of automatically generating signals representing a truth table of a circuit from data stored in a cell library, said data defining said circuit in terms comprising constants, variables, operators and primitive functions, whereby the said circuit can be structurally described by a set of equations consisting of said terms, said method comprising the steps of: reading said data from the cell library to a data processor and performing in said data processor the following steps: (i) parsing each equation in accordance with a corresponding abstract data tree having nodes and extremities, assigning to each node a respective one of the operators and primitive functions and assigning to each extremity a respective one of the constants and variables; (ii) building, in an ascending order determined by the respective tree, truth tables for each node thereof from the truth tables of the descendants of said each node, whereby a respective partial truth table is built for each equation; and (iii) merging the said partial truth tables into a complete truth table for said circuit; and storing signals representing said complete truth table.
Claim 5
Dependent Claim
17 words
A method according to claim 2 further comprising applying Boolean optimization to the said complete truth table.
Claim 6
Dependent Claim
16 words
A method according to claim 2 further comprising applying expression optimization to said complete truth table.
Claim 7
Dependent Claim
16 words
A method according to claim 2 wherein the constants represent zero, unity and unknown logic levels.
Claim 8
Dependent Claim
13 words
A method according to claim 2 wherein the variables comprise terminal signal values.
Claim 9
Dependent Claim
13 words
A method according to claim 2 wherein the said operators are combinatorial operators.
Claim 10
Dependent Claim
21 words
A method according to claim 7 wherein the said operators correspond at least to the functions NOT, AND, OR and EXCLUSIVE-OR.
Claim 11
Dependent Claim
26 words
A method according to claim 2 wherein the said primitive functions comprise at least one of a tristate function, a flip-flop function and a latch function.
Claim 12
Dependent Claim
31 words
A method according to claim 2 wherein the building step (ii) includes removing from the truth table for a node any duplication of values and any logically inconsistent set of values.
Claim 13
Independent Claim
184 words
A system for automatically generating signals representing a truth table of an electrical circuit from data stored in a cell library, said data defining said circuit in terms of constants, variable, operators and primitive functions, whereby the said circuit can be structurally described by a set of equations consisting of said terms, said system comprising: storage means for said data; a data processor for reading said data and performing the following steps: (i) parsing each equation in accordance with a corresponding abstract data tree having nodes and extremities, assigning to each node a respective one of the operators and primitive functions and assigning to each extremity a respective one of the constants and variables; (ii) building, in an ascending order determined by the respective tree, truth tables for each node thereof from the truth tables of the descendants of said each node, whereby a respective partial truth table is built for each equation; and (iii) merging the said partial truth tables into a complete truth table for said circuit; and means coupled to said data processor for storing signals representing said complete truth table.
Claim 14
Independent Claim
184 words
A system for automatically generating signals representing a truth table of an electrical circuit from data stored in a cell library, said data defining said circuit in terms of constants, variable, operators and primitive functions, whereby the said circuit can be structurally described by a set of equations consisting of said terms, said system comprising: storage means for said data; a data processor for reading said data and performing the following steps: (i) parsing each equation in accordance with a corresponding abstract data tree having nodes and extremities, assigning to each node a respective one of the operators and primitive functions and assigning to each extremity a respective one of the constants and variables; (ii) building, in an ascending order determined by the respective tree, truth tables for each node thereof from the truth tables of the descendants of said each node, whereby a respective partial truth table is built for each equation; and (iii) merging the said partial truth tables into a complete truth table for said circuit; and means coupled to said data processor for storing signals representing said complete truth table.
Claim 15
Dependent Claim
34 words
A system according to claim 11 wherein said data processor is further arranged to perform optimization of the said complete truth table and said signals represent an optimized version of said complete truth table.
References Cited (Backward Citations)
US4591993A
Cited
US4551814A
Cited
US4703435A
Cited
US4882690A
Cited
US4792909A
Cited
US5146583A
Cited
US4922432A
Cited
US5301318A
Cited
US4967367A
Cited
US5237513A
Cited
US5084824A
Cited
US5222030A
Cited
US5258919A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-05-15 | 1998-11-14 | 1999-05-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-05-15 | 2002-11-14 | 2003-05-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-05-15 | 2006-11-14 | 2007-05-16 | $7700.00 | Window Closed / Lapsed |