Finite state machine with minimized memory requirements

• US 5,473,531 A
• Filed: 12/28/1993
• Issued: 12/05/1995
• Est. Priority Date: 12/28/1993
• Status: Expired due to Term

• Current Assignee: AT&T IPM Corp. (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Mills, Thomas L., Flora-Holmquist, Alan R.
• Primary Examiner(s): Trammell, James P.
• Application Number:
  US08/174,646
• Time in Patent Office: 707 Days
• Field of Search: 364/148, 364/140, 364/141, 364/926.9-926.93, 395/500, 395/275
• US Class Current: 700/12
• CPC Class Codes: G05B 19/042 using digital processors G05B19/05 takes precedence
• CPC Class Codes: G05B 19/045 using logic state machines, consisting only of a memory or a programmable logic device containing the logic for the controlled machine and in which the state of its outputs is dependent on the state of its inputs or part of its own output states, e.g. binary decision controllers, finite state controllers
• CPC Class Codes: G05B 2219/23289 State logic control, finite state, tasks, machine, fsm

Abstract

A set of indexes associated with each state of the finite state machine provides an address locator to a location in memory of a microprocessor where sets of logical vectors are stored. A count stored in a group of logical vectors identifies the number of stored logical vectors and hence, permits memory allocation to vary depending upon the number of logical conditions to be applied for a given test. A predetermined null value entered in an index is interpreted by the finite state machine as requiring no further processing and having no corresponding memory allocated for logical vectors.

Claims

1. In a microcomputer containing an implementation of a finite state machine (FSM) that controls a process wherein a plurality of input signals received by the FSM correspond to monitored process conditions and output signals generated by the FSM correspond to commands that effect changes in parameters associated with the process, the FSM having a plurality of states and sets of selection vectors, logical data selectively stored in the selection vectors to define logical conditions, a method for implementing the FSM with minimized memory required by the microcomputer comprising the steps of:

a) storing in a first portion of memory of said microprocessor only said sets of selection vectors containing said logical data;

b) storing an index in a second portion of memory of said microcomputer for each state of said FSM, said index containing an address indicator corresponding to each set of said selection vectors;

c) during the operation of said FSM in a current state, said microprocessor accessing one of said sets of selection vectors via reading a corresponding one address indicator from a corresponding index.

2. The method according to claim 1 further comprising the step of storing a first count associated with each of group of sets of selection vectors associated with a state, said first count being the number of sets of selection vectors contained within the corresponding group, said microcomputer utilizing said first count to define the maximum number of sets of selection vectors to be processed for each state.

3. The method according to claim 1 further comprising the step of storing a first count associated with each of said sets of selection vectors, said first count being the number of selection vectors contained in each set, said microcomputer utilizing said first count to define the number of selection vectors associated with each set.

4. The method according to claim 3 further comprising the step of storing a second count associated with each of said sets of selection vectors, said second count being the number of selection vectors contained in each set, said microcomputer utilizing said second count to define the number of selection vectors associated with each set.

5. The method according to claim 4 further comprising the step of storing an control vector associated with each of said sets of selection vectors, said microcomputer executing a control vector associated with one set of selection vectors if at least one of the selection vectors of said one set satisfies a TRUE condition of a logical AND comparison with said input signals.

6. The method according to claim 1 further comprising the step of storing an control vector associated with each of said sets of selection vectors, said microcomputer executing a control vector associated with one set of selection vectors if at least one of the selection vectors of said one set satisfies a TRUE condition of a logical AND comparison with said input signals.

7. The method according to claim 1 further comprising the steps of storing a control vector associated with each of said sets of selection vectors, and executing a control vector associated with one set of selection vectors if at least one of the selection vectors of said one set satisfies a TRUE condition of a logical AND comparison with said input signals.

8. In a microcomputer containing an implementation of a finite state machine (FSM) that controls a process wherein a plurality of input signals received by the FSM correspond to monitored process conditions and output signals generated by the FSM correspond to commands that effect changes in parameters associated with the process, the FSM having a plurality of states and sets of selection vectors, logical data selectively stored in the selection vectors to define logical conditions, a method for minimizing memory required by the microcomputer for the FSM implementation comprising the steps of:

a) storing an index in memory of said microcomputer for each state of said FSM, said index containing an address locator corresponding to a set of said selection vectors;

b) assigning a predetermined null value to address locators that correspond to said sets containing selection vectors without any logical data;

