Temporal decomposition for design and verification

Details Temporal decomposition for design and verification Temporal decomposition for design and verification

2011-03-01

2011-03-01

Lin, Sun J (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Integrated circuit design processing

Logic design processing

C716S106000, C716S111000

Reexamination Certificate

active

07900173

ABSTRACT:
Behavior of a finite state machine is represented by unfolding a transition relation that represents combinational logic behavior of the finite state machine into a sequence of transition relations representing combinational logic behavior of the finite state machine in a sequence of time frames. At least one state is determined in a transition relation in the sequence that cannot be reached in a subsequent transition relation in the sequence. A subsequent transition relation in the sequence in which the at least one state cannot be reached is simplified with respect to the at least one unreachable state.

REFERENCES:
patent: 5680332 (1997-10-01), Raimi et al.
patent: 6182268 (2001-01-01), McElvain
patent: 6389586 (2002-05-01), McElvain
patent: 2004/0078674 (2004-04-01), Raimi et al.
M. Ganai and A. Aziz, “Improved SAT-based Bounded Reachability Analysis,” Proceedings of the 7th ASPDAC 15th International Conference on VLSI Design, pp. 729-734, Jan. 2002.
L. Zhang, M. Prasad and M. Hsiao, “Incremental Deductive & Inductive Reasoning for SAT-based Bounded Model Checking,” Proceedings of IEEE/ACM International Conference on Computer Aided Design, pp. 502-509, Nov. 2004.
A. Biere, A. Cimatti, E.M. Clarke, O. Strichman, Y. Zhu, et al., “Bounded Model Checking,” Advances in Computers, vol. 58, pp. 117-148, by Elsevier Sciences (USA), 2003.
A. Biere, A. Cimatti, E.M. Clarke, and Y. Zhu, “Symbolic model checking without BDDs” in 5th International Conference on Tools and Algorithms for Construction and Analysis of Systems (TACAS '99) (Amsterdam, Netherlands) pp. 193-207, Mar. 1999.
J. Baumgartner, A. Kuehlmann and J. Abraham, “Property checking via structural analysis,” in Computer-Aided Verification (CAV '02), (Copenhagen, Denmark), pp. 151-165, Jan. 1003.
D. Kroening and O. Strichman, “Efficient computation of recurrence diameters,” in International Conference for Verification, Model Checking, and Abstract Interpretation, Jan. 2003.
P. Chauhan, E. Clarke, J. Kukula, S. Sapra and D. Wang, “Automated abstraction refinement for model checking large state spaces using SAT based conflict analysis,” in Formal Methods of Computer Aided Design (FMCAD '02), pp. 33-51, Springer-Verlag, Nov. 2002.
K.L. McMillan and N. Amla, “Automated abstraction without counterexamples,” in International Conference on Tools and Algorithms for Construction and Analysis of Systems (TACAS '03), (Warsaw, Poland), pp. 2-17, Apr. 2003 LNCS 2619.
M. Sheeran, S. Singh and G. Stalmarck, “Checking safety properties using induction and a SAT-solver,” in Formal Methods in Computer-Aided Design (Austin, TX), pp. 108-125, Springer-Verlag, Nov. 2000.
A. Gupta, A. Gupta, Z. Yang and P. Ashar, “Dynamic Detection and Removal of Inactive Clauses in SAT with Application in Image Computation,” 38th Design Automation Conference Proceedings (Las Vegas, NV), 2001.
A. Kuehlmann and F. Krohm, “Equivalence Checking Using Cuts and Heaps,” in Proceedings of the 34th ACM/IEEE Design Automation Conference (Anaheim, CA), pp. 263-268, Jun. 1997.
A. Kuehlmann, V. Paruthi, F. Krohm and M.K. Ganai, “Robust Boolean Reasoning for Equivalence Checking and Functional Property Verification,” IEEE Transactions on Coomputer'Aided Design, vol. 21, No. 12, pp. 1377-1394, Dec. 2002.
P. Bjesse and K. Claessen, “SAT-based Verification without State Space Traversal,” in formal Methods in Computer-Aided Design (FMCAD '00), (Austin, TX), pp. 372-389, Springer-Verlag, Nov. 2000.
O. Shtrichman, “Pruning techniques for the SAT-based Bounded Model Checking Problem,” in Correct Hardware Design and Verification Methods (CHARME''01), (Livingston, Scotland), pp. 58-70, Springer-Verlang, Sep. 2001.
Bekki et al., “An Automatic Finite State Machine Synthesis Using Temporal Logic Decomposition”, Nov. 1991, IEEE International Conference on Computer-Aided Design, Digest of Technical Papers, pp. 422-425.
Beerel et al., “Covering Conditions and Algorithms for the Synthesis of Speed-Independent Circuits”, IEEE Transactions on CAD, pp. 1-17, Mar. 1998.

Affiliated with

Also associated with

Rating

Temporal decomposition for design and verification does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Temporal decomposition for design and verification, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Temporal decomposition for design and verification will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2658194