Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-01-04
2002-10-08
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000
Reexamination Certificate
active
06463565
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to methods and apparatus for designing state machines using tables and object-oriented programming techniques.
BACKGROUND OF THE INVENTION
Finite state machines are logical systems in which the sequential logic that implements the system has only a fixed number of possible states. When the system is in a given state, it may perform various predefined operations, such as displaying images or calculating results. The logic causes the system to advance from state to state causing the system to sequentially perform various operations. More specifically, when the logic is in a given state, the output and next sequential state are determined by a combinatorial function of the input to the logic and the present state of the logic. State machine approaches are typically utilized when designing and implementing protocols, user interfaces and complex systems involving asynchronous events, and solving other complex problems.
There are many methods for describing the behavior of finite state machines so that the implementing logic can be designed. These methods include abstract state machine notation, state diagrams, state tables, and hardware description languages.
FIG. 1
illustrates a very simple state diagram that has four states
100
,
102
,
104
and
106
. When the system is in each of these states, events that are represented by arrows can occur which move the system from one state to another. For example, in the diagram, the initial state
100
is assumed to be “State 1”. An event called “Event 1” and represented by arrow
108
causes the logic to advance to a new state
102
called “State 2.” The occurrence of another event called “Event 2” and represented by arrow
110
results in the logic moving to another state
104
called “State 3.” From “State 3”,
104
, an “Event 3” or an “Event 5” are possible. The occurrence of “Event 5”, represented by arrow
114
, results in the system returning to its original state
100
, that is “State 1.” Alternatively, the occurrence of “Event 3”, represented by arrow
112
, causes the system to advance to a new state
106
, called “State 4.” While the system is in “State 4”,
106
, the occurrences of “Event 1”, “Event 2”, “Event 3”, and “Event 5” do not change the system state as indicated by arrow
116
. However, another response, such as an error condition may be raised in response to these events. Finally if an event called “Event 4” occurs while the system is in state
106
, the system will advance as represented by arrow
118
back to State
1
,
100
.
When state tables are used to describe the logic behavior, the underlying logic is said to be “table driven.” In the communications area, table driven state machines have been used to graphically represent a solution to a communication problem. From the table, the underlying logic can be implemented quickly, often by programming teams. The is particularly true when a state machine is implemented in software. The use of tables also has the added advantage that future changes are relatively easy to implement, and the incidence of possible regressions is reduced or, at least, contained.
An example of a state table is illustrated in
FIG. 2
that shows a state table that implements a finite state machine illustrated by the state diagram of FIG.
1
. The table has four columns
200
,
202
,
204
and
206
that represent the current state, an event that occurs, the action taken when the event occurs and the resulting state of the system (which may be the current state), respectively. Each row, such as row
208
, represents a particular state and event combination represented by the first two columns
210
and the results which occur represented by the last two columns,
212
. As shown in
FIG. 2
, rows
208
and
214
, the system changes from “State 1” and “State 2” only if event
1
or event
2
occurs as appropriate. As shown by rows
216
and
218
, The system can advance from “State 3” to two different states if either of events
3
or
5
occur. “State 4” advances only if event
4
occurs, but events
1
,
2
,
3
, and
5
result in an error being reported, and the system remains in the current state—“State 4.”
A state table can be directly implemented in software by reproducing the state table in memory and using the current state and an event occurrence as inputs to perform a table lookup. Utilizing this table approach, the behavior of the implementing software becomes more readily apparent. As an example, if the system functionality must be extended at a later date, additional states, events, or functions may be added, and the implications easily understood. This easy expandability allows the system to be readily grown and reduces the exposure to regression. Another advantage of this approach is that the interaction of each of the functions is easily evaluated. Consequently, each of the functions (which normally require the most significant coding effort) can be assigned to a different programmer without requiring extensive coordination.
The problem with implementing the state table as a table lookup in memory is the additional memory required by the table. For large state tables, the amount of memory can be significant. In many cases, the benefits of this approach may outweigh the extra memory required, but in embedded systems, memory may have a more significant expense associated with it, and thus not justify this benefit.
The state table illustrated in
FIG. 2
may also be implemented in a more complete form
300
illustrated in FIG.
3
. This table is similar to the table illustrated in
FIG. 2
except that it has a row representing each possible state and each possible event. For example, State_
1
has a row representing each of events Event_
1
to Event_
5
, represented by rows
302
-
310
, respectively. If an event cannot occur in a particular state the Action column
301
is left blank and the NEXT STATE
303
remains the current state. Similarly State
2
has rows
312
-
320
representing Event_
1
to Event_
5
and State_
3
has rows
322
-
330
representing Event_
1
to Event_
5
. State_
4
has rows
332
-
340
representing Event_
1
to Event_
5
. A complete matrix like the one illustrated in
FIG. 3
forces the implementers to consider the impact of events that are not anticipated, but even more memory is required to implement the table.
Therefore, it is desirable to provide the advantages of a finite state machine implemented with a state table while reducing the amount of memory used in such an implementation as much as possible.
SUMMARY OF THE INVENTION
In accordance with the principles of the invention, a finite state machine is implemented by encapsulating the portions of a state table, which are associated with each state in a state object. Each state object is instantiated when the associated state is entered and destroyed when the state is exited. Since memory is only allocated at runtime when an object is instantiated and in existence, the amount of memory required to implement the state table is minimized.
In accordance with one embodiment, the state class from which the state object is instantiated can be subclassed. In accordance with normal object-oriented class design, a subclass inherits the state table of its parent class. However, the subclass allows table rows to be added and table rows present in the parent class to be overwritten in the subclass.
In accordance with another embodiment, state table in each state class includes methods that are called when the class is created and destroyed.
REFERENCES:
patent: 5473531 (1995-12-01), Flora-Holmquist et al.
patent: 5517432 (1996-05-01), Chandra et al.
patent: 6055594 (2000-04-01), Lo et al.
patent: 6198303 (2001-03-01), Rangasayee
patent: 6212625 (2001-04-01), Russell
Kelly Keith C.
Kelly Michael
Pietras Mark A.
Dinh Pavel
NetSpeak Corporation
Smith Matthew
LandOfFree
Method for designing object-oriented table driven state... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for designing object-oriented table driven state..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for designing object-oriented table driven state... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2926222