Binary time-frame expansion of sequential systems

• US 6,871,310 B2
• Filed: 06/03/2002
• Issued: 03/22/2005
• Est. Priority Date: 06/03/2002
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Fallah, Farzan
• Primary Examiner(s): TU, CHRISTINE TRINH LE
• Application Number:
  US10/162,018
• Publication Number:
  US 20030226075A1
• Time in Patent Office: 1,023 Days
• Field of Search: 714/724, 714/726, 714/727, 714/728, 714/729, 714/811, 714/815, 714/55, 716/1, 716/4, 716/5, 716/6, 713/500, 713/503
• US Class Current: 714/724
• CPC Class Codes: G06F 30/33 Design verification, e.g. functional simulation or model checking

Abstract

A processing system provides for analysis of sequential systems using binary time-frame expansion of these systems. This expansion technique produces models in which inputs and values for time may be treated as variables for producing various outputs and states.

Claims

1. A method for processing sequential systems comprising:

determining a maximum time-frame for analysis of a sequential system, the maximum time-frame representable using an n-bit binary value;

generating a binary time-frame expanded model of the sequential system, the binary time-frame expanded model having n cascaded binary time-frame clauses;

analyzing the sequential system using the binary time-frame expanded model; and

generating an analysis report.

2. The method of claim 1, wherein:

each of the clauses has a relative position, p, counted from the first of the clauses, which hasp equal to zero; and

each of the clauses comprises a series of 2^p copies of the sequential system.

3. The method of claim 2, wherein each of the clauses:

receives an initial state and 2^p input sets; and

generates a resulting state and 2^p output sets using the initial state and the input sets.

4. The method of claim 3, wherein, for each of the clauses:

a first copy of the sequential system receives a first one of the input sets and the initial state and generates a first one of the output sets and a state; and

each subsequent copy of the sequential system receives a subsequent one of the input sets and a state from a preceding one of the copies of the sequential system in the series and generates a subsequent one of the output sets and a state.

5. The method of claim 2, wherein each of the clauses receives an initial state and produces a resulting state, the resulting state a selection between the initial state and a state generated from the series of copies of the sequential system.

6. The method of claim 5, further comprising, for each clause, selecting between the initial state and the state generated from the series of copies of the sequential system based on a value for the p^th digit in a binary representation of a time-frame under analysis.

7. The method of claim 6, further comprising, for each clause:

selecting the initial state if the p^th digit in the binary representation has a value of zero; and

selecting the state generated from the series of copies of the sequential system if the p^th digit in the binary representation has a value of one.

8. The method of claim 1, wherein analyzing the sequential system:

specifying a desired condition for the sequential system; and

analyzing the binary time-frame expanded model to identify input vectors that result in the desired condition.

9. The method of claim 8, wherein generating the analysis report comprises:

determining whether the analysis has identified the input vectors for obtaining the desired condition;

if the analysis has identified the input vectors, identifying the input vectors within the analysis report; and

if the analysis has not identified the input vectors, indicating that the desired condition represent an infeasable problem in the analysis report.

10. The method of claim 1, wherein the sequential system comprises a semiconductor design having a plurality of logic elements and at least one memory element, the memory element maintaining state information used by at least one of the logic elements.

11. Software for processing sequential systems, the software embodied in a medium and operable when executed:

to determine a maximum time-frame for analysis of a sequential system, the maximum time-frame representable using an n-bit binary value;

to generate a binary time-frame expanded model of the sequential system, the binary time-frame expanded model having n cascaded binary time-frame clauses;

to analyze the sequential system using the binary time-frame expanded model; and

to generate an analysis report.

12. The software of claim 11, wherein:

each of the clauses has a relative position, p, counted from the first of the clauses, which hasp equal to zero; and

each of the clauses comprises a series of 2^p copies of the sequential system.

13. The software of claim 12, wherein the software is further operable, for each of the clauses:

to receive an initial state and 2^p input sets; and

to generate a resulting state and 2^p output sets using the initial state and the input sets.

14. The software of claim 13, wherein, for each of the clauses:

a first copy of the sequential system receives a first one of the input sets and the initial state and generates a first one of the output sets and a state; and

each subsequent copy of the sequential system receives a subsequent one of the input sets and a state from a preceding one of the copies of the sequential system in the series and generates a subsequent one of the output sets and a state.

15. The software of claim 12, wherein each of the clauses receives an initial state and produces a resulting state, the resulting state a selection between the initial state and a state generated from the series of copies of the sequential system.

16. The software of claim 15, further comprising, for each clause, selecting between the initial state and the state generated from the series of copies of the sequential system based on a value for the p^th digit in a binary representation of a time-frame under analysis.

17. The software of claim 16, further comprising, for each clause:

selecting the initial state if the p^th digit in the binary representation has a value of zero; and

selecting the state generated from the series of copies of the sequential system if the p^th digit in the binary representation has a value of one.

18. The software of claim 11, wherein analyzing comprises:

specifying a desired condition for the sequential system; and

analyzing the binary time-frame expanded model to identify input vectors that result in the desired condition.

19. The software of claim 18, wherein generating the analysis report comprises:

determining whether the analysis has identified the input vectors for obtaining the desired condition;

if the analysis has identified the input vectors, identifying the input vectors within the analysis report; and

if the analysis has not identified the input vectors, indicating that the desired condition represent an infeasable problem in the analysis report.

20. A binary time-frame expanded model of a sequential system comprising:

a plurality of binary time-frame clauses coupled in series, wherein each of the clauses has a relative position in the series, p, counted from the first of the clauses, which has p equal to zero, and wherein each of the clauses comprises a series of 2^p copies of the sequential system and a multiplexer;

wherein within each of the clauses, each of the copies receives an input set and input state information and generates an output set and output state information, a first copy in the series receives initial state information for the clause as the input state information for the first copy, other copies in the series receive the output state information from a preceding one of the copies in the series as the input state information for the other copies, and a last copy in the series provides the output state information from the last copy to the multiplexer; and

wherein each of the clauses receives the initial state information for the clause, provides the initial state information for the clause to the multiplexer, controls the multiplexer based on a value for the p^th digit in a binary representation of a time-frame under analysis to select between the output state information from the last copy and the initial state information for the clause, and provides selected state information from the multiplexer to a next one of the clauses.