The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Aug. 15, 2006
Filed:
Jan. 16, 2002
James Herbert Kukula, Hillsboro, OR (US);
Thomas Robert Shiple, Cupertino, CA (US);
Rajeev Kumar Ranjan, Santa Clara, CA (US);
James Herbert Kukula, Hillsboro, OR (US);
Thomas Robert Shiple, Cupertino, CA (US);
Rajeev Kumar Ranjan, Santa Clara, CA (US);
Synopsys, Inc., Mountain View, CA (US);
Abstract
In a finite state machine (FSM) a set of goal states, to be searched for their reachability from a start state, is defined. An overapproximated path is found from a start state to a goal state by a forward approximation technique. The overapproximated path representation relies upon a partitioning of the state and input bits of FSM. A state matrix of the overapproximated path is organized by time-steps of FSMalong a first dimension and by partitions of FSMstate bits along a second dimension. An underapproximated path, along the path of the stepping stone matrix, is determined. Underapproximation is typically accomplished by simulation. A sequence of states to be output is updated with the underapproximated path. If a start to goal state sequence has been found, the procedure ends. Otherwise, the above steps of over and under approximation are repeated, using the results of the last underapproximation as a start state.