State Machine Charts

State Machine Charts

State Machine Design with SM Charts

Another name for a sequential circuit is an algorithmic state machine or simply a state machine, named for the sequential circuit that is used to control a digital system that carries out a step-by-step procedure or algorithm.

As an alternative to using state graphs, a special type of flowchart, called a state machine flowchart or SM chart, may be used to describe the behavior of a state machine

State Machine Charts

SM charts are also called ASM (algorithmic state machine) charts.

Advantages:

1.   It is often easier to understand the operation of a digital system by inspection of the SM chart instead of the equivalent state graph.

2.   A given SM chart can be converted into several equivalent forms, and each form leads directly to a hardware realization.

An SM chart differs from an ordinary flowchart in that certain specific rules must be followed in constructing the SM chart. When these rules are followed, the SM chart is equivalent to a state graph, and it leads directly to a hardware realization.

Fig.1: Components of an SM Chart

Fig.1 shows the three principal components of an SM chart.

The state of the system is represented by a state box. The state box contains a state name, and it may contain an output list. A state code may be placed outside the box at the top.

A decision box is represented by a diamond-shaped symbol with true and false branches. The condition placed in the box is a Boolean expression that is evaluated to determine which branch to take.

The conditional output box, which has curved ends, contains a conditional output list.The conditional outputs depend on both the state of the system and the inputs.

An SM chart is constructed from SM blocks. Each SM block, contains exactly one state box together with the decision boxes and conditional output boxes associated with that state.

An SM block has exactly one entrance path and one or more exit paths. Each SM block describes the machine operation during the time that the machine is in one state.When a digital system enters the state associated with a given SM block, the outputs on the output list in the state box become true.

The conditions in the decision boxes are evaluated to determine which path (or paths) is (are) followed through the SM block.When a conditional output box is encountered along such a path, the corresponding conditional outputs become true. A path through an SM block from entrance to exit is referred to as a link path.

Fig.2: Example of an SM Block

From Fig.2, when state S1 is entered, outputs Z1 and Z2 become 1. If inputs X1 and X2 are both equal to 0, Z3 and Z4 are also 1, and at the end of the state time, the machine goes to the next state via exit path 1. On the other hand, if X1 =1 and X3 = 0, the output Z5 is 1, and an exit to the next state will occur via exit path 3.

A given SM block can generally be drawn in several different forms as shown in fig.3. In both Fig.3(a) and (b), the output Z2=1 if X1 = 0; the next state is S2 if X2 = 0 and S3 if X2 = 1.

Fig.3: Equivalent SM Blocks

Consider a Combinational circuit where only one state occurs and the state doesn’t change, i.e.,

Z1= A+A’BC = A + BC

Fig.4: Equivalent SM Chart for the combinational Network

Rules to be followed while constructing an SM block:

1.   For every valid combination of input variables, there must be exactly one exit path defined. This is necessary because each allowable input combination must lead to a single next state.

2.   No internal feedback within an SM block is allowed.

Fig.5: SM Block with Feedback

An SM block can have several parallel paths which lead to the same exit path as shown in fig.6 (a), and more than one of these paths can be active at the same time. Eg., if X1 = X2 = 1 and X3 = 0, the link paths marked with dashed lines are active, and the outputs Z1, Z2, and Z3 will be l. Although this would not be a valid flowchart for a program for a serial computer, it presents no problems for a state machine implementation. The state machine can have a multiple-output circuit that generates Z1, Z2, and Z3 at the same time.

In the serial SM block as shown in fig.6 (b) only one active link path between entrance and exit is possible. For any combination of input values the outputs will be the same as in the equivalent parallel form. The link path forX1=X2=1 and X3=0 is shown with a dashed line, and the outputs encountered on this path are Z1, Z2, and Z3. Regardless of whether the SM block is drawn in serial or parallel form, all of the tests take place within one clock time.

Fig.6: Equivalent SM Block

Conversion of a state graph for a sequential machine into an equivalent SM chart:

The state graph of Fig.7(a) has both Moore and Mealy outputs. The equivalent SM chart has three blocks - one for each state. The Moore outputs (Za, Zb and Zc) are placed in the state boxes because they do not depend on the input. The Mealy outputs (Z1 and Z2) appear in conditional output boxes as they depend on both the state and input.

Each SM block has only one decision box as only one input variable must be tested. For both the state graph and SM chart, Zc is always 1 in state S2. If X=0 in state S2, Z1 =1 and the next state is S0. If X = 1, Z2 = 1 and the next state is S2.

Fig.8 shows a timing chart for the SM chart with an input sequence X = 1, 1, 1, 0, 0, 0. All state changes occur immediately after the rising edge of the clock.

Since the Moore outputs (Za,Zb and Zc) depend on the state, they can only change immediately following a state change.

The Mealy outputs (Z1 and Z2) can change immediately after a state change or an input change. In any case, all outputs will have their correct value during the active edge of the clock.

   

Fig.7: Conversion of a state Graph to an SM Chart         Fig.8: Timing Chart