Finite state machine with minimized vector processing

• US 5,459,841 A
• Filed: 12/28/1993
• Issued: 10/17/1995
• Est. Priority Date: 12/28/1993
• Status: Expired due to Fees

• Current Assignee: AT&T IPM Corp. (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: O'Grady, James D., Flora-Holmquist, Alan R.
• Primary Examiner(s): Lall, Parshotam S.
• Assistant Examiner(s): VU, VIET DUY
• Application Number:
  US08/174,642
• Time in Patent Office: 658 Days
• Field of Search: 395/375, 395/775, 395/800, 364/715, 364/769
• US Class Current: 326/37
• 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

Conventional AND vectors are compared to corresponding input vectors of the same length as part of the logic processing associated with the finite state machine. AND vectors having a single set bit are translated into AND index vectors in which the bit position of the single set bit is encoded. AND index vectors are also identified by an index flag. The encoded bit position is utilized to identify the corresponding bit position in the input vector to perform a TRUE/FALSE test to determine an overall TRUE or FALSE indication. This technique avoids a bit by bit comparison for AND vectors having a single set bit.

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 sets of selection vectors, and target vectors against which the sets of selection vectors are compared, logical data is selectively stored as binary bits in the selection vectors and target vectors, a method for minimizing time required by the microcomputer implemented FSM comprising the steps of:

a) selecting selection vectors having a single bit that is set, said selection vector having a bit position associated with said single bit, said selected selection vectors defining a first group of vectors and unselected selection vectors defining a second group of vectors;

b) generating for each of said selected selection vectors a corresponding index vector encoded with a flag and containing a binary number identifying the bit position of said single bit that was set;

c) replacing said selected selection vector with said index vector;

d) before comparing a target vector with one of said unselected selection vectors and index vectors, determining if said one vector contains said flag;

e) if said one vector contains said flag, utilizing said binary number contained therein to identify a bit position in the corresponding target vector to which the comparison is to be made;

f) if said one vector to be compared contains said flag, making a logical comparison by determining if said bit position in the target vector is TRUE, thus avoiding a bit by bit comparison of said target vector with said one vector and reducing the time required for such comparison.

2. The method according to claim 1 further comprising the step of:

if said one vector does not contain said flag, comparing said target vector and one vector by a bit to bit comparison to determine if a TRUE condition exists.

3. The method according to claim 1 wherein said comparing step further comprises comparing said target vector and an index vector solely by determining if said bit position in said target vector is TRUE.

4. 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 sets of selection vectors, and target vectors against which the sets of selection vectors are compared, logical data is selectively stored as binary bits in the selection vectors and target vectors, the improvement comprising:

means for selecting selection vectors having a single bit being set, said selection vector having a bit position associated with said single bit, said selected selection vectors defining a first group of vectors and unselected selection vectors defining a second group of vectors;

means for generating, for each of said selected selection vectors, a corresponding index vector encoded with a flag and containing a binary number identifying the bit position of said single bit that is set;

means for replacing said selected selection vector with said index vector;

means for determining if one of said unselected vectors and index vectors selected for comparison with a target vector contains said flag;

means, responsive to said one vector containing said flag, for utilizing said binary number contained therein to identify a bit position in the target vector;

means, responsive to said one vector containing said flag, for making a logical comparison by determining if said bit position in the target vector is TRUE, thus avoiding a bit by bit comparison of said target vector with said one vector, and reducing the time required for such comparison.

5. The microcomputer according to claim 4 further comprising

means, responsive to said one vector not containing said flag, for comparing said target vector and one vector by a bit to bit comparison of said target vector with said one vector to determine if a TRUE condition exists.

6. The microcomputer according to claim 4 wherein said comparing means further comprises means for comparing said target vector and an index vector solely by determining if said bit position in the target vector is TRUE.

7. 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 changes to be made to parameters associated with the process, the FSM having sets of selection vectors, target vectors against which the sets of selection vectors are compared, and output action vectors that control the changes to be made to parameters associated with the process, logical data is selectively stored as binary bits in the selection vectors, target vectors, and output action vectors, a method for minimizing time required by the microcomputer implemented FSM comprising the steps of:

a) selecting output action vectors and selection vectors having a single bit that is set, said selected output action vectors and selection vectors having a bit position associated with said single bit;

b) for each of said selected vectors, generating a corresponding index vector encoded with a flag and containing a binary number identifying the bit position of said single bit that was set in the corresponding selected vector;

c) replacing said selected vectors with corresponding index vectors;

d) during execution of said implementation of the finite state machine, determining if a certain vector to be processed contains said flag;

e) if said certain vector contains said flag, utilizing the binary number contained in said certain vector to identify a bit position in said target vector associated with the processing of said certain vector;

f) if said certain vector contains said flag, logically processing said target vector based on whether said bit position in said target vector is TRUE, thus reducing the time required for processing said target vector relative to said certain vector.

8. The method according to claim 7 wherein said comparing step further comprises processing said target vector relative to said certain vector based solely on the determination of whether said bit position in the another vector is TRUE.