UNIT –III

Behavioral modeling of sequential logic modules

Flip-Flops
1. D FLIP-FLOP

LOGIC DIAGRAM: CHARACTERISTIC TABLE:

resetn clock d qn q n+1

1 x x 0
0 0 0 0
0 1 0 1
Behavioral Modelling:
module behvd_ff(d, clock, resetn, q); 0 0 1 0
input d, clock, resetn; 0 1 1 1
output q;
reg q;
always @(posedge clock)
if(!resetn)
q<=0;
else
q<=d;
endmodule

Verilog Test Bench:

module dtest_v;
reg d;
reg clock;
reg resetn;
wire q;
d_ff uut (.d(d), .clock(clock), .resetn(resetn), .q(q));
always
#5 clock=~clock;
initial begin
#100 $finish;
end
initial begin
clock=1;
reset n=0;
d=1'b0;
#20 reset n=1; d=1'b1;
 #20 reset n=0; d=1'b0;
end
endmodule
2. T FLIP-FLOP
LOGIC DIAGRAM: CHARACTERISTIC TABLE:

resetn clock t qn q n+1

1 x x 0
0 0 0 0

BLOCK DIAGRAM 0 1 0 1
0 0 1 1
0 1 1 0

Behavioral Modelling:
module tff_behv(t, clk, rst, q);
input t, clk, rst;
output reg q;
always@(posedge clk)
if(rst == 1)
q<=1'b0;
else
begin
if(t==1)
q<= ~q;
else
q<= q;
end
endmodule

VERILOG TEST BENCH:

module tfftest_v;
reg t;
reg clk;
reg rst;
wire q;
tff uut ( .t(t), .clk(clk), .rst(rst), .q(q));
always
#5 clk = ~clk;
initial begin
#100 $finish;
 end
initial begin
clk= 1; rst = 1; t=0;
#5 t=0;
#10 rst=0; t=1;
#30 t=0;
end
endmodule
3. JK FLIP-FLOP
LOGIC DIAGRAM: CHARACTERISTIC TABLE:

rst clk j k qn q n+1

1 x x x 0
0 0 0 0 0

0 0 0 1 1
BLOCK DIAGRAM
0 0 1 0 0
0 0 1 1 0

0 1 0 0 1

