US5383167A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for histogram based digital circuit simulator
Assignee: Nextwave Design Automation Inc
•
Filing: 1991-10-16
•
Granted: 1995-01-17
•
Expires: 2011-10-16
Abstract
Abstract A digital circuit simulator is provided that combines the speed of a single pass simulator with the probabalistic analysis previously available only through lengthy iteration, and that avoids the extensive reporting of false errors typical to single pass simulators. The simulator represents signal level transitions and component gate delays by probability histograms. Circuit operation is divided into events, each of which is the propagation through a single component of transitions in one or more input signals to the component. Signal propagation through a component is analyzed using component models, which are provided for a variety of basic components; more complex components are represented by decomposing them into a corresponding structure of basic components. Each event is analyzed using the histograms for the input signals and for the component gate delay. Signal conflicts due to timing problems between the various inputs to a component are identified and reported. Potential signal conflicts include spike and race conditions, glitches, and set-up and hold time problems. Probabilities are reported with the signal conflicts, which permitting the conflicts to be ranked according to their likelihood of occurrence.
Inventors
- 👤 Paul B. Weil
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 20:48
CPC Classifications
G; G06; G06F; G06F30/00; G06F30/30; G06F30/32; G06F30/33
Claims Analysis
Total Claims: 40
Claim 1
Independent Claim
175 words
A method of analyzing on a computer a signal transition propagation through a component, said component being one of a plurality of components of a digital circuit, each of said components having an input signal, an output signal, and a signal propagation delay time, said signals having logic level transitions over time, said computer having memory, said method comprising the step of: associating said component with at least one input signal and at least one output signal; scheduling at least one event comprising an input signal transition propagating through said component, and for each such event performing the steps of a) storing in said memory the signal propagation delay time of the component as a segmented probability distribution; b) storing in said memory the input signal level transition time as a segmented probability distribution; c) determinately combining the input signal transition probability distribution with the propagation delay probability distribution to generate the output signal transition time represented as a segmented probability distribution; and d) storing in said memory said output signal transition time probability distribution.
Claim 2
Independent Claim
175 words
A method of analyzing on a computer a signal transition propagation through a component, said component being one of a plurality of components of a digital circuit, each of said components having an input signal, an output signal, and a signal propagation delay time, said signals having logic level transitions over time, said computer having memory, said method comprising the step of: associating said component with at least one input signal and at least one output signal; scheduling at least one event comprising an input signal transition propagating through said component, and for each such event performing the steps of a) storing in said memory the signal propagation delay time of the component as a segmented probability distribution; b) storing in said memory the input signal level transition time as a segmented probability distribution; c) determinately combining the input signal transition probability distribution with the propagation delay probability distribution to generate the output signal transition time represented as a segmented probability distribution; and d) storing in said memory said output signal transition time probability distribution.
Claim 3
Dependent Claim
141 words
The method of claim 1, wherein a) the step of storing the signal propagation delay time of the component comprises storing a histogram having at least two segments, each segment having a time range and a probability corresponding to the likelihood of the delay time being within the segment time range; b) the step of storing the input signal level transition time comprises storing a histogram having at least two segments, each segment having a time range and a probability corresponding to the likelihood of the input signal transition time being within the segment time range; and c) the step of storing the output signal transition time comprises storing a histogram having at least two segments, each segment having a time range and a probability corresponding to the likelihood of the output signal transition time being within the segment time range.
Claim 4
Dependent Claim
22 words
The method of claim 1, further comprising the step of reporting to a user a measure of the output signal probability distribution.
Claim 5
Independent Claim
414 words
A method of analyzing on a computer a signal transition propagation through a component, said component being one of a plurality of components of a digital circuit, each of said components having an input signal, an output signal, and a signal propagation delay time, said signals having logic level transitions over time, said computer having memory, said method comprising the step of associating said component with at least one input signal and at least one output signal; scheduling at least one event comprising an input signal transition propagating through said component, and for each such event performing the steps of storing in said memory the signal propagation delay time of the component as a segmented probability distribution; storing in said memory the input signal level transition time as a segmented probability distribution; determinately combining the input signal transition probability distribution with the propagation delay probability distribution to generate the output signal transition time represented as a segmented probability distribution; and storing in said memory said output signal transition time probability distribution; wherein the step of storing the signal propagation delay time of the component comprises storing a histogram having at least two segments, each segment having a time range and a probability corresponding to the likelihood of the delay time being within the segment time range; wherein the step of storing the input signal level transition time comprises storing a histogram having at least two segments, each segment having a time range and a probability corresponding to the likelihood of the input signal transition time being within the segment time range; wherein the step of storing the output signal transition time comprises storing a histogram having at least two segments, each segment having a time range and a probability corresponding to the likelihood of the output signal transition time being within the segment time range; wherein time ranges have a begin time and an end time, and wherein said combining step comprises the steps of i) combining the signal transition histogram segments with the delay histogram segments to generate divisions, each division having a time range and probability, by performing the steps of 1) adding transition histogram segment begin times to delay histogram segment begin times to produce division begin times; 2) adding transition histogram segment end times to delay histogram segment end times to produce division end times; 3) multiplying transition histogram segment probabilities by delay histogram segment probabilities to produce division probabilities ii) generating an output signal transition histogram from the divisions.
Claim 6
Independent Claim
414 words
A method of analyzing on a computer a signal transition propagation through a component, said component being one of a plurality of components of a digital circuit, each of said components having an input signal, an output signal, and a signal propagation delay time, said signals having logic level transitions over time, said computer having memory, said method comprising the step of associating said component with at least one input signal and at least one output signal; scheduling at least one event comprising an input signal transition propagating through said component, and for each such event performing the steps of storing in said memory the signal propagation delay time of the component as a segmented probability distribution; storing in said memory the input signal level transition time as a segmented probability distribution; determinately combining the input signal transition probability distribution with the propagation delay probability distribution to generate the output signal transition time represented as a segmented probability distribution; and storing in said memory said output signal transition time probability distribution; wherein the step of storing the signal propagation delay time of the component comprises storing a histogram having at least two segments, each segment having a time range and a probability corresponding to the likelihood of the delay time being within the segment time range; wherein the step of storing the input signal level transition time comprises storing a histogram having at least two segments, each segment having a time range and a probability corresponding to the likelihood of the input signal transition time being within the segment time range; wherein the step of storing the output signal transition time comprises storing a histogram having at least two segments, each segment having a time range and a probability corresponding to the likelihood of the output signal transition time being within the segment time range; wherein time ranges have a begin time and an end time, and wherein said combining step comprises the steps of i) combining the signal transition histogram segments with the delay histogram segments to generate divisions, each division having a time range and probability, by performing the steps of 1) adding transition histogram segment begin times to delay histogram segment begin times to produce division begin times; 2) adding transition histogram segment end times to delay histogram segment end times to produce division end times; 3) multiplying transition histogram segment probabilities by delay histogram segment probabilities to produce division probabilities ii) generating an output signal transition histogram from the divisions.
Claim 7
Dependent Claim
37 words
The method of claim 4, wherein the step of generating the output signal transition histogram comprises generating the output signal transition histogram from end-range divisions only if said end-range divisions have probabilities above a predetermined minimum probability.
Claim 8
Independent Claim
145 words
A method of analyzing on a computer a digital circuit having a plurality of components, each of said components having an input signal, an output signal, and a signal propagation delay time, said signals having logic level transitions over time, said computer having memory, said method comprising the steps of: scheduling events comprising an input signal transition propagating through a component, and for each event performing the steps of a) storing in said memory the signal propagation delay time of the event component as a segmented probability distribution; b) storing in said memory the input signal level transition time as a segmented probability distribution; c) determinately combining the input signal transition probability distribution with the propagation delay probability distribution to generate the output signal transition time represented as a segmented probability distribution; and d) storing in said memory said output signal transition time probability distribution.
Claim 9
Independent Claim
145 words
A method of analyzing on a computer a digital circuit having a plurality of components, each of said components having an input signal, an output signal, and a signal propagation delay time, said signals having logic level transitions over time, said computer having memory, said method comprising the steps of: scheduling events comprising an input signal transition propagating through a component, and for each event performing the steps of a) storing in said memory the signal propagation delay time of the event component as a segmented probability distribution; b) storing in said memory the input signal level transition time as a segmented probability distribution; c) determinately combining the input signal transition probability distribution with the propagation delay probability distribution to generate the output signal transition time represented as a segmented probability distribution; and d) storing in said memory said output signal transition time probability distribution.
Claim 10
Independent Claim
220 words
A method of analyzing on a computer a digital circuit having a plurality of components, each of said components having an input signal, an output signal, and a signal propagation delay time, said signals having logic level transitions over time, said computer having memory, said method comprising the steps of scheduling events comprising an input signal transition propagating through a component, and for each event performing the steps of storing in said memory the signal propagation delay time of the event component as a segmented probability distribution; storing in said memory the input signal level transition time as a segmented probability distribution; determinately combining the input signal transition probability distribution with the propagation delay probability distribution to generate the output signal transition time represented as a segmented probability distribution; and storing in said memory said output signal transition time probability distribution; wherein the input signal is a unified input signal, wherein components have combinatorial specifications and may have a plurality of individual input signals, and wherein the step of storing an input signal transition probability distribution comprises the steps of i) determining transition probability distributions for the component's individual input signals; ii) combining the individual input transition probability distributions to form a unified input signal transition probability distribution; and iii) storing in said memory said unified input signal transition probability.
Claim 11
Independent Claim
220 words
A method of analyzing on a computer a digital circuit having a plurality of components, each of said components having an input signal, an output signal, and a signal propagation delay time, said signals having logic level transitions over time, said computer having memory, said method comprising the steps of scheduling events comprising an input signal transition propagating through a component, and for each event performing the steps of storing in said memory the signal propagation delay time of the event component as a segmented probability distribution; storing in said memory the input signal level transition time as a segmented probability distribution; determinately combining the input signal transition probability distribution with the propagation delay probability distribution to generate the output signal transition time represented as a segmented probability distribution; and storing in said memory said output signal transition time probability distribution; wherein the input signal is a unified input signal, wherein components have combinatorial specifications and may have a plurality of individual input signals, and wherein the step of storing an input signal transition probability distribution comprises the steps of i) determining transition probability distributions for the component's individual input signals; ii) combining the individual input transition probability distributions to form a unified input signal transition probability distribution; and iii) storing in said memory said unified input signal transition probability.
Claim 12
Dependent Claim
54 words
The method of claim 7, wherein the step of storing in said memory said unified input signal transition probability comprises storing a histogram having at least two segments, each segment having a time range and a probability corresponding to the likelihood of the unified input signal transition time being within the segment time range.
Claim 13
Independent Claim
102 words
A method of analyzing on a computer circuit errors resulting from timing conflicts between signal transitions, said conflicts including overlapping signal transitions, said computer having memory, said method comprising the steps of: a) determinately generating probabilities of occurrences of overlapping signal transitions; b) storing in memory for said probabilities, a histogram having at least two segments, each segment having a time range and a probability corresponding to the likelihood of the difference between signal transitions being within the segment time range; c) ranking circuit errors by probability of occurrence; d) reporting to a user a selected portion of said ranked circuit errors.
Claim 14
Independent Claim
102 words
A method of analyzing on a computer circuit errors resulting from timing conflicts between signal transitions, said conflicts including overlapping signal transitions, said computer having memory, said method comprising the steps of: a) determinately generating probabilities of occurrences of overlapping signal transitions; b) storing in memory for said probabilities, a histogram having at least two segments, each segment having a time range and a probability corresponding to the likelihood of the difference between signal transitions being within the segment time range; c) ranking circuit errors by probability of occurrence; d) reporting to a user a selected portion of said ranked circuit errors.
Claim 15
Dependent Claim
144 words
A digital circuit simulator for analyzing a digital circuit comprising a plurality of components, said simulator comprising: a) memory; b) means for associating each of said components with an input signal and an output signal, said signals having logic level transitions over time; c) means for scheduling events comprising an input signal transition propagating through a component; d) means for storing in memory a signal propagation delay time, for the component associated with an event, as a segmented probability distribution; e) means for storing in memory the input signal level transition time of said event as a segmented probability distribution; f) means for generating the output signal transition time of said event by determinately combining the input signal transition probability distribution with the propagation delay probability distribution; and g) means for storing in memory said output signal transition time as a segmented probability distribution.
Claim 16
Dependent Claim
144 words
A digital circuit simulator for analyzing a digital circuit comprising a plurality of components, said simulator comprising: a) memory; b) means for associating each of said components with an input signal and an output signal, said signals having logic level transitions over time; c) means for scheduling events comprising an input signal transition propagating through a component; d) means for storing in memory a signal propagation delay time, for the component associated with an event, as a segmented probability distribution; e) means for storing in memory the input signal level transition time of said event as a segmented probability distribution; f) means for generating the output signal transition time of said event by determinately combining the input signal transition probability distribution with the propagation delay probability distribution; and g) means for storing in memory said output signal transition time as a segmented probability distribution.
Claim 17
Dependent Claim
24 words
The digital circuit simulator of claim 10, further comprising means for reporting to a user a measure of the output signal transition probability distribution.
Claim 18
Dependent Claim
210 words
A digital circuit simulator for analyzing a digital circuit comprising a plurality of components, said simulator comprising memory; means for associating each of said components with an input signal and an output signal, said signals having logic level transitions over time; means for scheduling events comprising an input signal transition propagating through a component; means for storing in memory a signal propagation delay time, for the component associated with an event, as a segmented probability distribution; means for storing in memory the input signal level transition time of said event as a segmented probability distribution; means for generating the output signal transition time of said event by determinately combining the input signal transition probability distribution with the propagation delay probability distribution; and means for storing in memory said output signal transition time as a segmented probability distribution; wherein a) the input signal is a unified input signal; b) components have combinatorial specifications and may have a multiplicity of individual input signals; and c) the means for storing an input signal transition probability distribution comprises i) means for determining transition probability distributions for the individual input signals of the component, and ii) means for determinately combining the individual input transition probability distributions to form a unified input signal transition probability distribution.
Claim 19
Dependent Claim
210 words
A digital circuit simulator for analyzing a digital circuit comprising a plurality of components, said simulator comprising memory; means for associating each of said components with an input signal and an output signal, said signals having logic level transitions over time; means for scheduling events comprising an input signal transition propagating through a component; means for storing in memory a signal propagation delay time, for the component associated with an event, as a segmented probability distribution; means for storing in memory the input signal level transition time of said event as a segmented probability distribution; means for generating the output signal transition time of said event by determinately combining the input signal transition probability distribution with the propagation delay probability distribution; and means for storing in memory said output signal transition time as a segmented probability distribution; wherein a) the input signal is a unified input signal; b) components have combinatorial specifications and may have a multiplicity of individual input signals; and c) the means for storing an input signal transition probability distribution comprises i) means for determining transition probability distributions for the individual input signals of the component, and ii) means for determinately combining the individual input transition probability distributions to form a unified input signal transition probability distribution.
Claim 20
Dependent Claim
200 words
A digital circuit simulator for analyzing a digital circuit comprising a plurality of components, said simulator comprising memory; means for associating each of said components with an input signal and an output signal, said signals having logic level transitions over time; means for scheduling events comprising an input signal transition propagating through a component; means for storing in memory a signal propagation delay time, for the component associated with an event, as a segmented probability distribution; means for storing in memory the input signal level transition time of said event as a segmented probability distribution; means for generating the output signal transition time of said event by determinately combining the input signal transition probability distribution with the propagation delay probability distribution; means for storing in memory said output signal transition time as a segmented probability distribution; further comprising means for analyzing circuit errors resulting from timing conflicts between signal transitions, said conflicts including overlapping input signal transitions, said simulator further comprising a) means for determinately evaluating probabilities of occurrences of overlapping input signal transitions; b) means for ranking circuit errors by probability of occurrence; and c) means for reporting to a user a selected portion of said ranked circuit errors.
Claim 21
Dependent Claim
200 words
A digital circuit simulator for analyzing a digital circuit comprising a plurality of components, said simulator comprising memory; means for associating each of said components with an input signal and an output signal, said signals having logic level transitions over time; means for scheduling events comprising an input signal transition propagating through a component; means for storing in memory a signal propagation delay time, for the component associated with an event, as a segmented probability distribution; means for storing in memory the input signal level transition time of said event as a segmented probability distribution; means for generating the output signal transition time of said event by determinately combining the input signal transition probability distribution with the propagation delay probability distribution; means for storing in memory said output signal transition time as a segmented probability distribution; further comprising means for analyzing circuit errors resulting from timing conflicts between signal transitions, said conflicts including overlapping input signal transitions, said simulator further comprising a) means for determinately evaluating probabilities of occurrences of overlapping input signal transitions; b) means for ranking circuit errors by probability of occurrence; and c) means for reporting to a user a selected portion of said ranked circuit errors.
Claim 22
Independent Claim
99 words
A method of simulating a circuit, comprising identifying a component in a representation of said circuit; associating a first probability distribution with said component, said first probability distribution comprising a plurality of registers, each one of said plurality of registers having a predetermined time range and a numeric probability value associated therewith; associating an input signal and an output signal with said component; associating a second probability distribution with said input signal; determinately combining said first probability distribution and said second probability distribution to produce a third probability distribution; and associating said third probability distribution with said output signal.
Claim 23
Independent Claim
99 words
A method of simulating a circuit, comprising identifying a component in a representation of said circuit; associating a first probability distribution with said component, said first probability distribution comprising a plurality of registers, each one of said plurality of registers having a predetermined time range and a numeric probability value associated therewith; associating an input signal and an output signal with said component; associating a second probability distribution with said input signal; determinately combining said first probability distribution and said second probability distribution to produce a third probability distribution; and associating said third probability distribution with said output signal.
Claim 24
Dependent Claim
32 words
A method as in claim 14, wherein at least one of said first, second, and third probability distributions comprises a probability distribution that is not a uniform distribution or a normal distribution.
Claim 25
Dependent Claim
16 words
A method as in claim 14, wherein said first, second, and third probability distributions comprise histograms.
Claim 26
Dependent Claim
14 words
A method as in claim 14, wherein said step of determinately combining comprises convolution.
Claim 27
Dependent Claim
78 words
A method as in claim 14, wherein said step of determinately combining comprises determining a plurality of resultant time ranges, each having a numeric begin time and a numeric end time, in response to said time ranges in said first probability distribution; determining a plurality of resultant numeric probability values, in response to said numeric probability values in said first probability distribution; and associating said plurality of resultant numeric probability values with said plurality of resultant time ranges.
Claim 28
Dependent Claim
43 words
A method as in claim 18, wherein said step of determinately combining comprises storing in memory a set of correlation information for said third probability distribution, said correlation information including a statistical correlation between said second probability distribution and said third probability distribution.
Claim 29
Dependent Claim
94 words
A method as in claim 18, wherein said step of determinately combining comprises identifying at least one of said plurality of numeric probability values in said first probability distribution that is less than a predetermined threshold; identifying a like number of said plurality of time ranges in said first probability distribution associated with said at least one numeric probability value; and removing said at least one numeric probability value and said like number of said plurality of time ranges in said first probability distribution before determinately combining said first and said second probability distribution.
Claim 30
Dependent Claim
77 words
A method as in claim 18, wherein said step of determinately combining comprises identifying at least one of said plurality of resultant numeric probability values that is less than a predetermined threshold; identifying a like number of said resultant time ranges associated with said at least one resultant numeric probability value; and removing said at least one resultant numeric probability value and said like number of said resultant plurality of time ranges from said third probability distribution.
Claim 31
Independent Claim
96 words
A method of simulating a circuit, comprising identifying a first and a second signal in a representation of said circuit; associating a first probability distribution with said first signal and a second probability distribution with said second signal, said first probability distribution comprising a plurality of registers, each one of said plurality of registers having a predetermined time range and a numeric probability value associated therewith; determinately combining said first probability distribution and said second probability distribution to produce a third probability distribution; and associating said third probability distribution with a third signal for said circuit.
Claim 32
Independent Claim
96 words
A method of simulating a circuit, comprising identifying a first and a second signal in a representation of said circuit; associating a first probability distribution with said first signal and a second probability distribution with said second signal, said first probability distribution comprising a plurality of registers, each one of said plurality of registers having a predetermined time range and a numeric probability value associated therewith; determinately combining said first probability distribution and said second probability distribution to produce a third probability distribution; and associating said third probability distribution with a third signal for said circuit.
Claim 33
Dependent Claim
46 words
A method as in claim 22, comprising determining a correlation value in response to said first and said second signals; adjusting said first and said second probability distributions in response to said correlation value before determinately combining said first probability distribution and said second probability distribution.
Claim 34
Dependent Claim
18 words
A method as in claim 22, comprising associating said third probability distribution with an error for said circuit.
Claim 35
Independent Claim
146 words
A method of simulating a circuit, comprising identifying a first and a second signal in a representation of said circuit; associating a first probability distribution with said first signal and a second probability distribution with said second signal, said first probability distribution comprising a plurality of registers, each one of said plurality of registers having a predetermined time range and a numeric probability value associated therewith; determinately combining said first probability distribution arid said second probability distribution to produce a third probability distribution; associating said third probability distribution with an error for said circuit; associating a measure with said error in response to said probability distribution associated with said error; ordering at least two said errors in response to said measure associated with each one of said errors; and reporting a description of at least one of said errors in response to said step of ordering.
Claim 36
Independent Claim
146 words
A method of simulating a circuit, comprising identifying a first and a second signal in a representation of said circuit; associating a first probability distribution with said first signal and a second probability distribution with said second signal, said first probability distribution comprising a plurality of registers, each one of said plurality of registers having a predetermined time range and a numeric probability value associated therewith; determinately combining said first probability distribution arid said second probability distribution to produce a third probability distribution; associating said third probability distribution with an error for said circuit; associating a measure with said error in response to said probability distribution associated with said error; ordering at least two said errors in response to said measure associated with each one of said errors; and reporting a description of at least one of said errors in response to said step of ordering.
Claim 37
Dependent Claim
108 words
In a device for simulating a circuit, said device comprising means for identifying a component in a representation of said circuit, said component being associated with an input signal and an output signal, a data structure for representing a probability distribution, said data structure comprising a plurality of registers, each one of said plurality of registers associated with a time segment and a probability value, said time segments covering a continuous time range; and means for associating said plurality of registers with an event in said circuit, said event comprising a transition for said input signal, a transition for said output signal, or a delay for said component.
Claim 38
Dependent Claim
108 words
In a device for simulating a circuit, said device comprising means for identifying a component in a representation of said circuit, said component being associated with an input signal and an output signal, a data structure for representing a probability distribution, said data structure comprising a plurality of registers, each one of said plurality of registers associated with a time segment and a probability value, said time segments covering a continuous time range; and means for associating said plurality of registers with an event in said circuit, said event comprising a transition for said input signal, a transition for said output signal, or a delay for said component.
Claim 39
Dependent Claim
25 words
A data structure as in claim 26, wherein said probability values indicate a probability distribution that is not a uniform distribution or a normal distribution.
Claim 40
Dependent Claim
30 words
A data structure as in claim 26, wherein said probability values comprise a resultant of convolving a set of probability values in a first and a second said data structure.
References Cited (Backward Citations)
US4495585A
Cited
US4559602A
Cited
US5003248A
Cited
US5081592A
Cited
US5008940A
Cited
US4843309A
Cited
US5028914A
Cited
US4985844A
Cited
US5095454A
Cited
US5153501A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-01-16 | 1998-07-18 | 1999-01-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-01-16 | 2002-07-18 | 2003-01-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-01-16 | 2006-07-18 | 2007-01-17 | $7700.00 | Window Closed / Lapsed |