US5524082A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Redundancy removal using quasi-algebraic methods
Assignee: International Business Machines Corp
•
Filing: 1991-06-28
•
Granted: 1996-06-04
•
Expires: 2011-06-28
Abstract
Abstract A method is provided to remove redundancies in multi-level logic networks caused by reconverging signals at Boolean sum and product nodes. Generally, sum and product nodes which have potential redundancies are first identified. For each reconvergent signal at each of the nodes, it is determined whether it introduces redundancies using nondestructive Boolean analysis. No two-level expansion is made of the logic network. Moreover, for each confirmed redundancy, a redundant term is identified using Boolean analysis. Finally, the redundancy is removed, if desirable.
Inventors
- 👤 Paul W. Horstmann
- 👤 Thomas E. Rosser
- 👤 Prashant S. Sawkar
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 16:30
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/32; G06F30/327
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
85 words
A computer-based method for optimizing the ultimate implementation of a logic network by identifying redundancies in signal paths caused by reconverging signals, comprising the steps of: (a) identifying Boolean sum and product nodes in a database model of a logic network; (b) determining whether a convergent signal exists for each of said Boolean sum and product nodes; (c) identifying a redundant term for each of said Boolean sum and product nodes having a convergent signal; and (d) removing said redundant term from said database model.
Claim 2
Dependent Claim
85 words
A computer-based method for optimizing the ultimate implementation of a logic network by identifying redundancies in signal paths caused by reconverging signals, comprising the steps of: (a) identifying Boolean sum and product nodes in a database model of a logic network; (b) determining whether a convergent signal exists for each of said Boolean sum and product nodes; (c) identifying a redundant term for each of said Boolean sum and product nodes having a convergent signal; and (d) removing said redundant term from said database model.
Claim 3
Dependent Claim
23 words
The method of claim 1, wherein step (c) comprises the step of identifiying either a maximum AND term or a maximum OR term.
Claim 4
Dependent Claim
62 words
The method of claim 1, wherein said step (b) comprises the steps of: (i) identifying two logic inputs to one of said Boolean sum and product nodes; (ii) identifying a leaf set for each of said two logic inputs; and (ii) determining whether said leaf sets for said two logic inputs have any common leaves, wherein a common leaf indicates a redundancy.
Claim 5
Dependent Claim
113 words
The method of claim 3, wherein said step (c) comprises the steps of: (i) propogating a signal from said common leaf to root pins of said sum node or said product node; (ii) determining the signal phase of said signal; and (iii) if said signal phase is in-phase, then determining for said product node a maximum OR term that contains said common leaf and for said sum node a maximum AND term that contains said common leaf, and if the signal phase is out-of-phase, then determining for said product node a maximum AND term that contains said common leaf and for said sum node a maximum OR term that contains said common leaf.
Claim 6
Dependent Claim
43 words
The method of claim 1, further comprising the steps of determining whether the existence of said redundant term in said model would result in said compact logic and permitting said redundant term to remain in said model if said compact logic would result.
Claim 7
Dependent Claim
26 words
The method of claim 1, further comprising the step of replicating the logic between said redundant term and the respective node with said redundant term deleted.
Claim 8
Dependent Claim
19 words
The method of claim 1, further comprising the step of replacing said redundant term with a constant logic source.
Claim 9
Dependent Claim
18 words
The method of claim 1, further comprising the step of deleting the logic block generating the redundant term.
Claim 10
Dependent Claim
14 words
The method of claim 1, wherein said logic network is an unmodified logic network.
Claim 11
Dependent Claim
103 words
A computer system having access to a computer readable medium which has computer program logic recorded thereon, said logic establishing a network configuration in accordance with a plurality of protocols of a network architecture, said computer system comprising: first means for identifying Boolean sum and product nodes in a database model of a logic network; means for determining whether a convergent signal exists for each of said Boolean sum and product nodes; second means for identifying a redundant term for each of said Boolean sum and product nodes having a convergent signal; and means for removing said redundant term from said database model.
Claim 12
Dependent Claim
103 words
A computer system having access to a computer readable medium which has computer program logic recorded thereon, said logic establishing a network configuration in accordance with a plurality of protocols of a network architecture, said computer system comprising: first means for identifying Boolean sum and product nodes in a database model of a logic network; means for determining whether a convergent signal exists for each of said Boolean sum and product nodes; second means for identifying a redundant term for each of said Boolean sum and product nodes having a convergent signal; and means for removing said redundant term from said database model.
Claim 13
Dependent Claim
26 words
The computer system of claim 10, wherein said second means for identifying comprises means for identifiying either a maximum AND term or a maximum OR term.
Claim 14
Dependent Claim
64 words
The computer system of claim 10, wherein said means for determining comprises: means for identifying two logic inputs to one of said Boolean sum and product nodes; means for identifying a leaf set for each of said two logic inputs; and means for determining whether said leaf sets for said two logic inputs have any common leaves, wherein a common leaf indicates a redundancy.
Claim 15
Dependent Claim
114 words
The method of claim 12, wherein said step second means for identifying comprises: means for propogating a signal from said common leaf to root pins of said sum node or said product node; means for determining the signal phase of said signal; means for determining for said product node a maximum OR term that contains said common leaf and for said sum node a maximum AND term that contains said common leaf, if said signal phase is in-phase; and means for determining for said product node a maximum AND term that contains said common leaf and for said sum node a maximum OR term that contains said common leaf, if said signal is out-of-phase.
Claim 16
Dependent Claim
43 words
The computer system of claim 10, further comprising means for determining whether the existence of said redundant term in said model would result in said compact logic and permitting said redundant term to remain in said model if said compact logic would result.
Claim 17
Dependent Claim
26 words
The computer system of claim 10, further comprising means for replicating the logic between said redundant term and the respective node with said redundant term deleted.
Claim 18
Dependent Claim
19 words
The computer system of claim 10, further comprising means for replacing said redundant term with a constant logic source.
Claim 19
Dependent Claim
18 words
The computer system of claim 10, further comprising means for deleting the logic block generating the redundant term.
Claim 20
Dependent Claim
15 words
The computer system of claim 10, wherein said logic network is an unmodified logic network.
Claim 21
Independent Claim
152 words
A method for removing redundancies in a logic network, comprising the steps of: (1) building a logic model of the logic network; (2) analyzing said logic model in order to generate a list of sum nodes and product nodes, wherein said list only contains sum nodes and product nodes that have a potential redundancy; (3) identifying redundancies in said logic model by analyzing all pin pairs of said sum nodes and said product nodes, wherein for each pair of pins said identifying step includes, (i) selecting a pair of pins; (ii) identifying a leaf set for each pin in said pair of pins; (iii) comparing said leaf sets to determine whether said leaf sets have any leaves in common, wherein a common leaf is indicative of a redundancy; and (iv) performing a Boolean analysis on said redundancy to determine a redundant term; and (4) removing said redundant term from said logic network.
Claim 22
Independent Claim
152 words
A method for removing redundancies in a logic network, comprising the steps of: (1) building a logic model of the logic network; (2) analyzing said logic model in order to generate a list of sum nodes and product nodes, wherein said list only contains sum nodes and product nodes that have a potential redundancy; (3) identifying redundancies in said logic model by analyzing all pin pairs of said sum nodes and said product nodes, wherein for each pair of pins said identifying step includes, (i) selecting a pair of pins; (ii) identifying a leaf set for each pin in said pair of pins; (iii) comparing said leaf sets to determine whether said leaf sets have any leaves in common, wherein a common leaf is indicative of a redundancy; and (iv) performing a Boolean analysis on said redundancy to determine a redundant term; and (4) removing said redundant term from said logic network.
Claim 23
Dependent Claim
35 words
The method of claim 19, wherein said step of generating said list includes only placing a sum node or a product node on said list if said sum node or said product node fan out.
Claim 24
Dependent Claim
141 words
The method of claim 19, wherein said step of performing a Boolean analysis includes the steps of: (a) propogating a signal from said common leaf to root pins of said sum node or said product node; (b) determining whether the signal phase of said signal is either in-phase or out-of phase at said root pins, and if the signal phase is in-phase, then determining for said product node a maximum OR term that contains said common leaf and for said sum node a maximum AND term that contains said common leaf, and if the signal phase is out-of-phase, then determining for said product node a maximum AND term that contains said common leaf and for said sum node a maximum OR term that contains said common leaf, wherein said maximum OR term or said maximum AND term is said redundant term.
Claim 25
Dependent Claim
38 words
The method of claim 21, further comprising the step of determining if a logic path from said maximum OR term or said maximum AND term to said sum node or said product node is free of any fanouts.
References Cited (Backward Citations)
US4503537A
Cited
US4591993A
Cited
US4703435A
Cited
US4726023A
Cited
US4816999A
Cited
US5029102A
Cited
US4862399A
Cited
US4916627A
Cited
US5140526A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-06-04 | 1999-12-04 | 2000-06-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-06-04 | 2003-12-04 | 2004-06-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-06-04 | 2007-12-04 | 2008-06-04 | $7700.00 | Window Closed / Lapsed |