0 1 0 1 1
Behavioral Modelling:
module jkff_behv(j, k, clk, rst, q); 0 1 1 0 1
input j, k, clk, rst;
output reg q;
always@( posedge clk) 0 1 1 1 0
begin
if(rst == 1'b1)
q<= 1'b0;
else
case({j,k})
2'b00: q<=q;
2'b01: q<=1'b0;
2'b10: q<=1'b1;
2'b11: q<= ~q;
endcase
end
endmodule
Verilog Test Bench:
module jkfftest1_v;
reg j; reg k; reg clk; reg rst;
 wire q;
jkff uut (.j(j),.k(k), .clk(clk), .rst(rst),.q(q));
always
#5 clk = ~clk;
always
#5 rst = ~ rst;
initial begin
#100 $finish;
end
initial begin
rst = 0; j=1; k=0; clk=1;
#5 j=0; k=1; #5 j=1; k=1; #5 j=1; k=0;
end
endmodule
4. SR FLIP-FLOP
LOGIC DIAGRAM: CHARACTERISTIC TABLE:
rst clk s r qn q n+1

1 x x x 0
0 0 0 0 0

0 0 0 1 1
0 0 1 0 0
0 0 1 1 0
Behavioral Modelling:
module srff_behv(input s, r, clk, rst, output reg q); 0 1 0 0 1
always@( posedge clk)
begin 0 1 0 1 1
if(rst == 1'b1)
q<= 1'b0; 0 1 1 x x
else
case({s,r}) 0 1 1 x x
2'b00: q<=q;
2'b01: q<=1'b0;
2'b10: q<=1'b1;
2'b11: q<= 1’bx;
endcase
end
endmodule

VERILOG TEST BENCH:

module jkfftest1_v;
 reg j, k, clk, rst;
wire q;
jkff uut (.s(s),.r(r), .clk(clk), .rst(rst),.q(q));
always #5 clk = ~clk; always #5 rst = ~ rst;
initial begin
#100 $finish;
end
initial begin
rst = 0; s=1; r=0; clk=1;
#5 s=0; r=1; #5 s=0; r=1;
#5 s=1; r=1; #5 s=1; r=1;
#5s=1; r=1; #5 s=0; r=1;
#5s=0; r=0; #5 s=0; r=1;
#5 s=1; r=0; #5 s=1; r=0;
#5 s=0; r=0;
end
endmodule
5. SISO SHIFT REGISTER:

BLOCK DIAGRAM:

VERILOG SOURCE CODE:

Structral Modelling:
module siso(sin, clk, reset, sout);
input sin;input clk;
input reset;
output sout;
wire w1,w2,w3;
dff abc1 (.d(sin),.clk(clk ),.reset(reset),.q(w1));
dff abc2 (.d(w1),.clk(clk),.reset(reset),.q(w2));
dff abc3 (.d(w2),.clk(clk),.reset(reset),.q(w3));
dff abc4 (.d(w3),.clk(clk),.reset(reset),.q(sout));
endmodule
 Behavioral Modelling:
module siso1(sin, clk, reset, sout);
input sin, clk, reset;
output reg sout;
reg r1,r2,r3;
always @(posedge clk or posedge reset)
begin
if (!reset)
begin
sout <= 1'b0;
r1 <= 1'b0;
r2 <= 1'b0;
r3 <= 1'b0;
end
else
begin
r1 <= sin;
r2 <= r1;
r3 <= r2;
sout <= r3;
end
end
endmodule

VERILOG TEST BENCH:

module siso_tst_v;
reg sin;reg clk;
reg reset;
wire sout;
siso uut ( .sin(sin),.clk(clk),.reset(reset),.sout(sout));
initial beginsin = 0;
clk = 1;
reset = 1;
#20 reset = 0;
sin = 1'b1;
#10 sin = 1'b0;
#10 sin = 1'b1;
#10 sin = 1'b1;
#40;
end
always
#5 clk = ~ clk;
endmodule

6. PIPO SHIFT REGISTER:

BLOCK DIAGRAM:

VERILOG SOURCE CODE:

Structural Modelling:
module pipo_struc(pin, clk, reset, pout);
input [3:0] pin;
input clk, reset;
output reg [3:0] pout;
dff abc1 (.d(pin[0]),.clk(clk ),.reset(reset),.q(pout[0]));
dff abc2 (.d(pin[1]),.clk(clk),.reset(reset),.q(pout[1]));
dff abc3 (.d(pin[2]),.clk(clk),.reset(reset),.q(pout[2]));
dff abc4 (.d(pin[3]),.clk(clk),.reset(reset),.q(pout[3]));
endmodule

Behavioral Modelling:
module pipo(pin, clk, reset, pout);
input [3:0] pin;
input clk, reset;
output reg [3:0] pout;
always @ (posedge clk or posedge reset)
begin
if (reset)
pout <= 4'b0000;
else
pout <= pin;
end
endmodule

VERILOG TEST BENCH:

module pipo_tst_v;
reg [3:0] pin;
 reg clk;
reg reset;
wire [3:0] pout;
pipo uut ( .pin(pin),.clk(clk),.reset(reset),.pout(pout));
initial begin pin = 4'b0000;
clk = 1;
reset = 1;
#100 reset = 0;
pin = 4'b1010;
#100 pin = 4'b0110;
End
Always
#50 clk = ~ clk;
endmodule

7. 4-Bit Up/Down-Counter
BLOCK DIAGRAM:

VERILOG SOURCE CODE:

Structural Modelling:
module updowncounter_struc (q, reset, s, clk);
input [0:3]s;
input clk, reset;
output [0:3]q;
wire w,j1,j2,j3;
and(j1,w,q[0]);
and(j2,j1,q[1]);
and(j3,j2,q[2]);
or(s[1],j1,~j1);
or(s[2],j2,~j2);
or(s[3],j3,~j3);
jkff abc1 (s[0],s[0], clk, reset, q[0]);
jkff abc2 (s[1],s[1], clk, reset, q[1]);
jkff abc3 (s[2], s[2], clk, reset, q[2]);
jkff abc4 (s[3], s[3], clk, reset, q[3]);
endmodule
Behavioral Modelling:
module updowncount(q, reset, s, clk );
output reg [3:0]q;
input reset, clk
input [0:3]s;
always@(posedge clk)
begin
if(reset==1)
q<=0;
else
case(s)
0:q<=q+1;
1:q<=q-1;
endcase
end
endmodule

VERILOG TEST BENCH:

module updowncounttest_v;
reg reset;
reg s;
reg clk;
wire [3:0] q;
updowncount uut (.q(q),.reset(reset),.s(s),.clk(clk));
always
#5 clk= ~clk;
initial begin
#400 $finish;
end
initial begin
reset=1;clk=1;s=0;
#10 reset=0;
#150 reset=1;
#20 reset=0; s=1;
end
endmodule

Synchronous Sequential Circuits

We considered combinational logic circuits in which outputs are determined fully by the present
values of inputs. We also discussed how simple storage elements can be implemented in the form
of flip-flops. The output of a flip-flop depends on the state of the flip-flop rather than the value
of its inputs at any given time; the inputs cause changes in the state.
 In this chapter we deal with a general class of circuits in which the outputs depend on the
past behavior of the circuit, as well as on the present values of inputs. They are called sequential
circuits.
In most cases a clock signal is used to control the operation of a sequential circuit; such a
circuit is called a synchronous sequential circuit. The alternative, in which no clock signal is
used, is called an asynchronous sequential circuit.
Synchronous circuits are easier to design and are used in a vast majority of practical
applications; they are the topic of this chapter. Synchronous sequential circuits are realized using
combinational logic and one or more flip-flops.
The general structure of such a circuit is shown in Figure 1. The circuit has a set of
primary inputs, W, and produces a set of outputs, Z. The stored values in the flip-flops are
referred to as the state, Q, of the circuit.

Figure 1: The general form of a sequential circuit.

Under control of the clock signal, the flip-flops change their state as determined by the
combinational logic that feeds the inputs of these flip-flops. Thus the circuit moves from one
state to another. To ensure that only one transition from one state to another takes place during
one clock cycle, the flip-flops have to be of the edge-triggered type. They can be triggered either
by the positive (0 to 1 transition) or by the negative (1 to 0 transition) edge of the clock.
We will use the term active clock edge to refer to the clock edge that causes the change in
state. The combinational logic that provides the input signals to the flip-flops has two sources:
the primary inputs, W, and the present (current) state of the flip-flops, Q. Thus changes in state
depend on both the present state and the values of the primary inputs.
Figure 1 indicates that the outputs of the sequential circuit are generated by another
combinational circuit, such that the outputs are a function of the present state of the flip-flops
and of the primary inputs. Although the outputs always depend on the present state, they do not
necessarily have to depend directly on the primary inputs. Thus the connection shown in blue in
the figure may or may not exist. To distinguish between these two possibilities, it is customary to
say that sequential circuits whose outputs depend only on the state of the circuit are of Moore
type, while those whose outputs depend on both the state and the primary inputs are of Mealy
type. These names are in honor of Edward Moore and George Mealy, who investigated the
behavior of such circuits in the 1950s.
Sequential circuits are also called finite state machines (FSMs), which is a more formal
name that is often found in technical literature. The name derives from the fact that the
functional behavior of these circuits can be represented using a finite number of states. In this
chapter we will often use the term finite state machine, or simply machine, when referring to
sequential circuits.
 Basic Design Steps:
The steps involved in designing a synchronous sequential circuit as follows:
1. Obtain the specification of the desired circuit.
2. Derive the states for the machine by first selecting a starting state. Then, given the
specification of the circuit, consider all valuations of the inputs to the circuit and create new
states as needed for the machine to respond to these inputs. To keep track of the states as they are
visited, create a state diagram. When completed, the state diagram shows all states in the
machine and gives the conditions under which the circuit moves from one state to another.
3. Create a state table from the state diagram. Alternatively, it may be convenient to directly
create the state table in step 2, rather than first creating a state diagram.
4. In our sequential circuit example, there were only three states; hence it was a simple matter to
create the state table that does not contain more states than necessary. However, in practice it is
common to deal with circuits that have a large number of states. In such cases it is unlikely that
the first attempt at deriving a state table will produce optimal results, so that we may have more
states than is really necessary. This can be corrected by a procedure that minimizes the number
of states. We will discuss the process of state minimization.

5. Decide on the number of state variables needed to represent all states

and perform the state assignment. There are many different state
assignments possible for a given sequential circuit. Some assignments
may be better than others.

6. Choose the type of flip-flops to be used in the circuit. Derive the next-
state logic expressions to control the inputs to all flip-flops and then derive
logic expressions for the outputs of the circuit.
7. Implement the circuit as indicated by the logic expressions.

We introduced the steps used in the design of sequential circuits by using an example of a simple
controller for a vehicle. In this case the value of w reflected the speed of the vehicle. But, we
could consider this example in a more general sense, in that the value of w in each clock cycle
provides a sequence of symbols over time, where each symbol has the value 0 or 1. Our circuit
can detect sequences of symbols that consist of consecutive 1s, and indicate this by generating z
= 1 following each occurrence of two consecutive 1s.
Because the circuit detects a specific sequence of symbols; we can say that it acts as a
sequence detector.
1. Sequence detector for detecting the sequence 11 using Moore model

Figure 2: Sequences of input and output signals.

1. State Diagram
The first step in designing a finite state machine is to determine how many states are needed and
which transitions are possible from one state to another. The conceptually simplest method is to
use a pictorial representation in the form of a state diagram, which is a graph that depicts states
of the circuit as nodes (circles) and transitions between states as directed arcs.
The state diagram in Figure 3 defines the behavior that corresponds to our specification.
States A, B, and C appear as nodes in the diagram. Node A represents the starting state, and it is
also the state that the circuit will reach after an input w = 0 is applied. In this state the output z
should be 0, which is indicated as A/z = 0 in the node. The circuit should remain in state A as
long as w = 0, which is indicated by an arc with a label w = 0 that originates and terminates at
this node. The first occurrence of w = 1 (following the condition w = 0) is recorded by moving
from state A to state B. This transition is indicated on the graph by an arc originating at A and
terminating at B. The label w = 1 on this arc denotes the input value that causes the transition.
In state B the output remains at 0, which is indicated as B/z = 0 in the node. When the
circuit is in state B, it will change to state C if w is still equal to 1 at the next active clock edge. In
state C the output z becomes equal to 1. If w stays at 1 during subsequent clock cycles, the circuit
will remain in state C maintaining z = 1. However, if w becomes 0 when the circuit is either in
state B or in state C, the next active clock edge will cause a transition to state A to take place.
The Reset input causes a change to the starting state regardless of what state the circuit
happens to be in.

Figure 3 State diagram of a simple sequential circuit.

2. State Table

Although the state diagram provides a description of the behavior of a sequential circuit that is
easy to understand, to proceed with the implementation of the circuit it is convenient to translate
the information contained in the state diagram into a tabular form. Figure 4 shows the state table
for our sequential circuit. The table indicates all transitions from each present state to the next
state for different values of the input signal.
 Figure 4: State table corresponding to Figure 3.

3. State Assignment

The state table in Figure 4 defines the three states in terms of letters A, B, and C. When
implemented in a logic circuit, each state is represented by a particular valuation (combination of
values) of state variables. Each state variable may be implemented in the form of a flip-flop.
Since three states have to be realized, it is sufficient to use two state variables. Let these
variables be y1 and y2.
Now we can adapt the general block diagram in Figure 1 to produce the desired truth table, we
assign a specific valuation of variables y1 and y2 to each state. One possible assignment is given
in Figure 6, where the states A, B, and C are represented by y2y1 = 00, 01, and 10, respectively.
The fourth valuation, y2y1 = 11, is not needed in this case. The type of table given in Figure 6 is
usually called a state-assigned table.

Figure 6 State-assigned table corresponding to Figure 4.

4. Choice of Flip-Flops and Derivation of Next-State and Output Expressions

From the state-assigned table in Figure 6, we can derive the logic expressions for the next-state
and output functions. But first we have to decide on the type of flip-flops that will be used in the
circuit. The most straightforward choice is to use D-type flip-flops,
Figure 7 Derivation of logic expressions for the table in Figure 6.
 Figure 8 Final implementation of the sequential circuit.

5. Timing Diagram
To understand fully the operation of the circuit in Figure 8, let us consider its timing diagram
presented in Figure 9.

Figure 9 Timing diagram for the circuit in Figure 8.

2. Sequence detector for detecting the sequence 11 using Mealy model
Mealy-type machines in which the output values are generated based on both the state of the
circuit and the present values of its inputs. This provides additional flexibility in the design of
sequential circuits. We will introduce the Mealy-type machines, using a slightly altered version
of a previous example 1.

Figure 10: Sequences of input and output signals.

State diagram

Figure 11: State diagram of an FSM that realizes the task in Figure 10
State table

Figure 12: State table for the FSM in Figure 11.

State assigned table

Figure 13: State-assigned table for the FSM in Figure 12.

Assuming that y is realized as a D-type flip-flop, the required next-state and output expressions
are Y = D = w
z = wy
 Figure 14: Implementation of the FSM in Figure 13.

3. To swap the contents of two registers

A computer system usually contains a number of registers that hold data during various
operations. Sometimes it is necessary to swap the contents of two registers. Typically, this is
done by using a temporary location, which is usually a third register.
For example, suppose that we want to swap the contents of registers R1 and R2. We can
achieve this by first transferring the contents of R2 into the third register, say R3. Next, we
transfer the contents of R1 into R2. Finally, we transfer the contents of R3 into R1. Registers in a
computer system are connected via an interconnection network, as shown in Figure 10.
In addition to the wires that connect to the network, each register has two control signals.
The Rkout signal causes the contents of register Rk to be placed into the interconnection network.
The Rkin signal causes the data from the network to be loaded into Rk. The Rkout and Rkin
signals are generated by a control circuit, which is a finite state machine.
For our example, we will design a control circuit that swaps the contents of R1 and R2, in
response to an input w = 1. Therefore, the inputs to the control circuit will be w and Clock. The
outputs will be R1out , R1in, R2out , R2in, R3out , R3in, and Done which indicates the
completion of the required transfers.
The desired swapping operation will be performed as follows. The contents of R2 are first
loaded into R3, using the control signals R2out = 1 and R3in = 1. Then the contents of R1 are
transferred into R2, using R1out = 1 and R2in = 1. Finally, the contents of R3 (which are the
previous contents of R2) are transferred into R1, using R3out = 1 and R1in = 1. Since this step
completes the required swap, we will set the signal Done = 1. Assume that the swapping is
performed in response to a pulse on the input w, which has a duration of one clock cycle.
 Figure 11 gives a state diagram for a sequential circuit that generates the output control
signals in the required sequence. Note that to keep the diagram simple, we have indicated the
output signals only when they are equal to 1. In all other cases the output signals are equal to 0.

Figure 15: System for Example 3.

Figure 16: State diagram for Example 3.

 Figure 17: State table for Example 3.

Figure 18: State-assigned table corresponding to Figure 17.

Figure 19 Derivation of next-state expressions for Figure 18.

 Figure 20: Final implementation of the sequential circuit for Example 3.

4. One-Hot Encoding
In previous examples we used the minimum number of flip-flops to represent the states of the
FSM. Another interesting possibility is to use as many state variables as there are states.
In this method, for each state all but one of the state variables are equal to 0. The variable
whose value is 1 is deemed to be “hot.” The approach is known as the one-hot encoding method.
Consider the example 1 i.e., Sequence detector for detecting the sequence 11 using Moore model
of figure 4 and apply one-hot encoding method as follows.

Figure 21: shows how one-hot state assignment can be applied to the sequential circuit
of Figure 4.

Because there are three states, it is necessary to use three state variables. The chosen assignment
is to represent the states A, B, and C using the valuations y3y2y1 = 001, 010, and 100,
 respectively. The remaining five valuations of the state variables are not used. They can be
treated as don’t cares in the derivation of the next-state and output expressions.
Using this assignment, the resulting expressions are

Note that none of the next-state variables depends on the present-state variable y2. This suggests
that the second flip-flop and the expression Y2 = wy1 are not needed. (CAD tools detect and
eliminate such redundancies!) But even then, the derived expressions are not simpler than those
obtained using the state assignment in Figure 16. Although in this case the one-hot assignment is
not advantageous, there are many cases where this approach is attractive.

5. Serial Adder
Several schemes that can be used to add two n-bit numbers in parallel, ranging from carry-ripple
to carry-lookahead adders. In these schemes the speed of the adder unit is an important design
parameter. Fast adders are more complex and thus more expensive. If speed is not of great
importance, then a cost-effective option is to use a serial adder, in which bits are added a pair at
a time.
Mealy-Type FSM for Serial Adder

Figure 22: Block diagram for the serial adder.

Figure 23: State diagram for the serial adder FSM.

 Figure 24: State table for the serial adder FSM.

Figure 25: State-assigned table for Figure 24.

This assignment leads to the following next-state and output equations

Comparing these expressions with those for the full-adder

Figure 26 Circuit for the adder FSM in Figure 25.

B. Moore-Type FSM for Serial Adder

Figure 27: State diagram for the Moore-type serial adder FSM.
 Figure 28: State table for the Moore-type serial adder FSM.

Figure 29: State-assigned table for Figure 28.

The next-state and output expressions are

Figure 30: Circuit for the Moore-type serial adder FSM.

6. State Minimization
When a designer has to design a more complex FSM, it is likely that the initial attempt will result
in a machine that has more states than is actually required. Minimizing the number of states is of
interest because fewer flips-flops may be needed to represent the states and the complexity of the
combinational circuit needed in the FSM may be reduced. If the number of states in an FSM can
be reduced, then some states in the original design must be equivalent to other states in their
contribution to the overall behavior of the FSM. We can express this more formally in the
following definition.
Definition 1 – Two states Si and Sj are said to be equivalent if and only if for every possible
input sequence, the same output sequence will be produced regardless of whether Si or Sj is the
initial state.
Partitioning Minimization Procedure:
Suppose that a state machine has a single input w. Then if the input signal w = 0 is applied to this
machine in state Si and the result is that the machine moves to state Su, we will say that Su is a 0-
successor of Si. Similarly, if w = 1 is applied in the state Si and it causes the machine to move to
state Sv, we will say that Sv is a 1-successor of Si.
In general, we will refer to the successors of Si as its k-successors. When the FSM has
only one input, k can be either 0 or 1. But if there are multiple inputs to the FSM, then k
represents the set of all possible combinations (valuations) of the inputs.

From Definition 6.1 it follows that if the states Si and Sj are equivalent, then their corresponding
k-successors (for all k) are also equivalent. Using this fact, we can formulate a minimization
procedure that involves considering the states of the machine as a set and then breaking the set
into partitions that comprise subsets that are definitely not equivalent.
Definition 2 – A partition consists of one or more blocks, where each block comprises a subset
of states that may be equivalent, but the states in a given block are definitely not equivalent to
the states in other blocks.
Example 1: Figure 31 shows a state table for a particular FSM. In an attempt to minimize the
number of states, let us apply the partitioning procedure.

Figure 31: State table for Example 6.6.

The initial partition contains all states in a single block
P1 = (ABCDEFG)
 The next partition separates the states that have different outputs (note that this FSM is of Moore
type), which means that the states A, B, and D must be different from the states C, E, F, and G.
Thus the new partition has two blocks
P2 = (ABD) (CEFG)
Now we must consider all 0- and 1-successors of the states in each block. For the block (ABD),
the 0-successors are (BDB), respectively. Since all of these successor states are in the same block
in P2, we should still assume that the states A, B, and D may be equivalent. The 1-successors for
these states are (CFG). Since these successors are also in the same block in P2, we conclude that
(ABD) should remain in one block of P3.
Next consider the block (CEFG). Its 0-successors are (FFEF), respectively. They are in
the same block in P2. The 1-successors are (ECDG). Since these states are not in the same block
in P2, it means that at least one of the states in the block (CEFG) is not equivalent to the others.
In particular, the state F must be different from the states C, E, and G because its 1-successor is
D, which is in a different block than C, E, and G. Hence
P3 = (ABD) (CEG) (F)
Repeating the process yields the following. The 0-successors of (ABD) are (BDB), which are in
the same block of P3. The 1-successors are (CFG), which are not in the same block. Since F is in
a different block than C and G, it follows that the state B cannot be equivalent to states A and D.
The 0- and 1-successors of (CEG) are (FFF) and (ECG), respectively. Both of these subsets are
accommodated in the blocks of P3. Therefore
P4 = (AD) (B) (CEG) (F)
If we follow the same approach to check the 0- and 1-successors of the blocks (AD) and (CEG),
we find that
P5 = (AD)(B)(CEG)(F)
Since P5 = P4 and no new blocks are generated, it follows that states in each block are
equivalent.

Figure 32: Minimized state table for Example 31.

Example 2: As another example of minimization, we will consider the design of a sequential

circuit that could control a vending machine. Suppose that a coin-operated vending machine
dispenses candy under the following conditions:
• The machine accepts nickels and dimes.
• It takes 15 cents for a piece of candy to be released from the machine.
 If 20 cents is deposited, the machine will not return the change, but it will credit the buyer with 5
cents and wait for the buyer to make a second purchase.
Figure 33: Signals for the vending machine.

Figure 34: State diagram for Example 2.

 Figure 35: State table for Example 34.

Figure 36: Minimized state table for Example 35.

Using the minimization procedure, we obtain the following partitions
P1 = (S1, S2, S3, S4, S5, S6, S7, S8, S9)
P2 = (S1, S2, S3, S6) (S4, S5, S7, S8, S9)
P3 = (S1) (S3) (S2, S6) (S4, S5, S7, S8, S9)
P4 = (S1) (S3) (S2, S6) (S4, S7, S8) (S5, S9)
P5 = (S1) (S3) (S2, S6) (S4, S7, S8) (S5, S9)

Figure 37: Minimized state diagram for Example 2.

 Figure 38 Mealy-type FSM for Example 2.

7. Incompletely Specified FSMs

The partitioning scheme for minimization of states works well when all entries in the state table
are specified. Such is the case for the FSM defined in Figure 6.51. FSMs of this type are said to
be completely specified. If one or more entries in the state table are not specified, corresponding
to don’t-care conditions, then the FSM is said to be incompletely specified.
An example of such an FSM is given in Figure 6.55. As seen in Example 2, the
partitioning scheme works well for this FSM also. But in general, the partitioning scheme is less
useful when incompletely specified FSMs are involved, as illustrated by Example 6.8.

Figure 6.59 Incompletely specified state table for Example 6.8.

The partitioning minimization procedure can be applied to Mealy-type FSMs in the same way as
for Moore-type FSMs illustrated in Examples 6.6 and 6.7. Two states are considered equivalent,
and are thus placed in the same block of a partition, if their outputs are equal for all
corresponding input valuations. To perform the partitioning process, we can assume that the
unspecified outputs have a specific value. Not knowing whether these values should be 0 or 1, let
us first assume that both unspecified outputs have a value of 0.
Then the first two partitions are
P1 = (ABCDEFG)
P2 = (ABDG)(CEF)
 Note that the states A, B, D, and G are in the same block because their outputs are equal to 0 for
both w = 0 and w = 1. Also, the state’s C, E, and F are in one block because they have the same
output behavior; they all generate z = 0 if w = 0, and z = 1 if w = 1. Continuing the partitioning
procedure gives the remaining partitions
P3 = (AB)(D)(G)(CE)(F)
P4 = (A)(B)(D)(G)(CE)(F)
P5 = P4
The result is an FSM that is specified by six states.
Next consider the alternative of assuming that both unspecified outputs in Figure 6.59
have a value of 1. This would lead to the partitions
P1 = (ABCDEFG)
P2 = (AD)(BCEFG)
P3 = (AD)(B)(CEFG)
P4 = (AD)(B)(CEG)(F)
P5 = P4
This solution involves four states. Evidently, the choice of values assigned to unspecified
outputs is of considerable importance.
Finally, it is important to mention that reducing the number of states in a given FSM will not
necessarily lead to a simpler implementation.

8. Design of a Modulo-8 Counter Using the Sequential Circuit Approach

In this section we discuss the design of a counter circuit as a finite state machine. We already
know that counters can be realized as cascaded stages of flip-flops and some gating logic, where
each stage divides the number of incoming pulses by two. To keep our example simple, we
choose a counter of small size but also show how the design can be extended to larger sizes.
The specification for the counter is
• The counting sequence is 0, 1, 2, . . . , 6, 7, 0, 1, . . .
• There exists an input signal w. The value of this signal is considered during each clock cycle. If
w = 0, the present count remains the same; if w = 1, the count is incremented.
The counter can be designed as a synchronous sequential circuit using the design techniques
introduced in the previous sections.

State DiagramandStateTableforaModulo-8Counter

Figure 6.60 gives a state diagram for the desired counter. There is a state associated with each
count. In the diagram state A corresponds to count 0, state B to count 1, and so on. We show the
transitions between the states needed to implement the counting sequence. Note that the output
signals are specified as depending only on the state of the counter at a given time, which is the
Moore model of sequential circuits.
The state diagram may be represented in the state-table form as shown in Figure 6.61
 Figure 6.60 State diagram for the counter.

Figure 6.61 State table for the counter.

State Assignment

Figure 6.62 State-assigned table for the counter.

Implementation Using D-Type Flip-Flops
When using D-type flip-flops to realize the finite state machine, each next-state function, Yi , is
connected to the D input of the flip-flop that implements the state variable yi . The next-state
functions are derived from the information in Figure 6.62. Using Karnaugh maps in Figure 6.63,
we obtain the following implementation

However, we can rewrite these expressions as follows

Figure 6.63 Karnaugh maps for D flip-flops for the counter.

 Figure 6.64 Circuit diagram for the counter implemented with D flip-flops.

9. Analysis of Synchronous Sequential Circuits

In addition to knowing how to design a synchronous sequential circuit, the designer has to be
able to analyze the behavior of an existing circuit. The analysis task is much simpler than the
synthesis task. In this section we will show how analysis may be performed. To analyze a circuit,
we simply reverse the steps of the synthesis process. The outputs of the flip-flops represent the
present-state variables. Their inputs determine the next state that the circuit will enter. From this
information we can construct the state-assigned table for the circuit. This table leads to a state
table and the corresponding state diagram by giving a name to each state. The type of flip-flops
used in the circuit is a factor, as we will see in the examples that follow.
Example 1: Figure 6.75 gives an FSM that has two D flip-flops. Let y1 and y2 be the present-
state variables and Y1 and Y2 the next-state variables. The next-state and output expressions are

Figure 6.75 Circuit for Example 6.9.

Figure 6.76 Tables for the circuit in Figure 6.75.