Patent ID: 7899660

Claim:
A method performed by a processor for characterizing a digital circuit including input pins and associated output pins, comprising: receiving a truth table associated with the digital circuit to validate arcs by the processor, wherein each arc includes a path to an output pin from an associated input pin; determining, by the processor, valid arcs and their associated state information by identifying a change in each of the input pins that results in a change in associated one of the output pins using the truth table and declaring them as the valid arcs; forming a first arc table using the valid arcs and their associated state information by the processor; identifying redundant arcs in the first arc table using the associated state information wherein the redundant arcs include those states which do not affect an output transition at the output pin for a transition at the associated input pin; forming a second arc table by removing the identified redundant arcs and associated state information from the first arc table; wherein forming the second arc table by removing the identified redundant arcs and associated state information from the first arc table comprises: identifying an input pin for which states need to be reduced, wherein the states for the input pin are obtained from entries in the first arc table; identifying a valid state s′ for each state s such that hamming distance between s and s′ is 1, if a valid s′ is identified for a state s, then for each state pair s-s′ thus identified, identifying a pin which is different in the state pair and creating an entry in the second arc table for that state with the different pin marked as don't care ‘X’, if a valid s′ cannot be identified for a state s, then inserting that state s into the second arc table without any change in the output pins; and repeating the steps of identifying an input pin, identifying a valid state s′, identifying a pin, and inserting for each of the input pins; and repeatedly substituting the first arc table with the second arc table at each iteration; generating stimulus for each valid arc in the second arc table; and applying the generated stimulus to each valid arc and measuring resulting output to characterize the digital circuit.