Section 9.3 Finite-State Machines
745
example 38
The delay element in Figure 9.12 feeds the output from the terminal AND gate of
the network back into the initial OR gate at the next clock pulse. The initial output
of the delay element is assumed to be 0. The input sequences x 1 = 10010 and
x 2 = 11000 (read left to right) produce the effect shown in the table.
x 1
x 2
figure 9.12
time
t 0
t 1
t 2
t 3
t 4
x 1
1
0
0
1
0
x 2
1
1
0
0
0
Delay output
0
0
1
1
0
Circuit output
0
1
1
0
0
When one or more delay elements are introduced into a combinational network, the network is known as a sequential network. Unlike a combinational
network, loops (where output from a circuit becomes part of its input) are allowed,
provided that at least one delay element is incorporated into the loop. The delay
element prevents the confusion that results when a circuit tries to act on its current
output. Input sequences can be run through sequential networks (hence the name)
provided that the clock pulse synchronizes input signals as well as delay elements.
Any finite-state machine can be built using a sequential network. (We’ll
assume that all input and output values are binary; if not, they can be encoded
in binary form.) The general structure of such a network is shown in Figure 9.13.
It consists of two parts: (1) a combinational network (no delay elements) and (2)
some loops containing all the delay elements.
To build the network for a given finite-state machine, we represent each
machine state as a binary number, beginning with zero (0000, 0001, 0010,
0011, 0100, and so on); the assignment of states to numbers is arbitrary. At
any moment, each delay element in the network has a 0 or 1 signal on its
output line, so the collection of these output signals is a binary number and
therefore represents one of the states of the machine. As these signals feed into
the combinational network, they represent the current state; circuits within the
combinational network compute the next state, which is the pattern of 0s and 1s
on the input lines to the delay elements.
745
example 38
The delay element in Figure 9.12 feeds the output from the terminal AND gate of
the network back into the initial OR gate at the next clock pulse. The initial output
of the delay element is assumed to be 0. The input sequences x 1 = 10010 and
x 2 = 11000 (read left to right) produce the effect shown in the table.
x 1
x 2
figure 9.12
time
t 0
t 1
t 2
t 3
t 4
x 1
1
0
0
1
0
x 2
1
1
0
0
0
Delay output
0
0
1
1
0
Circuit output
0
1
1
0
0
When one or more delay elements are introduced into a combinational network, the network is known as a sequential network. Unlike a combinational
network, loops (where output from a circuit becomes part of its input) are allowed,
provided that at least one delay element is incorporated into the loop. The delay
element prevents the confusion that results when a circuit tries to act on its current
output. Input sequences can be run through sequential networks (hence the name)
provided that the clock pulse synchronizes input signals as well as delay elements.
Any finite-state machine can be built using a sequential network. (We’ll
assume that all input and output values are binary; if not, they can be encoded
in binary form.) The general structure of such a network is shown in Figure 9.13.
It consists of two parts: (1) a combinational network (no delay elements) and (2)
some loops containing all the delay elements.
To build the network for a given finite-state machine, we represent each
machine state as a binary number, beginning with zero (0000, 0001, 0010,
0011, 0100, and so on); the assignment of states to numbers is arbitrary. At
any moment, each delay element in the network has a 0 or 1 signal on its
output line, so the collection of these output signals is a binary number and
therefore represents one of the states of the machine. As these signals feed into
the combinational network, they represent the current state; circuits within the
combinational network compute the next state, which is the pattern of 0s and 1s
on the input lines to the delay elements.