3.

4 Finite�State�Machines 117

Of course, asynchronous circuits are occasionally necessary when com-
municating between systems with different clocks or when receiving inputs
at arbitrary times, just as analog circuits are necessary when communicat-
ing  with  the  real  world  of  continuous  voltages.  Furthermore,  research  in
asynchronous  circuits  continues  to  generate  interesting  insights,  some  of
which can improve synchronous circuits too.
Moore and Mealy machines
3 . 4 FINITE�STATE�MACHINES are named after their promot-
Synchronous  sequential  circuits  can  be  drawn  in  the  forms  shown  in ers, researchers who developed
Figure 3.22. These forms are called finite state machines (FSMs). They get automata theory, the mathe-
their name because a circuit with k registers can be in one of a finite num- matical underpinnings of state
machines, at Bell Labs.
ber (2k) of unique states. An FSM has M inputs, N outputs, and k bits of
Edward F. Moore
state. It also receives a clock and, optionally, a reset signal. An FSM con-
(1925–2003), not to be
sists  of  two  blocks  of  combinational  logic,  next  state  logic and  output confused with Intel founder
logic,  and  a  register  that  stores  the  state.  On  each  clock  edge,  the  FSM Gordon Moore, published his
advances to the next state, which was computed based on the current state seminal article, Gedanken-
and inputs. There are two general classes of finite state machines, charac- experiments on Sequential
terized by their functional specifications. In Moore machines, the outputs Machines in 1956. He subse-
depend only on the current state of the machine. In Mealy machines, the quently became a professor of
outputs  depend  on  both  the  current  state  and  the  current  inputs.  Finite mathematics and computer
state machines provide a systematic way to design synchronous sequential science at the University of
circuits given a functional specification. This method will be explained in Wisconsin.
George H. Mealy published
the remainder of this section, starting with an example.
A Method of Synthesizing
Sequential Circuits in 1955.
3 . 4 .1 FSM�Design�Example He subsequently wrote the
To  illustrate  the  design  of  FSMs,  consider  the  problem  of  inventing  a first Bell Labs operating
controller  for  a  traffic  light  at  a  busy  intersection  on  campus. system for the IBM 704
computer. He later joined
Engineering students are moseying between their dorms and the labs on
Harvard University.
Academic  Ave.  They  are  busy  reading  about  FSMs  in  their  favorite

CLK
M next k next
k N
inputs state state output
state
logic
outputs
logic

(a) Figure�3.22 Finite�state

machines:�(a) Moore�machine,
CLK (b)�Mealy�machine

M next k next
k N
inputs state state output
state
logic
outputs
logic

(b)
118 CHAPTER�THREE Sequential�Logic�Design

textbook  and  aren’t  looking  where  they  are  going.  Football  players  are
hustling  between  the  athletic  fields  and  the  dining  hall  on  Bravado
Boulevard.  They  are  tossing  the  ball  back  and  forth  and  aren’t  looking
where  they  are  going  either.  Several  serious  injuries  have  already
occurred at the intersection of these two roads, and the Dean of Students
asks Ben Bitdiddle to install a traffic light before there are fatalities.
Ben decides to solve the problem with an FSM. He installs two traffic
sensors,  TA and  TB,  on  Academic  Ave.  and  Bravado  Blvd.,  respectively.
Each sensor indicates TRUE if students are present and FALSE if the street
is empty. He also installs two traffic lights, LA and LB, to control traffic.
Each  light  receives  digital  inputs  specifying  whether  it  should  be  green,
yellow, or red. Hence, his FSM has two inputs, TA and TB, and two out-
puts,  LA and  LB.  The  intersection  with  lights  and  sensors  is  shown  in
Figure 3.23. Ben provides a clock with a 5-second period. On each clock
tick  (rising  edge),  the  lights  may  change  based  on  the  traffic  sensors.  He
also provides a reset button so that Physical Plant technicians can put the
controller in a known initial state when they turn it on. Figure 3.24 shows
a black box view of the state machine.
Ben’s  next  step  is  to  sketch  the  state  transition  diagram,  shown  in
Figure 3.25, to indicate all the possible states of the system and the transi-
tions  between  these  states.  When  the  system  is  reset,  the  lights  are  green
on  Academic  Ave.  and  red  on  Bravado  Blvd.  Every  5  seconds,  the  con-
troller examines the traffic pattern and decides what to do next. As long
Bravado

Dining
Hall
LB

LA TB
LA
Figure�3.23 Campus�map
Academic TA TA Ave.

Labs TB LB Dorms
Blvd.

Athletic
Fields

CLK

Figure�3.24 Black�box�view�of TA Traffic LA

Light
finite�state�machine
TB Controller LB

Reset
 3.4 Finite�State�Machines 119

TA
Reset
S0 TA S1
LA: green LA: yellow
LB: red LB: red 

Figure�3.25 State�transition
diagram

S3 S2
LA: red LA: red
LB: yellow LB: green
TB
TB

as  traffic  is  present  on  Academic  Ave.,  the  lights  do  not  change.  When
there  is  no  longer  traffic  on  Academic  Ave.,  the  light  on  Academic  Ave.
becomes yellow for 5 seconds before it turns red and Bravado Blvd.’s light
turns  green.  Similarly,  the  Bravado  Blvd.  light  remains  green  as  long  as
traffic is present on the boulevard, then turns yellow and eventually red.
In  a  state  transition  diagram,  circles  represent  states  and  arcs  repre-
sent  transitions  between  states.  The  transitions  take  place  on  the  rising
edge  of  the  clock;  we  do  not  bother  to  show  the  clock  on  the  diagram,
because it is always present in a synchronous sequential circuit. Moreover,
the clock simply controls when the transitions should occur, whereas the
diagram indicates which transitions occur. The arc labeled Reset pointing
from outer space into state S0 indicates that the system should enter that
state upon reset, regardless of what previous state it was in. If a state has
multiple  arcs  leaving  it,  the  arcs  are  labeled  to  show  what  input  triggers
each transition. For example, when in state S0, the system will remain in
that state if TA is TRUE and move to S1 if TA is FALSE. If a state has a
single arc leaving it, that transition always occurs regardless of the inputs.
For  example,  when  in  state  S1,  the  system  will  always  move  to  S2.  The
value that the outputs have while in a particular state are indicated in the
state. For example, while in state S2, LA is red and LB is green.
Ben  rewrites  the  state  transition  diagram  as  a  state  transition  table
(Table  3.1),  which  indicates,  for  each  state  and  input,  what  the  next
state,  S�,  should  be.  Note  that  the  table  uses  don’t  care  symbols  (X)
whenever the next state does not depend on a particular input. Also note
that Reset is omitted from the table. Instead, we use resettable flip-flops
that always go to state S0 on reset, independent of the inputs.
The state transition diagram is abstract in that it uses states labeled
{S0, S1, S2, S3} and outputs labeled {red, yellow, green}. To build a real
circuit,  the  states  and  outputs  must  be  assigned  binary  encodings. Ben
chooses the simple encodings given in Tables 3.2 and 3.3. Each state and
each output is encoded with two bits: S1:0, LA1:0, and LB1:0.
120 CHAPTER�THREE Sequential�Logic�Design

Table�3.1 State�transition�table Table�3.2 State�encoding

Current  Inputs Next State State Encoding S1:0

State S TA TB S�
S0 00
S0 0 X S1
S1 01
S0 1 X S0
S2 10
S1 X X S2
S3 11
S2 X 0 S3

S2 X 1 S2

S3 X X S0

Table�3.3 Output�encoding Ben updates the state transition table to use these binary encodings, as

shown in Table 3.4. The revised state transition table is a truth table speci-
Output Encoding L1:0
fying the next state logic. It defines next state, S�, as a function of the cur-
green 00 rent  state,  S, and  the  inputs.  The  revised  output  table  is  a  truth  table
specifying the output logic. It defines the outputs, LA and LB, as functions
yellow 01
of the current state, S.
red 10 From this table, it is straightforward to read off the Boolean equa-
tions for the next state in sum-of-products form.
 S�1 � S1S0 � S1S0TB � S1S0 TB
(3.1)
 S�0 �S1S0TA � S1S0TB 
The  equations  can  be  simplified  using  Karnaugh  maps,  but  often
doing it by inspection is easier. For example, the TB and  TB terms in the
S�1 equation  are  clearly  redundant.  Thus  S�1 reduces  to  an  XOR  opera-
tion. Equation 3.2 gives the next state equations.

Table�3.4 State�transition�table�with�binary�encodings

Current State Inputs Next State

S1 S0 TA TB S�1 S�0
0 0 0 X 0 1
0 0 1 X 0 0

0 1 X X 1 0
1 0 X 0 1 1

1 0 X 1 1 0
1 1 X X 0 0
 3.4 Finite�State�Machines 121

Table�3.5 Output�table

Current State Outputs
S1 S0 LA1 LA0 LB1 LB0
0 0 0 0 1 0

0 1 0 1 1 0

1 0 1 0 0 0
1 1 1 0 0 1

 S�1�S1 ⊕ S0
(3.2)
 S�0 � S1S0TA �S1S0TB 
Similarly, Ben writes an output table (Table 3.5) indicating, for each
state,  what  the  output  should  be  in  that  state.  Again,  it  is  straightfor-
ward to read off and simplify the Boolean equations for the outputs. For
example, observe that LA1 is TRUE only on the rows where S1 is TRUE.
 LA1� S  1
 LA0�S1 S0
(3.3)
 LB1�S1
 LB0� S 1 S0
Finally, Ben sketches his Moore FSM in the form of Figure 3.22(a).
First,  he  draws  the  2-bit  state  register,  as  shown  in  Figure  3.26(a).  On
each clock edge, the state register copies the next state, S�1:0, to become
the state, S1:0. The state register receives a synchronous or asynchronous
reset to initialize the FSM at startup. Then, he draws the next state logic,
based on Equation 3.2, which computes the next state, based on the cur-
rent state and inputs, as shown in Figure 3.26(b). Finally, he draws the
output logic, based on Equation 3.3, which computes the outputs based
on the current state, as shown in Figure 3.26(c).
Figure 3.27 shows a timing diagram illustrating the traffic light con-
troller  going  through  a  sequence  of  states.  The  diagram  shows  CLK,
Reset, the inputs TA and TB, next state S�, state S, and outputs LA and LB.
Arrows indicate causality; for example, changing the state causes the out-
puts to change, and changing the inputs causes the next state to change.
Dashed lines indicate the rising edge of CLK when the state changes.
The clock has a 5-second period, so the traffic lights change at most
once every 5 seconds. When the finite state machine is first turned on, its
state is unknown, as indicated by the question marks. Therefore, the sys-
tem should be reset to put it into a known state. In this timing diagram,
122 CHAPTER�THREE Sequential�Logic�Design

CLK
S'1 S1
CLK
S'1 S1
TA S'0 S0
r
S'0 S0 TB Reset
r S1 S0
Reset
state register inputs next state logic state register
(a) (b)

CLK LA1
This schematic uses some S'1 S1
AND gates with bubbles on LA0
the inputs. They might be
constructed with AND gates TA S'0 S0
LB1
and input inverters, with r
NOR gates and inverters for TB Reset
the non-bubbled inputs, or S1 S0 LB0
with some other combination
of gates. The best choice
inputs next state logic state register output outputs
depends on the particular logic
(c)
implementation technology.
Figure�3.26 State�machine�circuit�for�traffic�light�controller

Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9 Cycle 10

CLK

Reset

TA

TB

S'1:0 ?? S0 (00) S1 (01) S2 (10) S3 (11) S0 (00) S1 (01)

S1:0 ?? S0 (00) S1 (01) S2 (10) S3 (11) S0 (00)

LA1:0 ?? Green (00) Yellow (01) Red (10) Green (00)

LB1:0 ?? Red (10) Green (00) Yellow (01) Red (10)

0 5 10 15 20 25 30 35 40 45 t (sec)
Figure�3.27 Timing�diagram�for�traffic�light�controller
 3.4 Finite�State�Machines 123

S immediately resets to S0, indicating that asynchronously resettable flip- Despite Ben’s best efforts, stu-
flops are being used. In state S0, light LA is green and light LB is red. dents don’t pay attention to
In  this  example,  traffic  arrives  immediately  on  Academic  Ave. traffic lights and collisions
Therefore,  the  controller  remains  in  state  S0,  keeping  LA green  even continue to occur. The Dean
though traffic arrives on Bravado Blvd. and starts waiting. After 15 sec- of Students next asks him to
onds, the traffic on Academic Ave. has all passed through and TA falls. design a catapult to throw
At the following clock edge, the controller moves to state S1, turning LA engineering students directly
yellow. In another 5 seconds, the controller proceeds to state S2 in which from their dorm roofs
LA turns red and LB turns green. The controller waits in state S2 until all through the open windows
of the lab, bypassing the
the traffic on Bravado Blvd. has passed through. It then proceeds to state
troublesome intersection all
S3,  turning  LB yellow.  5  seconds  later,  the  controller  enters  state  S0,
together. But that is the sub-
turning LB red and LA green. The process repeats. ject of another textbook.

3 . 4 . 2 State�Encodings
In the previous example, the state and output encodings were selected arbi-
trarily. A different choice would have resulted in a different circuit. A natu-
ral question is how to determine the encoding that produces the circuit with
the fewest logic gates or the shortest propagation delay. Unfortunately, there
is  no  simple  way  to  find  the  best  encoding  except  to  try  all  possibilities,
which is infeasible when the number of states is large. However, it is often
possible to choose a good encoding by inspection, so that related states or
outputs  share  bits.  Computer-aided  design  (CAD)  tools  are  also  good  at
searching the set of possible encodings and selecting a reasonable one.
One  important  decision  in  state  encoding  is  the  choice  between
binary  encoding  and  one-hot  encoding.  With  binary  encoding, as  was
used in the traffic light controller example, each state is represented as a
binary number. Because K binary numbers can be represented by log2K
bits, a system with K states only needs log2K bits of state.
In one-hot encoding, a separate bit of state is used for each state. It is
called  one-hot  because  only  one  bit  is  “hot”  or  TRUE  at  any  time.  For
example, a one-hot encoded FSM with three states would have state encod-
ings of 001, 010, and 100. Each bit of state is stored in a flip-flop, so one-
hot encoding requires more flip-flops than binary encoding. However, with
one-hot encoding, the next-state and output logic is often simpler, so fewer
gates are required. The best encoding choice depends on the specific FSM.

Example�3.6 FSM STATE ENCODING
A divide-by-N counter has one output and no inputs. The output Y is HIGH for
one clock cycle out of every N. In other words, the output divides the frequency
of the clock by N. The waveform and state transition diagram for a divide-by-3
counter is shown in Figure 3.28. Sketch circuit designs for such a counter using
binary and one-hot state encodings.
124 CHAPTER�THREE Sequential�Logic�Design

CLK

Y
(a)

Figure�3.28 Divide-by-3�counter Reset

(a)�waveform�and�(b)�state
transition�diagram S0 S1 S2
Y: 1 Y: 0 Y: 0

(b)

Table�3.6 Divide-by-3�counter Solution: Tables 3.6 and 3.7 show the abstract state transition and output tables

state�transition�table before encoding.

Current Next Table 3.8 compares binary and one-hot encodings for the three states.

State State
The binary encoding uses two bits of state. Using this encoding, the state transi-
S0 S1 tion  table  is  shown  in  Table  3.9.  Note  that  there  are  no  inputs;  the  next  state
depends only on the current state. The output table is left as an exercise to the
S1 S2
reader. The next-state and output equations are:
S2 S0
  S�1� S1 S0
(3.4)
  S�0 � S1S0

Y � S1S0 (3.5)
Table�3.7 Divide-by-3�counter
output�table The one-hot encoding uses three bits of state. The state transition table for this
encoding is shown in Table 3.10 and the output table is again left as an exercise
Current
to the reader. The next-state and output equations are as follows:
State Output
S0 1   S�2 � S  1
  S�1� S  0 (3.6)
S1 0
  S�0 � S2
S2 0
Y � S0 (3.7)
Figure 3.29 shows schematics for each of these designs. Note that the hardware
for  the  binary  encoded  design  could  be  optimized  to  share  the  same  gate  for
Y and S�0. Also observe that the one-hot encoding requires both settable (s) and
resettable  (r)  flip-flops  to  initialize  the  machine  to  S0  on  reset.  The  best  imple-
mentation  choice  depends  on  the  relative  cost  of  gates  and  flip-flops,  but  the
one-hot design is usually preferable for this specific example.

A  related  encoding  is  the  one-cold encoding,  in  which  K states  are
represented with K bits, exactly one of which is FALSE.
 3.4 Finite�State�Machines 125

Table�3.8 Binary�and�one-hot�encodings�for�divide-by-3�counter

State Binary Encoding One-Hot Encoding

S2 S1 S0 S1 S0
S0 0 0 1 0 1

S1 0 1 0 1 0

S2 1 0 0 0 0

Table�3.9 State�transition�table�with�binary
encoding

Current State Next State
S1 S0 S�1 S�0
0 0 0 1
0 1 1 0

1 0 0 0

Table� 3.10 State� transition� table� with� one-hot� encoding

Current State Next State
S2 S1 S0 S�2 S�1 S�0
0 0 1 0 1 0

0 1 0 1 0 0
1 0 0 0 0 1

CLK
S'1 S1
Y
S'0 S0
r
S1 S0 Reset
Figure�3.29 Divide-by-3�circuits
for�(a)�binary�and�(b)�one-hot
next state logic state register output logic output encodings
(a)

CLK
S1 S2 S0
Y
r r s
Reset

(b)
126 CHAPTER�THREE Sequential�Logic�Design

3 . 4 . 3 Moore�and�Mealy�Machines
So far, we have shown examples of Moore machines, in which the output
An easy way to remember the depends  only  on  the  state  of  the  system.  Hence,  in  state  transition  dia-
difference between the two
grams for Moore machines, the outputs are labeled in the circles. Recall
types of finite state machines
that Mealy machines are much like Moore machines, but the outputs can
is that a Moore machine typi-
cally has more states than a
depend  on  inputs  as  well  as  the  current  state.  Hence,  in  state  transition
Mealy machine for a given diagrams for Mealy machines, the outputs are labeled on the arcs instead
problem. of in the circles. The block of combinational logic that computes the out-
puts uses the current state and inputs, as was shown in Figure 3.22(b).

Example�3.7 MOORE VERSUS MEALY MACHINES
Alyssa  P.  Hacker  owns  a  pet  robotic  snail  with  an  FSM  brain.  The  snail  crawls
from left to right along a paper tape containing a sequence of 1’s and 0’s. On each
clock  cycle,  the  snail  crawls  to  the  next  bit.  The  snail  smiles  when  the  last  four
bits that it has crawled over are, from left to right, 1101. Design the FSM to com-
pute  when  the  snail  should  smile.  The  input  A is  the  bit  underneath  the  snail’s
antennae.  The  output  Y is  TRUE  when  the  snail  smiles.  Compare  Moore  and
Mealy state machine designs. Sketch a timing diagram for each machine showing
the input, states, and output as your snail crawls along the sequence 111011010.

Solution: The  Moore  machine  requires  five  states,  as  shown  in  Figure  3.30(a).
Convince yourself that the state transition diagram is correct. In particular, why
is there an arc from S4 to S2 when the input is 1?
In comparison, the Mealy machine requires only four states, as shown in Figure
3.30(b). Each arc is labeled as A/Y. A is the value of the input that causes that
transition, and Y is the corresponding output.

Tables  3.11  and  3.12  show  the  state  transition  and  output  tables  for  the  Moore
machine. The Moore machine requires at least three bits of state. Consider using a
binary  state  encoding:  S0 � 000,  S1 � 001,  S2 � 010,  S3 � 011,  and  S4 � 100.
Tables  3.13  and  3.14  rewrite  the  state  transition  and  output  tables  with  these
encodings (These four tables follow on page 128).
From  these  tables,  we  find  the  next  state  and  output  equations  by  inspection.
Note that these equations are simplified using the fact that states 101, 110, and
111  do  not  exist.  Thus,  the  corresponding  next  state  and  output  for  the  non-
existent states are don’t cares (not shown in the tables). We use the don’t cares
to minimize our equations.

S�2 � S1S  0A
S�1� S1 S0A� S1S0 � S2A (3.8)
S�0�S2S1S0 A � S1S0A
 3.4 Finite�State�Machines 127

Y � S2 (3.9)
Table 3.15 shows the combined state transition and output table for the Mealy
machine. The Mealy machine requires at least two bits of state. Consider using a
binary  state  encoding:  S0 � 00,  S1 � 01,  S2 � 10,  and  S3 � 11.  Table  3.16
rewrites the state transition and output table with these encodings.
From these tables, we find the next state and output equations by inspection.

S�1� S  1S0 � S1S0 A

(3.10)
S  �0� S  1S0 A � S1 S  0 A � S1S0 A

Y � S1S  0 A (3.11)

The  Moore  and  Mealy  machine  schematics  are  shown  in  Figure  3.31(a)  and
3.31(b), respectively.
The  timing  diagrams  for  the  Moore  and  Mealy  machines  are  shown  in  Figure
3.32  (see  page  131).  The  two  machines  follow  a  different  sequence  of  states.
Moreover, the Mealy machine’s output rises a cycle sooner because it responds to
the  input  rather  than  waiting  for  the  state  change.  If  the  Mealy  output  were
delayed  through  a  flip-flop,  it  would  match  the  Moore  output.  When  choosing
your FSM design style, consider when you want your outputs to respond.

1
Reset
1 1 0 1

S0 S1 S2 S3 S4
0 0 0 0 1
0
1 0 0
0

Figure�3.30 FSM�state
(a) transition�diagrams:�(a)�Moore
machine,�(b)�Mealy�machine
1/1
Reset
1/0 1/0 0/0

S0 S1 S2 S3
0/0 1/0 0/0
0/0
(b)
128 CHAPTER�THREE Sequential�Logic�Design

Table�3.11 Moore�state�transition�table

Current State Input Next State

S A S�
S0 0 S0

S0 1 S1
Table� 3.12 Moore� output� table
S1 0 S0
S1 1 S2 Current Output
State
S2 0 S3 S Y
S2 1 S2 S0 0

S3 0 S0 S1 0

S3 1 S4 S2 0

S4 0 S0 S3 0

S4 1 S2 S4 1

Table�3.13 Moore�state�transition�table�with�state�encodings

Current State Input Next State

S2 S1 S0 A S�2 S�1 S�0
0 0 0 0 0 0 0
0 0 0 1 0 0 1
Table�3.14 Moore�output�table
0 0 1 0 0 0 0
with�state�encodings
0 0 1 1 0 1 0
Current State Output
0 1 0 0 0 1 1 S2 S1 S0 Y
0 1 0 1 0 1 0 0 0 0 0

0 1 1 0 0 0 0 0 0 1 0

0 1 1 1 1 0 0 0 1 0 0

1 0 0 0 0 0 0 0 1 1 0

1 0 0 1 0 1 0 1 0 0 1
 3.4 Finite�State�Machines 129

Table�3.15 Mealy�state�transition�and�output�table

Current State Input Next State Output

S A S� Y
S0 0 S0 0

S0 1 S1 0

S1 0 S0 0
S1 1 S2 0

S2 0 S3 0

S2 1 S2 0

S3 0 S0 0

S3 1 S1 1

Table�3.16 Mealy�state�transition�and�output�table�with
state�encodings

Current State Input Next State Output

S1 S0 A S�1 S�0 Y
0 0 0 0 0 0
0 0 1 0 1 0

0 1 0 0 0 0
0 1 1 1 0 0

1 0 0 1 1 0

1 0 1 1 0 0

1 1 0 0 0 0

1 1 1 0 1 1

3 . 4 . 4 Factoring�State�Machines
Designing complex FSMs is often easier if they can be broken down into
multiple interacting simpler state machines such that the output of some
machines is the input of others. This application of hierarchy and modu-
larity is called factoring of state machines.
130 CHAPTER�THREE Sequential�Logic�Design

A CLK
S'2 S2
Y

S'1 S1

S'0 S0

Reset
S0
S1
Figure�3.31 FSM�schematics�for S2
(a)�Moore�and�(b)�Mealy (a)
machines
A

CLK
S'1 S1
Y

S'0 S0

Reset

S0
S1
(b)

Example�3.8 UNFACTORED AND FACTORED STATE MACHINES
Modify  the  traffic  light  controller  from  Section  3.4.1  to  have  a  parade  mode,
which  keeps  the  Bravado  Boulevard  light  green  while  spectators  and  the  band
march  to  football  games  in  scattered  groups.  The  controller  receives  two  more
inputs: P and R. Asserting P for at least one cycle enters parade mode. Asserting
R for  at  least  one  cycle  leaves  parade  mode.  When  in  parade  mode,  the  con-
troller proceeds through its usual sequence until LB turns green, then remains in
that state with LB green until parade mode ends.

First,  sketch  a  state  transition  diagram  for  a  single  FSM,  as  shown  in  Figure
3.33(a). Then, sketch the state transition diagrams for two interacting FSMs, as
 3.4 Finite�State�Machines 131

Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9 Cycle 10

CLK

Reset

A 1 1 1 0 1 1 0 1 0
Moore Machine
S ?? S0 S1 S2 S2 S3 S4 S2 S3 S4 S0

Y
Mealy Machine
S ?? S0 S1 S2 S2 S3 S1 S2 S3 S1 S0

Figure�3.32 Timing�diagrams�for�Moore�and�Mealy�machines

shown  in  Figure  3.33(b).  The  Mode  FSM  asserts  the  output  M when  it  is  in
parade  mode.  The  Lights  FSM  controls  the  lights  based  on  M and  the  traffic
sensors, TA and TB.