c) storing in memory of said microprocessor selection vectors contained in said sets with corresponding address locators that do not contain said null value, no memory in said microprocessor used for storage of selection vectors contained in said sets corresponding to address locators that contain said null value;

d) assigning a non-null value to address locators that correspond to sets containing selection vectors with logical data, said non-null value serving as a pointer to a location in memory that contains the corresponding selection vectors;

e) during the operation of said FSM in a given state, said microprocessor seeks to access one set of selection vectors via reading a corresponding one address locator, the microprocessor interpreting a null value in said one address locator as an indication that no FSM processing of the associated one set of selection vectors is required, the microprocessor interpreting a non-null value in the one address locator as an indication that FSM processing of the associated one set of selection vectors is required, whereby memory is not required for the storage of selection vectors that do not contain logical data.

9. The method according to claim 8 wherein said microcomputer interprets a non-null value in the one address locator as address information and proceeds to access said one set of selection vectors at a memory location in the memory indicated by said non-null value.

10. The method according to claim 8 further comprising the step of storing a first count associated with said sets of selection vectors, said first count being the number of sets of selection vectors, said microcomputer utilizing said first count to define the maximum number of sets of selection vectors to be processed.

11. The method according to claim 8 further comprising the step of storing first counts associated with each of said sets of selection vectors, said first count being the number of selection vectors contained in each set, said microcomputer utilizing said first counts to define the number of selection vectors associated with each set.

12. The method according to claim 11 further comprising the step of storing second counts associated with each of said sets of selection vectors, said second count being the number of selection vectors contained in each set, said microcomputer utilizing said second counts to define the number of selection vectors associated with each set.

13. The method according to claim 8 further comprising the step of storing a control vector associated with each of said sets of selection vectors, said microcomputer executing a control vector associated with one set of selection vectors if at least one of the selection vectors of said one set satisfies a TRUE condition of a logical AND comparison with said input signals.

14. The method according to claim 8 further comprising the steps of storing a control vector associated with each of said sets of selection vectors, and executing a control vector associated with one set of selection vectors if at least one of the selection vectors of said one set satisfies a TRUE condition of a logical AND comparison with said input signals.

15. In a control system in which a process is controlled by a finite state machine (FSM) wherein a plurality of input signals received by the FSM correspond to monitored process conditions and output signals generated by the FSM correspond to commands that effect changes in parameters associated with the process, the FSM having a plurality of S states and sets of selection vectors, logical data selectively stored in the selection vectors to define logical conditions, the FSM implemented in a microcomputer having associated memory, the improvement comprising:

means for storing in said memory an address locator corresponding to a set of said selection vectors for each state S of said FSM;

means for assigning a predetermined null value to address locators that correspond to sets containing selection vectors without any logical data;

means for storing in memory of said microprocessor selection vectors contained in said sets corresponding to address locators that do not contain said null value and using no memory in said microprocessor for storage of selection vectors contained in sets corresponding to address locators that contain said null value;

means for assigning a non-null value to address locators that correspond to sets containing selection vectors with logical data, said non-null value serving as a pointer to a location in said memory that contains the corresponding selection vectors;

means for during the operation of said FSM in a given state wherein said microprocessor seeks to access one set of selection vectors via reading a corresponding one address locator, the microprocessor interpreting a null value in said one address locator as an indication that no FSM processing of the associated one set of selection vectors is required, the microprocessor interpreting a non-null value in the one address locator as an indication that FSM processing of the associated one set of selection vectors is required, whereby memory is not required for the storage of selection vectors that do not contain logical data.

16. The control system according to claim 15 wherein said microcomputer interprets a non-null value in the one address locator as address information and proceeds to access said one set of selection vectors at a memory location in the memory indicated by said non-null value.

17. The control system according to claim 15 further comprising means for storing a first count associated with said sets of selection vectors, said first count being the number of sets of selection vectors, said first count to defining the maximum number of sets of selection vectors to be processed.

18. The control system according to claim 15 further comprising means for storing first counts associated with each of said sets of selection vectors, said first count being the number of selection vectors contained in each set, said first counts defining the number of selection vectors associated with each set.

19. The control system according to claim 18 further comprising means for storing second counts associated with each of said sets of selection vectors, said second count being the number of selection vectors contained in each set, said second counts defining the number of selection vectors associated with each set.

20. The control system according to claim 17 further comprising means for storing a control vector associated with each of said sets of selection vectors, and means for executing a control vector associated with one set of selection vectors if at least one of the selection vectors of said one set satisfies a TRUE condition of a logical AND comparison with said input signals.