EXAMPLE 1: sequence detector.

State Table

A synchronous sequential machine with a single input line x and a single output
line z is to be designed. The specifications are as follows: the output is to be z = 1 if
and only if the specific input sequence ...0110 occurs at consecutive clock pulses;
otherwise z = 0.

State Diagram

State Assignments

1 2
Digital Logic Design Principles by N. Balabanian and B. Carlson

Implementation
Excitation maps

the output is 1 for exactly one state (state C) and one input (x = 0).
Since C has the assignment y1y2 = 10, the expression for the output
function is
z = x'y1y2'

3 4
Rules of Thumb for Assigning States
1. Two present states should be assigned adjacent codes if they have the same
next state for:
a. Each input combination
b. Different input combinations, if the next state can also be given adjacent
assignments
c. Some input combinations, but not necessarily all
2. For all inputs, codes assigned to the next states for each present state should
be adjacent.
3. Assignments should simplify the output function.

Example 2

5 6

Example 4

Example 3

7 8
 STATE EQUIVALENCE AND MACHINE MINIMIZATION

Two states Si and Sj in a finite-state machine are equivalent if the

same output sequence is produced in response to an input
sequence, starting in either state, and this is true for every finite
input sequence.

Example: state table is given in the below figure. The objective is to find all
groups of equivalent states and to reduce the table to one having a minimal
number of states.

Example 5

9 10

The group of states A, D, F have the same output for x = 0; they also have the same
output for x = 1. Hence, they are not distinguishable with an input sequence of length
1. Similarly, the states B, C, E, G are indistinguishable with an input sequence of
length 1. All the states in the table can be partitioned into two blocks of states,
written as follows: P1 = {ADF; BCEG}
If, for each input symbol, the next states from all states in a block are not in the same
block but fall in two distinct blocks, then the two sub-blocks are distinguishable.
Hence, the original block must be subdivided. Thus, for x = 1, the next states from
the block BCEG are DFFD; these are all in the block ADF. However, for x = 0, the
next states from the block BCEG are CEBA; all except the next state from state G
are in the same block. Hence, block BCEG must be subdivided into two blocks, BCE
and G. The resulting partition is P2 = {ADF; BCE; G}, The next states from any one
block in partition P2 were found to be in the same block; hence, these next states
will have the same outputs for each input bit. These next states in each block are,
then, 1-equivalent. Hence, their predecessor states are 2-equivalent.
The process is now repeated with partition P2. Again we take each block one at a time
and, for each input, examine their next states to see if they fall in the same new
block. For each input, the next states from the block BCE fall in the same block. This
is also true for x = 0 for block ADF; however, for x = 1, the next states for block ADF
are GBC. These next states are not in the same block; hence, a further refinement of
P2 is needed. The states in each new block are [Link] process must be
repeated on the multistate blocks in partition P3. Go through the process and
confirm that no further refinements of the partition are needed. The states within
each block cannot be distindguished; hence, they are equivalent. This final partition
is called the equivalence partition.
11