Solution: Figure  3.34(a)  shows  the  single  FSM  design.  States  S0  to  S3  handle
normal mode. States S4 to S7 handle parade mode. The two halves of the dia-
gram  are  almost  identical,  but  in  parade  mode,  the  FSM  remains  in  S6  with  a
green  light  on  Bravado  Blvd.  The  P and  R inputs  control  movement  between
these two halves. The FSM is messy and tedious to design. Figure 3.34(b) shows
the  factored  FSM  design.  The  mode  FSM  has  two  states  to  track  whether  the
lights are in normal or parade mode. The Lights FSM is modified to remain in
S2 while M is TRUE.

P Mode
R FSM

M
Figure�3.33 (a)�single�and
(b) factored�designs�for
TA LA modified�traffic�light
Lights
TB FSM LB controller FSM
P
R LA
Controller
TA FSM LB
Controller 
TB FSM

(a) (b)
132 CHAPTER�THREE Sequential�Logic�Design

P TA

P TA
R TA R TA
Reset
S0 P TA S1 RT A
S4 R TA S5
LA: green LA: yellow
LB: red LB: red P LA: green LA: yellow
LB: red LB: red
R
P
P TA
P
R
P R
S3 P TB S2 R
LA: red LA: red S7 S6
LB: yellow LB: green LA: red LA: red
P TB LB: yellow LB: green

P R

Figure�3.34 State�transition R TB
RT B
diagrams:�(a)�unfactored,
(b) factored
(a)

TA
Reset
S0 TA S1
LA: green LA: yellow
LB: red LB: red

P
Reset
S3 S2 P
S0 S1
LA: red LA: red
LB: yellow M: 0 M: 1
LB: green R
MTB
M + TB R
Lights FSM Mode FSM
(b)

3 . 4 . 5 FSM�Review
Finite  state  machines  are  a  powerful  way  to  systematically  design
sequential circuits from a written specification. Use the following proce-
dure to design an FSM:
� Identify the inputs and outputs.
� Sketch a state transition diagram.
 3.5 Timing�of�Sequential�Logic 133

� For a Moore machine:
– Write a state transition table.
– Write an output table.
� For a Mealy machine:
– Write a combined state transition and output table.
� Select state encodings—your selection affects the hardware design.
� Write Boolean equations for the next state and output logic.
� Sketch the circuit schematic.
We will repeatedly use FSMs to design complex digital systems through-
out this book.

3 . 5 TIMING�OF�SEQUENTIAL�LOGIC
Recall that a flip-flop copies the input D to the output Q on the rising edge
of the clock. This process is called sampling D on the clock edge. If D is
stable at either 0 or 1 when the clock rises, this behavior is clearly defined.
But what happens if D is changing at the same time the clock rises?
This problem is similar to that faced by a camera when snapping a
picture. Imagine photographing a frog jumping from a lily pad into the
lake. If you take the picture before the jump, you will see a frog on a lily
pad.  If  you  take  the  picture  after  the  jump,  you  will  see  ripples  in  the
water.  But  if  you  take  it  just  as  the  frog  jumps,  you  may  see  a  blurred
image of the frog stretching from the lily pad into the water. A camera is
characterized by its aperture time, during which the object must remain
still for a sharp image to be captured. Similarly, a sequential element has
an aperture time around the clock edge, during which the input must be
stable for the flip-flop to produce a well-defined output.
The aperture of a sequential element is defined by a setup time and
a  hold time,  before  and  after  the  clock  edge,  respectively.  Just  as  the
static  discipline  limited  us  to  using  logic  levels  outside  the  forbidden
zone, the dynamic discipline limits us to using signals that change out-
side the aperture time. By taking advantage of the dynamic discipline,
we  can  think  of  time  in  discrete  units  called  clock  cycles,  just  as  we
think  of  signal  levels  as  discrete  1’s  and  0’s.  A  signal  may  glitch  and
oscillate wildly for some bounded amount of time. Under the dynamic
discipline, we are concerned only about its final value at the end of the
clock cycle, after it has settled to a stable value. Hence, we can simply
write  A[n],  the  value  of  signal  A at  the  end  of  the  nth clock  cycle,
where n is an integer, rather than A(t), the value of A at some instant t,
where t is any real number.
The clock period has to be long enough for all signals to settle. This
sets a limit on the speed of the system. In real systems, the clock does not