SM Charts and Microprogramming
State Machine Charts:
SM charts resemble software flowcharts. Flowcharts have been very useful in software design for
decades, and in a similar fashion, SM charts have been useful in hardware design.
A proper state graph has to obey some conditions:
(i) one and exactly one transition from a state must be true at any time and
(ii) the next state must be uniquely defined for every input combination.
The conditions in the decision boxes are evaluated to determine which paths are followed through
the SM block. When a conditional output box is encountered along such a path, the corresponding
conditional outputs become true. If an output is not encountered along a path, that output is false
by default. A path through an SM block from entrance to exit is referred to as a link path.
The state box contains a state name, followed by a slash (/) and an optional output list. After a
state assignment has been made, 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.
Example of an SM block:
For the example shown, when state S1 is entered, outputs Z1 and Z2 become 1. If input X1 = 0,
Z3 and Z4 also become 1. If X1 = X2 = 0, 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 l and exiting to the
next state will occur via exit path 3. Since Z3 and Z4 are not encountered along this link path, Z3
= Z4 = 0 by default.
A given SM block can generally be drawn in several different forms. Figure 5-3 shows two
equivalent SM blocks. In both (a) and (b), the output Z2 = 1 if X1 = 0; the next state is S2 if X2 =
0 and S3 if X2 = 1. As illustrated in this example, the order in which the inputs are tested may
affect the complexity of the SM chart.
if A + BC = l; otherwise Z1 = 0. Figure 5-4(b) shows an equivalent SM chart in which the input
variables are tested individually. The output is Z1 = 1 if A = 1 or if A = 0, B = 1, and C = 1. Hence,
Z1 = A + A’BC = A + BC.
Convert State graph to SM chart:
It is easy to convert a state graph for a sequential machine to an equivalent SM chart. The state
graph of the following figure has both Moore and Mealy outputs. The equivalent SM chart has
three blocks—one for each state. The Moore outputs (Za, Zb, Zc) are placed in the state boxes,
since they do not depend on the input. The Mealy outputs (Z1, Z2) appear in conditional output
boxes, since they depend on both the state and input. In this example, each SM block has only one
decision box, since 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 = l and
the next state is S2. We have added a state assignment (S0 = 00, S1 = 01, S2 = 11) next to the state
boxes.
Series and Parallel
If The output is Z1 = 1, if A + BC = 1; otherwise Z1 = 0. The following figure shows an equivalent
SM chart in which the input variables are tested individually. The output is Z1 = 1 if A = 1 or if A
= 0, B = 1, and C = 1. Hence,
Derivation of SM charts
Binary multiplier:
In state S0, when the start signal St is 1, the registers are loaded. In S1, the multiplier bit M is
tested.
• If M = 1, an add signal is generated and the next state is S2.
• If M = 0, a shift signal is generated and K is tested.
Conversion of an SM chart to a Verilog process is straightforward. A case statement can be used
to specify what happens in each state.
The add-shift control generates the required sequence of add and shift signals. The counter counts
the number of shifts and outputs K = 1 just before the last shift occurs. In state S0, when the start
signal St is 1, the registers are loaded. In S1, the multiplier bit M is tested. If M = 1, an add signal
is generated and the next state is S2. If M = 0, a shift signal is generated and K is tested. If K = 1,
this will be the last shift and the next state is S3. In S2, a shift signal is generated, since a shift must
always follow an add. If K = 1, the circuit goes to S3 at the time of the last shift; otherwise, the
next state is S1. In S3, the done signal is turned on.
Behavioral Verilog code for multiplier controller:
module Mult (CLK, St, K, M, Load, Sh, Ad, Done);
input CLK; input St; input K; input M; output Load; output Sh; output Ad; output Done;
reg Ad; reg Sh; reg Load; reg Done;
reg[1:0] State; reg[1:0] Nextstate;
initial begin
State = 0; Nextstate = 0;
end
always @(St or K or M or State) begin
Load = 1’b0; Sh = 1’b0; Ad = 1’b0; Done = 1'b0;
case (State)
0:
begin
if (St == 1'b1) begin
Load = 1'b1; Nextstate = 1;
end
else begin
Nextstate = 0;
end end
1:
begin
if (M == 1'b1) begin
Ad = 1'b1; Nextstate = 2;
end
else begin
Sh = 1'b1;
if (K == 1'b1) begin
Nextstate = 3;
end
else begin
Nextstate = 1;
end
end end
2:
begin
Sh = 1'b1;
if (K == 1'b1) begin
Nextstate = 3;
end
else begin
Nextstate = 1;
end end
3:
begin
Done = 1'b1; Nextstate = 0;
end endcase
end
always @(posedge CLK)
begin
State ,= Nextstate;
end endmodule
Dice Game
Each counter counts in the sequence 1, 2, 3, 4, 5, 6, 1, 2, . . . . Thus, after the “roll” of the dice, the
sum of the values in the two counters will be in the range 2 through 12. The rules of the game are
as follows:
1. After the first roll of the dice, the player wins if the sum is 7 or 11. The player loses if the sum
is 2, 3, or 12. Otherwise, the sum the player obtained on the first roll is referred to as a point, and
he or she must roll the dice again.
2. On the second or subsequent roll of the dice, the player wins if the sum equals the point, and he
or she loses if the sum is 7. Otherwise, the player must roll again until he or she finally wins or
loses.
The inputs to the dice game come from two push buttons, Rb (roll button) and Reset. Reset is used
to initiate a new game. When the roll button is pushed, the dice counters count at a high speed, so
the values cannot be read on the display. When the roll button is released, the values in the two
counters are displayed.
Block diagram
SM chart for dice game
D7 = 1, if the sum of the dice is 7.
D711 = 1, if the sum of the dice is 7 or 11.
D2312 = 1, if the sum of the dice is 2, 3 or 12.
Eq = 1, if the sum of the dice equals the number stored in the point register.
Rb = 1, when the roll button is pressed.
Reset = 1, when the reset button is pressed.
Roll = 1, enabled the dice counters.
Sp = 1, causes the sum to be stored in the point register.
Win = 1, turns on the win light,
Lose = 1, turns on the lose light.
The resulting SM chart is:
Behavioral model for dice game controller:
module DiceGame (Rb, Reset, CLK, Sum, Roll, Win, Lose);
input Rb;
input Reset;
input CLK;
input[3:0] Sum; output Roll; output Win; output Lose;
reg Roll; reg Win; reg Lose;
reg[2:0] State; reg[2:0] Nextstate; reg[3:0] Point; reg Sp;
initial begin
State 5 0;
Nextstate 5 0;
Point 5 2;
end
always @(Rb or Reset or Sum or State) begin
Sp 5 1’b0; Roll 5 1’b0; Win 5 1’b0; Lose 5 1’b0; Nextstate 5 0; case (State)
0:
begin
if (Rb 55 1’b1) begin
Nextstate 5 1;
end end
1:
begin
if (Rb 55 1’b1) begin
Roll 5 1’b1;
end
else if (Sum 55 7 | Sum 55 11) begin
Nextstate 5 2;
end
else if (Sum 55 2 | Sum 55 3 | Sum 55 12) begin
Nextstate 5 3;
end
else begin
Sp 5 1’b1;
Nextstate 5 4;
end end
2:
begin
Win 5 1’b1;
if (Reset 55 1’b1) begin
Nextstate 5 0;
end end
3:
begin
Lose 5 1’b1;
if (Reset 55 1’b1) begin
Nextstate 5 0;
end end
4:
begin
if (Rb 55 1’b1) begin
Nextstate 5 5;
end end
5:
begin
if (Rb 55 1’b1) begin
Roll 5 1’b1;
end
else if (Sum 55 Point) begin
Nextstate 5 2;
end
else if (Sum 55 7) begin
Nextstate 5 3;
end
else begin
Nextstate 5 4;
end
end default :
begin
Nextstate 5 0;
end endcase
end
always @(posedge CLK)
begin
State <5 Nextstate;
if (Sp 55 1’b1) begin
Point <5 Sum;
end end
endmodule
Realization of SM charts
Methods used to realize SM charts are similar to the methods used to realize state graphs. As with
any sequential circuit, the realization will consist of a combinational subcircuit, together with flip-
flops for storing the state of the circuit. Before deriving next-state and output equations from an
SM chart, a state assignment must be made. The best way of making the assignment depends on
how the SM chart is realized.
The procedure for deriving the next state equation for a flip-flop Q from the SM chart is as follows:
1. Identify all of the states in which Q = 1.
2. For each of these states, find all the link paths that lead into the state.
3. For each of these link paths, find a term that is 1 when the link path is followed.
4. That is, for a link path from Si to Sj, the term will be 1 if the machine is in state Si and the
conditions for exiting to Sj are satisfied.
5. The expression for Q1 (the next state of Q) is formed by ORing together the terms found
in step 3
Implementation of Binary Multiplier Controller
We can realize this SM chart with two D flip-flops and a combinational circuit.
Let us assume that the state assignments are
AB = 00 for S0,
AB = 01 for S1,
AB = 10 for S2, and
AB = 11 for S3.
Since S0 has two exit paths, the table has two rows for present state S0. The first row corresponds
to the St = 0 exit path, so the next state and outputs are 0. In the second row, St = 1, so the next
state is 01 and the other PLA outputs are 1000.
Implementation of the Dice Game
Since A, B, C, and Rb have assigned values in most of the rows of the table, these four variables
are used on the map edges, and the remaining variables are entered within the map. E1, E2, E3,
and E4 on the maps represent the expressions given below the maps. We use a straight binary state
assignment. The combinational circuit has 9 inputs and 7 outputs. Three of the inputs correspond
to current state, and three of the outputs provide the next-state information.
The state transition table has one row for each link path on the SM chart. In state ABC = 000, the
next state is A1B1C1 = 000 or 001, depending on the value of Rb. Since state 001 has four exit
paths, the table has four corresponding rows. When Rb is 1, Roll is 1 and there is no state change.
When Rb = 0 and D711 is 1, the next state is 010. When Rb = 0 and D2312 = 1, the next state is 011.
For the link path from state 001 to 100, Rb, D711, and D2312 are all 0, and Sp is a conditional output.
This path corresponds to row 4 of the state transition table, which has Sp = 1 and A1B1C1 = 100.
Data flow model for dice game:
module DiceGame (Rb, Reset, Clk, Sum, Roll, Win, Lose);
input Rb;
input Reset;
input Clk;
input[3:0] Sum;
output Roll;
output Win;
output Lose;
wire Sp;
wire Eq;
wire D7;
wire D711;
wire D2312;
wire DA;
wire DB;
wire DC;
reg A;
reg B;
reg C;
reg[3:0] Point;
initial
begin
A = 0;
B = 0;
C = 0;
End
always @(posedge Clk)
begin
A <= DA ;
B <= DB ;
C <= DC ;
if (Sp == 1’b1)
Point <= Sum ;
end
assign
Win = B & ~C ;
assign Lose = B & C ;
assign Roll = ~B & C & Rb ;
assign Sp = ~A & ~B & C & ~Rb & ~D711 & ~D2312 ;
assign D7 = (Sum == 7) ? 1’b1 : 1’b0 ;
assign D711 = ((Sum == 11) | (Sum == 7)) ? 1’b1 : 1’b0 ;
assign D2312 = ((Sum == 2) | (Sum == 3) | (Sum == 12)) ? 1’b1 : 1’b0 ;
assign Eq = (Point == Sum) ? 1’b1 : 1’b0 ;
assign DA = (~A & ~B & C & ~Rb & ~D711 & ~D2312) | (A & ~C) | (A & Rb) | (A & ~D7
& ~Eq) ;
assign DB = ((~A & ~B & C & ~Rb) & (D711 | D2312)) | (B & ~Reset) | ((A & C & ~Rb)
& (Eq | D7)) ;
assign DC = (~B & Rb) | (~A & ~B & C & ~D711 & D2312) | (B & C & ~Reset) | (A & C
& D7 & ~Eq) ;
endmodule
Microprogramming
Microprogramming is a technique to implement the control unit of a digital system.
Microprogramming is building a special computer for executing the algorithmic flow chart
describing the controller of a system. This development stemmed out of the separation of
architecture and controller.
S0: if St is true, produce Load signal and go to S1,
else go to S0;
S1: if M is true, produce Ad and go to S2,
else produce Sh, check whether K is 1;
if K is 1 go to S3;
if K is 0 go to S1;
S2: produce Sh; if K = 0, go to S1;
else go to S3;
S3: produce Done and go to S0;
If a memory can store all control signals and the next state information corresponding to each state
for each input condition, one should be able to realize the controller by just “sequencing” through
the memory. For this reason, microprogrammed controllers are also often called sequencers. The
memory that stores the control words is called the control store or microprogram memory.
Microprogramming can be implemented in a variety of ways. The general idea is to store a control
word corresponding to each state. The control word is also called a microinstruction.
Typical Hardware arrangement for Microprogramming:
The ROM output has four fields: TEST, NSF, NST, and OUTPUT. TEST controls the input MUX,
which selects one of the inputs to be tested in each state. If this input is 0 (false), the second MUX
selects the NSF field as the next state. If the input is 1 (true), it selects the NST field as the next
state. The OUTPUT bits correspond to the control signals. Note that in order to use this hardware
arrangement, the SM chart must have only Moore outputs, since the outputs can be a function only
of the state.
Microprogramming becomes easy if the following two transformations are done on SM charts:
i. Eliminate all conditional outputs by transforming to a Moore machine.
ii. Test only one input (qualifier) in each state.
Microprogrammed multiplier SM chart with no conditional outputs:
The corresponding actions can be described by the following pseudocode:
S0: if St is true, go to S01,
else go to S0;
S01: produce Load; Go to S1;
S1: if M is true, go to S11, else go to S12;
S11: produce Ad; go to S2;
S12: produce Sh; if K = 0, go to S1; else go to S3;
S2: produce Sh; if K = 0, go to S1;
else go to S3;
S3: produce Done; go to S0;
Eg.2. The following SM chart is to be realized using the two-address microprogramming structure.
Convert the SM chart to the proper form by adding a minimum number of states to the given
diagram. Make a suitable state assignment. Write the microprogram required to implement this
SM chart.
Soln:
Linked State Machines
When a sequential machine becomes large and complex, it is desirable to divide the machine into
several smaller machines that are linked together. Each of the smaller machines is easier to design
and implement. Also, one of the submachines may be “called” in several different places by the
main machine.
⮚ As an example of using linked state machines, we split the SM chart of the following figure
into two linked SM charts. In the figure, Rb is used to control the roll of the dice in states
S0 and S1 and in an identical way in states S4 and S5.
⮚ The main control generates an En_roll (enable roll) signal in T0 and then waits for a
Dn_roll (done rolling) signal before continuing. Similar action occurs in T1.
⮚ The roll-control machine waits in state S 0 until it receives an En_roll signal from the main
dice-game control. Then, when the roll button is pressed (Rb = 1), the machine goes to S1
and generates a Roll signal.
⮚ It remains in S1 until Rb = 0, in which case, the Dn_roll signal is generated and the machine
goes back to state S0.
Eg.3. Draw an SM chart for the BCD-to-binary converter.
Soln:
Eg.4. Realize the SM chart of the following SM chart using the two-address microprogramming.
Convert the SM chart to the proper form by adding a minimum number of states to the given chart.
Write the microprogram required to implement the circuit.
Soln: